3
$\begingroup$

I'm trying to work out a proof for the following proposition:

Let $A \in \mathbb{R}^{n,n}$ a real, symmetric matrix with eigenvalues $\lambda_1 \ge \lambda_2 \ge \cdots \ge \lambda_n$, then

$$\max \lbrace {\rm tr} ( V^t A V ) \mid V \in \mathbb{R}^{n,k}, \, V^t V={\rm Id}_k \rbrace = \sum\limits_{i=1}^k \lambda_k $$

I've already found a proof myself which I've posted at the end of this question. However, I feel I've still missed a very important point: This theorem should be a direct consequence of the min/max- or Courant-Fischer-characterization of eigenvalues (https://en.wikipedia.org/wiki/Min-max_theorem). Although, after realizing that $\text{tr}(V^TAV) = \sum_{i=1}^k <Av_i,v_i>$, this approach looks very promising, I was not able to continue the proof.

For $k=1$ the statement is directly proven by Courant-Fischer. For other values of $k$ inductive reasing comes to mind. However, it is not clear to me, why this 'greedy approach' (maximize $k-1$ summands first and then choose the $k$-th accordingly) reaches the true maximum and how the minimum of the Courant-Fischer characterization isn't an issue.

I'd be very thankful for hints and solutions!

different proof without min/max-theorem: Choose an orthonormal basis consisting of eigenvectors, writeall $v_i$'s in this representation and calculate

$\text{tr}(V^TAV) = \sum_{i=1}^n \lambda_i (\sum_{j=1}^k \alpha_{i,j}^2) = \sum_{i=1}^n h_i \lambda_i$

with $h_i := \sum_{j=1}^k \alpha_{i,j}^2$. Since $V^TV=\text{Id}_k$ we have $0 \le h_i \le 1$ and $\sum_{i=1}^n=k$. This shows that the maximum is attained for $h_1 = ... = h_k =1$ and $h_{k+1} = ... = h_n = 0$, which proofs the claim.

$\endgroup$
  • $\begingroup$ Not exactly the same thing, but you can prove it with Cauchy's interlacing theorem and the characterization of the trace in terms of the eigenvalues. $\endgroup$ – Federico Poloni Aug 24 '16 at 19:10
  • $\begingroup$ I don't see it as an immediate consequence of the Courant-Fisher theorem. The Courant-Fisher theorem bounds the smallest eigenvalue of a compression, but here you need a bound on the sum of the eigenvalues. That's a different Schatten norm, so they don't look the same thing to me. $\endgroup$ – Federico Poloni Aug 24 '16 at 19:14
  • $\begingroup$ @FedericoPoloni Thanks for your prompt reply. The idea to derive it from Courant-Fischer comes from a remark in this paper www-users.cs.umn.edu/~saad/PDF/umsi-2009-31.pdf (at the very beginning of chapter 2) and some threads here on mathoverflow I'm not able to find anymore. In my opinion the authors suggested that the step from Courant-Fischer to the claim above should be obvious. $\endgroup$ – Max M Aug 24 '16 at 19:32
  • $\begingroup$ @FedericoPoloni Also, maybe we're talking about different theorems. I've linked the formulation of the Courant-Fischer I'm thinking of in my question above. It directly bounds the smallest and biggest eigenvalue, but also offers a characterization of the ones in between. $\endgroup$ – Max M Aug 24 '16 at 19:33
  • $\begingroup$ Which of the various statement in that page do you call the Courant-Fisher theorem? For me it is en.wikipedia.org/wiki/Min-max_theorem#Min-max_theorem. It is possible that what Saad's paper calls "Courant-Fisher characterization" is the whole statement in en.wikipedia.org/wiki/…. $\endgroup$ – Federico Poloni Aug 24 '16 at 19:41
1
$\begingroup$

As you pointed out we have $$tr(V^T A V) = \sum_{i=1}^k \langle A v_i, v_i \rangle$$

Our restraints are $\langle v_i, v_i \rangle = 1$ and $\langle v_i, v_j \rangle = 0$.

Now suppose we took a greedy approach, and tried to maximize $\langle A v_1, v_1 \rangle$ first, and then maximimize $\langle A v_2, v_2 \rangle$ subject to the constraint that $\langle v_1, v_2 \rangle = 0$ and so on. Then by min-max C-F, we would have $\langle A v_1, v_1\rangle = \lambda_1$, and $\langle A v_i, v_i \rangle \geq \lambda_i$ for each $i$. Hence this approach would yield the fact that $\max tr(V^T A V) \geq \sum_1^k \lambda_i$.

This reduces the problem to showing that $tr(V^T A V) \leq \sum_1^k \lambda_i$ for all choices of $v_i$. This is equivalent to the fact that the diagonal entries of $A$ are majorized by the eigenvalues of $A$, a statement proved in https://en.wikipedia.org/wiki/Schur%E2%80%93Horn_theorem.

I am not aware of a version of the second fact that relies on C-F, although it might exist.

$\endgroup$
  • $\begingroup$ I agree with the first part. However, C-F is not really needed for this inequality. For the second part, I don't see yet why it is enough to bound the diagonal entries of $A$... $\endgroup$ – Max M Aug 27 '16 at 17:43
1
$\begingroup$

I think your simple argument is perfectly appropriate. We could bring in min-max as follows: as already pointed out by Nick and yourself, the only thing that's not immediately clear is the estimate $$ \sum_{j=1}^k \langle v_j, A v_j\rangle \le \sum_{j=1}^k \lambda_j , \quad\quad\quad\quad (1) $$ and here $\lambda_1\ge\lambda_2\ge\ldots$, and the $v_j$ are arbitrary orthonormal vectors.

The LHS computes the trace of the restriction $A_0:=PAP$, with $P$ denoting the projection onto the span of the columns $v_j$ of $V$.

It is an immediate consequence of min-max that restriction does not increase eigenvalues, $\lambda_j(A_0)\le \lambda_j(A)$, and this gives (1).

More explicitly, consider for example $$ \lambda_2(A) = \min_w \max_{v\perp w, |v|=1} \langle v, A v\rangle \ge \min_w\max _{v\perp w, |v|=1, Pv=v} \langle v, A v\rangle = \min_{w, Pw=w} \ldots = \lambda_2(A_0) . $$

$\endgroup$
  • $\begingroup$ Thanks a lot! This feels like the argument the authors had in their mind. With $P := V V^T$ and the equality $\text{tr}(V^T A V) = \text{trace} (PAP)$, it answers the question completely. $\endgroup$ – Max M Aug 27 '16 at 17:34
  • $\begingroup$ After some months I came back to this and realized that I don't understand the second to last equation sign. How can I recover something that will lead to $\lambda_2(A_0)$ after I have introducted the condition $Pv=v$? $\endgroup$ – Max M Jan 9 '17 at 20:25

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.