proof of Wielandt-Hoffman theorem

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

$$A=V^{†}CV\mathit{\hspace{1em}}\text{and}\mathit{\hspace{1em}}B=W^{†}DW,$$

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

$${\parallel A-B\parallel }_F^2={\parallel V^{†}CV-W^{†}DW\parallel }_F^2={\parallel C\parallel }_F^2+{\parallel D\parallel }_F^2-2\mathrm{Re}\mathrm{tr}[C^{†}{U}^{†}DU],$$

where $U=W{V}^{†}$. 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

$${\parallel A-B\parallel }_F^2=\sum _i({|a_i|}^2+{|b_i|}^2)-2\mathrm{Re}\sum _{ij}{\overline{a}}_i{|u_{ij}|}^2{b}_j\ge \sum _i({|a_i|}^2+{|b_i|}^2)-2\underset{S}{\min }\mathrm{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

$${\parallel A-B\parallel }_F^2\ge \sum _i({|a_i|}^2+{|b_{\sigma (i)}|}^2)-2\underset{\sigma }{\min }\mathrm{Re}\sum _{ij}{\overline{a}}_i{b}_{\sigma (i)}=\underset{\sigma }{\min }{|a_i-b_{\sigma (i)}|}^2,$$

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

Title	proof of Wielandt-Hoffman theorem
Canonical name	ProofOfWielandtHoffmanTheorem
Date of creation	2013-03-22 14:58:51
Last modified on	2013-03-22 14:58:51
Owner	Andrea Ambrosio (7332)
Last modified by	Andrea Ambrosio (7332)
Numerical id	6
Author	Andrea Ambrosio (7332)
Entry type	Proof
Classification	msc 15A18
Classification	msc 15A42