1
$\begingroup$

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$ ?

$\endgroup$
3
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – H.S Dec 28 '15 at 23:42
  • 2
    $\begingroup$ @H.S Note that permutation matrices are unitary. What does "unitarily invariant" mean to you? $\endgroup$ – Omnomnomnom Dec 29 '15 at 0:04
  • $\begingroup$ You are right. Thanks for guide. $\endgroup$ – H.S Dec 29 '15 at 0:35
3
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ It may be well known, but I didn't know it! Neat trick, I should have thought to bring in the $1$-norm. $\endgroup$ – Omnomnomnom Dec 29 '15 at 0:06
  • $\begingroup$ @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. $\endgroup$ – user1551 Dec 29 '15 at 3:15
  • $\begingroup$ @user1551 Thanks for your patience, The final question : Why does $\rho (A) \ge 1$? $\endgroup$ – H.S Dec 31 '15 at 16:14
  • 1
    $\begingroup$ @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$. $\endgroup$ – user1551 Dec 31 '15 at 16:34
  • 1
    $\begingroup$ @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. $\endgroup$ – user1551 May 10 '18 at 6:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.