# Hoffman-Wielandt Theorem Proof

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.

• The statement is ambiguous (if not wrong) if the order of the eigenvalues are not specified. E.g. if $A=B=\operatorname{diag}(1,2)$ but the eigenvalues of $A$ and $B$ are arranged in opposite order, then the inequality would imply that $2\le 0$. Things also get complicated if the eigenvalues do not have the same signs. Mar 24, 2016 at 15:41
• @user1551 Thanks for catching that. It so happens that $\lambda_1$ is used as the largest eigenvalue and $\lambda_J$ is used as the smallest eigenvalue. (This wasn't directly in the statement of the theorem in this text, but was somewhere else.) Mar 24, 2016 at 15:43
• @user1551 The post has been edited. Mar 24, 2016 at 15:44

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.