Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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

share|cite|improve this question
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
up vote 1 down vote accepted

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

share|cite|improve this answer

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

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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