# proof of Wielandt-Hoffman theorem

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

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

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

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

where $U=W{V}^{\u2020}$. 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}{\mathrm{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}{\mathrm{min}}\mathrm{Re}\sum _{ij}{\overline{a}}_{i}{b}_{\sigma (i)}=\underset{\sigma}{\mathrm{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 |