# proof of Wielandt-Hoffman theorem

Since both $A$ and $B$ are normal, they can be diagonalized by unitary transformations:

 $A=V^{\dagger}CV\quad\text{and}\quad B=W^{\dagger}DW,$

where $C$ and $D$ are diagonal, $V$ and $W$ are unitary, and $(~{})^{\dagger}$ denotes the conjugate transpose. The Frobenius matrix norm is defined by the quadratic form $\|A\|_{F}^{2}=\operatorname{tr}[A^{\dagger}A]$ and is invariant under unitary transformations, hence

 $\|A-B\|_{F}^{2}=\|V^{\dagger}CV-W^{\dagger}DW\|_{F}^{2}=\|C\|_{F}^{2}+\|D\|_{F% }^{2}-2\operatorname{Re}\operatorname{tr}[C^{\dagger}U^{\dagger}DU],$

where $U=WV^{\dagger}$. The matrix $U$ is also unitary, let its matrix elements be given by $(U)_{ij}=u_{ij}$. Unitarity implies that the matrix with elements $|u_{ij}|^{2}$ has its row and column sums equal to $1$, in other words, it is doubly stochastic.

The diagonal elements $C_{ii}=a_{i}$ are eigenvalues of $A$ and $D_{ii}=b_{i}$ are those of $B$. Writing out the Frobenius norm explicitly, we get

 $\|A-B\|_{F}^{2}=\sum_{i}(|a_{i}|^{2}+|b_{i}|^{2})-2\operatorname{Re}\sum_{ij}% \overline{a}_{i}|u_{ij}|^{2}b_{j}\geq\sum_{i}(|a_{i}|^{2}+|b_{i}|^{2})-2\min_{% S}\operatorname{Re}\sum_{ij}\overline{a}_{i}s_{ij}b_{j},$

where the minimum is taken over all doubly stochastic matrices $S$, whose elements are $(S)_{ij}=s_{ij}$. By the Birkoff-von Neumann theorem, doubly stochastic matrices form a closed convex (http://planetmath.org/ConvexSet) polyhedron with permutation matrices at the vertices. The expression $\sum_{ij}\overline{a}_{i}s_{ij}b_{j}$ is a linear functional on this polyhedron, hence its minimum is achieved at one of the vertices, that is when $S$ is a permutation matrix.

If $S$ represents the permutation $\sigma$, its action can be written as $\sum_{j}s_{ij}b_{j}=b_{\sigma(i)}$. Finally, we can write the last inequality as

 $\|A-B\|_{F}^{2}\geq\sum_{i}(|a_{i}|^{2}+|b_{\sigma(i)}|^{2})-2\min_{\sigma}% \operatorname{Re}\sum_{ij}\overline{a}_{i}b_{\sigma(i)}=\min_{\sigma}|a_{i}-b_% {\sigma(i)}|^{2},$

which is exactly the statement of the Wielandt-Hoffman theorem.

Title proof of Wielandt-Hoffman theorem ProofOfWielandtHoffmanTheorem 2013-03-22 14:58:51 2013-03-22 14:58:51 Andrea Ambrosio (7332) Andrea Ambrosio (7332) 6 Andrea Ambrosio (7332) Proof msc 15A18 msc 15A42