Eigenvalues of a matrix with entries involving combinatorics

Question

Let $F(n, l, i, j)$ be the cardinality of the set \begin{eqnarray*} \{(k_1, \cdots, k_n)\in\mathbb{Z}^{\oplus 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*} Define an $n\times n$ matrix $M(l, n)$ by \begin{eqnarray*} M_{ij}(l, n)=(-1)^{i+j}F(n, l, i, j). \end{eqnarray*} In fact $M(l, n)$ is related to the Adams operations on $U(n)$, and I can show using algebraic topology that the eigenvalues are $1, l, l^2, \cdots, l^{n-1}$. Note that the last column vector of $M(l, n)$ is $(0, 0, \cdots, 0, 1)$ and so it is an eigenvector corresponding to the eigenvalue 1. When $n=2$, $M(l, 2)$ is $\begin{pmatrix}l&0\\ 1-l& 1\end{pmatrix}$.

Question: Are there more elementary ways to show this?

Added: For a fixed $n$ and different $l$, the matrices $M(l, n)$ commute with each other (more precisely, $M(l_1, n)M(l_2, n)=M(l_1l_2, n)$) and thus they are simultaneously diagonalisable and their eigenvectors do not depend on $l$. See the answer to this question for a set of eigenvectors of $M(l, n)$. A side question is how one can obtain the eigenvectors using elementary methods.

Answer 1

One can prove this statement along the following lines.

1. Prove that ${\rm Trace}(M(l,n)) = 1+l +\cdots + l^{n-1}$.
2. Prove that $M(l,n)^p = M(l^p,n)$.

Clearly, these statements 1 and 2 together imply that the eigenvalues are $1,l,\ldots, l^{n-1}$.

We will assume throughout that $l\geq 2$, otherwise the statement is obvious.

The proof of the first statement is by induction on $n$. The case $n=1$ is obvious. We are now looking for the cardinalities of sets of $k_1,\ldots, k_n\in [0,l-1]$ whose sum is divisible by $l-1$. If this number is $A_{n,l}$, then we have $$ A_{n,l} = 2 A_{n-1,l} + (l^{n-1} - A_{n-1,l}) $$ by splitting these sets into those with $k_n = 0\mod (l-1)$ and $k_n\neq 0\mod (l-1)$.

Clearly, this recursion proves statement 1.

Let me prove the statement 2 for p=2. Let me ignore the $(-1)^{i+j}$ signs in the definition of the matrix, since these can be removed by conjugating by a ${\rm diag}((-1)^i)$ matrix.

We are looking for a number of ways of writing $$ l^2\, j - i = a_1 + \ldots + a_n $$ with $a_r \in [0,l^2-1]$. We can write for each $r$ $$ a_r = l \,b_r + c_r $$ with $b_r,c_r\in [0,l-1]$.

We then have $$ l^2\,j - i = l\, \sum_r b_r + \sum_r c_r. $$

This shows that $\sum_r c_r = -i \mod l$, so $$ \sum_r c_r = l j_1 - i $$ for some $j_1$. Clearly, $j_1\in [1,\ldots,n]$.

Then we have $$ \sum_r b_r = l j - j_1. $$ Therefore, $$ M(l^2,n)_{i,j} = \sum_{j_1} M(l,n)_{i,j_1}M(l,n)_{j_1,j}. $$ This proves the desired matrix identity.

The argument for $p>2$ is completely analogous (or one can prove $M(l^p,n) = M(l^{p-1},n)M(l,n)$). So we are done.

Answer 2

Let $F(n,\ell)$ be the matrix with coefficients $$F_{i,j}(n,\ell)=[t^{\ell j-i}] \left(\frac{1-t^\ell}{1-t}\right)^n,\,\;\;\;1\leq i,j \leq n$$ Above Pat Devlin pointed out that it suffices to show that the $(n-1)\times (n-1)$ submatrix $L(n,\ell)$ with coefficients $$L_{i,j}(n,\ell)=[t^{\ell j-i}] \left(\frac{1-t^\ell}{1-t}\right)^n,\,\;\;\;1\leq i,j \leq n-1$$ has eigenvalues $\ell,\ell^2,\ldots,\ell^{n-1}$.

In fact, for positive integer $\ell\geq 2$ the matrices $P(n,\ell)$ with coefficients $$P_{i,j}(n,\ell)=\frac{1}{\ell^n} [t^{(j+1)\ell-i-1}] \left(\frac{1-t^\ell}{1-t}\right)^{n+1},\,\;\;\; 0\leq i,j \leq n-1$$ are known. They are the transition matrices for the Markov chains describing the propagation of carries when $n$ integers which have independent uniform $\ell$-ary ''digits'' are added (clearly $\ell^n\cdot P(n,\ell)=L(n+1,\ell)$).

These matrices are subject of the fascinating article Carries, Combinatorics and an Amazing Matrix by John Holte (American Mathematical Monthly, 104 (2), 1997)).

