Let $V$ be a real vector space of $n(<\infty)$ dimensional equipped with an inner product $\langle,\rangle$. Let $B:V\to V$ be a symmetric linear transform on $V$. Let $\lambda_1\leq\cdots\leq\lambda_n$ be the eigenvalues of $B$. Then how to prove that \begin{eqnarray} \lambda_1+\cdots+\lambda_k=\min\left\{\sum_{j=1}^k \langle e_j, Be_j\rangle\ |\ (e_j)_{j=1}^k\text{ is an orthonormal system of }V\right\} \end{eqnarray}? Thank you.

  • 2
    $\begingroup$ This is the min-max theorem. The proof is on this wikipedia link and easy to understand $\endgroup$ – Ewan Delanoy Dec 12 '15 at 19:01

Usually when you have a symmetric map, respectively a symmentric matrix, you first diagonalize it and then you read the rest of the question. In this case: pick an orthonormal basis of $V$, consisting of eigenvectors of $B$. In this basis the matrix of $B$ is $D = diag(\lambda_1, \cdots \lambda_n)$ and hence in your expression above $$RHS = \min \{ \sum_{j=1}^k \langle f_j, Df_j\rangle | (f_j)_{j=1}^k \textrm{is an orthonormal system}\}$$

and I renamed $e_j$ to $f_j$ for clarity. Now, if we pick $f_j$ to be the stanard basis vectors $e_j$ we get $$ \sum_{j=1}^k \langle e_j, De_j\rangle = \lambda_1 + \ldots + \lambda_k$$ Thus, $LHS \geq RHS$ Now we need to show equality.

Proceed by induction on $k \leq n$ The case $k = n$ is a restatement of the claim $tr(D) = tr (P^tDP)$ where the columns of $P$ are $(f_j)_{j=1}^n$

Assume we know the statement for $k+1 \leq n$ $$\lambda_1 + \cdots + \lambda_{k+1} = \min \{ \sum_{j=1}^{k+1} \langle f_j, Df_j\rangle \} $$ If we fix $f_{k+1}$we are going to increase the RHS, as the minimum will be on a smaller set. So, choose $f_{k+1} = e_{k+1}$ Then $\langle e_{k+1}, De_{k+1}\rangle = \lambda_{k+1}$ so we can subtract $\lambda_{k+1}$ from both sides f the equation and get: $$\lambda_1 + \cdots + \lambda_{k} \leq \min \{ \sum_{j=1}^{k} \langle f_j, Df_j\rangle \} $$ But we already showed the reverse inequality, so actually

$$\lambda_1 + \cdots + \lambda_{k} = \min \{ \sum_{j=1}^{k} \langle f_j, Df_j\rangle \} $$ and we have the claim for $k\geq 1$, so the induction is complete.

Note: try induction from $k$ to $k+1$ to see why induction from $k+1$ to $k$ is easier!

  • $\begingroup$ In your induction argument I understood that $\lambda_1+\cdots+\lambda_k\leq \min\left\{\left. \displaystyle\sum_{j=1}^k\langle f_j,f_j\rangle\ \right|\ (f_j)_{j=1}^k\text{ is an orthonormal system of }\langle\{e_{k+1}\}\rangle^\bot\right\}$. But I still do not understand how to show LHS$\leq$RHS. $\endgroup$ – stb2084 Dec 6 '15 at 13:28
  • $\begingroup$ I cannot edit my comment above. I would like to correct my RHS as $\lambda_1+\cdots+\lambda_k\leq \min\left\{\left. \displaystyle\sum_{j=1}^k\langle f_j,Df_j\rangle\ \right|\ (f_j)_{j=1}^k\text{ is an orthonormal system of }\langle\{e_{k+1}\}\rangle^\bot\right\}$. $\endgroup$ – stb2084 Dec 6 '15 at 13:39
  • $\begingroup$ The minimum of a function over a collection $f_j$ is smaller than the function, evaluated at any given point (say $f_j = e_j$ ) So, the minimum you wrote in the comment above is $\leq \sum_{j=1}^{k} (e_j , De_j) = \lambda_1 + \cdots + \lambda_k$ Thus, you have equality. $\endgroup$ – Milen Ivanov Dec 6 '15 at 13:49
  • $\begingroup$ In order not to remove my last post: I misunderstood your question. I think you have a fair point that the minimum you wrote is over a smaller space: I forgot about it. I think a second induction, this time on $n$ will do the job. I'll comment again when I get the answer. $\endgroup$ – Milen Ivanov Dec 6 '15 at 13:59
  • $\begingroup$ @MilenIvanov Your proof is incomplete but you are close. You did not sufficiently notice the fact that we have a trace notion on subspaces (the sum $\sum_{k} <f_k,Tf_k>$ is independent of the choice of orthonormal basis $(f_k)$ of a given subspace). See my comment on the OP $\endgroup$ – Ewan Delanoy Dec 12 '15 at 19:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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