# A combinatorial determinant

## 1 Coefficients of powers of power series

###### Theorem 1

Let $`f=1+a_1x+a_2x^2+\mathrm{}`$ be a formal power series, and define a matrix $`c`$ by<sup>1</sup><sup>1</sup>1 “$`[x^k]g`$” means the coefficient of $`x^k`$ in the series $`g`$.

$$c_{i,j}=[x^j]f^i(i,j0).$$
(2)   
Then

$$det\left((c_{i,j})_{i,j=0}^n\right)=a_1^{n(n+1)/2}(n=0,1,2,\mathrm{}).$$
(3)   
To prove this, define a matrix $`b`$ by

$$b_{i,j}=(1)^{i+j}\left(\genfrac{}{}{0pt}{}{i}{j}\right),(i,j0).$$
(4)   
Then we claim that $`bc`$ is upper triangular with powers of $`a_1`$ on its diagonal. Indeed we have

$`{\displaystyle \underset{j}{}}b_{i,j}c_{j,k}`$ $`=`$ $`{\displaystyle \underset{j}{}}(1)^{i+j}\left({\displaystyle \genfrac{}{}{0pt}{}{i}{j}}\right)[x^k]f^j=(1)^i[x^k]{\displaystyle \underset{j}{}}(1)^j\left({\displaystyle \genfrac{}{}{0pt}{}{i}{j}}\right)f^j`$   
$`=`$ $`(1)^i[x^k](1f)^i=[x^k](a_1x+a_2x^2+\mathrm{})^i=\{\begin{array}{cc}0,\hfill & \text{if }k<i\text{;}\hfill \\ a_1^i,\hfill & \text{if }k=i\text{,}\hfill \end{array}`$   
as claimed. Since $`bc`$ is this upper triangular matrix, and $`detb=1`$, the determinant of $`c`$ is $`_{i=0}^na_1^i=a_1^{n(n+1)/2}`$. $`\mathrm{}`$

Ed Bender has noted that the hypothesis $`a_0=1`$ can be removed. Indeed if $`a_00`$, apply the result to $`f/a_0`$ and discover that the theorem is unchanged. If $`a_0=0`$ the result follows by continuity.

In order to gain an extra free parameter in the identities that are to follow, as well as to introduce the idea of the proof of Mina’s theorem in general form, we’ll restate Theorem 1 in terms of the $`z`$th power of $`f`$.

###### Theorem 2

Let $`f=1+a_1x+a_2x^2+\mathrm{}`$ be a formal power series, let $`z`$ be a complex number, and define a matrix $`c`$ by

$$c_{i,j}=[x^j]f^{zi}(i,j0).$$
(5)   
Then

$$det\left((c_{i,j})_{i,j=0}^n\right)=(za_1)^{n(n+1)/2}(n=0,1,2,\mathrm{}).$$
(6)   
## 2 Some examples

1. This investigation began when I was looking at the infinite matrix whose $`(i,j)`$ entry is the number of representations of the integer $`j`$ as a sum of $`i`$ squares of nonnegative integers $`(i,j=0,1,2,\mathrm{})`$, and noticed that its determinant is 1. This matrix begins as

$$\left(\begin{array}{ccccccccc}\hfill 1& \hfill 0& \hfill 0& \hfill 0& \hfill 0& \hfill 0& \hfill 0& \hfill 0& \hfill \mathrm{}\\ \hfill 1& \hfill 1& \hfill 0& \hfill 0& \hfill 1& \hfill 0& \hfill 0& \hfill 0& \hfill \mathrm{}\\ \hfill 1& \hfill 2& \hfill 1& \hfill 0& \hfill 2& \hfill 2& \hfill 0& \hfill 0& \hfill \mathrm{}\\ \hfill 1& \hfill 3& \hfill 3& \hfill 1& \hfill 3& \hfill 6& \hfill 3& \hfill 0& \hfill \mathrm{}\\ \hfill 1& \hfill 4& \hfill 6& \hfill 4& \hfill 5& \hfill 12& \hfill 12& \hfill 4& \hfill \mathrm{}\\ \hfill 1& \hfill 5& \hfill 10& \hfill 10& \hfill 10& \hfill 21& \hfill 30& \hfill 20& \hfill \mathrm{}\\ \hfill 1& \hfill 6& \hfill 15& \hfill 20& \hfill 21& \hfill 36& \hfill 61& \hfill 60& \hfill \mathrm{}\\ \hfill 1& \hfill 7& \hfill 21& \hfill 35& \hfill 42& \hfill 63& \hfill 112& \hfill 141& \hfill \mathrm{}\\ \hfill \mathrm{}& \hfill \mathrm{}& \hfill \mathrm{}& \hfill \mathrm{}& \hfill \mathrm{}& \hfill \mathrm{}& \hfill \mathrm{}& \hfill \mathrm{}& \hfill \mathrm{}\end{array}\right)$$

