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 (resit) / 5

A scalar $\lambda$ is an eigenvalue of an $n\times n$ matrix $P$ if there is a nonzero vector $\mathbf{v}$ such thatAny such vector is an eigenvector corresponding to $\lambda$. The requirement that an eigenvector be nonzero is essential: the zero vector would satisfy the equation for every scalar and would convey no information.

Use the state order Tall, Medium, Short and column probability distributions, so that ${\mathbf{p}}_{n+1}=P{\mathbf{p}}_n$. The $j$th column records the child's probability distribution given parent state $j$. Thus the transition matrix isEvery entry is nonnegative and every column sums to one. This convention also gives the requested property $P^T(1,1,1{)}^T=(1,1,1{)}^T$. A row-distribution convention would use the transposed transition matrix consistently instead. The stated Markov chain is the mathematical model to analyze; no additional biological assumptions are needed.

Condition on the intermediate parent's height and use the Markov property. The three mutually exclusive paths through Tall, Medium and Short contributeEquivalently, this is entry $(3,1)$ of the matrix power $P^2$. Hence

For $1=(1,1,1{)}^T$, the entries of $P^{T}1$ are the column sums of $P$. Henceso $1$ is an eigenvalue of $P^T$, with eigenvector $1$.

The determinant is unchanged by matrix transposition, soThus $P-I$ has a nontrivial null space, givingThe same argument with $\lambda I$ shows that a matrix and its transpose have the same characteristic polynomial. It does not say that they have the same eigenvectors: here $P1=(0.9,1.2,0.9{)}^T\ne 1$.

Find a stationary distribution $\mathbf{\pi }=(u,v,w{)}^T$ from $P\mathbf{\pi }=\mathbf{\pi }$ and $u+v+w=1$. The first two independent linear equations areThey give $u=9w/8$ and $v=7w/4$. Normalization gives $w=8/31$, hence

To justify the limit using the assumptions, distinct eigenvalues give an eigenbasis, over the complex numbers if necessary. Choose $\mathbf{\pi }$ as the eigenvector for 1 and let ${\mathbf{v}}_2,{\mathbf{v}}_3$ correspond to the other eigenvalues ${\lambda }_2,{\lambda }_3$. Expand the initial probability distribution asSince $1^{T}P=1^T$, each ${\lambda }_j\ne 1$ satisfiesMultiplying the expansion by $1^T$ therefore gives $\alpha =1$. It follows thatbecause $|{\lambda }_2|,|{\lambda }_3|<1$. The components of the limiting probability distribution are approximately $0.2903,0.4516,0.2581$.