Holte proved that $P(n,\ell)$ has eigenvalues $1,\ell^{-1},\ldots,\ell^{-(n-1)}$, that the eigenvectors do not depend on the base $\ell$, and described the left and right eigenvectors explicitly. He also showed that $P(n,a)\cdot P(n,b)=P(n,ab)$.

The $P(n,b)$ also appear in the probability of card shuffling. They are the transition matrices for the Markov chains describing the descents in the permutations generated by shuffling a deck of $n$ cards with successive $b$-shuffles. (Persi Diaconis and Jason Fulman, Carries, shuffling and an amazing matrix, AMM November 2009 (arXiv preprint)).

Answer 3

Here's part way to an answer. I reduce the problem to one that sounds simpler, and I also argue why $l^{n-1}$ is an eigenvalue.

Let $f_{n, l} (k)$ denote the number of ways to write $k$ as an ordered sum $k = a_1 + \cdots + a_{n}$ where $a_{i} \in \{0, 1, \ldots, l-1\}$ [so your function is $F(n, l, i, j) = f_{n,l} (lj - i)$]. The matrix you considered is

$$ M = \Big( (-1)^{i+j} f_{n,l} (lj - i) \Big)_{i,j}. $$ Since you only want the eigenvalues, we can ignore the $(-1)^{i+j}$ term since doing so will give us a matrix similar to $M$. Moreover, since (as noted in original post) the last column of this matrix is $(0, 0, \ldots , 0, 1)$, we can ignore the last row and last column of $M$ when finding the other eigenvalues. Thus, your claim is equivalent to the following:

---

Equivalent problem: Consider the $(n-1) \times (n-1)$ matrix $A$ whose $(i,j)$-entry is given by $f_{n,l} (lj - i) = F(n, l, i,j)$. Show that the eigenvalues of $A$ are $l, l^2, \ldots, l^{n-1}$.

---

We first claim that the row sums of $A$ are constant and equal to $l^{n-1}$ [this shows one of the eigenvalues we need]. To see this, note the sum along row $i$ is equal to $\sum_{j=1} ^{n-1} f_{n,l} (lj - i)$, which is equal to the number of $n$-tuples in $\{0, 1, \ldots, l-1\}^n$ whose sum is $-i$ modulo $l$. This is clearly $l^{n-1}$ since the first $n-1$ values are free choices, and the last is then determined by the others.

---

Some other facts: Let $R$ be the $(n-1) \times (n-1)$ matrix with $1$'s along the diagonal $i+j=n$ and $0$'s elsewhere. Then because $f_{n,l} (k) = f_{n,l} (n(l-1)-k)$, this implies $AR = RA$ (i.e., $a_{i,j} = a_{n-i, n-j}$). (This fact looks very useful for finding eigenvectors, and it's why I think one should ignore the last row and column of $M$.)

It's also not difficult to see (if one's familiar with generating functions in enumeration problems) that $$\sum_{k=0}^{\infty} x^{k} f_{n,l} (k) = \left( 1 + x + x^2 + \cdots + x^{l-1} \right)^n = \left( \frac{1-x^{l}}{1-x} \right)^n.$$