This is an array of the type considered in (2) above, where $`f=1+x+x^4+x^9+x^{16}+\mathrm{}`$. Hence by Theorem 1, the determinant of every upper-left $`n\times n`$ section of this infinite matrix is 1. The same will be true if “squares” is replaced by “cubes” or any higher power, or for that matter by any increasing sequence $`\{0,1,\mathrm{}\}`$ at all!
2. Take $`f=1+x`$ in Theorem 2 to discover that

$$det\left(\left(\genfrac{}{}{0pt}{}{zi}{j}\right)\right)_{i,j=0}^n=z^{\left(\genfrac{}{}{0pt}{}{n+1}{2}\right)}(n=0,1,2,\mathrm{}).$$
3. With $`f=(e^x1)/x`$ in Theorem 2 we find a determinant that involves the Stirling numbers of the second kind,

$$det\left(\frac{(zi)!}{(zi+j)!}\left\{\genfrac{}{}{0pt}{}{zi+j}{zi}\right\}\right)_{i,j=0}^n=\left(\frac{z}{2}\right)^{n(n+1)/2}(n=0,1,2,\mathrm{}).$$
4. With $`f=\mathrm{log}(1+x)/x`$ in Theorem 2 we evaluate one that contains the Stirling numbers of the first kind,

$$det\left(\frac{(zi)!}{(zi+j)!}\left[\genfrac{}{}{0pt}{}{zi+j}{zi}\right]\right)_{i,j=0}^n=\left(\frac{z}{2}\right)^{n(n+1)/2}(n=0,1,2,\mathrm{}).$$
5. Now let $`f=(1\sqrt{14x})/(2x)=1+x+\mathrm{}`$ in Theorem 2. If we use the fact that

$$\left(\frac{1\sqrt{14x}}{2x}\right)^k=\underset{n0}{}\frac{k(2j+k1)!}{j!(k+j)!}x^n,$$

then the resulting determinantal identity can be put in the form

$$det\left(\frac{(2j+zk1)!}{(zk+j)!}\right)_{j,k=1}^n=z^{\left(\genfrac{}{}{0pt}{}{n}{2}\right)}\mathrm{\hspace{0.17em}1}!\mathrm{\hspace{0.17em}2}!\mathrm{\hspace{0.17em}3}!\mathrm{}(n1)!(n=1,2,\mathrm{}).$$

## 3 The additive structure of this case

This case of Mina’s theorem, in which we evaluate at $`x=0`$, has an interesting structure because, if the series involved are normalized to constant term 1, then the matrices are all trangularized by the same matrix $`b`$ of (4).

Usually, determinants don’t relate well to addition of matrices. That is, if $`detU`$, $`detV`$ can be evaluated in simple closed form, there is no reason to suppose that the same is true of $`det(U+V)`$. But the determinants that we are now studying act nicely under matrix addition. Thus, if $`u_{i,j}=[x^i]f^j`$, and $`v_{i,j}=[x^i]g^j`$, then $`b(u+v)`$ is triangular, with diagonal entries $`f^{}(0)^i+g^{}(0)^i`$ $`(i=0,1,2,\mathrm{})`$, and so

$$det(u_{i,j}+v_{i,j})_{i,j=0}^n=\underset{i=0}{\overset{n}{}}(f^{}(0)^i+g^{}(0)^i).$$

