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 / 4

The update must place the sum of the two current entries in the first coordinate and retain the old first coordinate in the second. Thus choose the matrixBy matrix multiplication, $A(L_n,L_{n-1}{)}^T=(L_n+L_{n-1},L_n{)}^T=(L_{n+1},L_n{)}^T$ for every $n\ge 1$, using the given recurrence relation. This is the companion-matrix representation of the Lucas numbers.

Use mathematical induction on $n$. For $n=0$, the identity matrix gives $(1,2{)}^T=(L_1,L_0{)}^T$. If $A^n(1,2{)}^T=(L_{n+1},L_n{)}^T$, applying $A$ and using part (a) gives $A^{n+1}(1,2{)}^T=(L_{n+2},L_{n+1}{)}^T$. ThereforeThe base case is essential: the starting vector represents consecutive Lucas numbers, not two arbitrary initial values.

The characteristic polynomial isIts two distinct real roots are the eigenvaluesTheir product is $-1$, so $\psi =-1/\phi$. Equivalently, ${\phi }^2=\phi +1$ implies $1/\phi =\phi -1$. The positive eigenvalue is the golden ratio.

For an eigenvalue $t\in \{\phi ,\psi \}$, the equation $A(x,y{)}^T=t(x,y{)}^T$ gives $x=ty$ and $(t+1)y=t^{2}y$. The second identity holds because $t^2=t+1$. Taking $y=1$ gives the eigenvectorsEach associated eigenspace consists of all scalar multiples of its displayed vector. A zero vector is excluded when speaking of an eigenvector.

The requested order is $A=P^{-1}DP$. To obtain this order directly, put the transposes of the two eigenvectors in the rows of $P$, using the fact that $A$ is symmetric:Then $\det P=\phi -\psi =\sqrt{5}\ne 0$, so $P$ is an invertible matrix, withMultiplication gives $PA=\left(\begin{array}{cc}\phi +1& \phi \\ \psi +1& \psi \end{array}\right)=DP$, since ${\phi }^2=\phi +1$ and ${\psi }^2=\psi +1$. Multiplying by $P^{-1}$ proves the required diagonalization. Putting the eigenvectors in columns would instead give the equally standard order $A=QD{Q}^{-1}$, so the convention must be checked rather than copied mechanically.

The initial vector decomposes especially simply in the eigenbasis:because $\phi +\psi =1$. Applying $A^n$ multiplies the two eigenvectors by ${\phi }^n$ and ${\psi }^n$. Part (b) then yieldsReading the second coordinate gives the Lucas closed formAt $n=0$ this is 2 and at $n=1$ it is 1. Each summand obeys the same recurrence relation, which independently verifies the formula and explains why the irrational parts cancel to give an integer.