Hoffman-Wielandt Theorem Proof

Question

Exercise 3.3 of Izenman's Modern Multivariate Statistical Techniques: let $\mathbf{A}$, $\mathbf{B}$ be symmetric $J \times J$ matrices, with eigenvalues $\{\lambda_j(\mathbf{A})\}$ and $\{\lambda_j(\mathbf{B})\}$ respectively, arranged in descending order with respect to $j$ (so $\lambda_1$ is largest, $\lambda_J$ is the smallest for both matrices). Prove that $$\sum_{j=1}^{J}\left[\lambda_j(\mathbf{A}) - \lambda_j(\mathbf{B})\right]^2 \leq \text{tr}\{(\mathbf{A}-\mathbf{B})(\mathbf{A}-\mathbf{B})^{T}\}\text{.}$$ The hint says to use spectral decomposition, so $$\begin{align*} \mathbf{A} &= \sum_{j=1}^{J}\lambda_j(\mathbf{A})\mathbf{v}_j(\mathbf{A})\mathbf{v}^T_j(\mathbf{A}) \\ \mathbf{B} &= \sum_{j=1}^{J}\lambda_j(\mathbf{B})\mathbf{v}_j(\mathbf{B})\mathbf{v}^T_j(\mathbf{B}) \end{align*}$$ where the $\mathbf{v}_j(\cdot)$ denote the eigenvectors of the matrix $\cdot$ corresponding to $\lambda_j$. Then it says to express $$\text{tr}\{(\mathbf{A}-\mathbf{B})(\mathbf{A}-\mathbf{B})^{T}\}$$ in terms of the decomposition. I have $$\mathbf{A}-\mathbf{B} = \sum_{j=1}^{J}[\lambda_j(\mathbf{A})\mathbf{v}_j(\mathbf{A})\mathbf{v}^T_j(\mathbf{A})-\lambda_j(\mathbf{B})\mathbf{v}_j(\mathbf{B})\mathbf{v}^T_j(\mathbf{B})] $$ and $$(\mathbf{A}-\mathbf{B})^{T} = \mathbf{A}^{T}-\mathbf{B}^{T} = \sum_{j=1}^{J}[\lambda_j(\mathbf{A})\mathbf{v}^T_j(\mathbf{A})\mathbf{v}_j(\mathbf{A})-\lambda_j(\mathbf{B})\mathbf{v}^T_j(\mathbf{B})\mathbf{v}_j(\mathbf{B})]\tag{1}\text{.}$$ I suppose we could assume the vectors are normalized, so we get $\mathbf{v}^T_j(\mathbf{A})\mathbf{v}_j(\mathbf{A}) = \mathbf{v}^T_j(\mathbf{B})\mathbf{v}_j(\mathbf{B}) = 1$. But I'm not sure what else to do. Direct multiplication looks like a very messy approach (which would possibly involve induction on $J$), but I thought I'd ask here for suggestions.

Answer 1

Symmetric matrices are orthogonally diagonalisable. Let $A=U\Lambda U^T$ and $B=V\Sigma V^T$, where $U,V$ are real orthogonal and the eigenvalues in the two diagonal matrices $\Lambda,\Sigma$ are arranged in descending order. Let also $W=U^TV$. Then the inequality in question is equivalent to $$ \operatorname{tr}\left((\Lambda-\Sigma)^2\right) \le \operatorname{tr}\left((U\Lambda U^T-V\Sigma V^T)^2\right).\tag{1} $$ Expand the square terms on both sides, we may in turn rewrite $(1)$ as $$ \operatorname{tr}(\Lambda W\Sigma W^T) \le \operatorname{tr}(\Lambda\Sigma).\tag{2} $$ It is well-known that the LHS of the above inequality is maximised when $W=I$ (and therefore the inequality is true). To see this, let $S$ be the entrywise square of the real orthogonal matrix $W$. Then $S$ is a doubly stochastic matrix and the LHS is equal to $\sum_{i,j}\lambda_i\sigma_js_{ij}$, which is a linear function in the entries of $S$. By Birkhoff-von Neumann theorem, the set of all doubly stochastic matrices is the convex hull of all permutation matrices. Therefore the LHS of $(2)$ is maximised when $W$ is a permutation matrix. It is easy to see that among all permutation matrices, $W=I$ gives the global maximum.