Past exam of the year 1 of the computer science course of the University of Oxford / 2003 / Calculus, probability, linear algebra, discrete mathematics, logic and proof, and models of computation / 4

The three elementary row operations are:

The nonzero requirement in the second operation ensures that each elementary row operation is reversible.

For a square matrix, the corresponding changes in its determinant areThese follow respectively from the alternating property, multilinearity in the rows, and the fact that a determinant with two equal rows vanishes.

If a square matrix $A$ is an invertible matrix, multiplicativity of the determinant givesso $\det A\ne 0$.

Conversely, suppose $\det A\ne 0$. Use Gaussian elimination to reduce $A$ to row echelon form $U$. Each elementary row operation multiplies the determinant by a nonzero factor, so $\det U\ne 0$. If this square matrix had fewer than $n$ pivots, its row echelon form would have a zero row and hence zero determinant, a contradiction. Therefore it has a pivot in every row and column, and further elementary row operations reduce it to $I$.

Each elementary row operation is multiplication on the left by an invertible matrix, its inverse being the reverse operation. Thus $E_k\cdots E_{1}A=I$ implies $A=E_1^{-1}\cdots E_k^{-1}$, a product of invertible matrices. Hence

Let $A_n$ denote the given tridiagonal matrix and put $D_n=\det A_n$, including $D_0=1$ for the empty determinant. The starting values areFor $n\ge 3$, apply the following elementary row operations in the indicated order, always using the updated rows:The first three rows now beginwith the fourth column omitted if $n=3$. When $n\ge 4$, also use $R_4\leftarrow R_4-R_3$. The resulting block upper triangular matrix has a $3\times 3$ upper triangular matrix with diagonal entries all one in its top left corner, and $A_{n-3}$ in its bottom right corner. All elementary row operations preserved the determinant except the single row interchange. ThereforeApplying this recurrence relation to the three starting values proves by mathematical induction thatEquivalently, the sequence is periodic with period six, with values $1,1,0,-1,-1,0$ starting at $n=0$. A compact closed form is $D_n=\sin ((n+1)\pi /3)/\sin (\pi /3)$.

A square matrix is an invertible matrix exactly when its determinant is nonzero. The preceding recurrence relation therefore gives