7
$\begingroup$

After noticing that the determinant of an $n \times n$ matrix $A_n$ with elements $a_{i,j}=i^j$, $1 \le i \le n$, $1 \le j \le n$, is the superfactorial (product of the first $n$ factorials), I wanted to try other cases.

I noticed that with $a_{i,j}=\binom{n+i-1}{j}$:

$$\lvert A_n \rvert = \binom{2n-1}{n}$$

This one has been proved in this answer using the paper Binomial Determinants, Paths, and Hook Length Formulae by Gessel and Viennot.

After this I tried $a_{i,j}=\left[{n+i-1\atop j}\right]$ (unsigned Stirling numbers of the first kind) and obtained:

$$\lvert A_n \rvert = (n-1)!^{n} \tag{1}\label{1}$$

and with $a_{i,j}={n+i-1 \brace j}$ (Stirling numbers of the second kind):

$$\lvert A_n \rvert = n!^{n-1} \tag{2}\label{2}$$

Any hint for proving $(1)$ and $(2)$?

@Peter Taylor found the following generalizations:

With $a_{i,j}=\left[{k+i-1\atop j}\right]$ (unsigned Stirling numbers of the first kind):

$$\lvert A_n \rvert = (k-1)!^{n} \tag{3}\label{3}$$

and with $a_{i,j}={k+i-1 \brace j}$ (Stirling numbers of the second kind):

$$\lvert A_n \rvert = n!^{k-1} \tag{4}\label{4}$$

$\endgroup$
5
  • 4
    $\begingroup$ You may find the following papers by Kratthenthaler and Ehrenborg useful: sciencedirect.com/science/article/pii/S0024379505003356 and users.dimi.uniud.it/~giacomo.dellariccia/Glossary/Stirling/… $\endgroup$
    – Max Muller
    May 24 at 9:49
  • 1
    $\begingroup$ Maybe I have an out-by-one error in my indexing of the Stirling numbers of the first kind, but I find that generalising to $a_{i,j}=\left[{k+i-1\atop j}\right]$ gives $(k-1)!^n$ and $a_{i,j}={k+i-1 \brace j}$ gives $n!^{k-1}$ $\endgroup$ May 24 at 10:25
  • $\begingroup$ @Peter Taylor you are right, my bad. I added your generalizations. $\endgroup$
    – BillyJoe
    May 24 at 10:36
  • 2
    $\begingroup$ Further generalising, symmetric polynomials unify your examples and many others. If we take a general sequence of Comtet numbers of the first kind $$c(n, k) = e_{n-k}(\xi_1, \ldots, \xi_n)$$ then the $n \times n$ matrix with values $a_{i,j} = c(k+i-1, j-1)$ appears to have determinant $(\xi_1 \cdots \xi_k)^n$. Similarly, if we take a general sequence of Comtet numbers of the second kind $$C(n, k) = h_{n-k}(\xi_1, \ldots, \xi_{k+1})$$ then the $n \times n$ matrix with values $a_{i,j} = C(k+i-1, j-1)$ appears to have determinant $(\xi_1 \cdots \xi_n)^k$. $\endgroup$ May 24 at 10:54
  • 2
    $\begingroup$ Theorems 44 and 45 of @MaxMuller's first reference generalise my previous comment even further. $\endgroup$ May 24 at 21:42

2 Answers 2

3
$\begingroup$

If we take a general sequence of (unsigned) Comtet numbers of the first kind [1, 2] $$c(n, k) = e_{n-k}(\xi_1, \ldots, \xi_n)$$ then the $n \times n$ submatrix with a row offset of $k$ has determinant $$\det_{0 \le i, j < n} \Big( e_{k+i-j}(\xi_1, \ldots, \xi_{k+i}) \Big) = (\xi_1 \cdots \xi_k)^n$$

Similarly, if we take a general sequence of Comtet numbers of the second kind $$C(n, k) = h_{n-k}(\xi_1, \ldots, \xi_{k+1})$$ then the $n \times n$ submatrix with a row offset of $k$ has determinant $$\det_{0 \le i,j < n} \Big( h_{k+i-j}(\xi_1, \ldots, \xi_{j+1}) \Big) = (\xi_1 \cdots \xi_n)^k$$

