uniolympiads Ελληνικά

IMC 2017, Day 2, Problem 8

Define the sequence A1,A2,…A_1, A_2, \dots of matrices by the following recurrence:

A1=(0110),An+1=(AnI2nI2nAn)(n=1,2,… )A_1 = \begin{pmatrix} 0 & 1 \\ 1 & 0 \end{pmatrix}, \quad A_{n+1} = \begin{pmatrix} A_n & I_{2^n} \\ I_{2^n} & A_n \end{pmatrix} \quad (n = 1, 2, \dots)

where ImI_m is the m×mm \times m identity matrix.

Prove that AnA_n has n+1n + 1 distinct integer eigenvalues λ0<λ1<⋯<λn\lambda_0 < \lambda_1 < \dots < \lambda_n with multiplicities (n0),(n1),…,(nn)\binom{n}{0}, \binom{n}{1}, \dots, \binom{n}{n}, respectively.

Original from the official PDFDene the sequence A 1 , A 2 , . . . of matrices by the following recurrence: 0 1 A 1 = , 1 0 A n+1 = A n I 2 n I 2 n A n (n = 1, 2, . . .) where I m is the m × m identity matrix. Prove that n A n has n + 1 distinct integer eigenvalues λ 0 < λ 1 < . . . < λ n with multiplicities n n , 1 , . . . , n , respectively. 0

This transcription was compared symbol by symbol with the original, but not yet by a person.

Time on this problem 0:00

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∈Nn\in\mathbb{N}, matrix AnA_n is symmetric 2n×2n2^n\times 2^n matrix with elements from the set {0,1}\{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)A_n = I_{2^{n-1}}\otimes A_1 + A_{n-1}\otimes I_2, \tag{1}
where ⊗\otimes is binary operation over the space of matrices, defined for arbitrary B∈Rn×pB\in\mathbb{R}^{n\times p} and C∈Rm×sC\in\mathbb{R}^{m\times s} as
B⊗C:=[b11Cb12C…b1pCb21Cb22C…b2pC⋮bn1Cb12C…bnpC]nm×ps.B\otimes C := \begin{bmatrix} b_{11}C & b_{12}C & \ldots & b_{1p}C \\ b_{21}C & b_{22}C & \ldots & b_{2p}C \\ \vdots & & & \\ b_{n1}C & b_{12}C & \ldots & b_{np}C \end{bmatrix}_{nm\times ps}.

Lemma 1. If B∈Rn×nB\in\mathbb{R}^{n\times n} has eigenvalues λi\lambda_i, i=1,…,ni = 1,\ldots,n and C∈Rm×mC\in\mathbb{R}^{m\times m} has eigenvalues μj\mu_j, j=1,…,mj = 1,\ldots,m, then B⊗CB\otimes C has eigenvalues λiμj\lambda_i\mu_j, i=1,…,ni = 1,\ldots,n, j=1,…,mj = 1,\ldots,m. If BB and CC are diagonalizable, then A⊗BA\otimes B has eigenvectors yi⊗zjy_i\otimes z_j, with (λi,yi)(\lambda_i,y_i) and (μj,zj)(\mu_j,z_j) being eigenpairs of BB and CC, respectively.

Proof 1. Let (λ,y)(\lambda,y) be an eigenpair of BB and (μ,z)(\mu,z) an eigenpar of CC. Then

(B⊗C)(y⊗z)=By⊗Cz=λy⊗μz=λμ(y⊗z).(B\otimes C)(y\otimes z) = By\otimes Cz = \lambda y\otimes\mu z = \lambda\mu(y\otimes z).

If we take (λ,y)(\lambda,y) to be an eigenpair of A1A_1 and (μ,z)(\mu,z) to be an eigenpair of An−1A_{n-1}, then from (1) and Lemma 1 we get

An(z⊗y)=(I2n−1⊗A1+An−1⊗I2)(z⊗y)=(I2n−1⊗A1)(z⊗y)+(An−1⊗I2)(z⊗y)=(λ+μ)(z⊗y).\begin{aligned} A_n(z\otimes y) &= (I_{2^{n-1}}\otimes A_1 + A_{n-1}\otimes I_2)(z\otimes y) \\ &= (I_{2^{n-1}}\otimes A_1)(z\otimes y) + (A_{n-1}\otimes I_2)(z\otimes y) \\ &= (\lambda+\mu)(z\otimes y). \end{aligned}

So the entire spectrum of AnA_n can be obtained from eigenvalues of An−1A_{n-1} and A1A_1: just sum up each eigenvalue of An−1A_{n-1} with each eigenvalue of A1A_1. Since the spectrum of A1A_1 is σ(A1)={−1,1}\sigma(A_1) = \{-1,1\}, we get

σ(A2)={−1+(−1),−1+1,1+(−1),1+1}={−2,0(2),2}σ(A3)={−1+(−2),−1+0,−1+0,−1+2,1+(−2),1+0,1+0,1+2}={−3,(−1)(3),1(3),3}σ(A4)={−1+(−3),−1+(−1(3)),−1+1(3),−1+3,1+(−3),1+(−1(3)),1+1(3),1+3}={−4,(−2)(4),0(3),2(4),4}.\begin{aligned} \sigma(A_2) &= \{-1+(-1), -1+1, 1+(-1), 1+1\} = \{-2, 0^{(2)}, 2\} \\ \sigma(A_3) &= \{-1+(-2), -1+0, -1+0, -1+2, 1+(-2), 1+0, 1+0, 1+2\} = \{-3, (-1)^{(3)}, 1^{(3)}, 3\} \\ \sigma(A_4) &= \{-1+(-3), -1+(-1^{(3)}), -1+1^{(3)}, -1+3, 1+(-3), 1+(-1^{(3)}), 1+1^{(3)}, 1+3\} \\ &= \{-4, (-2)^{(4)}, 0^{(3)}, 2^{(4)}, 4\}. \end{aligned}

Inductively, AnA_n has n+1n+1 distinct integer eigenvalues −n,−n+2,−n+4,…,n−4,n−2,n-n, -n+2, -n+4, \ldots, n-4, n-2, n with multiplicities (n0),(n1),(n2),…,(nn)\binom{n}{0}, \binom{n}{1}, \binom{n}{2}, \ldots, \binom{n}{n}, 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.

How did it go?