Stochastic Matrices: Kind of like Sudoku, but kind of not.
July 22, 2010
At some point, I mentioned that if is a complex vector space and is a linear map such that , then has an eigenvalue. We also noted that if is an odd dimensional real space, then has an eigenvalue. Stochastic matrices, which are in probability theory and a whole bunch of other places, have this same sort of nice property: if happens to be stochastic, then there exists an eigenvalue!
But what the heck is a (right) stochastic matrix? Well, it’s not difficult to explain: it is a matrix such that in each of the rows, all of the numbers in that row add up to 1. So, for example, look at the matrix
Notice that the numbers in the first row add up to one and, similarly, the second and third rows also add up to 1 each. But
is not a stochastic matrix, because the first row does not add up to 1 (as, obviously, 1 + 2 + 0 = 3). Sad. But, now, here’s the formal theorem.
Theorem: If is a nontrivial finite-dimensional vector space and is a linear map such that is a stochastic matrix, then has an eigenvalue.
Proof. Okay, let’s find it. Let’s write out :
where for all . Now, let’s find an eigenvalue by finding an eigenvector. Think about this for a second. We want
and we only know one thing about , namely that it’s stochastic. So, if you haven’t figured it out yet, let’s let be the vertical vector that’s made up of all 1’s. So,
which is nice. Notice, then, that corresponds to the eigenvector with all 1’s that we just described. .