3
$\begingroup$

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

$\endgroup$
2
$\begingroup$

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\\} $$

$\endgroup$
  • 1
    $\begingroup$ 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$. $\endgroup$ – darij grinberg Aug 18 '18 at 21:31
  • 1
    $\begingroup$ 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. $\endgroup$ – darij grinberg Aug 18 '18 at 21:41
  • 1
    $\begingroup$ 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. $\endgroup$ – darij grinberg Aug 18 '18 at 23:05
  • 1
    $\begingroup$ 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. $\endgroup$ – darij grinberg Aug 18 '18 at 23:17
  • 1
    $\begingroup$ 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. $\endgroup$ – darij grinberg Aug 18 '18 at 23:51
0
$\begingroup$

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.

@Suvrit https://mathoverflow.net/questions/258284/is-the-matrix-left2m-choose-2j-i-right-i-j-12m-1-nonsingular

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.