# Effect of doubly stochastic matrix on vector norm

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

-
If $\|x\|_2$...what? You , miss something in your second question. –  1015 Apr 10 '13 at 3:13
@julien Thanks, updated. –  Rein Apr 10 '13 at 3:42

## 2 Answers

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

-

From here, we have that the largest eigenvalue of a stochastic matrix is $1$. Hence, we have $$\Vert Dx \Vert_2 \leq \Vert x \Vert_2$$

-