Eigenvalues of a matrix with entries involving combinatorics

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.

• Is it possible to make an example about your question. Thanks – Amin235 Nov 20 '16 at 7:30
• @Amin235 I edited the question and gave an example of $M$ when $n=2$. – No_way Nov 20 '16 at 15:21
• Thank you so much that you made an example. I wanted to see an example for a large values of $n$, like $n=5$ or even you present the form of matrix in general. I feel, there is a linear sequence numbers for $M$ matrix. Is it possible to tell me what dose it mean the $n$th power of the $M$ matrix in the combinatorics language? Excuse me, If i ask too many question. – Amin235 Nov 20 '16 at 23:14
• @AlexeyUstinov Thank you for pointing this out. Indeed they are related. However note that entries of $M$ are number of ordered partitions of some numbers whereas the Gauss polynomials give number of partitions without regard to the order. – No_way Nov 21 '16 at 14:13

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.

• I suppose you are not surprised that the proof is related to Adams operations as well :) – Lev Borisov Nov 28 '16 at 15:02
• Nice solution! (y) And it's elementary enough indeed. Sure, I expect the proof still has something to do with Adams operations. – No_way Nov 29 '16 at 9:32

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)).

• Thank you for your answer. It's surprising that this matrix is related to carries and shuffling! – No_way Dec 10 '16 at 5:31
• In my eyes it suggests that the Adams operation should have a nice combinatorial interpretation, at least for the case $K^*(U(n))$. (But I am no expert). – esg Dec 11 '16 at 16:09

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.$$

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\}$.

• Eigenvectors do seem to depend on $l$ in the last coordinate, no? Which is why I think we should ignore the last row and column of $M.$ – Pat Devlin Nov 28 '16 at 12:50
• @Pat Devlin No, you can easely see it in the case $n=2$. I don't see any reasons to ignore the last row and column of $M$ so far. – Alexey Ustinov Nov 28 '16 at 13:13
• @AlexeyUstinov Eigenvectors do not depend on $l$ because those matrices (for a fixed $n$) commute with each other and thus are simultaneously diagonalizable. Thank you for your answer, and I am very interested in the appearance of the special numerical sequence in a particular entries of an eigenvector. Could you please explain why this sequence shows up? By the way I have just given another set of eigenvectors (not normalised to integers as you did here) in an answer to your another question in MO. – No_way Nov 29 '16 at 9:39
• @No_way This matrices map any polynomial vector to the polynomial vector of the same (or lower) degree. If matrix is degenerate then we can find some polynomial in its kernel. It is very nice that you are interested in this polynomials. Will they have any meaning in algebraic topology? – Alexey Ustinov Nov 29 '16 at 10:47
• @AlexeyUstinov Yes, I think they bear some links to algebraic topology. As I pointed out in an answer to your another MO question on the eigenvectors of these matrices, these polynomials are related to the generating function $\displaystyle\left(\frac{t}{\sinh t}\right)^y$. While I do not know precisely the link, but the similar function $\displaystyle \frac{\frac{\sqrt{t}}{2}}{\sinh \frac{\sqrt{t}}{2}}$ is used to define the $\widehat{A}$-genus of manifolds. See en.wikipedia.org/wiki/Genus_of_a_multiplicative_sequence – No_way Nov 29 '16 at 12:58

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.