Past exam of the year 1 of the computer science course of the University of Oxford / 2015 / Digital systems, linear algebra, introduction to formal proof / 1 / f / Solution

The remaining eigenvalues areThey have absolute value less than one. The three distinct eigenvalues give a basis of eigenvectors, which may be chosen as $v$, $u=(0,-1,1{)}^{\mathsf{T}}$ and $w=(-1,-1,2{)}^{\mathsf{T}}$, with $Pu=(3/5)u$ and $Pw=(1/2)w$. Write an arbitrary initial probability vector as $x_0=cv+\alpha u+\beta w$. Summing its entries shows $c=1$, because the entries of $v$ sum to one and those of $u,w$ sum to zero. ThereforeThis proves convergence for every initial probability vector, rather than merely identifying a possible limit. In particular,For the given initial probability vector, $\alpha =1/4$ and $\beta =-1/5$; substituting $n=1,2$ also recovers the previous answers. The slowest decaying eigenvector component has factor $(3/5{)}^n$.