60th Putnam 1999 Problem B5 n is an integer greater than 2 and φ = 2π/n. A is the n x n matrix (a ij ), where a ij = cos(i + j)φ for i ≠ j, 1 + cos2jφ for i = j. Find det A.
A direct approach does not work (at least, I could not get it to work). However, if we let B be the n x n matrix (b ij ) with b ij = cos(i + j)φ. Then the eigenvalues λ 1 , λ 2 , ... , λ n of B satisfy the characteristic polynomial det(B - λ I) = 0. Hence det A = P (λ i + 1). For r = 1, 2, 3, ... , n, let v r be the column vector (e iφr , e 2iφr , e 3iφr , ... , e niφr ). Using cos sφ = (e isφ + e - isφ )/2, we have that 2Bv r is the column vector with jth element ( e iφ(j+1+r) + e iφ(j+2+2r) + e iφ(j+3+3r) + ... + e iφ(j+n+nr) ) + ( e iφ(-j-1+r) + e iφ(-j-2+2r) + e iφ(-j-3+3r) + ... + e iφ(-j-n+nr) ) = e iφj (α + α 2 + ... + α n ) + e -iφj (β + β 2 + ... + β n ), where α = e iφ(r+1) and β = e iφ(r-1) . If r is not 1 or n - 1, then α and β are nth roots of 1 other than 1 and hence α + α 2 + ... + α n = β + β 2 + ... + β n = 0, so 2Bv r = 0, and so v r is an eigenvector with eigenvalue 0. If r = 1, then β = 1, and so α + α 2 + ... + α n = 0, β + β 2 + ... + β n = n. Hence Bv 1 = n/2 v n-1 . Similarly, if r = n - 1, then α = 1, and so α + α 2 + ... + α n = n, β + β 2 + ... + β n = 0. Hence Bv n-1 = n/2 v 1 . So (v 1 + v n-1 )/2 [which is the column vector (cos φ, cos 2φ, cos 3φ, ... , cos nφ) ] is an eigenvector with eigenvalue n/2, and (v 1 - v n-1 )/2i [which is the column vector (sin φ, sin 2φ, ... , sin nφ) ] is an eigenvector with eigenvalue -n/2. Finally, notice that the determinant with columns v r is a Vandermonde determinant, whose value (using the well-known formula) is ∏ r>s (e irφ - e isφ ) ≠ 0. So we have found n - 2 linearly independent eigenvectors for the eigenvalue 0, and hence 0 is an eigenvalue of multiplicity n - 2 (and there are no other eigenvalues). Thus det A = ∏(λ i + 1) = (1 + n/2)(1 - n/2) = -n 2 /4 + 1. 60th Putnam 1999 © John Scholes jscholes@kalva.demon.co.uk 14 Dec 1999