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αkk 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αkk 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).