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 invariantunder 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 elementsbe given by ${(U)}_{ij}=u_{ij}$. Unitarity implies that the matrix withelements ${|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$, whoseelements are ${(S)}_{ij}=s_{ij}$. By the Birkoff-von Neumann theorem, doublystochastic matrices form a closed convex (http://planetmath.org/ConvexSet) polyhedronwith 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 lastinequality 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.