The permutation matrices are the doubly stochastic matrices with the highest Frobenius norm

Question

In a 2013 talk, Alexandre d'Aspremont did claim the following:

Among all doubly stochastic matrices, the rotations, hence, the permutation matrices, have the highest Frobenius norm

I had never encountered this result. Searching for it on Mathematics SE produced nothing of interest. Assuming this result is indeed correct, a reference would be most appreciated.

---

_Related:

• How would you encourage an orthogonal matrix to be a permutation matrix?

• Which probability mass function has the largest Euclidean norm?

Answer 1

Let $D$ be a doubly stochastic matrix.

proof 1:
Provided you understand Birkhoff - von Neumann, this is an elementary convexity result.

Consider that $\big\Vert \text{_}\big\Vert_F:M^{n\times n}\longrightarrow \mathbb R$ is a strictly convex map [this follows from triangle inequality and homogeneity of re-scaling by positive numbers]. By Birkhoff- von Neumann we know $D$ is in the convex hull of $n\times n$ Permutation matrices so the extremum exists and must be at a vertex of the simplex. That is with $w_k\geq 0$ and $\sum_ k w_k =1$
$\big \Vert D \big \Vert_F = \big \Vert \sum_{k}w_k P^{(k)} \big \Vert_F \leq \sum_{k} w_k\cdot \big \Vert P^{(k)} \big \Vert_F = \sum_{k} w_k\cdot\sqrt{n}=\sqrt n$
where the upper bound is Jensen's Inequality (or triangle inequality if you prefer)

proof 2:
observe that $0\leq d_{i,j}\leq 1$ so
$\big \Vert D\big\Vert_F^2 =\sum_{i=1}^n\sum_{j=1}^n d_{i,j}^2\leq \sum_{i=1}^n\sum_{j=1}^n d_{i,j}=\mathbf 1^T\big(D\mathbf 1\big)=\mathbf 1^T\mathbf 1=n$
with equality iff all $d_{i,j}\in \big\{0,1\big\}$ and by double stochasticity this implies exactly one $1$ in each column and row, and all else are zero, i.e. the max occurs iff $D$ is a permutation matrix.