# Why do these polynomials split almost in the middle?

Start with a palindromic sequence of integers $$(a_0, a_1, \ldots, a_{n+1})$$, i.e. $$a_j=a_{n+1-j}$$, and put $$a_j:=0$$ for $$j<0$$ and $$j>n+1$$. You may readily guess that the choice of the binomial coefficients $$a_j=\binom{n+1}j$$ has been at the origin for this question.

So we consider the $$n \times n$$-matrix $$B$$ whose $$\left(i, j\right)$$-th entry is $$a_{2j-i}$$ for all $$i, j \in \left\{ 1, 2, \ldots, n \right\}$$.

E.g. for $$n=4$$ and the sequence $$(1,2,3,3,2,1)$$, this would be $$B = \left(\begin{array}{rrrrr} 2& 3& 1 & 0 \\ 1 & 3& 2& 0 \\ 0 & 2& 3 & 1 \\ 0 & 1 & 3& 2 \end{array}\right).$$

Now what about the eigenvalues of such a matrix? In the case of binomial coefficients, they turned out to be integers in the cited question, and more precisely $$2^1, 2^2, \ldots, 2^n$$. In the general case, one might expect the characteristic polynomial of $$B$$ to be irreducible, apart from the trivial right eigenvector $$(1,\dots,1)$$ with eigenvalue $$s:=\sum_{j=0}^{n/2} a_j$$ for even $$n$$. But I have found that it always splits into two (generally irreducible) factors of degrees $$\lfloor\frac {n+1}2\rfloor$$ and $$\lfloor\frac {n-1}2\rfloor$$. And of course I wonder why.

Moreover, it appears that the absolute terms of those two factoring polynomials have an integer ratio $$R$$, which is in fact just a linear combination of the $$a_j$$'s: $$R=\sum_{j\in\mathbb Z} (-1)^{j+1}a_{\lfloor\frac {n}2\rfloor+2j}.$$ This is about the easiest way to write this finite sum without having to distinguish between even and odd $$n$$. In fact, for odd $$n=2k+1$$, half of the terms cancel out by palindromicity, making this $$R=-a_k +2 a_{k-2}-2 a_{k-4}+2 a_{k-6}-+\cdots,$$ while for even $$n=2k$$, all the different $$a_j$$ (thus, say, $$a_0,...,a_k$$) occur with signs $$-++--++-\cdots$$, viz. $$R=-a_k + a_{k-1}+ a_{k-2}- a_{k-3}-++-\cdots.$$

Some examples for small $$n$$, writing the initial sequence as $$(a,b,c,b,a)$$ etc.: for $$n=3$$, we have $$P(x)=\Bigl[x-\color{blue}{b}\Bigr]\Bigl[x^2-(b+c)x+\color{blue}{b}\underbrace{(2a-c)}_R\Bigr]$$

For $$n=4$$, $$P(x)=\overbrace{\Bigl[x-(a+b+c)\Bigr]}^{\text{trivial}}\Bigl[x+\color{blue}{(a-b)}\Bigr]\Bigl[x^2-cx+\color{blue}{(a-b)}\underbrace{(a+b-c)}_R\Bigr]$$

For $$n=5$$, $$P(x)=\Bigl[x^2+(-a+b+c)x+\color{blue}{(-ab+bc-ad)}\Bigr]\cdot\\ \Bigl[x^3-(a+b+c+d)x^2+(ab-bc+bd+cd)x+\color{blue}{(-ab+bc-ad)}\underbrace{(2b-d)}_R\Bigr]$$

For $$n=6$$, $$P(x)=\overbrace{\Bigl[x-(a+b+c+d)\Bigr]}^{\text{trivial}}\cdot\Bigl[x^2 + (a - c)x + \color{blue}{(a^2-b^2 + bc-ad)}\Bigr]\cdot\\ \Bigl[x^3-(b+d)x^2+(b^2-c^2+cd-ab)x+\color{blue}{(a^2-b^2 + bc-ad)} \underbrace{(-a+b+c-d)}_R\Bigr]$$

As a by-product it follows that if the determinant of $$B$$ is divided by $$R$$ (or, for even $$n$$, by $$Rs$$), we remain with a square.

Sadly, there do not seem to exist matrices $$M_1$$ and $$M_2$$ of respective sizes $$\lfloor\frac {n+1}2\rfloor\times \lfloor\frac {n+1}2\rfloor$$ and $$\lfloor\frac {n-1}2\rfloor\times \lfloor\frac {n-1}2\rfloor$$ with entries depending in an "easy" (i.e. linear) way of the $$a_j$$ such that for a suitable matrix $$V$$ $$B=V^{-1}\pmatrix{M_1& 0\\ 0 & M_2}V\quad \text{ resp. (for even n)}\quad B=V^{-1}\pmatrix{s&0&0\\ 0 &M_1&0\\0& 0 & M_2}V.$$