Note in particular that for your question (the Stirling numbers respectively of the first and second kinds, omitting the row $n=0$ and column $k=0$) we can take $\xi_i = i$.

A more natural generalisation of both the binomial and the Stirling examples you give is to take a row offset of $k$ and a column offset of $1$, but the resulting LU factorisations are far uglier.

Proofs

In a comment, Max Muller gave a reference to C. Krattenthaler, Advanced determinant calculus: A complement, Lin. Alg. and its Applications, 411 (2005), 68-166. Theorems 44 and 45 are very much in the same area, certainly generalise the result for Comtet numbers of the first kind. I'm no longer confident that they also cover Comtet numbers of the second kind, but I haven't wrestled with them enough to say that they definitely don't. Regardless, the paper which Krattenthaler references for these results is described as "in press" and, 17 years later, doesn't appear yet to have been published, so I give proofs for the more restricted claims made above.

Theorem: $\det_{0 \le i, j < n} \Big( e_{k+i-j}(\xi_1, \ldots, \xi_{k+i}) \Big) = (\xi_1 \cdots \xi_k)^n$

Proof: $\Big( e_{k+i-j}(\xi_1, \ldots, \xi_{k+i}) \Big)_{0 \le i, j < n} = L_e U_e$ where $$\begin{eqnarray*}L_e &=& \Big( e_{i-j}(\xi_{k+1}, \ldots, \xi_{k+i}) \Big)_{0 \le i, j < n} \\ U_e &=& \Big( e_{k+i-j}(\xi_1, \ldots, \xi_k) \Big)_{0 \le i, j < n} \end{eqnarray*}$$

To verify the factorisation observe that $$(L_e U_e)_{i,j} = \sum_{a=0}^{n-1} e_{i-a}(\xi_{k+1}, \ldots, \xi_{k+i}) e_{k+a-j}(\xi_1, \ldots, \xi_k) = e_{k+i-j} (\xi_1, \ldots, \xi_{k+i})$$

Trivially, $\det L_e = 1$ and $\det U_e = e_k(\xi_1, \ldots, \xi_k)^n = (\xi_1 \cdots \xi_k)^n$.
$\blacksquare$

Theorem: $\det_{0 \le i,j < n} \Big( h_{k+i-j}(\xi_1, \ldots, \xi_{j+1}) \Big) = (\xi_1 \cdots \xi_n)^k$

Again we use an LU-factorisation as $L_h U_h$ where $$\begin{eqnarray*}L_h &=& \Big( h_{i-j}(\xi_1, \ldots, \xi_{j+1}) \Big)_{0 \le i, j < n} \\ U_h &=& \Big( h_{k+i-j}(\xi_{i+1}, \ldots \xi_{j+1}) \Big)_{0 \le i, j < n} \end{eqnarray*}$$

I don't find that the verification yields to proof by inspection this time because of the overlap in variables between the two halves of each term:

$$(L_h U_h)_{i,j} = \sum_{a=0}^{n-1} h_{i-a}(\xi_1, \ldots, \xi_{a+1}) h_{k+a-j}(\xi_{a+1}, \ldots \xi_{j+1})$$

So let $P(i,j,k, \vec{\xi}) = \sum_{a=0}^{j} h_{i-a}(\xi_1, \ldots, \xi_{a+1}) h_{k+a-j}(\xi_{a+1}, \ldots \xi_{j+1})$ and we aim to prove by induction on $j$ that $P(i,j,k,\xi) = h_{i+k-j}(\xi_1, \ldots, \xi_{j+1})$.

Base case, $j=0$: $P(i,0,k, \vec{\xi}) = h_{i}(\xi_1) h_{k-j}(\xi_{1}) = h_{i+k-j}(\xi_i)$

