Are there constructive examples of doubly stochastic matrices (whose rows and columns all sum up to $1$ and contain only nonnegative 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 nonnegative ? $\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 nondiagonalizable, 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 2parameter family of examples.
Let $$A=\pmatrix{a&b&1ab\cr22a3b&3a+4b2&1ab\cr a+3b1&33a5b&2a+2b1\cr}$$ If $a$ and $b$ are chosen so that all the entries are between 0 and 1, then this is a doublystochastic matrix. It has the repeated eigenvalue $3a+3b2$, which is not 1 if $a+b\ne1$. The matrix $A(3a+3b2)I$ has rank 2, provided $a+2b\ne1$. So if $a$ and $b$ are chosen in accordance with the stated conditions, this is a nondiagonalizable doublystochastic 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 columnsums 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 oneparameter family $$A=\pmatrix{a&(2/3)a&1/3\cr a&(2/3)a&1/3\cr12a&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 semisimple. The matrix is permutationally similar to a block uppertriangular matrix $B$ whose diagonal blocks are irreducible. Because $B$ is doubly stochastic too, the sum of the entries in the uppertriangular blocks equals that of the entries in the lowertriangular blocks. The latter is zero, whereas the former is a sum of nonnegative terms. The uppertriangular part is thus zero: $B$ is block diagonal. Now apply PerronFrobenius to each diagonal block.