Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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|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
add comment

2 Answers 2

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|improve this answer
add comment

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|improve this answer
add comment

Your Answer

 
discard

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.