Putnam 99/B5 solution

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.

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 (b_ij) with b_ij = cos(i + j)φ. Then the eigenvalues λ₁, λ₂, ... , λ_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(α + α² + ... + αⁿ) + e^-iφj(β + β² + ... + βⁿ), 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 α + α² + ... + αⁿ = β + β² + ... + βⁿ = 0, so 2Bv_r = 0, and so v_r is an eigenvector with eigenvalue 0. If r = 1, then β = 1, and so α + α² + ... + αⁿ = 0, β + β² + ... + βⁿ = n. Hence Bv₁ = n/2 v_n-1. Similarly, if r = n - 1, then α = 1, and so α + α² + ... + αⁿ = n, β + β² + ... + βⁿ = 0. Hence Bv_n-1 = n/2 v₁. So (v₁ + 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₁ - 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²/4 + 1.

60th Putnam 1999