International Mathematics Competition
for University Students
2017

IMC2017: Day 2, Problem 8

8. Define the sequence $A_1,A_2,\ldots$ of matrices by the following recurrence: $$ 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,\ldots) $$ where $I_m$ is the $m\times m$ identity matrix.

Prove that $A_n$ has $n+1$ distinct integer eigenvalues $\lambda_0< \lambda_1<\ldots <\lambda_n$ with multiplicities $\binom{n}{0},\binom{n}{1},\ldots,\binom{n}{n}$, respectively.

Proposed by: Snježana Majstorović, University of J. J. Strossmayer in Osijek

Solution. For each $n\in\mathbb{N}$, the matrix $A_n$ is a symmetric $2^n\times 2^n$ matrix with entries from the set $\{0,1\}$, so that all elements in the main diagonal are equal to zero. We can write $$ A_n=I_{2^{n-1}}\otimes A_1+A_{n-1}\otimes I_2, \qquad\qquad(1) $$ where $\otimes$ is a binary operation over the space of matrices, defined for arbitrary $B\in \mathbb{R}^{n\times p}$ and $C\in\mathbb{R}^{m\times s}$ as $$ B\otimes C:=\left[\begin{array}{cccc} 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_{n2} C & \ldots & b_{np} C\\ \end{array}\right]_{nm\times ps}. $$

Lemma. If $B\in \mathbb{R}^{n\times n}$ has eigenvalues $\lambda_i$, $i=1,\ldots,n$ and $C\in\mathbb{R}^{m\times m}$ has eigenvalues $\mu_j$, $j=1,\ldots,m$, then $B\otimes C$ has eigenvalues $\lambda_i\mu_j$, $i=1,\ldots,n$, $j=1,\ldots,m$. If $B$ and $C$ are diagonalizable, then $B\otimes C$ has eigenvectors $y_i\otimes z_j$, with $(\lambda_i,y_i)$ and $(\mu_j,z_j)$ being eigenpairs of $B$ and $C$, respectively.

Pproof. Let $(\lambda,y)$ and $(\mu,z)$ be eigenpairs of $B$ and $C$, respectively, where $\lambda,\mu\in \mathbb{R}$ and $y,z\in\mathbb{R}^n$. Then $$(B\otimes C)(y\otimes z)=By\otimes Cz=\lambda y\otimes \mu z=\lambda \mu (y\otimes z). \qquad\qquad\Box $$

~

If we choose $(\lambda,y)$ to be an eigenpair of $A_1$ and $(\mu,z)$ to be an eigenpair of $A_{n-1}$, then from (1) and the Lemma we get \begin{eqnarray*} 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{eqnarray*} So, the entire spectrum of $A_n$ can be obtained from the eigenvalues of $A_{n-1}$ and $A_1$: we calculate the sum of each eigenvalue of $A_{n-1}$ with each eigenvalue $A_1$. Since the spectrum of $A_1$ is $\sigma(A_1)=\{-1,1\}$, we get \begin{eqnarray*} \sigma(A_2)&=& \{-1+(-1), -1+1, 1+(-1), 1+1\}=\{-2,0^{(2)},2\} \end{eqnarray*} Let us assume that $A_{n-1}$ has eigenvalues $$\,\,-(n-1),-(n-1)+2,-(n-1)+4,\ldots,(n-1)-4,(n-1)-2,n-1\,\,$$ with multiplicities ${n-1\choose 0}, {n-1\choose 1},{n-1\choose 2},\ldots, {n-1\choose n-1}$, respectively. Then, the eigenvalues of $A_n$ are $$\,\,-(n-1)+1,-(n-1)+2+1,-(n-1)+4+1,\ldots,(n-1)-4+1,(n-1)-2+1,n-1+1\,\,$$ with multiplicities ${n-1\choose 0}, {n-1\choose 1},{n-1\choose 2},\ldots, {n-1\choose n-1}$, respectively, and $$\,\,-(n-1)-1,-(n-1)+2-1,-(n-1)+4-1,\ldots,(n-1)-4-1,(n-1)-2-1,n-1-1\,\,$$ with multiplicities ${n-1\choose 0}, {n-1\choose 1},{n-1\choose 2},\ldots, {n-1\choose n-1}$, respectively. By a simple calculation we can conclude that $A_n$ has $n+1$ distinct integer eigenvalues $\,\,-n,-n+2,-n+4,\ldots,n-4,n-2,n\,\,$ with multiplicities ${n\choose 0}, {n\choose 1},{n\choose 2},\ldots, {n\choose n}$, respectively.

Discussion on ArtOfProblemSolving.com