# Why does $\left\| {\left| A \right|} \right\| \le \left\| {\left| I \right|} \right\|$, for every doubly stochastic matrix $A \in M_n$?

Let $\left\| {\left| . \right|} \right\|$ be a unitarily invariant matrix norm on $M_n$.

Why does $\left\| {\left| A \right|} \right\| \le \left\| {\left| I \right|} \right\|$, for every doubly stochastic matrix $A \in M_n$ ?

## 2 Answers

Hint: The result is fairly immediate if we use Birkhoff's theorem. Note that permutation matrices are unitary.

• Thanks, For solve this question( by Birkhoff–von Neumann) we need that $\left\| {\left| P \right|} \right\| \le \left\| {\left| I \right|} \right\|$ for any Permutation matrix $P$.Why is true? – H.S Dec 28 '15 at 23:42
• @H.S Note that permutation matrices are unitary. What does "unitarily invariant" mean to you? – Omnomnomnom Dec 29 '15 at 0:04
• You are right. Thanks for guide. – H.S Dec 29 '15 at 0:35

In the spirit of Omnomnomnom's answer, here is an alternative approach that doesn't require Birkhoff theorem.

It is well-known that when $A$ is doubly stochastic, its operator norm is equal to $1$ (because $1\le\rho(A)^2 \le \|A\|_2^2 = \rho(A^TA) \le \|A^TA\|_1 = 1$). So, by unitary invariance of the norm $|||\cdot|||$ in question and by singular value decomposition, you may assume that $A$ is a nonnegative diagonal matrix whose largest diagonal entry is $1$. It is easy to show that such a matrix is a convex combination of at most $2n$ diagonal real orthogonal matrices.

• It may be well known, but I didn't know it! Neat trick, I should have thought to bring in the $1$-norm. – Omnomnomnom Dec 29 '15 at 0:06
• @Omnomnomnom Your answer is nice. I prefer using Birkhoff theorem, because it results in a much cleaner solution. I give another proof here just for the sake of finding another proof. – user1551 Dec 29 '15 at 3:15
• @user1551 Thanks for your patience, The final question : Why does $\rho (A) \ge 1$? – H.S Dec 31 '15 at 16:14
• @H.S $A$ is doubly stochastic, so $1$ is an eigenvalue of $A$. Now $\rho(A)$ is the modulus of the largest-sized eigenvalue of $A$. Hence $\rho(A)\ge1$. – user1551 Dec 31 '15 at 16:34
• @user550103 Perron-Frobenius theorem does imply that the spectral radius of a row/column/doubly stochastic matrix is $1$, but a doubly (rather than row- or column-) stochastic matrix is concerned, this fact follows immediately from the squeezing inequality in my answer. Perron-Frobenius theorem is not needed. – user1551 May 10 '18 at 6:02