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

The zero matrix has the required pattern, and matrix addition and scalar multiplication preserve every prescribed zero entry. This proves the vector subspace condition. A basis consists of the matrix unitsThey independently select every permitted entry of a tridiagonal matrix, so the dimension is $n+2(n-1)=3n-2$ for $n\ge 1$.

For $D=\mathrm{diag}(d_1,d_2,d_3)$, the upper entry of $D^{-1}AD$ in positions $i,i+1$ is $b_i{d}_{i+1}/d_i$, and the corresponding lower entry is $c_i{d}_i/d_{i+1}$. They are equal when $(d_{i+1}/d_i{)}^2=c_i/b_i$. All coefficients used here are positive, so chooseDirect matrix multiplication gives the symmetric matrixIts pattern remains tridiagonal. This is positive diagonal symmetrization of a tridiagonal matrix.

For the analogous positive off-diagonal entries in size $n$, takeThe same entrywise computation gives $(D^{-1}AD{)}_{ii}=a_i$ and $(D^{-1}AD{)}_{i,i+1}=(D^{-1}AD{)}_{i+1,i}=\sqrt{b_i{c}_i}$, with every other entry zero. Thus the result is a symmetric matrix with a tridiagonal pattern. Positivity of the diagonal entries $a_i$ is not needed for this positive diagonal symmetrization of a tridiagonal matrix; positivity of $b_i,c_i$ ensures the displayed positive, invertible $D$. In particular, the assertion is not an arbitrary-real-coefficient symmetrization claim when the off-diagonal signs differ.

They are similar matrices, so their eigenvalues, with algebraic multiplicities, are identical. Explicitly,Moreover their eigenvectors correspond by $Av=\lambda v⟺(D^{-1}AD)(D^{-1}v)=\lambda D^{-1}v$. Since the transformed matrix is a real symmetric matrix, the spectral theorem for real symmetric matrices also shows that $A$ has real eigenvalues and is a diagonalizable matrix.

Use banded Gaussian elimination followed by back substitution. To distinguish the right-hand side from the upper-diagonal coefficients $b_i$, write it as $r_i$. If the modified pivot elements are nonzero, the tridiagonal elimination recurrences areThey eliminate just the one entry below each pivot element. Solve the resulting upper bidiagonal matrix system byThere is a bounded number of arithmetic operations per row in each sweep, giving $O(n)$ arithmetic operations and $O(n)$ storage. The unpivoted recurrences cost $8n-7$ arithmetic operations under the usual scalar-operation count.

For a general tridiagonal matrix, nonsingularity alone does not guarantee these pivot elements. If a zero or unsafe pivot element occurs, use partial pivoting between the current row and the next row. These are the only possible nonzero candidates in the current column; adjacent row swaps introduce at most a second upper diagonal. Tracking that fill-in keeps both Gaussian elimination and back substitution at $O(n)$ arithmetic operations. For example, $\left(\begin{array}{cc}0& 1\\ 1& 0\end{array}\right)$ is invertible but requires a row swap. If the input is singular, report a zero final pivot element; a unique solution cannot be promised, and compatibility or free-variable analysis is a separate issue. No nonsingularity or safe-pivot assumption is silently inferred from the word tridiagonal.

Let $f_j$ be the determinant of the leading $j\times j$ principal submatrix. Expansion along the last row gives an $a_j{f}_{j-1}$ term and a $c_{j-1}$ term with negative cofactor sign. In the latter minor, the final column has only $b_{j-1}$ nonzero, and deleting that row and column leaves the leading $(j-2)\times (j-2)$ principal submatrix. Thus the tridiagonal determinant recurrence isHere $f_0=1$ is the empty determinant convention, needed to include $f_2=a_1{a}_2-b_1{c}_1$. The derivation uses cofactor expansion, so the recurrence relation remains valid when coefficients or intermediate determinants vanish; it never divides by a pivot element.

Evaluate the recurrence relation successively, retaining only the preceding two values. Each of the $n-1$ updates uses three multiplications and one subtraction. Hence $4(n-1)=O(n)$ arithmetic operations and $O(1)$ auxiliary storage suffice, excluding the stored input. Naively branching into two recursive calls would repeat work; the sequential computation is essential. This is an arithmetic-operation bound, not a bit-complexity bound for arbitrarily large exact integers.