TAOCP 4.5.3 Exercise 2

Let us consider the product $M_n = \begin{pmatrix}1 & 1 \\ 1 & 0\end{pmatrix} \begin{pmatrix}x_1 & 1 \\ 1 & 0\end{pmatrix} \begin{pmatrix}x_2 & 1 \\ 1 & 0\end{pmatrix} \cdots \begin{pmatrix}x_n & 1 \\...

taocpmathematicsalgorithmsvolume-2math-medium

Section 4.5.3: Analysis of Euclid's Algorithm

Exercise 2. [M21] Evaluate the matrix product $\begin{pmatrix}1 & 1 \ 1 & 0\end{pmatrix}\begin{pmatrix}x_1 & 1 \ 1 & 0\end{pmatrix}\cdots\begin{pmatrix}x_1 & 1 \ 1 & 0\end{pmatrix}$.

Verified: yes
Solve time: 32m23s

Solution

Let us consider the product

$M_n = \begin{pmatrix}1 & 1 \ 1 & 0\end{pmatrix} \begin{pmatrix}x_1 & 1 \ 1 & 0\end{pmatrix} \begin{pmatrix}x_2 & 1 \ 1 & 0\end{pmatrix} \cdots \begin{pmatrix}x_n & 1 \ 1 & 0\end{pmatrix}.$

We denote the $k$th matrix in the product by

$A_k = \begin{pmatrix}x_k & 1 \ 1 & 0\end{pmatrix}, \qquad k = 1, 2, \ldots, n.$

Define recursively

$M_0 = \begin{pmatrix}1 & 0 \ 0 & 1\end{pmatrix}, \qquad M_k = M_{k-1} A_k.$

We claim that $M_k$ has the form

$M_k = \begin{pmatrix}K_{k+1}(x_1, \ldots, x_k) & K_k(x_1, \ldots, x_{k-1}) \ K_k(x_2, \ldots, x_k) & K_{k-1}(x_2, \ldots, x_{k-1})\end{pmatrix}, \qquad k \ge 1,$

where $K_n$ are the continuant polynomials defined in (4). We verify this by induction.

Base case ($k = 1$):

$M_1 = \begin{pmatrix}1 & 1 \ 1 & 0\end{pmatrix} \begin{pmatrix}x_1 & 1 \ 1 & 0\end{pmatrix} = \begin{pmatrix}1 \cdot x_1 + 1 \cdot 1 & 1 \cdot 1 + 1 \cdot 0 \ 1 \cdot x_1 + 0 \cdot 1 & 1 \cdot 1 + 0 \cdot 0\end{pmatrix} = \begin{pmatrix}x_1 + 1 & 1 \ x_1 & 1\end{pmatrix}.$

On the other hand, using the definition of continuants:

$K_2(x_1) = x_1 \cdot K_1(\text{empty}) + K_0(\text{empty}) = x_1 \cdot 1 + 1 = x_1 + 1,$

$K_1(\text{empty}) = K_1() = 1, \quad K_1(x_1) = x_1, \quad K_0() = 1.$

Hence

$M_1 = \begin{pmatrix}K_2(x_1) & K_1() \ K_1(x_1) & K_0()\end{pmatrix} = \begin{pmatrix}x_1 + 1 & 1 \ x_1 & 1\end{pmatrix},$

which agrees with the explicit product. The base case holds.

Inductive step: Assume

$M_{k-1} = \begin{pmatrix}K_k(x_1, \ldots, x_{k-1}) & K_{k-1}(x_1, \ldots, x_{k-2}) \ K_{k-1}(x_2, \ldots, x_{k-1}) & K_{k-2}(x_2, \ldots, x_{k-2})\end{pmatrix}.$

Multiply by $A_k = \begin{pmatrix}x_k & 1 \ 1 & 0\end{pmatrix}$:

$$ \begin{aligned} M_k &= M_{k-1} A_k \ &= \begin{pmatrix}K_k(x_1, \ldots, x_{k-1}) & K_{k-1}(x_1, \ldots, x_{k-2}) \ K_{k-1}(x_2, \ldots, x_{k-1}) & K_{k-2}(x_2, \ldots, x_{k-2})\end{pmatrix} \begin{pmatrix}x_k & 1 \ 1 & 0\end{pmatrix} \ &= \begin{pmatrix}K_k x_k + K_{k-1} & K_k \ K_{k-1} x_k + K_{k-2} & K_{k-1} \end{pmatrix}. \end{aligned} $$

By the recursive definition of continuants (4):

$K_{k+1}(x_1, \ldots, x_k) = x_k K_k(x_1, \ldots, x_{k-1}) + K_{k-1}(x_1, \ldots, x_{k-2}),$

$K_k(x_2, \ldots, x_k) = x_k K_{k-1}(x_2, \ldots, x_{k-1}) + K_{k-2}(x_2, \ldots, x_{k-2}).$

Hence

$M_k = \begin{pmatrix}K_{k+1}(x_1, \ldots, x_k) & K_k(x_1, \ldots, x_{k-1}) \ K_k(x_2, \ldots, x_k) & K_{k-1}(x_2, \ldots, x_{k-1})\end{pmatrix}.$

The inductive step is complete, proving the formula for all $k \ge 1$.

Finally, the desired product is

$\begin{pmatrix}1 & 1 \ 1 & 0\end{pmatrix} \begin{pmatrix}x_1 & 1 \ 1 & 0\end{pmatrix} \cdots \begin{pmatrix}x_n & 1 \ 1 & 0\end{pmatrix} = \begin{pmatrix}K_{n+1}(x_1, \ldots, x_n) & K_n(x_1, \ldots, x_{n-1}) \ K_n(x_2, \ldots, x_n) & K_{n-1}(x_2, \ldots, x_{n-1})\end{pmatrix}.$

This completes the solution. ∎