Frobenius norm of the difference of two doubly stochastic matrices

Question

What is the maximum possible value of the Frobenius norm of the difference of two doubly stochastic matrices? An easy guess is $\sqrt{2N}$, with the first matrix having all $1$s on the main diagonal, and the other one with $1$s on the anti-diagonal (and $0$s elsewhere). But I am unable to move in the direction of proving that this is indeed the maximum bound.

Answer 1

Let $A$ and $B$ be two doubly stochastic matrices. Then $$ \|A-B\|_F^2 =\operatorname{tr}(A^TA+B^TB-A^TB-B^TA) \le\operatorname{tr}(A^TA)+\operatorname{tr}(B^TB). $$ Since $A$ and $B$ are doubly stochastic, so are $A^TA$ and $B^TB$. Yet, each diagonal element of a stochastic matrix is at most one. Therefore $\operatorname{tr}(A^TA)+\operatorname{tr}(B^TB)\le2N$ and in turn $\|A-B\|_F^2\le2N$. This upper bound is tight when $N\ge2$: equality holds when $A$ and $B$ are permutation matrices with non-overlapping $1$s, such as $$ A=I_N\ \text{ and }\ B=\pmatrix{0&1\\ &\ddots&\ddots\\ &&\ddots&1\\ 1&&&0}. $$