So how to prove this reducibility of the characteristic polynomial and the conjectured ratio of the absolute terms?

• You are correct that I had a bug in my calculations. Corrected Sage code Mar 11 at 0:00
• There is a similar behaviour if the columns are shifted by $3$ instead of $2$. The entries $B_{i,j}=a_{3j-i}$ are now from a palindromic sequence of odd length $2n+3$. Sage code. For even $n$, both factors have the same coefficients in the $a_i$ up to some signs. For odd $n$, no integer quotient of CTs. Mar 13 at 20:04

I have found an answer for the reducibility part of the question. In fact, I found that any "palindromic matrix" $$M=((a_{i,j}))_{i,j\in\{1,..n\}}$$ (i.e. with 180° rotational symmetry $$a_{i,j}=a_{n+1-i,n+1-j}$$) has a splitting characteristic polynomial, and moreover, the suggested matrix decompositions do exist.
After all, this looks quite elementary, though it does not seem to be well-known (or not known at all?) Thanks go to Peter Taylor for the idea with the Sage code. Sage is so much more efficient than Pari/GP when it comes to factoring polynomials with more than about 4 variables, so I'd never have been able to spot the patterns with Pari. (And the zero entries in the original matrices, a special case of this, didn't help either.)

For even order $$n=2k$$, let's write $$M=\pmatrix{A&B^{\circ}\\ B &A^\circ}=M^\circ.$$ For odd order $$n=2k+1$$, let's write $$M=\pmatrix{A&v&B^{\circ}\\ w&c&w^{\leftarrow}\\ B &v^{\uparrow}&A^\circ}=M^\circ.$$

Here, $$A$$ and $$B$$ are general $$k\times k$$ matrices with integer entries, $$v$$ is a column vector of length $$k$$, $$w$$ is a row vector of length $$k$$, $$v^{\uparrow}$$ and $$w^{\leftarrow}$$ denote the vectors with mirrored entries, thus reflected vertically/horizontally, $$A^\circ={A^{\uparrow}}^{\leftarrow}={A^{\leftarrow}}^{\uparrow}$$ a matrix rotated by 180°, and $$c\in\mathbb Z$$ is the central entry. (Note that for the vectors, we could as well write $$v^\circ$$ and $$w^\circ$$.)

For even $$n=2k$$, define matrices $$M_1$$ and $$M_2$$ of size $$k$$ simply by $$M_1:= A-B^{\uparrow},\quad M_2:= A+B^{\uparrow}.$$ For odd $$n=2k+1$$, define matrices $$M_1$$ and $$M_2$$ of respective sizes $$k$$ and $$k+1$$ by $$M_1:= A-B^{\uparrow},\quad M_2:= \pmatrix{A+B^{\uparrow}&2v\\ w&c}.$$ Then in both cases, the characteristic polynomial splits as $$\chi_M(x)=\chi_{M_1}(x)\chi_{M_2}(x)$$.
Here is some Sage code, where each matrix is followed by its charpoly.

Note that if we replace $$M$$ by $$M^T$$, then $$M_1$$ is just transposed, but $$M_2$$ becomes for odd $$n$$ a different matrix $$\pmatrix{A^T+(B^T)^{\leftarrow}&2w^T\\ v^T&c}=\pmatrix{A+B^{\uparrow}&v\\ 2w&c}^T$$ with the same characteristic polynomial.

Coming back to the actual question, it remains to prove that $$\frac{\det M_2}{\det M_1}$$ has the conjectured form (removing the factor $$\sum a_i$$ for even $$n$$). For even $$n$$, I now think that the form $$B=V^{-1}\pmatrix{s&0&0\\ 0 &M_1&0\\0& 0 & M_2}V$$ does also exist, but I have a hard time finding the general form of $$M_1$$.

The first of the characteristic polynomials are $$p=x+a_0-a_1 \Longrightarrow M_1=(-a_0 + a_1)\quad\ \ \ \quad\\ p=x^2 + (a_0 - a_2)x + a_0^2 - a_1^2 + a_1a_2- a_0a_3 \\ \Longrightarrow M_1=\pmatrix{ -a_0 + a_1 &a_0\\ -a_0 + a_1 - a_2 + a_3 & -a_1 + a_2 }$$ (up to transposition), so far almost trivial. But the next one is already unfeasible to do by hand: $$p=x^3 - a_3x^2 + \bigl[(a_0-a_2) (a_2-a_3 ) + ( a_0-a_1) ( a_4- a_3 )\bigr]x\\ - a_0^3 + a_0^2(a_1 + a_4)+a_0(a_1^2+ a_3^2 - a_2a_3 - 2a_1a_4)- a_1^3 + a_1^2a_4+ a_1a_2^2 - a_1a_2a_3.$$ I have asked another question of independent interest about how to recover such a matrix from its characteristic polynomial.