Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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<x,Ax\right>}{\left<x,x\right>}\,:\, 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!

share|improve this question
1  
The statement is called the min-max theorem which might help in finding suitable references. –  Fabian Dec 13 '12 at 23:18

1 Answer 1

up vote 2 down vote accepted

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<x,Ax\right>}{\left<x,x\right>}\,:\, x\in V\,,\, x\neq0\right\} = \min\left\{{\left<x,Ax\right>}\,:\, 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,Ax\right>}\,:\, 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,Ax\right>}\,:\, 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.

share|improve this answer
    
Thanks a lot! That is a very elegant proof! –  Serpahimz Dec 14 '12 at 14:38

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.