Inductive step, $j > 0$: \begin{eqnarray*} P(i,j,k, \vec{\xi}) &=& \sum_{a=0}^{j} h_{i-a}(\xi_1, \ldots, \xi_{a+1}) h_{k+a-j}(\xi_{a+1}, \ldots \xi_{j+1}) \\ &=& h_{i-j}(\xi_1, \ldots, \xi_{j+1}) h_{k}(\xi_{j+1}) + \sum_{a=0}^{j-1} h_{i-a}(\xi_1, \ldots, \xi_{a+1}) h_{k+a-j}(\xi_{a+1}, \ldots \xi_{j+1}) \\ &=& \xi_{j+1}^k h_{i-j}(\xi_1, \ldots, \xi_{j+1}) + \sum_{a=0}^{j-1} \sum_{b=0}^{k+a-j} \xi_{j+1}^b h_{i-a}(\xi_1, \ldots, \xi_{a+1}) h_{k+a-b-j}(\xi_{a+1}, \ldots \xi_{j}) \\ &=& \xi_{j+1}^k h_{i-j}(\xi_1, \ldots, \xi_{j+1}) + \sum_{b=0}^{k-1} \xi_{j+1}^b \sum_{a=0}^{j-1} h_{i-a}(\xi_1, \ldots, \xi_{a+1}) h_{k+a-b-j}(\xi_{a+1}, \ldots \xi_{j}) \\ &=& \xi_{j+1}^k h_{i-j}(\xi_1, \ldots, \xi_{j+1}) + \sum_{b=0}^{k-1} \xi_{j+1}^b P(i,j-1,k-b-1, \vec{\xi}) \\ &=& \xi_{j+1}^k h_{i-j}(\xi_1, \ldots, \xi_{j+1}) + \sum_{b=0}^{k-1} \xi_{j+1}^b h_{i+k-b-j}(\xi_1, \ldots, \xi_j) \\ &=& h_{i+k-j}(\xi_1, \ldots, \xi_{j+1}) \end{eqnarray*}

By design, we have $(L_h U_h)_{i,j} = P(i,j,k, \vec{\xi})$, with the difference in upper limit of the sum being trivial due to the term $h_{k+a-j}(\xi_{a+1}, \ldots \xi_{j+1})$. Then $\det L_h = 1$ and $\det U_h = h_k(\xi_1) \cdots h_k(\xi_n) = (\xi_1 \cdots \xi_n)^k$.
$\blacksquare$

[1] Louis Comtet, Nombres de Stirling généraux et fonctions symétriques, C. R. Acad. Sc. Paris, t. 275 (1972), Sér. A 747–750.
[2] Hopkins, Speyer, Taylor, Zaimi, Matrices of combinatorial sequences that are inverse in two ways , MO question 418266 and answers

$\endgroup$
6
2
$\begingroup$

I realize you've seen a solution to $\det\binom{n+i-1}j=\binom{2n-1}n$ earlier. But, I just wanted to give it a different proof, in case you encounter similar questions. The method is called Dodgson's condensation. It runs as follows: suppose you consider a matrix $M_n$ with entries $m_{i,j}$ for $1\leq i,j\leq n$. Now, let $M_n(a,b)$ be the matrix constructed by shifting indices $i\rightarrow i+a$ and $j\rightarrow j+b$; that is, $m_{i+a,j+b}$. Then, the theorem states that $$\vert M_n(a,b)\vert=\frac{\vert M_{n-1}(a,b)\vert \vert M_{n-1}(a+1,b+1)\vert - \vert M_{n-1}(a+1,b)\vert \vert M_{n-1}(a,b+1)\vert}{\vert M_{n-2}(a+1,b+1)\vert}. \tag1$$ Here, $\vert M\vert$ stands for the determinant of $M$.

In the present case, let $M_n(a,b)$ be the matrix of entries $\binom{i+a}{j+b}$, for $1\leq i,j\leq n$. We claim that $$\vert M_n(a,b)\vert=\prod_{k=0}^b\frac{\binom{n+a-k}n}{\binom{n+k}k}. \tag2$$ The proof is simple. Just plug-in the RHS of (2) into (1), in place of $\vert M_n(a,b)\vert$, and verify (1) holds true. This is a routine check. Finally, just check initial conditions, say for $n=1$ and $n=2$. $\square$

Remark. Your original problem is the case $a=n-1, b=0$.

$\endgroup$
1
  • $\begingroup$ Wow, Dodgson is Lewis Carroll, the author of "Alice in Wonderland". Thank you. $\endgroup$
    – BillyJoe
    May 26 at 21:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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