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

An eigenvalue and eigenvector pair $(\lambda ,v)$ for a square matrix $A$ satisfiesThe scalar $\lambda$ and the coordinates of $v$ belong to the chosen field, usually $\mathbb{R}$ or $\mathbb{C}$. The nonzero condition is essential: the zero vector satisfies the equation for every $\lambda$ and therefore cannot define an eigenvalue.

The vectors $v_1,\dots ,v_n$ are linearly independent ifThey are linearly dependent if some such relation has at least one nonzero coefficient. All coefficients lie in the underlying field. Thus linear independence means that only the trivial linear combination gives zero; linear dependence means that a nontrivial one does.

Apply $A$ to the stated linear combination and use each eigenvector equation:Subtract ${\lambda }_{k+1}$ times the original relation. This givesThe assumed linear independence implies ${\alpha }_i({\lambda }_i-{\lambda }_{k+1})=0$ separately for every $i$. Since the eigenvector $z_{k+1}$ is nonzero, not all ${\alpha }_i$ can vanish. Choose any $i$ with ${\alpha }_i\ne 0$; division by that coefficient gives ${\lambda }_i={\lambda }_{k+1}$. In fact every nonzero coefficient is attached to that same eigenvalue.

Interpret “distinct eigenvalues” as $n$ pairwise distinct eigenvalues in the chosen field. Select a nonzero eigenvector $z_i$ for each. A single nonzero vector is linearly independent. Suppose inductively that $z_1,\dots ,z_k$ are linearly independent. If adding $z_{k+1}$ made the set linearly dependent, its nontrivial relation would have a nonzero coefficient of $z_{k+1}$, since otherwise it would contradict the induction hypothesis. Solving for $z_{k+1}$ would place it in the linear span of the first $k$ eigenvectors.

Part (c) would then force ${\lambda }_{k+1}={\lambda }_i$ for some $i\le k$, contradicting pairwise distinctness. Mathematical induction therefore proves that all $n$ selected eigenvectors are linearly independent, forming a basis. If the field is $\mathbb{R}$, the assertion requires $n$ real eigenvalues; a real matrix can instead have nonreal eigenvalues and a eigenvector basis over the complex numbers.

For $A$, the triangular matrix formula gives the characteristic polynomialThe three eigenvalues are distinct, so part (d) already proves the existence of an eigenvector basis. Explicit choices, ordered by eigenvalues $1,3,2$, areTheir column matrix has determinant one, and direct multiplication gives respectively one, three and two times the indicated vector.

For $B$, expansion along the last row givesAgain the three eigenvalues are distinct. An explicit eigenvector basis, ordered by eigenvalues $4,2,3$, isIts column matrix has determinant $-2\ne 0$. In particular, $B$'s diagonal entries are not its eigenvalues: it is not a triangular matrix.

Finally $C=I_3$, so every nonzero vector is an eigenvector with eigenvalue one. Choose the standard basis $e_1,e_2,e_3$. These are linearly independent even though their eigenvalues coincide. Distinct eigenvalues are sufficient for an eigenvector basis, and are not necessary.