6
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ 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. $\endgroup$
    – user1551
    Mar 24, 2016 at 15:41
  • $\begingroup$ @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.) $\endgroup$ Mar 24, 2016 at 15:43
  • $\begingroup$ @user1551 The post has been edited. $\endgroup$ Mar 24, 2016 at 15:44

1 Answer 1

13
$\begingroup$

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.

$\endgroup$
2
  • 2
    $\begingroup$ clear demonstration! A similar proof can be found on the very rich site djalil.chafai.net/blog/2011/12/03/… $\endgroup$
    – Jean Marie
    Mar 24, 2016 at 16:32
  • $\begingroup$ I have seen a similar inequality stated for the singular values of general matrices. How can one extend this proof to handle that case? $\endgroup$
    – Ben
    Apr 18, 2021 at 21:13

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.