Define the sequence A1,A2,… of matrices by the following recurrence:
A1=(0110),An+1=(AnI2nI2nAn)(n=1,2,…)
where Im is the m×m identity matrix.
Prove that An has n+1 distinct integer eigenvalues λ0<λ1<⋯<λn with multiplicities (0n),(1n),…,(nn), respectively.
Original from the official PDF
This transcription was compared symbol by symbol with the original, but not yet by a person.
Time on this problem
Work for at least 45 minutes before opening the solution.
Official solution
(Proposed by Snježana Majstorović, University of J. J. Strossmayer in Osijek, Croatia)
Solution. For each n∈N, matrix An is symmetric 2n×2n matrix with elements from the set {0,1}, so that all elements on the main diagonal are equal to zero. We can write
An=I2n−1⊗A1+An−1⊗I2,(1)
where ⊗ is binary operation over the space of matrices, defined for arbitrary B∈Rn×p and C∈Rm×s as
Lemma 1. If B∈Rn×n has eigenvalues λi, i=1,…,n and C∈Rm×m has eigenvalues μj, j=1,…,m, then B⊗C has eigenvalues λiμj, i=1,…,n, j=1,…,m. If B and C are diagonalizable, then A⊗B has eigenvectors yi⊗zj, with (λi,yi) and (μj,zj) being eigenpairs of B and C, respectively.
Proof 1. Let (λ,y) be an eigenpair of B and (μ,z) an eigenpar of C. Then
(B⊗C)(y⊗z)=By⊗Cz=λy⊗μz=λμ(y⊗z).
If we take (λ,y) to be an eigenpair of A1 and (μ,z) to be an eigenpair of An−1, then from (1) and Lemma 1 we get
So the entire spectrum of An can be obtained from eigenvalues of An−1 and A1: just sum up each eigenvalue of An−1 with each eigenvalue of A1. Since the spectrum of A1 is σ(A1)={−1,1}, we get
Inductively, An has n+1 distinct integer eigenvalues −n,−n+2,−n+4,…,n−4,n−2,n with multiplicities (0n),(1n),(2n),…,(nn), respectively.
Transcribed from the official solutions, page 3. This transcription has not been checked a second time; if in doubt, look at the original.
Archive problem: the statement is the official text (transcribed, with the original above). Subject classification and difficulty were estimated automatically; hints and a worked solution are added over time.