# Smith’s determinant

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

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. Francisco

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. Francisco, thanks. I fixed the error.

3. 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.)