[Math] Effect of doubly stochastic matrix on vector norm

Question

Let $D$ be a $N \times N$ doubly stochastic matrix, $x$ be a $N$ dimensional vector.

What is the relation between $\Vert Dx \Vert_2$ and $\Vert x \Vert_2$?

In addition if $\Vert x \Vert_2=1$, what can I say about $\Vert Dx \Vert_2$?

Answer 1

It's true that a doubly stochastic matrix $D$ has operator norm 1. But that's not because of its eigenvalues, because $\|P\|=1$ is false for a general stochastic matrix $P$.

Rather, from the Birkhoff–von Neumann theorem we know that $D$ is a convex combination of permutation (norm one) matrices, and hence $\|D\|\leq 1$.

Alternatively, if $D$ is doubly stochastic then $D^* D$ is stochastic and therefore its eigenvalues are bounded by one in modulus. Therefore $\|D\|=1$.