Exact polynomial formulas for signaletic transition matrices

Spectra of the parallel and series transition matrices

Let $k\ge1$, and work over a field $K$ of characteristic zero. Index rows and columns by subsets $S,T\subseteq[k]$. The transition matrices in Hivert–Pilaud, Conjecture 4.32 are

$$\begin{aligned} M^\parallel_{S,T}&=\mathbf1_{\{T\not\subseteq S\}},\\ M^\ddagger_{S,T}&=\mathbf1_{\{T\not\subseteq[|S|]\}}. \end{aligned}$$

Here $[0]=\varnothing$; a subset records the positions bearing the symbol $\succ$ in the source. Define

$$A_k(t)=\sum_{\sigma\in S_k}t^{\operatorname{des}(\sigma)},$$ $$\begin{aligned} Q_k(t)&=(-1)^{k+1}t^2A_k(-t),\\ h&=2^k-k-1. \end{aligned}$$

We prove all four identities:

$$\begin{aligned} \pi_\parallel(t)&=(t+1)^{k-1}Q_k(t),\\ \chi_\parallel(t)&=(t+1)^hQ_k(t),\\ \pi_\ddagger(t)&=Q_k(t),\\ \chi_\ddagger(t)&=t^hQ_k(t). \end{aligned} \tag{1}$$

The symbols $\pi$ and $\chi$ denote minimal and characteristic polynomials of the corresponding matrices. The integer $h$ is the Eulerian number counting permutations with one descent. In the shifted normalization $E_k(t)=tA_k(t)$ used in the author manuscript, one has $Q_k(t)=(-1)^k tE_k(-t)$, so (1) is also exactly the conjecture in that normalization.

We first recall the common $(k+1)$-dimensional block, then determine the additional blocks of the two transition matrices.

1. The common Eulerian block

Set

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

The calculation for Conjecture 4.36 gives this common block. We recall it as an ingredient, separately from the additional spectral assertions for the larger matrices. We need

$$\begin{aligned} \pi_N(t)=\chi_N(t)&=Q_k(t),\\ \operatorname{rank}N&=k. \end{aligned} \tag{2}$$

Here is a self-contained verification. Let $P=[\binom{i}{j}]$ be the lower Pascal matrix, let $u$ be the all-ones column vector, and put $b_j=\binom{k}{j}$. Then $N=ub^{\mathsf T}-P$. For $m\ge0$, the binomial theorem gives

$$\begin{aligned} (P^mu)_i&=(m+1)^i,\\ b^{\mathsf T}P^mu&=(m+2)^k. \end{aligned}$$

The classical Eulerian generating function, recalled in the source's Proposition 2.34, is

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

The rank-one determinant lemma, used in formal power series, gives

$$\det(I-zN)=(1+z)^{k+1}F(z),$$

where

$$F(z)=1-z\sum_{m\ge0}(-z)^m(m+2)^k.$$

Removing the $r=1$ term of (3), dividing by $w$, and setting $w=-z$ gives $F(z)=A_k(-z)/(1+z)^{k+1}$. Consequently,

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

Thus $\chi_N(t)=t^{k+1}A_k(-1/t)=Q_k(t)$, using the reciprocity $A_k(t)=t^{k-1}A_k(1/t)$ obtained by reversing permutations.

The columns $u,Pu,\ldots,P^ku$ form a Vandermonde matrix with distinct bases $1,\ldots,k+1$, hence a basis over $K$. Moreover,

$$N(P^mu)=(m+2)^k u-P^{m+1}u.$$

Induction shows that $u,Nu,\ldots,N^ku$ span the same space. Consequently $u$ is cyclic for $N$, proving $\pi_N=\chi_N$.

Finally, if $e_0$ is the first coordinate vector, then $Pe_0=u$ and $b^{\mathsf T}e_0=1$. The equation $Nx=0$ forces $x=(b^{\mathsf T}x)e_0$, and $Ne_0=0$. Hence $\ker N=Ke_0$ and $\operatorname{rank}N=k$. This proves (2). Comparing coefficients of $w^2$ in (3) also gives $[t]A_k(t)=2^k-k-1=h$.

2. The level-constant subspace

Let $V=K^{\mathcal P([k])}$, with coordinate vectors $e_T$. Let $U$ consist of vectors whose coordinate at $T$ depends only on $|T|$. Thus $\dim U=k+1$.

For either transition matrix and a row indexed by a set of size $i$, the sum over columns of size $j$ is

$$\binom{k}{j}-\binom{i}{j}.$$

For $M^\parallel$, the excluded columns are the $j$-subsets of $S$; for $M^\ddagger$, they are the $j$-subsets of $[i]$. Therefore both matrices preserve $U$, and their restrictions to $U$, in the level-value coordinates, are exactly $N$. This is the source's Lemma 4.33. It supplies the common block, but the remaining spectral information requires the arguments below.

