Smith’s determinant

Here’s a curious identity I ran across while browsing Knuth’s magnum opus.

\[\left| \begin{array}{llll} \gcd(1,1) & \gcd(1,2) & \ldots & \gcd(1, n) \\ \gcd(2,1) & \gcd(2,2) & \ldots & \gcd(2, n) \\ \vdots & \vdots & & \vdots \\ \gcd(n,1) & \gcd(n,2) & \ldots & \gcd(n, n) \end{array}\right| = \varphi(1) \varphi(2) \cdots \varphi(n) \]

Here gcd(i, j) is the greatest common divisor of i and j, and φ(n) is Euler’s phi (or totient) function, the number of positive integers less than or equal to n and relatively prime to n.

The more general version of Smith’s determinant replaces gcd(i, j) above with f( gcd(i, j) ) for an arbitrary function f.

As a hint at a proof, you can do column operations on the matrix to obtain a triangular matrix with φ(i) in the ith spot along the diagonal.

Source: TAOCP vol 2, section 4.5.2, problem 42.

3 thoughts on “Smith’s determinant

  1. The first two elements in the second row are equal that the two ones in the first row. I think they would be gcd(2,1) and gcd(2,2), wouldn’t they?

    Sorry about my poor English.

  2. Cute fact (proved by Smith in the same paper as the identity itself): the same identity holds if instead of {1,2,…,n} we use any set of positive integers with the property that all factors of elements of the set are themselves elements of the set.

    (The same proof by doing column-ops proves this generalization with no extra work.)

Leave a Reply

Your email address will not be published. Required fields are marked *