5
$\begingroup$

I got the following exercise to solve:

Let $A\in\mathbb{R}^{n\times n}$ be a symmetric matrix and let $\lambda_{1}\geq\lambda_{2}\geq\cdots\geq\lambda_{n}$ be its eigenvalues sorted in a desecnding order. Show that: $\lambda_{k}=\max_{V,\,\dim\left(V\right)=k}\left\{ \min\frac{\left}{\left}\,:\, x\in V\,,\, x\neq0\right\} $ There is no mention of some specific inner product being taken here so I assume it needs to be proven for a general inner product on an $n$ dimensional real inner-product space.

I'm completely stumped with this, help would be greatly appreciated!

  • 1
    The statement is called the [min-max theorem](http://en.wikipedia.org/wiki/Min-max_theorem) which might help in finding suitable references.2012-12-13

1 Answers 1

4

Fix an orthonormal basis $e_1,\ldots,e_n$ of $V$. As $A$ is symmetric, we can choose the basis so that $A$ is diagonal, i.e. $Ae_j=\lambda_je_j$.

Note that $ \min\left\{\frac{\left}{\left}\,:\, x\in V\,,\, x\neq0\right\} = \min\left\{{\left}\,:\, x\in V\,,\, \|x\|=1\right\} $

For any $x=\sum_{j=1}^nc_je_j$ with $\sum_jc_j^2=1$, we have $ \langle x,Ax\rangle = \left\langle \sum_{j=1}^nc_je_j,\sum_{j=1}^nc_j\lambda_je_j\right\rangle=\sum_{j=1}^n\lambda_j\,c_j^2. $ Assume that $x\in V$, where $\dim V=k$. Consider the subspace $W=\text{span}\{e_k,e_{k+1},\ldots,e_{n}\}$. As $\dim W=n-k+1$, $V\cap W$ cannot be zero (otherwise, we would find $n+1$ linearly independent elements of $V$). Any $x\in V\cap W$ with norm one is of the form $x=\sum_{j=k}^nc_je_j$ with $\sum c_j^2=1$, so $ \langle x,Ax\rangle = \sum_{j=k}^n\lambda_jc_j^2\leq\lambda_k. $ This shows that $ \min\left\{{\left}\,:\, x\in V\,,\, \|x\|=1\right\}\leq\lambda_k. $ As $V$ was arbitrary, we have shown that $ \max_{\dim V=k}\left\{\min\left\{{\left}\,:\, x\in V\,,\, \|x\|=1\right\}\right\}\leq\lambda_k. $ Since the equality is achieved for $V=\text{span}\{e_1,\ldots,e_k\}$, we are done.

  • 0
    Thanks a lot! That is a very elegant proof!2012-12-14