# Why the largest eigenvalue is the bound?

I am new to Linear Algebra, say introduction level (know the definition and some basic properties, theories about it but not really familiar with doing math on it). Please explain to me:

If A is an inverse of a positive definite matrix, then why all of its eigenvalues are positive and why $\frac{x^TAAx}{1+x^TAx}$ is bounded above by the largest eigenvalue of A?

Can you recommend some books that offer a higher level than introduction that can help me get over these kind of problems? I'm learning Machine Learning by the way.

Thank you.

• Is it $x^T A A x$ or just $x^T A x$ in the numerator? – Antonio Vargas Dec 29 '13 at 17:58
• @AntonioVargas Yes, just $x^TAx$ – Learner Dec 29 '13 at 18:16
• So it should be just $\frac{x^TAx}{1+x^TAx}$? – Calle Dec 29 '13 at 18:57
• I'm suspicious of the $1 + x^T A x$ in the denominator, because that would lead to an upper bound of 1, regardless of how small the largest eigenvalue is. I suspect $x^T x$ is supposed to be in the denominator instead. – Hugh Denoncourt Dec 29 '13 at 18:58
• Oh, I'm sorry, my mistake reading your comments, so sorry. it is exactly $\frac{x^TAAx}{1+x^TAx}$ as written in the main post :) – Learner Dec 30 '13 at 0:28

$A$ is inverse of positive definite matrix then $A$ is positive definite. Positive definite matrices have real parts of eigenvalue positive ( in case of symmetric matrices, where eigenvalues are real, then simply eigenvalues are positive).

Since you mention, eigenvalues are real so I assume, you're talking about symmetric matrices. This is relatively easy to analyze case since, in this case eigenvectors are orthogonal.

If $q_{i}$'s are eigenvectors (hence $Aq_{i}=\lambda_{i}q_{i}$, then any $x$ can be written as x=$\Sigma\alpha_{i}q_{i}$, and it follows that

$\frac{x^TAAx}{1+x^TAx} = \frac{\Sigma\alpha_{i}\lambda^{2}_{i}}{1+\Sigma\alpha_{i}\lambda_{i}}$

It is now easy to see that maximum would occur when all $\alpha_{i}$ are zero except one that corresponds to largest eigenvalue. Hence $\frac{\lambda^{2}_{max}}{1+\lambda_{max}}\leq \lambda_{max}$. Thus the quantity is bounded by largest eigenvalue.

In order to be able to do such manipulation with eigenvalues and eigenvectors, I suggest you read about

1. Chapter on eigenvalue computation from Numerical Linear Algebra by (Trefethen and Bau) this book used to be available online
2. About Rayleigh quotient
3. For much more deeper theoretical understanding, you can read about Min-Max theorems about eigenvalue
4. It will be also useful to read about singular values and singular vector for more general cases where eigenvalues are not positive or real