Answer 4

Another small part of an answer.

According to numerical experiments eigenvectors does not depend on $l$ for $l\ge 2$. So if we want to know these vectors we may start with $l=2$. In this case situation is more simple because for $l=2$ we have $f_{n,l} (k) = \binom nk$ and $ M_{ij}=(-1)^{i+j}\binom n{2j-i}. $ Eigenvectors will be just polynomials if we remove signs from $M$ and take $\widetilde{M} $ with $ \widetilde{M} _{ij}=\binom n{2j-i}. $

Suppose that eigenvectors of $\widetilde{M}$ are rows of matrix $V$. Then first examples are $$n=2,\qquad \widetilde{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 \widetilde{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 \widetilde{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 \widetilde{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}.$$

More simple polynomials are $Q_m(x)=P_m(x+n/2)$: $$Q_0(x)=1,\quad Q_1(x)=2x,\quad Q_2(x)=3x^2-\frac{n}4,\quad Q_3(x)=4x^3-nx, \quad Q_4(x)=5x^4-\frac{5n}2 x^2+\frac{n(5n+2)}{48}.$$

Also numbers $1$, $3$, $11$, $25$ standing above the last unit in $V$ are numbers from the sequence A025529: $a(n) = (1/1 + 1/2 + ... + 1/n)LCM\{1,2,...,n\}$.

Answer 5

As I mentioned in the question, the matrix $M(l, n)$ is related to the Adams operations on $U(n)$. Let me elaborate further on this.

Recall that for a finite CW complex $X$, $K^{-1}(X)$ is $[X, U(\infty)]$, the group of homotopy classes of maps from $X$ to $U(\infty)$. Let $G$ be a compact Lie group and $\delta: R(G)\to K^{-1}(G)$ be the map which sends a $G$ representation $\rho$ to the homotopy class of it viewed the map $G\stackrel{\rho}{\rightarrow}U(n)\hookrightarrow U(\infty)$. If $G=U(n)$, then by a theorem of L. Hodgkin, its $K$-theory is the exterior algebra \begin{eqnarray} K^*(U(n))=\bigwedge\nolimits^*_\mathbb{Z}(\delta(\sigma_n), \delta(\wedge^2\sigma_n), \cdots, \delta(\wedge^n\sigma_n)), \end{eqnarray} where $\sigma_n$ is the standard representation of $U(n)$. The Adams operation $\psi^l$ on the primitive $\mathbb{Z}$-module of this exterior algebra has $lM(l, n)$ as the matrix representation with respect to the basis $\delta(\sigma_n), \cdots, \delta(\wedge^n\sigma_n)$. The definition of Adams operations implies that they commute with each other, so do $M(l, n)$ for different positive $l$ and fixed $n$, and their eigenvectors are independent of $l$ due to simultaneous diagonazability.

Using the definition of Chern character and Adams operation, one can easily get the following statement:

Let $X$ be a finite CW-complex and $\alpha\in K^{-1}(X)$. Then we have \begin{eqnarray} \text{ch}(\psi^l(\alpha))=\sum_il^i\text{ch}_{2i-1}(\alpha) \end{eqnarray} where $\text{ch}_k(\alpha)$ is the degree $k$ term of $\text{ch}(\alpha)$.

Returning to the case $X=U(n)$, we know that $H^*(U(n), \mathbb{Q})$ is also an exterior algebra on $n$ primitive generators of degrees $1, 3, 5, \cdots, 2n-1$. So if $\alpha$ is a (rational) primitive element of $K^*(U(n))\otimes\mathbb{Q}$ which is also an eigenvector of $\psi^l$, then there exists $1\leq j\leq n$ such that $\text{ch}_{2i-1}(\alpha)$ is zero for $i\neq j$ but nonzero for $i=j$, and the corresponding eigenvalue is $l^j$. So the eigenvalues of $lM(l, n)$ are $l, l^2, \cdots, l^n$. This recent paper has more details of the above discussion.