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

Choose $A=I_2$ and $B=3I_2$. Then $AB=3I_2=A^2+A+I_2$. Both are real $2\times 2$ matrices, as required.

Rearrange the identity intoTaking determinants gives $\det A\det (B-A-I)=1$. Hence $\det A\ne 0$, so $A$ is an invertible matrix, with $A^{-1}=B-A-I$. This uses that the matrices are finite and square: a right inverse then implies a two-sided inverse. Applying the identity to a vector in the kernel without first establishing commutation would not justify cancelling an $A$ on the wrong side. The argument is a case of invertibility forced by a polynomial product identity.

Multiply the original equation on the left by $A^{-1}$ to obtainEach term on the right commutes with $A$. ThusNo general commutativity of matrix multiplication is being assumed; it follows from this particular expression for $B$.

Let $Av=\lambda v$ for a real eigenvalue $\lambda$ and a nonzero real eigenvector $v$. Part (b) gives $\lambda \ne 0$ and $A^{-1}v={\lambda }^{-1}v$. The expression for $B$ in part (c) therefore givesConsequently $\lambda +1+{\lambda }^{-1}$ is a real eigenvalue of $B$, with the same eigenvector $v$. For a real matrix and real eigenvalue, a nonzero real vector can be chosen in the real kernel of $A-\lambda I$; no complex-vector assumption is needed.

For scalar $a=A\ne 0$, part (c) givesThe numerator is strictly positive for every real $a$, and the denominator is nonzero. Therefore $B\ne 0$ and hence $B$ is invertible. This proof uses the order structure of the real scalars; it does not say that the matrix $A^2+A+I$ must be nonsingular in higher dimension.

An integer-entry example isDirect matrix multiplication gives $A^2=\left(\begin{array}{cc}-1& 1\\ -1& 0\end{array}\right)$, so adding $A$ and $I_2$ gives the zero matrix. Equivalently, this is the companion matrix of $t^2+t+1$ and has the two nonreal cube roots of unity as eigenvalues. The direct multiplication is already a complete proof. It also shows why part (e) does not extend to all real square matrices: with this $A$, choosing $B=0$ satisfies the original product identity.