Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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

share|improve this question
    
Not diagonalizable over what field? –  Igor Rivin Jan 13 '11 at 0:26
7  
Igor, what do you think the field can be, if the entries are non-negative ? –  Denis Serre Jan 13 '11 at 9:09
    
@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. –  Igor Rivin Jan 16 '11 at 21:22
add comment

3 Answers

up vote 27 down vote accepted

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.

share|improve this answer
    
Thanks! We were thinking of $w$ and an upper diagonal in the $w^\perp$ space as well but we couldn't nail it! –  Kaveh Khodjasteh Jan 13 '11 at 17:01
add comment

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.

share|improve this answer
add comment

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.

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.