# 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$? –  Guess who it is. 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

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\,.$$
@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