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

By matrix multiplication, $D_{ij}={\sum }_{k=1}^N{B}_{ik}{C}_{kj}$. A potentially nonzero term requires $k=i$ because $B$ is a diagonal matrix, and $k=j$ because $C$ is a diagonal matrix. For $i\ne j$ these requirements cannot both hold. Thus every summand is zero and $D_{ij}=0$ whenever $i\ne j$.

The diagonal matrix entry is $D_{ii}={\sum }_{k=1}^N{B}_{ik}{C}_{ki}$. Only $k=i$ can contribute, so $D_{ii}=B_{ii}{C}_{ii}$. This also shows that the product is a diagonal matrix, with its diagonal obtained by entrywise multiplication of the two diagonals.

Repeatedly applying the previous product rule givesFormally, the result holds for $p=1$; multiplication by $B$ preserves the zero off-diagonal matrix entries and multiplies each diagonal matrix entry by $B_{ii}$, proving the induction step.

The characteristic polynomial is $\det (\lambda I-A)={\lambda }^2-\lambda -1$. Its distinct eigenvalues are $\alpha =(1+\sqrt{5})/2$ and $\beta =(1-\sqrt{5})/2$. For either eigenvalue $\lambda$, the vector $(\lambda ,1{)}^{\top }$ is an eigenvector, since $A(\lambda ,1{)}^{\top }=(\lambda +1,\lambda {)}^{\top }=\lambda (\lambda ,1{)}^{\top }$.

ChooseThe determinant of $S$ is $\alpha -\beta =\sqrt{5}\ne 0$, soIts columns being eigenvectors gives $AS=SD$, and left multiplication by $S^{-1}$ proves $S^{-1}AS=D$.

The initial vector records both initial Fibonacci numbers: $V_1=(U_2,U_1{)}^{\top }=(1,1{)}^{\top }$. For $n\ge 2$,Conversely this vector recurrence forces the second component to be the preceding first component and forces their sum to be the next first component, recovering the scalar recurrence and its initial conditions. Iterating, or using mathematical induction, yields $V_n=A^{n-1}(1,1{)}^{\top }$ for every $n\ge 1$.

The diagonalization gives $A=SD{S}^{-1}$ and hence $A^{n-1}=S{D}^{n-1}{S}^{-1}$: the intervening factors $S^{-1}S$ cancel. The diagonal matrix power has entries ${\alpha }^{n-1},{\beta }^{n-1}$. Since $1-\beta =\alpha$ and $\alpha -1=-\beta$,Reading the second component gives the Binet formulaThe derivation includes $n=1$, and the expression gives $U_1=U_2=1$, consistent with the specified indexing.