6
$\begingroup$

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.

  • 0
    "matrix compression" and "cauchy's interlacing theorem" might be helpful here for you.2010-12-22
  • 0
    I guess you are assuming that $\mathbf X$ has full rank... there isn't anything special about the columns of $\mathbf X$?2010-12-23
  • 0
    @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.2010-12-23

1 Answers 1

5

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.

  • 0
    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 ;)2011-01-14
  • 0
    @mpiktas, you welcome. I did my best to fix the formatting ;)2011-01-14
  • 0
    could you provide a reference or explain how you got the first equality? Pardon the ignorance..2011-01-14
  • 0
    @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.2011-01-14