TAOCP 4.5.2 Exercise 42

We are asked to evaluate the determinant D_n = \begin{vmatrix} \gcd(1,1) & \gcd(1,2) & \cdots & \gcd(1,n) \\ \gcd(2,1) & \gcd(2,2) & \cdots & \gcd(2,n) \\ \vdots & & & \vdots \\

taocpmathematicsalgorithmsvolume-2math-hard

Section 4.5.2: The Greatest Common Divisor

Exercise 42. [M30] Evaluate the determinant

$$\begin{vmatrix} \gcd(1,1) & \gcd(1,2) & \cdots & \gcd(1,n) \ \gcd(2,1) & \gcd(2,2) & \cdots & \gcd(2,n) \ \vdots & & & \vdots \ \gcd(n,1) & \gcd(n,2) & \cdots & \gcd(n,n) \end{vmatrix}$$

*4.5.3. Analysis of Euclid's Algorithm

The execution time of Euclid's algorithm depends on $T$, the number of times the division step A2 is performed. (See Algorithm 4.5.2A and Program 4.5.2A.) The quantity $T$ is also an important factor in the running time of other algorithms, such as the evaluation of functions satisfying a reciprocity formula (see Section 3.3.3). We shall see in this section that the mathematical analysis of this quantity $T$ is interesting and instructive.

Relation to continued fractions. Euclid's algorithm is intimately connected with continued fractions, which are expressions of the form

$$\frac{b_1}{a_1 + \dfrac{b_2}{a_2 + \dfrac{b_3}{a_3 + \dfrac{\cdots}{\displaystyle a_{n-1} + \frac{b_n}{a_n}}}}} = b_1/(a_1 + b_2/(a_2 + b_3/(\cdots(a_{n-1} + b_n/a_n)\cdots)))). \eqno(1)$$

Continued fractions have a beautiful theory that is the subject of several classic books, such as O. Perron, Die Lehre von den Kettenbrüchen, 3rd edition (Stuttgart: Teubner, 1954), 2 volumes; A. Khinchin, Continued Fractions, translated by Peter Wynn (Groningen: P. Noordhoff, 1963); and H. S. Wall, Analytic Theory

Verified: yes
Solve time: 17m06s

Setup

We are asked to evaluate the determinant

$$ D_n = \begin{vmatrix} \gcd(1,1) & \gcd(1,2) & \cdots & \gcd(1,n) \ \gcd(2,1) & \gcd(2,2) & \cdots & \gcd(2,n) \ \vdots & & & \vdots \ \gcd(n,1) & \gcd(n,2) & \cdots & \gcd(n,n) \end{vmatrix}. $$

Let $d_{ij} = \gcd(i,j)$. The problem is to compute

$$ D_n = \det(d_{ij})_{1 \le i,j \le n}. $$

We will use standard properties of the gcd function and the Möbius function $\mu(k)$, as introduced in Section 4.5.2 and Section 1.2.4. Specifically, we rely on the formula

$$ i = \sum_{d \mid i} \phi(d), \quad \text{or more generally} \quad d_{ij} = \sum_{k \mid \gcd(i,j)} \phi(k), $$

where $\phi$ is Euler's totient function. This allows the determinant to be expressed in a form suitable for factorization.

Solution

We start by expressing $d_{ij}$ using the identity

$$ \gcd(i,j) = \sum_{k \mid i, k \mid j} \phi(k) = \sum_{k \mid i, k \mid j} \phi(k). \eqno(1) $$

Define the $n \times n$ matrix $[d_{ij}]$ by $d_{ij} = \gcd(i,j)$. Let $U$ be the $n \times n$ matrix with entries

$$ u_{ik} = \begin{cases} 1, & k \mid i, \ 0, & \text{otherwise.} \end{cases} \eqno(2) $$

Let $\Phi = \text{diag}(\phi(1), \phi(2), \dots, \phi(n))$. Then by equation (1) we can write

$$ d_{ij} = \sum_{k=1}^n u_{ik} \phi(k) u_{jk}. \eqno(3) $$

In matrix notation,

$$ D = U , \Phi , U^\mathsf{T}. \eqno(4) $$

Since $U$ is lower-triangular with ones on the diagonal (each $i$ is divisible by $1,2,\dots,i$ but in the order given, the diagonal entries $u_{ii} = 1$), its determinant is $1$. Then

$$ \det(D) = \det(U , \Phi , U^\mathsf{T}) = (\det U)^2 \det \Phi = \det \Phi = \prod_{k=1}^n \phi(k). \eqno(5) $$

Hence the determinant evaluates to

$$ \boxed{\prod_{k=1}^n \phi(k)}. $$

This is the classical Smith determinant formula (H. J. S. Smith, 1876).

Verification

For small values of $n$, we check explicitly.

  • If $n=1$, the matrix is $[1]$, determinant $1 = \phi(1)$.
  • If $n=2$, the matrix is

$$ \begin{pmatrix} \gcd(1,1) & \gcd(1,2) \ \gcd(2,1) & \gcd(2,2) \end{pmatrix} = \begin{pmatrix} 1 & 1 \ 1 & 2 \end{pmatrix}, \quad \det = 2 - 1 = 1. $$

Also $\prod_{k=1}^2 \phi(k) = \phi(1) \cdot \phi(2) = 1 \cdot 1 = 1$.

  • If $n=3$, the matrix is

$$ \begin{pmatrix} 1 & 1 & 1 \ 1 & 2 & 1 \ 1 & 1 & 3 \end{pmatrix}, \quad \det = 1(2 \cdot 3 - 1 \cdot 1) - 1(1 \cdot 3 - 1 \cdot 1) + 1(1 \cdot 1 - 2 \cdot 1) = 5 - 2 - 1 = 2, $$

and $\prod_{k=1}^3 \phi(k) = 1 \cdot 1 \cdot 2 = 2$. The formula matches.

These checks confirm the general formula.

Notes

The same method applies if $\gcd(i,j)$ is replaced by any multiplicative function $f$; one obtains

$$ \det(f(\gcd(i,j))) = \prod_{k=1}^n (f * \mu)(k), $$

where $*$ denotes Dirichlet convolution and $\mu$ is the Möbius function. This generalization appears in Section 4.5.2 and is the basis for many identities in number theory.

This completes the proof.

∎