# Product of binary matrices with binary eigenvalues

Consider two binary matrices with obvious patterns: $$C= \begin{bmatrix} 1 &0 &0 &0 &0 &0 &0\\ 1 &0 &0 &0 &0 &0 &0\\ 0 &1 &0 &0 &0 &0 &0\\ 0 &1 &0 &0 &0 &0 &0\\ 0 &0 &1 &0 &0 &0 &0\\ 0 &0 &1 &0 &0 &0 &0\\ 0 &0 &0 &1 &0 &0 &0 \end{bmatrix}$$ and $$T= \begin{bmatrix} 1 &1 &0 &0 &0 &0 &0\\ 0 &1 &1 &0 &0 &0 &0\\ 0 &0 &1 &1 &0 &0 &0\\ 0 &0 &0 &1 &1 &0 &0\\ 0 &0 &0 &0 &1 &1 &0\\ 0 &0 &0 &0 &0 &1 &1\\ 0 &0 &0 &0 &0 &0 &1 \end{bmatrix}$$

The eigenvalues of the matrices $$T^n C,n=0,1,2,3$$ are zeros and consecutive powers of $$2$$ equal to $$0,1,2,4$$. I'd like to have a proof of the generalization of this fact for matrices of larger size with the same patterns.

Note, the entries of $$T^n C$$ in the left upper corner are zeros and binomial coefficients for the power $$n+1$$.

A motivation for this question is in Binary eigenvalues matrices and continued fractions

Some thoughts:

Note that $T = I + N$, where $I$ is the identity matrix and $$N = \pmatrix{0&1\\&0&1\\&&0&1\\&&&0&1\\&&&&0&1\\&&&&&0&1\\&&&&&&0}$$ Notably, $N^7 = 0$. Because $NI = IN$, we can compute $T^n = (I + N)^n$ by binomial expansion. That is, we have $$T^n = \binom n0 I + \binom n1 N + \cdots + \binom n6 N^6$$ We can verify that $T^n$ is therefore the upper triangular Toeplitz matrix for which, in the notation of the linked wiki page, we have $a_{-k} = \binom nk$ whenever $0 \leq k \leq n$ and all other entries are $0$.

With that, we may compute $$T^n C = \pmatrix{\binom n0 + \binom n1 & \binom n2 + \binom n3 & \binom n4 + \binom n5 & \binom n6 &0&0&0\\ \binom n0 & \binom n1 + \binom n2 & \binom n3 + \binom n4 & \binom n5 & 0&0&0\\ 0 & \binom n0 + \binom n1 & \binom n2 + \binom n3 & \binom n4 & 0&0&0\\ 0 & \binom n0 & \binom n1 + \binom n2 & \binom n3 & 0&0&0\\ 0 & 0 & \binom n0 + \binom n1 & \binom n2 & 0&0&0\\ 0 & 0 & \binom n0 & \binom n1 & 0&0&0\\ 0 & 0 & 0 & \binom n0 & 0&0&0\\}$$

• Note that the characteristic polynomial of $T^n C$ does not factor into linear terms for $n = 4$. I suspect that for $N \times N$-matrices, we only should expect powers of $2$ and zeros for $n \leq \left\lfloor N/2 \right\rfloor$. – darij grinberg Aug 18 '18 at 21:31
• An approach that seems promising is to compute the characteristic polynomial of $T^n C$ as $\det \left(X I_N - T^n C\right)$. The matrix $X I_N - T^n C$ is block-triangular, so we only need to find the determinant of its northwestern $4\times 4$-block. The corresponding block of $T^n C$ has $\left(i, j\right)$-th entry $\dbinom{n}{2j-i} + \dbinom{n}{2j-i-1} = \dbinom{n+1}{2j-i}$; I recall such a matrix appear in the work of Christian Krattenthaler, possibly even on MathOverflow. – darij grinberg Aug 18 '18 at 21:41
• Note that the only matrices we need to study are the $n \times n$-matrices $B_n$ whose $\left(i,j\right)$-th entry is $\dbinom{n+1}{2j-i}$ for all $i, j \in \left\{1,2,\ldots,n\right\}$. Once we know the characteristic polynomial of this $B_n$ (which I conjecture to be $\left(X-2^1\right)\left(X-2^2\right)\cdots\left(X-2^n\right)$), we'll obtain those of $T^n C$ for all $N \geq 2n$ using their block-triangular structure. Note that the product of the eigenvalues reminds me of the Aztec diamond. – darij grinberg Aug 18 '18 at 23:05
• Okay, it is definitely true that $\det\left(B_n\right) = 2^{1+2+\cdots+n}$ (so the product of the eigenvalues is correct). This follows from considering $B_n$ as the matrix in the Jacobi-Trudi formula for the skew Schur polynomial $s_{\left(n,n,\ldots,n\right) / \left(n-1,n-2,\ldots,1,0\right)}\left(1,1,\ldots,1\right)$ in $n+1$ variables all set to $1$ (written in terms of the elementary symmetric functions). But this is probably a dead end; I have never heard anything about characteristic polynomials of Jacobi-Trudi matrices. – darij grinberg Aug 18 '18 at 23:17
• Okay, the first eigenvalue ($2$) stands: Let $v_n$ be the column vector whose $i$-th entry (for $i = 1, 2, \ldots, n$) is $\left(-1\right)^{i-1} \dbinom{n-1}{i-1}$. Then, $B_n v = 2 v$. The other eigenvectors look less simple, however. – darij grinberg Aug 18 '18 at 23:51

The left upper block of the matrix $T^n C$ can be conjugated to upper triangular one with the eigenvalues on diagonal by Pascal triangle matrix.