TAOCP 4.5.3 Exercise 3

Let D_n= \det \begin{pmatrix} x_1 & 1 & 0 & \cdots & 0 \\

taocpmathematicsalgorithmsvolume-2math-medium

Section 4.5.3: Analysis of Euclid's Algorithm

Exercise 3. [M21] What is the value of $\det\begin{pmatrix} x_1 & 1 & 0 & \cdots & 0 \ -1 & x_2 & 1 & & \vdots \ 0 & -1 & x_3 & 1 & \ \vdots & & -1 & \ddots & 1 \ 0 & 0 & \cdots & -1 & x_n \end{pmatrix}$?

Verified: yes
Solve time: 1m30s

Solution

Let

$$ D_n= \det \begin{pmatrix} x_1 & 1 & 0 & \cdots & 0 \ -1 & x_2 & 1 & \cdots & 0 \ 0 & -1 & x_3 & \ddots & \vdots \ \vdots & & \ddots & \ddots & 1 \ 0 & 0 & \cdots & -1 & x_n \end{pmatrix}. $$

We shall show that

$$ D_n=K_n(x_1,x_2,\ldots,x_n), $$

where $K_n$ is the continuant polynomial defined by (4).

For $n=0$, the determinant of the empty matrix is $1$, hence

$$ D_0=1=K_0. $$

For $n=1$,

$$ D_1=\det(x_1)=x_1=K_1(x_1). $$

Assume $n\ge2$. Expanding $D_n$ by the first row gives

$$ D_n = x_1 \det \begin{pmatrix} x_2 & 1 & 0 & \cdots & 0 \ -1 & x_3 & 1 & \cdots & 0 \ 0 & -1 & x_4 & \ddots & \vdots \ \vdots & & \ddots & \ddots & 1 \ 0 & 0 & \cdots & -1 & x_n \end{pmatrix} - \det \begin{pmatrix} -1 & 1 & 0 & \cdots & 0 \ 0 & x_3 & 1 & \cdots & 0 \ 0 & -1 & x_4 & \ddots & \vdots \ \vdots & & \ddots & \ddots & 1 \ 0 & 0 & \cdots & -1 & x_n \end{pmatrix}. $$

The first determinant is $D_{n-1}$ with variables $x_2,\ldots,x_n$.

In the second determinant, the first column contains only the entry $-1$ in the first row. Expanding by that column yields

$$ -\det \begin{pmatrix} -1 & 1 & 0 & \cdots & 0 \ 0 & x_3 & 1 & \cdots & 0 \ 0 & -1 & x_4 & \ddots & \vdots \ \vdots & & \ddots & \ddots & 1 \ 0 & 0 & \cdots & -1 & x_n \end{pmatrix} = \det \begin{pmatrix} x_3 & 1 & 0 & \cdots & 0 \ -1 & x_4 & 1 & \cdots & 0 \ 0 & -1 & x_5 & \ddots & \vdots \ \vdots & & \ddots & \ddots & 1 \ 0 & 0 & \cdots & -1 & x_n \end{pmatrix}. $$

Hence

$$ D_n = x_1 D_{n-1}(x_2,\ldots,x_n) + D_{n-2}(x_3,\ldots,x_n). $$

This is exactly the recurrence (4) that defines the continuants. Since $D_0=K_0$ and $D_1=K_1$, induction on $n$ gives

$$ D_n=K_n(x_1,x_2,\ldots,x_n). $$

Therefore the determinant is

$$ \boxed{ \det \begin{pmatrix} x_1 & 1 & 0 & \cdots & 0 \ -1 & x_2 & 1 & & \vdots \ 0 & -1 & x_3 & 1 & \ \vdots & & -1 & \ddots & 1 \ 0 & 0 & \cdots & -1 & x_n \end{pmatrix} = K_n(x_1,x_2,\ldots,x_n) }. $$

∎