Linear algebra proof definition of a stochastic matrix

[0rthodontist]

I was reading through the section of my linear algebra book that deals with Markov chains. It said that in a stochastic matrix A, there is always a probability vector v such that Av = v.

I didn't see a precise definition of a stochastic matrix, but I gather it means that every entry is between 0 and 1 inclusive, and each column sums to 1. And apparently a probability vector is just a stochastic matrix of width 1.

The book declined to prove it, and I am not finding it easy to do so. It means that all stochastic matrices have 1 as an eigenvalue, and also that the entries in at least one eigenvector for that eigenvalue all have the same sign.

I'm thinking, stochastic matrices transform probability vectors into other probability vectors, so if you start with a probability vector v = (v1, ... , vn) and keep transforming it it always stays on the probability vector plane v1 + ... + vn = 1, in the first quadrant/octant/etc. If the stochastic matrix has n linearly independent eigenvectors, then it's simple: just write v as a linear combination of eigenvectors. If any eigenvalues for these eigenvectors are greater than 1 then v eventually goes to infinity under repeated transformations by A, so all eigenvalues are <= 1. There must be an eigenvalue that is 1, because otherwise v would eventually go to 0. And the eigenvalues less than 1 drop away, so the conclusion follows. However, is it true that a stochastic matrix will always have n l.i. eigenvectors?

Also is there a simpler way to prove it, maybe by starting with det (A - I) = 0?

 

[Hurkyl]

Hrm.


First off, a stochastic matrix can have negative entries. See http://en.wikipedia.org/wiki/Stochastic_matrix


I can see a few approaches that might work.

You could try and do something with the Jordan canonical form.

You could try to write A as a limit of diagonalizable stochastic matrices, and do something with that.

You could try proving the theorem directly by chasing around the iterates of some v, or by looking at the set of limit points of the sequence A^n v. (Armed, of course, with the knowledge that all of the iterates are probability vectors)

 

[0rthodontist]

The book actually gave it as a problem with hints at the end of the section, though it's odd they didn't mention that in the text where I first came across it. Anyway, the trick they used is in the matrix A - I, add to the last row all the rows above it. Since each column of A - I sums to 0, the last row will then be 0.

They said that the part about the steady state vector v = Av having positive entries is given in advanced texts.