For example,

$$det\left(\left(\genfrac{}{}{0pt}{}{ri}{j}\right)+\left(\genfrac{}{}{0pt}{}{si}{j}\right)\right)_{i,j=0}^n=\underset{i=0}{\overset{n}{}}(r^i+s^i),$$

and more generally if $`S`$ is any set of numbers, and $`c`$ is a function on $`S`$, then

$$det\left(\underset{rS}{}c(r)\left(\genfrac{}{}{0pt}{}{ri}{j}\right)\right)_{i,j=0}^n=\underset{j=0}{\overset{n}{}}\left(\underset{rS}{}c(r)r^j\right).$$

An interesting special case is obtained by taking $`S`$ to be a set of $`m`$ equally spaced points in an interval, say $`(0,1)`$, taking the $`c(r)`$’s all equal to $`1/m`$, and taking the limit as $`m\mathrm{}`$. The result is that

$$det\left(_0^1f(x)\left(\genfrac{}{}{0pt}{}{xi}{j}\right)𝑑x\right)_{i,j=0}^n=\underset{j=0}{\overset{n}{}}\mu _j(f),$$

where the $`\mu _i(f)=_0^1x^if(x)𝑑x`$ are the moments of $`f`$. For example,

$$det\left(_0^1\left(\genfrac{}{}{0pt}{}{xi}{j}\right)𝑑x\right)_{i,j=0}^n=\frac{1}{(n+1)!}.$$

## 4 Proof of Mina’s theorem

Now we prove Mina’s theorem by proving the following small generalization of it.

$$det\left\{\left(\frac{d^j}{dx^j}f(x)^{zx_i}\right)_{i,j=0}^n\right\}=f(x)^{z_0^n(x_ii)}\left(zf^{}(x)\right)^{n(n+1)/2}\underset{0i<jn}{}(x_jx_i).$$
(7)   
This will follow easily from the following observation.

###### Lemma 1

Let $`\{p_j(x)\}`$ $`(j=0,1,2,\mathrm{})`$ be any sequence of polynomials such that the $`j`$th one is of degree $`j`$, for each $`j0`$. Then the determinant of the matrix $`Q=\{p_j(x_i)\}_{i,j=0}^n`$ is equal to the product of the highest coefficients of $`p_0,p_1,\mathrm{},p_n`$ times the discriminant of the $`x_i`$’s.

Indeed, if $`A`$ is the lower triangular matrix of coefficients of the $`p_j`$’s and $`V`$ is the Vandermonde matrix of the $`x_i`$’s then $`Q=AV`$. $`\mathrm{}`$

Now let $`\alpha _{i,j}=D^j(f(x)^{zx_i})`$, where $`D=d/dx`$. We claim that, for each $`j=0,1,\mathrm{},`$ $`\alpha _{i,j}`$ is of the form $`f^{zx_ij}`$ times a polynomial in $`z`$ of exact degree $`j`$, whose coefficients are functions of $`x`$ and whose highest coefficient is $`(x_if^{})^j`$. In view of Lemma 1, this claim will prove the theorem. However this claim is trivial to prove by induction on $`j`$. $`\mathrm{}`$

Theorem 2 is the special case of (7) in which $`x=0`$, $`z=1`$, and the polynomials $`p_j(x)`$ are given by

$$p_j(x)=\underset{\mathrm{}=0}{\overset{j}{}}\frac{x^{\mathrm{}}}{\mathrm{}!}[t^j]\left(\mathrm{log}y(t)^{\mathrm{}}\right),$$

with highest coefficients $`a_1^j/j!`$.

## 5 Remarks

1. The family of matrices of the form (2) was previously investigated by Doron Zeilberger , from the point of view of constant term identities.
2. My thanks go to Brendan McKay for some e-mail exchanges that were helpful in clarifying the ideas here.
3. By comparing (1) and (7) we see that the absence of $`f(x)`$ on the right side of the former is because of the “lucky coincidence” that in the former, $`x_0+x_1+\mathrm{}+x_n=n(n+1)/2`$.