### 60th Putnam 1999

Problem B5

n is an integer greater than 2 and φ = 2π/n. A is the n x n matrix (aij), where aij = cos(i + j)φ for i ≠ j, 1 + cos2jφ for i = j. Find det A.

Solution

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 (bij) with bij = cos(i + j)φ. Then the eigenvalues λ1, λ2, ... , λn of B satisfy the characteristic polynomial det(B - λ I) = 0. Hence det A = Pi + 1).

For r = 1, 2, 3, ... , n, let vr be the column vector (eiφr, e2iφr, e3iφr, ... , eniφr). Using cos sφ = (eisφ + e-isφ)/2, we have that 2Bvr is the column vector with jth element ( eiφ(j+1+r) + eiφ(j+2+2r) + eiφ(j+3+3r) + ... + eiφ(j+n+nr) ) + ( eiφ(-j-1+r) + eiφ(-j-2+2r) + eiφ(-j-3+3r) + ... + eiφ(-j-n+nr) ) = eiφj(α + α2 + ... + αn) + e-iφj(β + β2 + ... + βn), where α = eiφ(r+1) and β = eiφ(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 2Bvr = 0, and so vr is an eigenvector with eigenvalue 0. If r = 1, then β = 1, and so α + α2 + ... + αn = 0, β + β2 + ... + βn = n. Hence Bv1 = n/2 vn-1. Similarly, if r = n - 1, then α = 1, and so α + α2 + ... + αn = n, β + β2 + ... + βn = 0. Hence Bvn-1 = n/2 v1. So (v1 + vn-1)/2 [which is the column vector (cos φ, cos 2φ, cos 3φ, ... , cos nφ) ] is an eigenvector with eigenvalue n/2, and (v1 - vn-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 vr is a Vandermonde determinant, whose value (using the well-known formula) is ∏r>s(eirφ - eisφ) ≠ 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) = -n2/4 + 1.