This is a followup to a previous question where a nice counter example came up to the proposition "stochastic matrices can only have trivial Jordan forms".

This question looks at the more strict case of doubly stochastic matrices:

$${\bf M} \in \mathbb [0,1]^{n\times n} : \cases{ \displaystyle \sum_{i}{\bf M}_{ij} = 1, \forall j\\\displaystyle \sum_{j}{\bf M}_{ij} = 1, \forall i}$$

Can we find a counter example for those too?


Yes. As $1$ is always a semi-simple eigenvalue of a doubly stochastic matrix, the smallest-sized counterexample is $3\times3$, and here is a random counterexample. Consider $$ M=\frac1{15}\pmatrix{ 4&4&7\\ 6&6&3\\ 5&5&5}. $$ Since $Mu=0$ for $u=(1,-1,0)^T$ and $Mv=u$ for $v=(0,-5,5)^T$, $M$ has a $2\times2$ nilpotent Jordan block in its Jordan form.

  • $\begingroup$ Nice!, But is it possible for non-0 eigenvalues too? $\endgroup$ – mathreadler Sep 4 '17 at 12:35
  • 2
    $\begingroup$ @mathreadler Sure. $tM+(1-t)I$ would be such a counterexample for any $0<t<1$. $\endgroup$ – user1551 Sep 4 '17 at 12:37
  • $\begingroup$ That's a nice looking example. Was there any trick to come up with it? $\endgroup$ – Omnomnomnom Sep 4 '17 at 15:53
  • 1
    $\begingroup$ @Omnomnomnom There wasn't any trick. As $1$ is a semi-simple eigenvalue, if there is any 3x3 counterexample $M$ at all, it has to be a convex combination of $I_3$ and a doubly stochastic matrix similar to $1\oplus J_2(0)$. So it suffices to consider a singular $M$ and a natural choice is to perturb the all-one matrix in a minimal way, i.e. to try $$M=\frac1{3c}\pmatrix{c-d&c-d&c+2d\\c+d&c+d&c-2d\\c&c&c}$$ with $c\ge|2d|>0$. Now any such $c,d$ in this range will give you a valid counterexample because $M(1,-1,0)^T=0$ and $\frac cdM(0,-1,1)^T=(1,-1,0)^T$. $\endgroup$ – user1551 Sep 4 '17 at 16:17
  • $\begingroup$ @user1551 that's a clever way to do it. I was wondering how you should perturb the all-one matrix in such a way that you maintain the right multiplicity of eigenvalues, but that's clear now. $\endgroup$ – Omnomnomnom Sep 4 '17 at 19:24

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.