Are there constructive examples of doubly stochastic matrices (whose rows and columns all sum up to $1$ and contain only non-negative entries) that are not diagonalizable?

  • $\begingroup$ Not diagonalizable over what field? $\endgroup$ – Igor Rivin Jan 13 '11 at 0:26
  • 7
    $\begingroup$ Igor, what do you think the field can be, if the entries are non-negative ? $\endgroup$ – Denis Serre Jan 13 '11 at 9:09
  • 1
    $\begingroup$ @Denis: let's be reductionist: A: does $x^2+1$ factor? B: over what field? Does this exchange make sense to you? If so, so should my previous comment. $\endgroup$ – Igor Rivin Jan 16 '11 at 21:22

Sure. For example:

$$A = \begin{pmatrix} 5/12 & 5/12 & 1/6 \\ 1/4 & 1/4 & 1/2 \\ 1/3 & 1/3 & 1/3 \end{pmatrix}$$

Note that $$A \begin{pmatrix} 0 \\ 1 \\ -1 \end{pmatrix} = \begin{pmatrix} 1/4 \\ -1/4 \\ 0 \end{pmatrix} \ \mbox{and} \ A^2 \begin{pmatrix} 0 \\ 1 \\ -1 \end{pmatrix} = 0.$$ This shows that $A$ is not diagonalizable, as, for diagonalizable matrices, $A$ and $A^2$ have the same kernel.

Now, let me explain how to find this. Let $w$ be the all ones vector. The condition that $A$ is doubly stochastic is that $Aw =w$ and $A^T w = w$ (ignoring positivity for now). For any nonzero vector $v \in \mathbb{R}^n$, we have $Av =v$ and $A^T v = v$ if and only if $Av=v$ and $A$ sends $v^{\perp}$ into itself. This equivalence is obvious for $v=e_1$, and the truth of the statement is preserved by orthogonal changes of coordinate, so it is true for any nonzero $v$.

So, I wanted $Aw=w$ and $A$ to preserve $w^{\perp}$. So, if $A$ is going to be non-diagonalizable, it has to have a nontrivial Jordan block on $w^{\perp}$. So I tried making $A$ be of the form $\left( \begin{smallmatrix} 0 & c \\ 0 & 0 \end{smallmatrix} \right)$ in the basis $\begin{pmatrix} 1 & -1 & 0 \end{pmatrix}^T$, $\begin{pmatrix} 0 & 1 & -1 \end{pmatrix}^T$. At first I tried this with $c=1$, but some of the entries came out negative. So I redid it with a smaller value of $c$. (I knew this had to work because, when $c=0$, you get $A = \left( \begin{smallmatrix} 1/3 & 1/3 & 1/3 \\ 1/3 & 1/3 & 1/3 \\ 1/3 & 1/3 & 1/3 \end{smallmatrix} \right)$ so, by continuity, for $c$ small enough I had to get nonnegative entries.

  • $\begingroup$ Thanks! We were thinking of $w$ and an upper diagonal in the $w^\perp$ space as well but we couldn't nail it! $\endgroup$ – Kaveh Khodjasteh Jan 13 '11 at 17:01

Here's a 2-parameter family of examples.

Let $$A=\pmatrix{a&b&1-a-b\cr2-2a-3b&3a+4b-2&1-a-b\cr a+3b-1&3-3a-5b&2a+2b-1\cr}$$ If $a$ and $b$ are chosen so that all the entries are between 0 and 1, then this is a doubly-stochastic matrix. It has the repeated eigenvalue $3a+3b-2$, which is not 1 if $a+b\ne1$. The matrix $A-(3a+3b-2)I$ has rank 2, provided $a+2b\ne1$. So if $a$ and $b$ are chosen in accordance with the stated conditions, this is a non-diagonalizable doubly-stochastic matrix.

I found this by letting $A(1,1)=a$, $A(1,2)=b$, $A(2,1)=a-\lambda$, $A(2,2)=b+\lambda$, letting the other entries be what they have to be to make all row- and column-sums 1, and then choosing $\lambda$ to make the trace $1+2\lambda$, so the eigenvalues have to be $\lambda$ repeated and 1.

EDIT: If, for some reason, you want the matrix to be singular, then just take $\lambda=0$. Then you get the one-parameter family $$A=\pmatrix{a&(2/3)-a&1/3\cr a&(2/3)-a&1/3\cr1-2a&2a-(1/3)&1/3\cr}$$ Now if you choose $a=1/4$ you get (essentially) David Speyer's example.


In complement to David's answer, the eigenvalue $\lambda=1$ of a doubly stochastic matrix $A$ is always semi-simple. The matrix is permutationally similar to a block upper-triangular matrix $B$ whose diagonal blocks are irreducible. Because $B$ is doubly stochastic too, the sum of the entries in the upper-triangular blocks equals that of the entries in the lower-triangular blocks. The latter is zero, whereas the former is a sum of non-negative terms. The upper-triangular part is thus zero: $B$ is block diagonal. Now apply Perron-Frobenius to each diagonal block.


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.