# Eigenvectors of a matrix with entries involving combinatorics

In the question Eigenvalues of a matrix with entries involving combinatorics No_way asked about eigenvectors of $n\times n$ matrix $M$ with entries \begin{eqnarray*} M_{ij}=(-1)^{i+j}F(n, l, i, j), \end{eqnarray*} where $F(n,l,i,j)$ is the cardinality of the set \begin{eqnarray*} \{(k_1, \cdots, k_n)\in\mathbb{Z}^{n}|0\leq k_r\leq l-1\text{ for }1\leq r\leq n\text{, }k_1+\cdots+k_n=lj-i\}. \end{eqnarray*} These eigenvalues are known to be $1, l, l^2, \cdots, l^{n-1}$.

Let's remove signs and consider the matrix $M$ with $M_{ij}=F(n, l, i, j)$. According to my numerical experiments eigenvectors do not depend on $l$ for $l\ge 2$ and they are polynomials.

Q1: Why do eigenvectors not depend on $l$?

For $l=2$ we have $M_{ij}=\binom n{2j-i},$ and first examples are (eigenvectors of $M$ are rows of $V$) $$n=2,\qquad M=\left( \begin{array}{cc} 2 & 0 \\ 1 & 1 \\ \end{array} \right),\qquad V=\left( \begin{array}{cc} 1 & 1 \\ 0 & 1 \\ \end{array} \right);$$ $$n=3,\qquad M=\left( \begin{array}{ccc} 3 & 1 & 0 \\ 1 & 3 & 0 \\ 0 & 3 & 1 \\ \end{array} \right),\qquad V=\left( \begin{array}{ccc} 1 & 1 & 1 \\ -1 & 1 & 3 \\ 0 & 0 & 1 \\ \end{array} \right);$$

$$n=4,\qquad M=\left( \begin{array}{cccc} 4 & 4 & 0 & 0 \\ 1 & 6 & 1 & 0 \\ 0 & 4 & 4 & 0 \\ 0 & 1 & 6 & 1 \\ \end{array} \right),\qquad V=\left( \begin{array}{cccc} 1 & 1 & 1 & 1 \\ -1 & 0 & 1 & 2 \\ 2 & -1 & 2 & 11 \\ 0 & 0 & 0 & 1 \\ \end{array} \right);$$

$$n=5,\qquad M=\left( \begin{array}{ccccc} 5 & 10 & 1 & 0 & 0 \\ 1 & 10 & 5 & 0 & 0 \\ 0 & 5 & 10 & 1 & 0 \\ 0 & 1 & 10 & 5 & 0 \\ 0 & 0 & 5 & 10 & 1 \\ \end{array} \right),\qquad V=\left( \begin{array}{ccccc} 1 & 1 & 1 & 1 & 1 \\ -3 & -1 & 1 & 3 & 5 \\ 11 & -1 & -1 & 11 & 35 \\ -3 & 1 & -1 & 3 & 25 \\ 0 & 0 & 0 & 0 & 1 \\ \end{array} \right).$$

Denote by $v_m=(v_m(1),\ldots,v_m(n))$ rows of $V$ ($0\le m\le n-1$). They defined up to multiplicative constant and $v_m(k)=\mu_m P_m(k)$ where $P_m(x)$ are some special polynomials of degree $m$. In particular for $m=0,1,2,3,4$ we have $$P_0(x)=1,\quad P_1(x)=2x-n,\quad P_2(x)=3x^2-3nx+\frac{n(3n-1)}{4},$$ $$P_3(x)=4x^3-6nx^2+n(3n-1)x-\frac{n^2(n-1)}{2},$$ $$P_4(x)=5x^4-10nx^3+\frac{5n(3n-1)}{2}x^2-\frac{5n^2(n-1)}{2}x+\frac{n(15n^3-30n^2+5n+2)}{48}.$$

Q2: What is the generating function for these polynomials?

• Have you noticed that the coefficient of $x^k$ in $P_m(x)$ seems to be essentially the same for constant $m-k$? More precisely, $[x^m]P_m=m+1, [x^{m-1}]P_m=- {{m+1}\choose{2}}n, [x^{m-2}]P_m=+ {{m+1}\choose3}\dfrac {n(3n-1)}4,$ $[x^{m-3}]P_m=-{{m+1}\choose4}\dfrac{n^2(n-1)}{2}, [x^{m-4}]P_m={{m+1}\choose5}\dfrac{n(15n^3-30n^2+5n+2)}{48}...$ So we would only need to know $P_m(0)$, i.e. the polynominals in $n$ which are the constant terms of $P_m(x)$. – Wolfgang Nov 29 '16 at 8:51
• @Wolfgang Nice argument. It means that $P_m(x)$ is something like binomial convolution of $P_m=P_m(0)$ with falling factorials. It correspond to the product of two exponential generating functions and we only need to know exponential generating function for $P_m$. – Alexey Ustinov Nov 29 '16 at 10:41

In fact for a fixed $n$, the matrices $M(l, n)$ for $l>0$ commute with each other and thus are simultaneously diagonalisable. For your second question, if $\{p_j(y)\}$ is a sequence of polynomials satisfying \begin{eqnarray} \left(\frac{t}{\sinh t}\right)^y=\sum_{j=0}^\infty p_j(y)t^{2j}. \end{eqnarray} then the $i$-th entry of an eigenvector corresponding to the eigenvalue $l^{n-k-1}$ is \begin{eqnarray} (-1)^{i-1}\sum_{j=0}^{\lfloor\frac{k}{2}\rfloor}\frac{p_j(n)}{(k-2j)!}(n-2i)^{k-2j}. \end{eqnarray} I believe from here we can work out what the generating function of your $P_m(x)$ is.