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. 
 A: 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)).
A: 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.$$
A: 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.
A: One can prove this statement along the following lines.


*

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

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