3. The parallel matrix: the complementary Jordan exponent

Let $W$ consist of the vectors $x\in V$ satisfying

$$\sum_{|T|=j}x_T=0 \qquad(0\le j\le k).$$

Averaging over permutations of $[k]$ is a projection onto $U$ with kernel $W$. Characteristic zero allows this averaging, so

$$V=U\oplus W, \qquad \dim W=h.$$

Let $J$ be the all-ones matrix and let $Z_{S,T}=\mathbf1_{\{T\subseteq S\}}$ be the Boolean-lattice zeta matrix. Then $M^\parallel=J-Z$. Both $Z$ and $J$ commute with permutations of $[k]$, so they preserve $U$ and $W$. Since $J$ vanishes on $W$,

$$M^\parallel|_W=-Z|_W.$$

Consider the subset-raising operator

$$De_T=\sum_{a\notin T}e_{T\cup\{a\}}.$$

Adding $r$ distinct elements in all possible orders gives

$$D^re_T=r!\sum_{\substack{S\supseteq T\\ |S|=|T|+r}}e_S.$$

In particular $D^{k+1}=0$ and

$$Z=\sum_{r=0}^{k}\frac{D^r}{r!}. \tag{5}$$

The Boolean-incidence exponential identity (5) is classical; see Feinsilver, §2.2.3.

The operator $D$ commutes with permutations of $[k]$, so $W$ is $D$-invariant. Assume for now that $k\ge2$. We claim that its nilpotency index on $W$ is exactly $k-1$.

Indeed, $D^{k-1}$ can have a nonzero contribution only from levels $0$ and $1$. The level-$0$ coordinate of a vector in $W$ is zero. The contribution from level $1$ is a multiple of $e_{[k]}$, with coefficient $(k-1)!\sum_{|T|=1}x_T=0$. Thus

$$D^{k-1}|_W=0.$$

For the opposite bound, take $x=e_{\{1\}}-e_{\{2\}}\in W$. The coefficient of $e_{[k]\setminus\{2\}}$ in $D^{k-2}x$ is $(k-2)!\ne0$. Hence $D^{k-2}|_W\ne0$, including when $k=2$.

By (5), $Z-I=D H(D)$ for a polynomial $H$ with $H(0)=1$. The operator $H(D)$ is invertible and commutes with $D$. Therefore $Z-I$ has the same nilpotency index as $D$ on $W$. It follows that

$$\begin{aligned} \pi_{-Z|_W}(t)&=(t+1)^{k-1},\\ \chi_{-Z|_W}(t)&=(t+1)^h. \end{aligned}$$

Finally,

$$Q_k(-1)=(-1)^{k+1}k!\ne0.$$

Thus the two minimal polynomials on $U$ and $W$ are relatively prime. Their least common multiple is their product, while characteristic polynomials multiply under direct sums. Together with (2), this proves both parallel identities in (1) for $k\ge2$.

4. The series matrix: no additional nilpotent extension

Every row of $M^\ddagger$ depends only on the row's cardinality. Hence $M^\ddagger(V)\subseteq U$. Its row indexed by $[k]$ is zero, so its image is contained in

$$\begin{aligned} U_0&=\{x\in U:x_{[k]}=0\},\\ \dim U_0&=k. \end{aligned}$$

By (2), the restriction to $U$ has rank $k$. Therefore

$$M^\ddagger(V)=M^\ddagger(U)=U_0. \tag{6}$$

For any $v\in V$, (6) provides $a\in U$ with $M^\ddagger a=M^\ddagger v$. Thus $v-a\in\ker M^\ddagger$, proving

$$V=U+\ker M^\ddagger.$$

The polynomial $Q_k$ annihilates the restriction to $U$, and it also annihilates $\ker M^\ddagger$ because $Q_k(0)=0$. It therefore annihilates all of $V$. Conversely, the minimal polynomial on $V$ must be a multiple of the minimal polynomial $Q_k$ of the restriction to $U$. This proves $\pi_\ddagger=Q_k$.

The induced map on $V/U$ is zero, and $\dim(V/U)=h$. In a basis extending a basis of $U$, the matrix is block upper triangular with diagonal blocks $N$ and a zero matrix of order $h$. Consequently $\chi_\ddagger(t)=t^hQ_k(t)$, proving the series identities.

When $k=1$, both transition matrices equal $N_1$, while $h=0$ and $W=0$. Since $N_1\ne0$ and $N_1^2=0$, all four polynomials are $t^2$, exactly as asserted in (1). This completes the proof for every positive integer $k$.