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

The transition matrix acts on a column probability vector in the order Central, Headington, Botley. Thus column $j$ records the destinations of buses starting at station $j$. The Central-to-Headington, Headington-to-Botley and Botley-to-Central entries giveEach column sums to one, as required for this column convention for a stochastic matrix.

For a square matrix $M$, an eigenvalue–eigenvector pair consists of a scalar $\lambda$ and a nonzero vector $v$ satisfyingThe linear map represented by $M$ therefore scales $v$ by $\lambda$. The exclusion of the zero vector matters: otherwise every scalar would satisfy the equation trivially.

Use matrix multiplication to evolve the probability vector by $x_{n+1}=P{x}_n$. With $x_0=(0.4,0.4,0.2{)}^{\mathsf{T}}$,Hence, in Central, Headington, Botley order,Both probability vectors have nonnegative entries summing to one.

Define the characteristic polynomial using $p(\lambda )=\det (\lambda I-P)$, where $I$ is the identity matrix. Expanding the determinant along the first row givesThus the characteristic equation isThe convention $\det (P-\lambda I)$ changes the sign of this cubic polynomial but gives the same roots.

The factorization of the characteristic polynomial shows that $\lambda =1$ is an eigenvalue. To find its normalized eigenvector, solve $(P-I)v=0$ together with $v_C+v_H+v_B=1$. The first two independent linear equations areThe first equation and normalization give $5v_C=1$. The second gives $v_H-v_B=v_C/2=1/10$, while $v_H+v_B=4/5$. Consequently,All entries are positive and sum to one. This probability vector is the stationary distribution.

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$.