Non-diagonalizable doubly stochastic matrices

Question

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?

Answer 1

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.

Answer 2

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.

Answer 3

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.