TAOCP 1.2.8 Exercise 24

Exercise 24. [HM20] Evaluate the $n \times n$ determinant

$$ \begin{pmatrix} 1 & -1 & 0 & 0 & \cdots & 0 & 0 & 0 \ 1 & 1 & -1 & 0 & \cdots & 0 & 0 & 0 \ 0 & 1 & 1 & -1 & \cdots & 0 & 0 & 0 \ \vdots & \vdots & \vdots & \vdots & \ddots & \vdots & \vdots & \vdots \ 0 & 0 & 0 & 0 & \cdots & 1 & 1 & -1 \ 0 & 0 & 0 & 0 & \cdots & 0 & 1 & 1 \end{pmatrix}. $$

Verified: no
Solve time: -

Solution

Let $D_n$ denote the determinant of the $n \times n$ matrix

$$ A_n = \begin{pmatrix} 1 & -1 & 0 & 0 & \cdots & 0 & 0 & 0 \ 1 & 1 & -1 & 0 & \cdots & 0 & 0 & 0 \ 0 & 1 & 1 & -1 & \cdots & 0 & 0 & 0 \ \vdots & \vdots & \vdots & \vdots & \ddots & \vdots & \vdots & \vdots \ 0 & 0 & 0 & 0 & \cdots & 1 & 1 & -1 \ 0 & 0 & 0 & 0 & \cdots & 0 & 1 & 1 \end{pmatrix}. $$

We first observe that $A_n$ is a tridiagonal matrix with entries $1$ on the main diagonal except for the last entry (still $1$), $1$ on the subdiagonal (starting from row $2$), and $-1$ on the superdiagonal except for the last column. Specifically, the entries satisfy

$$ (A_n)_{i,j} = \begin{cases} 1 & \text{if } j=i \text{ or } j=i-1,\ -1 & \text{if } j=i+1,\ 0 & \text{otherwise.} \end{cases} $$

We now expand $D_n$ along the first row. Let $D_n$ denote the determinant of $A_n$. The first row has only two nonzero entries: $1$ in column $1$ and $-1$ in column $2$. By the Laplace expansion along the first row, we have

$$ D_n = 1 \cdot \det(M_{1,1}) - (-1)\cdot \det(M_{1,2}), $$

where $M_{1,1}$ is the $(n-1)\times(n-1)$ matrix obtained by removing the first row and first column, and $M_{1,2}$ is obtained by removing the first row and second column. Examining the structure of $A_n$, we see that

$$ M_{1,1} = \begin{pmatrix} 1 & -1 & 0 & \cdots & 0 \ 1 & 1 & -1 & \cdots & 0 \ 0 & 1 & 1 & \cdots & 0 \ \vdots & \vdots & \vdots & \ddots & -1 \ 0 & 0 & 0 & 1 & 1 \end{pmatrix}_{(n-1)\times(n-1)} $$

is exactly $A_{n-1}$, so $\det(M_{1,1}) = D_{n-1}$.

The matrix $M_{1,2}$ has the form

$$ M_{1,2} = \begin{pmatrix} 1 & -1 & 0 & \cdots & 0 \ 0 & 1 & -1 & \cdots & 0 \ 0 & 1 & 1 & \cdots & 0 \ \vdots & \vdots & \vdots & \ddots & -1 \ 0 & 0 & 0 & 1 & 1 \end{pmatrix}_{(n-1)\times(n-1)}. $$

By swapping the first and second rows of $M_{1,2}$, we see that it becomes a block upper-triangular matrix with top-left $1\times1$ block equal to $1$ and bottom-right block of size $(n-2)\times(n-2)$ equal to $A_{n-2}$. Swapping the rows changes the sign of the determinant once, so $\det(M_{1,2}) = - D_{n-2}$.

Substituting, we obtain the recurrence

$$ D_n = D_{n-1} + D_{n-2}, \quad n \ge 3, $$

which is exactly the Fibonacci recurrence.

The initial conditions are easily computed:

$$ D_1 = \det(1) = 1, \qquad D_2 = \det\begin{pmatrix}1 & -1 \ 1 & 1 \end{pmatrix} = 1\cdot 1 - (-1)\cdot 1 = 2. $$

Comparing with the Fibonacci numbers $F_n$ defined by $F_0=0$, $F_1=1$, $F_2=1$, $F_3=2$, we see that

$$ D_n = F_{n+1}. $$

Hence, for all $n\ge 1$, the determinant of the given $n\times n$ tridiagonal matrix is

$$ \boxed{F_{n+1}}. $$

This completes the proof.

∎