Eulerian polynomial conjecture for the matrices $N_k$

The characteristic and minimal polynomials of the Pascal-difference matrix

Let $k\ge 1$, and work over a field $K$ of characteristic zero. Set

$$N=N_k=\left[\binom{k}{j}-\binom{i}{j}\right]_{0\le i,j\le k},$$

where $\binom{i}{j}=0$ for $j>i$. Define the two Eulerian normalizations by

$$\begin{aligned} A_k(t)&=\sum_{\sigma\in S_k}t^{\operatorname{des}(\sigma)},\\ E_k(t)&=tA_k(t). \end{aligned}$$

Here $\operatorname{des}(\sigma)$ is the number of indices $i<k$ with $\sigma_i>\sigma_{i+1}$. We prove

$$\begin{aligned} \pi_N(t)&=\chi_N(t)\\ &=(-1)^{k+1}t^2A_k(-t)\\ &=(-1)^k tE_k(-t). \end{aligned} \tag{1}$$

This is Hivert–Pilaud, Conjecture 4.36. Their arXiv version 2 uses $A_k$ in Definition 2.31, whereas Definition 2.30 of the author manuscript uses the shifted polynomial $E_k$. Thus the two displayed forms in (1) express the same identity. The proof uses the classical Eulerian generating function, Pascal's binomial identity, and the rank-one determinant lemma.

1. A rank-one perturbation of the Pascal matrix

Let $P=[\binom{i}{j}]_{0\le i,j\le k}$, let $u$ be the column vector whose entries are all $1$, and let $b$ be the column vector with $b_j=\binom{k}{j}$. Then

$$N=ub^{\mathsf T}-P. \tag{2}$$

For every integer $m\ge0$ and every $0\le i\le k$, the binomial theorem gives

$$(P^mu)_i=(m+1)^i. \tag{3}$$

Indeed, the assertion holds for $m=0$, and multiplication by $P$ replaces $(m+1)^i$ by

$$\sum_{j=0}^i\binom{i}{j}(m+1)^j=(m+2)^i.$$

In particular,

$$\begin{aligned} b^{\mathsf T}P^mu &=\sum_{i=0}^k\binom{k}{i}(m+1)^i\\ &=(m+2)^k. \end{aligned} \tag{4}$$

2. The characteristic polynomial

All power series in this section are formal, in $K[[z]]$; no convergence assumption is needed. Since $I+zP$ has invertible constant term, its inverse is

$$(I+zP)^{-1}=\sum_{m\ge0}(-z)^mP^m.$$

The rank-one determinant lemma and the fact that $P$ is lower triangular with diagonal entries $1$ give

$$\begin{gathered} \det(I-zN)=(1+z)^{k+1}\\ {}\cdot\bigl(1-zb^{\mathsf T}(I+zP)^{-1}u\bigr). \end{gathered} \tag{5}$$

The classical Eulerian identity, recalled as Proposition 2.34 in arXiv version 2 of the source, is

$$\sum_{r\ge1}r^k w^r =\frac{wA_k(w)}{(1-w)^{k+1}}. \tag{6}$$

Removing its $r=1$ term and dividing by $w$ yields

$$1+w\sum_{m\ge0}(m+2)^k w^m =\frac{A_k(w)}{(1-w)^{k+1}}.$$

Use (4) in (5), and then substitute $w=-z$ in this last identity. The factors $(1+z)^{k+1}$ cancel, so

$$\det(I-zN)=A_k(-z). \tag{7}$$

Consequently,

$$\chi_N(t)=t^{k+1}A_k(-1/t).$$

Reversing the positions of a permutation replaces its number of descents by $k-1$ minus that number. Hence

$$A_k(t)=t^{k-1}A_k(1/t).$$

Applying this reciprocity to the preceding expression for $\chi_N$ gives

$$\chi_N(t)=(-1)^{k+1}t^2A_k(-t). \tag{8}$$

3. A cyclic vector gives the minimal polynomial

Put $v_m=P^mu$. By (3), the matrix with columns $v_0,v_1,\ldots,v_k$ has $(i,m)$ entry $(m+1)^i$. It is a Vandermonde matrix, with determinant

$$\prod_{0\le a<b\le k}(b-a)\ne0.$$

Thus $v_0,\ldots,v_k$ are linearly independent over $K$. Characteristic zero ensures that all the factors $b-a$ are nonzero.

Equations (2) and (4) give the exact relation

$$Nv_m=(m+2)^k u-v_{m+1}. \tag{9}$$

Starting from $v_0=u$, induction on $m$ using (9) shows that

$$v_m\in\operatorname{span}_K \{u,Nu,\ldots,N^m u\}.$$

For $m=0,\ldots,k$, these inclusions show that $u,Nu,\ldots,N^ku$ span the whole $(k+1)$-dimensional space. They are therefore linearly independent: $u$ is a cyclic vector for $N$.

If a nonzero polynomial of degree at most $k$ annihilated $N$, applying it to $u$ would contradict this independence. The minimal polynomial thus has degree at least $k+1$. By the Cayley–Hamilton theorem it divides the monic characteristic polynomial, which has degree $k+1$. Therefore $\pi_N=\chi_N$, completing (1).

The boundary $k=1$ is included: $A_1(t)=1$ and $N_1$ is nonzero with $N_1^2=0$, so both polynomials are $t^2$.