7
$\begingroup$

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?

$\endgroup$
2
  • 1
    $\begingroup$ 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)$. $\endgroup$
    – Wolfgang
    Nov 29, 2016 at 8:51
  • $\begingroup$ @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$. $\endgroup$ Nov 29, 2016 at 10:41

1 Answer 1

5
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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