# An identity for the sum of $k$ smallest eigenvalues

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.

• This is the min-max theorem. The proof is on this wikipedia link and easy to understand – 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!

• 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. – stb2084 Dec 6 '15 at 13:28
• 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\}$. – stb2084 Dec 6 '15 at 13:39
• 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. – Milen Ivanov Dec 6 '15 at 13:49
• 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. – Milen Ivanov Dec 6 '15 at 13:59
• @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 – Ewan Delanoy Dec 12 '15 at 19:04