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

With column vectors, entry $P_{ij}$ is the fraction moving from region $j$ to region $i$. The first column is therefore $(1/2,1/4,1/4{)}^{\mathsf{T}}$, the second is $(1/2,1/2,0{)}^{\mathsf{T}}$, and the third is $(1/2,0,1/2{)}^{\mathsf{T}}$. HenceEach column sums to one, as required for this convention for a stochastic matrix. Multiplying by $P$ conserves the total resources.

For a square matrix $M$, an eigenvalue–eigenvector pair is a scalar $\lambda$ and a nonzero vector $v$ satisfyingThus the linear map represented by $M$ scales this particular direction by $\lambda$. The nonzero condition excludes the zero vector, which would otherwise satisfy the displayed equation for every scalar.

Apply the transition matrix once and then again:Therefore, in USA, Europe, Rest of World order and in trillions of dollars,Each total remains ten, giving a quick check on the matrix multiplication.

Use the characteristic polynomial convention $p(\lambda )=\det (\lambda I-P)$, with $I$ the identity matrix. Put $u=\lambda -1/2$. ThenThe required characteristic polynomial equation for this matrix is thereforeUsing $\det (P-\lambda I)$ instead negates the cubic polynomial and leaves the eigenvalues unchanged.

The factor $(\lambda -1)$ proves that one is an eigenvalue. To find its normalized eigenvector, solve $Pv=v$. The second and third rows giveso $v_2=v_3=v_1/2$. The normalization $v_1+v_2+v_3=1$ now givesIts entries are nonnegative and sum to one, and direct matrix multiplication verifies $Pv=v$. As a probability vector it is the stationary distribution; as resource shares it assigns half to the USA and a quarter to each other region.

The other eigenvalues are $1/2$ and $0$. Their magnitudes are strictly less than one. All three eigenvalues are distinct, so their eigenvectors form a basis and the matrix is diagonalizable. Every component outside the stationary direction therefore decays under repeated application of $P$.

For an explicit justification, chooseThen $Pw=w/2$, $Pu=0$, andThe zero-eigenvalue component disappears after one step. For every $n\ge 1$,Thus the shares converge to $v$ and the resource vector converges to $10v$, since the conserved total is ten. For any other initial resource vector of total $T$, the same eigenvector argument gives the limit $Tv$.