On the question of when eigen values are guaranteed to be positive (and the property of positive definiteness)

["Subbarao Kambhampati" <rao@asu.edu>]

There was a question in the class (by Dmitry I think) as to when can we be sure that  eigen values of a matrix are all positive.

Here is the answer

 All symmetric matrices are guaranteed to have real valued eignen values, but are not all guaranteed to have positive eigen values.

Having positive eigen values turns out to be closely related to a *very* important property of matrices called "positive definiteness"

However, if the symmetric matrix M under consideration can be written as B*B'  where B is a non-singular matrix (i.e., has non-zero determinant),
then it is guaranteed to have +ve eigen values. (Notice that the matrices we power-iterated on in A/H computation are of this form).

-------------

While we are at it, we should note that the property of having positive eigen values is intimately linked to another very deep and useful property called
"positive definiteness"

A matrix M is called positive definite, if for *any* vector u,

 u * M * u' > 0  (it is called positive semi-definite if  "greater than" is replaced by "greater than or equal to")

It turns out that M is +ve definite if and only if it has all positive eigen values (you can sort of  see the "if" case in terms of viewing vector/matrix multiplication in terms of
stretching vector's projections in the eigen vector directions by the amount equal to eigen values).


cheers
Rao