# Do the maximal eigenvalues of $(X^TX)^{-1}$ matrix increase when number of columns of $X$ increases?

Suppose we have a square real $n\times n$ matrix $X=[x_1,...,x_n]$, where $x_i$ is $i$-th column of the matrix.

Now define $X_k=[x_1,..,x_k]$, i.e. matrix $X_k$ columns are the first $k$ columns of the matrix $X$. Define $\lambda_k$ as the maximal eigenvalue of $(X_k^TX_k)^{-1}$.

Is it possible to prove that $\lambda_1\le \lambda_2\le ... \le \lambda_n$?

If $X$ is orthogonal, then the answer is yes. Maybe this holds only for certain matrices? Any pointers would be greatly appreciated.

-
"matrix compression" and "cauchy's interlacing theorem" might be helpful here for you. – user1709 Dec 22 '10 at 21:23
I guess you are assuming that $\mathbf X$ has full rank... there isn't anything special about the columns of $\mathbf X$? – J. M. Dec 23 '10 at 1:32
@J. M., yes $X$ has full rank. Concerning columns, we can assume that limit $\lim_{n\to\infty}1/n X^TX$ exists and is a full rank matrix. Not sure that it helps. – mpiktas Dec 23 '10 at 3:37

The answer is Yes:

Assume that $X_{k+1}^TX_{k+1}$ is invertible. One can check that its lowest absolute eigenvalue is given by $$\left\vert{\frac1{\lambda_{k+1}}}\right\vert=\min\limits_{y\in{\mathbb R}^{k+1},\,\left\lVert y\right\lVert_2=1}\left\lVert{X_{k+1}y}\right\lVert_2^2\,,$$

It holds $$\min\limits_{y\in{\mathbb R}^{k+1},\,\left\lVert y\right\lVert_2=1}\left\lVert{X_{k+1}y}\right\lVert_2^2\leq\min\limits_{y\in{\mathbb R}^{k},\,\left\lVert y\right\lVert_2=1}\left\lVert{X_{k}y}\right\lVert_2^2\,.$$

This completes the proof.

-
thanks. Who could have thought that bounties can be so effective :) I'll award you one when it is possible (you can award one only after 24 hours), but please fix the formatting ;) – mpiktas Jan 14 '11 at 14:36
@mpiktas, you welcome. I did my best to fix the formatting ;) – Nabyl Bod Jan 14 '11 at 15:52
could you provide a reference or explain how you got the first equality? Pardon the ignorance.. – user1736 Jan 14 '11 at 17:49
@user1736. The spectral theorem shows that the lowest eigenvalue of $X^TX$ is the min of the euclidean norm of $X$ on the unit sphere. – Nabyl Bod Jan 14 '11 at 23:41