Prove Wielandt minimax formula

Question

The statements are as follows:
Let $1\leqslant i_1<i_2<\cdots<i_k\leqslant n$ be integers. Define a partial flag to be a nested collection $V_1\subset V_2\cdots\subset V_k$ of subspaces of $\mathbb{C}^n$ s.t. $\dim(V_j)=i_j$ for all j between 1 and k. Define the Schubert variety $X(V_1,…,V_k)$ to be the collection of all k-dimensional subspaces W s.t. $dim(W\cap V_j)\geqslant j$. Show that for any Hermitian matrix A,
$$\lambda_{i_1}+…+\lambda_{i_k}=\sup_{V_1,…,V_k} \inf_{W\in X(V_1,…,V_k)}tr(A|_{W})$$.
Where $\lambda_{i_j}$ means the $i_j$ th eigenvalue of A, from large to small. The trace in the right formula stands for the partial trace of A on W.

I have proofed that the LHS is no bigger than the RHS using induction on k, but I do not know how to prove the other side.

Answer 1

Suppose that the $n \times n$ Hermitian matrix $A$ has orthonormal eigenvectors $e_i$ corresponding to $\lambda_i$ by the spectral theorem, where $\lambda_1 \geq \dots \geq \lambda_n$. Then, for any $v = \sum_{i=1}^{n} c_i e_i$ with $c_1,\dots,c_n \in \mathbb{C}$, we have $$ v^{*}Av = \sum_{i=1}^{n} \lambda_i |c_i|^2 . $$

Proof of "$\mathrm{LHS\leq RHS}$". We can choose $U_j = \mathrm{span}_\mathbb{C}\{ e_i ： 1 \leq i \leq i_j \}$, and thus $U_1 \subset \cdots \subset U_k$ form a partial flag. Pick any $k$-dimensional $W \in X(U_1,\dots,U_k)$. To obtain an orthonormal basis $v_1,\dots,v_k$ of $W$ such that $v_j \in U_j$ for $1\leq j\leq k$, we proceed as following:

1. Write $W_k = W$ and $U_0 = \{\mathbf{0}\}$ for convenience;
2. Let $\ell_k = \min\{1\leq j\leq k : W_k \subset U_j\} - 1$, which is finite since $W_k \subset U_k$;
3. Pick some unit vector $v_k \in \{v\in W_k : v\perp(U_{\ell_k}\cap W_k)\}$, which exists since $U_{\ell_k}\cap W_k \neq W_k$;
4. Let $W_{k-1} = \{ w\in W_k : w \perp v_k \}$, which lies in $X(U_1,\dots,U_{k-1})$ since $U_{\ell_k}\cap W_k \subset W_{k-1} \subset U_{\ell_k + 1}$;
5. Repeat step 2.~4. with $k \leftarrow k-1$, until $k$ decreases to $0$.

Therefore, noting that $v_j^{*}Av_j \geq \lambda_{i_j}$, we have $$ \mathrm{tr}(A|_W) = \sum_{j=1}^{k} v_j^{*}Av_j \geq \sum_{j=1}^{k} \lambda_{i_j} .$$

Proof of "$\mathrm{LHS\geq RHS}$". It suffices to show that for any partial flag $V_1 \subset \cdots \subset V_k$, there exists some $W \in X(V_1,\dots,V_k)$ so that $$\mathrm{tr}(A|_W) \leq \sum_{j=1}^{k} \lambda_{i_j}.$$ To that end, we perform induction on the dimension $n$. Observe that the $n=1$ case is trivial, so we may assume $n \geq 2$. Let $m = \max(i_1-1, 1)$ and define $$E = \mathrm{span}_\mathbb{C}\{ e_i ： m+1 \leq i \leq n \},$$ then $\dim(E) = n-m < n$. Also, the restriction $A|_E$ of $A$ to $E$ has eigenvalues $\lambda_i' = \lambda_{m+i}$ for $1\leq i\leq n-m$. To obtain a new partial flag, we proceed as following:

1. Pick some $(i_k - m)$-dimensional $V_k' \subset V_k \cap E$, which exists since $$\dim(V_k \cap E) = \dim(V_k) + \dim(E) - \dim(V_k + E) \geq i_k + (n-m) - n = i_k - m ;$$
2. For $j = k-1,\cdots,1$, pick some $(i_j - m)$-dimensional $V_j' \subset V_j \cap V_{j+1}'$, which exists since $$\dim(V_j \cap V_{j+1}') = \dim(V_j) + \dim(V_{j+1}') - \dim(V_j + V_{j+1}') \geq i_j + (i_{j+1}-m) - i_{j+1} = i_j - m .$$

If $i_1 > 1$, then $m = i_1 - 1$ and $\dim(V_1') = 1$, so $V_1'\subset\cdots\subset V_k'$ form a partial flag of $E$. Applying the induction hypothesis to $A|_E$, we find some $W \in X(V_1',\dots,V_k') \subset X(V_1,\dots,V_k)$ as desired. Otherwise, $i_1 = 1$ and $m = 1$. By the induction hypothesis, we can find some $W' \in X(V_2',\dots,V_k')$ such that $\mathrm{tr}(A|_{W'}) \leq \sum_{j=2}^{k} \lambda_{i_j}$. Let $\ell = \max\{j: V_j \subset W'\}+1 \leq k$ and pick some $v \in V_{\ell}\setminus W'$, then $W = W' + \mathrm{span}_\mathbb{C}\{v\}$ satisfies our demand, which can be partly known from that $\lambda_{i_1} = \lambda_1 \geq w^{*}Aw$ for any unit vector $w$ in the orthogonal complement of $W'$ in $W$.