Problem 11179

(American Mathematical Monthly, Vol.112, October 2005) Proposed by D. Beckwith (USA).

For positive integersi and j let

mi,j=

−1 if j | (i + 1) 0 if j 6 | (i + 1) ,

and whenn ≥ 2 let Mn be the(n − 1) × (n − 1) matrix with (i, j)-entry mi,j. Evaluatedet(Mn).

Solution proposed by Roberto Tauraso, Dipartimento di Matematica, Universit`a di Roma “Tor Vergata”, via della Ricerca Scientifica, 00133 Roma, Italy.

We show that for n ≥ 2 the determinant of Mn is equal to the value of the M¨obius function at n:

det(Mn) = µ(n) =

0 if n has one or more repeated prime factors
(−1)^{r} if n is the product of r distinct prime factors .
We will use the Iverson bracket notation

[proposition] =

1 if the proposition is true 0 if the proposition is false . Let n =Qr

k=1p^{α}_{k}^{k} be the prime factorization of n ≥ 2 then
[j = n] =

r

Y

k=1

([j|n] − [j|n/pk])

because if j is a proper divisor of n then at least for one prime pk, p^{α}_{k}^{k} does not divide j and therefore
the factor [j|n] − [j|n/pk] = 1 − 1 = 0.

On the other hand, by expanding the product, since [j|a] · [j|b] = [j| gcd(a, b)], then [j = n] = X

I⊆{1,...,r}

(−1)^{|I|}· [j|n/Y

k∈I

pk]

where the sum is taken over all subsets of the set {1, . . . , r}.

Now we modify the last row of Mn by adding a proper linear combination of the other rows. This operation does not change the determinant of Mn, but it will help us to compute it.

If n is not the product of r distinct prime factors then we set for j = 1, . . . , n − 1
m^{′}_{(n−1),j} := X

I⊆{1,...,r}

(−1)^{|I|}· m(n/Q

k∈Ipk−1),j

= − X

I⊆{1,...,r}

(−1)^{|I|}· [j|n/Y

k∈I

pk] = −[j = n] = 0.

Therefore the new last row is identically zero and det(Mn) = 0 = µ(n).

If n is the product of r distinct prime factors, that is n =Qr

k=1pk, then we set for j = 1, . . . , n − 1
m^{′}_{(n−1),j} := X

I({1,...,r}

(−1)^{|I|}· m(n/Q

k∈Ipk−1),j

= − X

I({1,...,r}

(−1)^{|I|}· [j|n/Y

k∈I

pk] = −[j = n] + (−1)^{r}· [j|n/

r

Y

k=1

pk]

= −[j = n] + (−1)^{r}· [j|1] = (−1)^{r}· [j = 1].

Hence the entries of the new last row are all zero but one, that is m^{′}_{(n−1),1}= (−1)^{r}.
In order to find the determinant we expand the computation along the last row:

det(Mn) = (−1)^{(n−1)+1}· m^{′}_{(n−1),1}· det(Tn)

where Tn is the (n − 2) × (n − 2) matrix obtained by eliminating the last row and the first column from the matrix Mn. The main diagonal entries of Tn are mi,i+1= −[i|i] = −1 for i = 1, . . . , n − 2.

The entries above the main diagonal of Tn are mi,j= −[j|i + 1] = 0 because j > i + 1. Hence Tn is
a lower-triangular matrix and det(Tn) = (−1)^{n−2}. Finally

det(Mn) = (−1)^{n}· (−1)^{r}· (−1)^{n−2}= (−1)^{r}= µ(n).