• Non ci sono risultati.

# 0 if n has one or more repeated prime factors (−1)r if n is the product of r distinct prime factors

N/A
N/A
Protected

Condividi "0 if n has one or more repeated prime factors (−1)r if n is the product of r distinct prime factors "

Copied!
2
0
0

Testo completo

(1)

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

(2)

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



Riferimenti

Documenti correlati

Muir’s book A Treatise on the Theory of

Since we are comparing two polynomials, it follows that the identity holds for all x

Proposed by Olivier Bernardi (USA), Thaynara Arielly de Lima (Brazil), and Richard Stanley (USA).. Let S 2n denote the symmetric group of all permutations

Therefore the product of the absolute values of the roots of one of the polynomials g and h is equal

[r]

Solution proposed by Roberto Tauraso, Dipartimento di Matematica, Universit`a di Firenze, viale Morgagni 67/A, 50134 Firenze, Italy.. We denote by σ(n) the sum of the divisors of

The mathematical representations characterized by the smallest number of nonzero parameters are called canonical forms.. • The most interesting canonical forms are

LOWER PRICE OF GOOD 1 CAUSES A LOWER MONEY INCOME.. MONEY INCOME CHANGE HAS THE SIGN