# determinant of a matrix with binomial coefficient entries

I trying to prove a statement, which boils down to showing that the determinant of a specific matrix is nonzero. I use the convention that $\binom{n}{k} = 0$ if $k > n$ or $k < 0$. Let $k,l$ be natural numbers such that $k \le l$. Then the $n\times n$-Matrix $A$ is defined to have the entries

$a_{ij} = \binom{l}{k +i - j}$. So it looks like $A = \left( \begin{array}{cccccc} \binom{l}{k} & \cdots & \binom{l}{0} & 0 & \cdots & 0 \\ \vdots & \ddots & & \ddots & \ddots & \vdots \\ \binom{l}{l} & & \ddots & & \ddots & 0 \\ 0& \ddots && \ddots & & \binom{l}{0}\\ \vdots&\ddots&\ddots&&\ddots&\vdots\\ 0&\cdots&0& \binom{l}{l} & \cdots & \binom{l}{k} \end{array}\right)$. Clearly the cases $k = l$ and $k = 0$ are trivial, since $A$ is then triangular. My first idea was to use the formula $\binom{r}{s} = \binom{r-1}{s-1} + \binom{r}{s}$ and add columns/rows to each other. But that does not work out that well...

So if anyone has any ideas, or this matrix is known to be invertible, I would be very thankful.

• Do you have any results for values of determinant for some especial cases of matrices such as $3 \times 3$ for some values of $l$ and $k$. If you have these information please add to your question as an example. Thanks. Mar 7 '18 at 17:43
• I considered the example $A = \left( \begin{array}{ccc} \binom{2}{1} & \binom{2}{0} & 0 \\ \binom{2}{2} & \binom{2}{1} & \binom{2}{0} \\ 0 & \binom{2}{2} & \binom{2}{1} \\ \end{array} \right)$ which has determinant $\operatorname{det}(A) = 2^3 - 2 - 2 = 4$. But I did not calculate a lot of examples yet. Mar 7 '18 at 21:46
• Your determinant is the number of all semistandard tableaux of shape $\left(k,k,\ldots,k\right)$ (with $l$ copies of $k$) and entries in $\left\{1,2,\ldots,l\right\}$. There is a hook-content formula for that. Mar 7 '18 at 22:18
• @darijgrinberg Could you perhaps write a short answer with more explanation? Mar 8 '18 at 17:18
• @fredgoodman: Please remind me again this weekend if I haven't until then. Mar 8 '18 at 23:26

Answer: The determinant of $A$ is $\dfrac{H\left(k\right) H\left(l-k\right) H\left(n\right) H\left(l+n\right)}{H\left(l-k+n\right) H\left(n+k\right) H\left(l\right)}$, where we are using the notation $H\left(m\right)$ for the hyperfactorial $\left(m-1\right)! \left(m-2\right)! \cdots 1! 0!$ of a nonnegative integer $m$.

(There are various other ways to express the answer, but the above is the most compact.)

1st proof. Theorem 8 in my note A hyperfactorial divisibility says that for every nonnegative integers $a$, $b$ and $c$, we have \begin{align*} & \dfrac{H\left( a\right) H\left( b\right) H\left( c\right) H\left( a+b+c\right) }{H\left( b+c\right) H\left( c+a\right) H\left( a+b\right) }\\ & =\det\left( \left( \dbinom{a+b+i-1}{a+i-j}\right) _{1\leq i\leq c,\ 1\leq j\leq c}\right) =\det\left( \left( \dbinom{a+b}{a+i-j}\right) _{1\leq i\leq c,\ 1\leq j\leq c}\right) . \end{align*} Applying this to $a = k$, $b = l-k$ and $c = n$ (noticing that $b$ is nonnegative because $k \leq l$), we obtain \begin{align*} &\dfrac{H\left(k\right) H\left(l-k\right) H\left(n\right) H\left(l+n\right)}{H\left(l-k+n\right) H\left(n+k\right) H\left(l\right)} \\ & =\det\left( \left( \dbinom{l+i-1}{k+i-j}\right) _{1\leq i\leq n,\ 1\leq j\leq n}\right) =\det\left( \left( \dbinom{l}{k+i-j}\right) _{1\leq i\leq n,\ 1\leq j\leq n}\right) . \end{align*} But the matrix on the right(most) side of this equality is exactly your $A$; so the Answer is proven.

2nd proof (sketched). The question has a combinatorial interpretation in terms of nonintersecting lattice paths on a rectangular grid, or semistandard Young tableaux, or Schur functions. These three objects are essentially different languages for the same argument; I will use the third since it is the easiest to write about.

I'll assume that you are familiar with the concept of symmetric functions (see, e.g., Chapter 2 of Darij Grinberg and Victor Reiner, Hopf algebras in combinatorics, or Mark Wildon, An involutive introduction to symmetric functions, or Chapter 7 of Richard Stanley, Enumerative Combinatorics, volume 2). In particular, I'll use the notations common in this subject, such as $s_\lambda$ for a Schur function and $e_i$ for an elementary symmetric function.

Set $b = l-k$; this is a nonnegative integer since $k \leq l$.

Let $\lambda$ be the partition $\left(n^b\right)$, which is to be understood as a shorthand for $\left(\underbrace{n,n,\ldots,n}_{b\text{ terms}}\right)$. The transpose (aka conjugate) $\lambda^t$ of this partition $\lambda$ is then $\left(b^n\right)$ (understood similarly). The Jacobi-Trudi formula (the one that uses elementary symmetric functions) thus says that $$s_\lambda = \det \left( \left( e_{b-i+j} \right) _{1\leq i\leq n,\ 1\leq j\leq n} \right) .$$ Now, substitute $\underbrace{1,1,\ldots,1}_{l \text{ entries}},0,0,0,\ldots$ for the countably many indeterminates into this equality. This substitution transforms each elementary symmetric function $e_p$ into $e_p\left(\underbrace{1,1,\ldots,1}_{l \text{ entries}},0,0,0,\ldots\right) = \dbinom{l}{p}$. Thus, the equation transforms into $$s_\lambda\left(\underbrace{1,1,\ldots,1}_{l \text{ entries}},0,0,0,\ldots\right) = \det \left( \left( \dbinom{l}{b-i+j} \right) _{1\leq i\leq n,\ 1\leq j\leq n} \right) .$$ Since each $i$ and $j$ satisfy $\dbinom{l}{b-i+j} = \dbinom{l}{k+i-j}$ (indeed, this follows from the symmetry of Pascal's triangle, because $l - \left(b-i+j\right) = k+i-j$), this rewrites as $$s_\lambda\left(\underbrace{1,1,\ldots,1}_{l \text{ entries}},0,0,0,\ldots\right) = \det \left( \left( \dbinom{l}{k+i-j} \right) _{1\leq i\leq n,\ 1\leq j\leq n} \right) = \det A .$$ It remains to compute the left hand side.

But the combinatorial definition of $s_\lambda$ shows that $s_\lambda\left(\underbrace{1,1,\ldots,1}_{l \text{ entries}},0,0,0,\ldots\right)$ is just the number of semistandard Young tableaux of shape $\lambda$ with entries in $\left\{1,2,\ldots,l\right\}$. For this number, there is a formula (known as Weyl's character formula in type A; see, e.g., https://mathoverflow.net/questions/106606/new-formula-for-counting-ssyts ), which can be written as $$s_\lambda\left(\underbrace{1,1,\ldots,1}_{l \text{ entries}},0,0,0,\ldots\right) = \dfrac{1}{H\left(l\right)} \prod_{1 \leq i < j \leq l} \left(\left(\lambda_i - i\right) - \left(\lambda_j - j\right)\right) ,$$ where $\lambda_p$ is the $p$-th entry of $\lambda$ (so, in our case, $\lambda_p = b$ if $p \leq n$, and otherwise $\lambda_p = 0$). It takes a while to massage the right hand side so as to look like the Answer given above (the first step is to observe that the only factors in the product that are distinct from $1$ are those with $1 \leq i \leq n$ and $n < j \leq l$, so that all other factors can be discarded), but it isn't difficult (you just need to check that two large products have the same factors).

• I appreciate for your valuable answer. Mar 14 '18 at 5:34
• Nice elegant answer. Do you have any idea how to get the inverse of that matrix? Mar 21 '18 at 15:09

I am sure that the full answer is given by Darij Grinberg in his comment. This is indeed a problem in combinatorics.

If, however, all you want to see is that your determinant is non-zero then this may help.

First, for convenience, swap $k$ and $\ell-k$. Set $N=n+k$. Label all rows, columns, bases starting at $0$.

Then your determinant is an $n\times n$ minor of the $N\times N$ matrix $M$ where $m_{ij}=\binom{\ell}{j-i}$; to be precise it is the minor corresponding to the pair $\{1,2,\dots,n\}\times \{N-n, \dots, N-2,N-1\}$.

Now the matrix $M$ is just $(1+N)^\ell$, where $N$ is the matrix with $1$'s on the superdiagonal and $0$ elsewhere. So $M^{(n)}$, the matrix formed from the $n\times n$ minors of $M$, can be expressed $$M^{(n)}=\left((1+N)^\ell\right)^{(n)}=\left((1+N)^{(n)}\right)^\ell$$ by the usual rule.

Write $a_{I,J}$ for the entry of $(1+N)^{(n)}$ labelled by the pair $(I,J)$ of $n$-subsets of $\{0,\dots, N-1\}$, and $b_{I,J}$ for the corresponding entry of $M^{(n)}$. We have then $$b_{I,J}= \sum_{I_1,I_2,\dots, I_{\ell-1}} a_{I,I_1}a_{I_1,I_2}\dots a_{I_{\ell-1},J}.$$

Now we need to say something about the $a_{I,J}$. It is easiest to proceed a bit more abstractly and so let $e_0,\dots,e_{N-1}$ be an ordered basis of the underlying vector space, and let $e_N=0$. We can suppose that our linear map $N$ acts as $e_i N=e_{i+1}$ for all $i=0,1,\dots, N-1$.

Now consider the action of $M=1+N$ on the $n$-th exterior products, ordered lexicographically. $$e_{i_1}\wedge e_{i_2}\wedge \dots \wedge e_{i_{n}} (1+N) = (e_{i_1}+e_{i_1+1})\wedge (e_{i_2}+e_{i_2+1})\wedge \dots \wedge(e_{i_{n}}+e_{i_{n}+1}).$$

As $i_1<i_2<\dots<i_n$ we have $i_1<i_1+1\leqslant i_2<i_2+1\leqslant i_3<\dots<i_n$. This means that when we expand the product on the right hand side all the terms are in canonical form, we need not perform any swaps; and each basis element can occur at most once.

Hence each $a_{I,J}$ is either $0$ or $1$.

We then have that each $b_{I,J}$ is a natural number.

To prove that the one we are interested in, the one with $I=\{1,2,\dots,n\}$, $J= \{N-n, \dots, N-2,N-1\}$, is non-zero we merely have to find a chain $I,I_1,I_2,\dots I_{\ell -1}, J$ with the $a_{I_s,I_{s+1}}=1$. This is left as an exercise for the reader.

Too long for comment and because of this I write it as an answer. With Maple calculations the following results are obtained: Let $l=2m$ for some positive integer $m$( for the case $l=2m+1$ we have similar process). Consider the variable $k'$ in the following form $$k'=\left\{ \begin{array}{} k & 1\leq k\leq m,\\ k-t & m<k\leq l-1, \end{array} \right.$$ where $t=k \pmod{m}$. Consider $A^{(l,k)}$ is $n \times n$ matrix with definition of your question, then the determinant of $A^{(l,k)}$ is $$\det(A^{(l,k)})=\frac{g(n,k')}{f(l,k)}$$ where $$\begin{array}{cc} g(n,k')=&(n+l-1)(n+l-2)^2(n+l-3)^3 \cdots (n+l-k'+1)^{k'-1} (n+l-k'+2)^{k'} \\ &\cdots (n+k'+1)^{k'} (n+k')^{k'} (n+k'-1)^{k'-1} \cdots (n+3)^3(n+2)^2(n+1) \end{array}$$ and $f(l,k)$ is a product of several factorial numbers that are depend on $l$( I cant obtain a direct relation for it). For instance,

$$\begin{array}{cc} f(l,1)=f(l,l-1)=(l-1)!,\\ f(l,2)=f(l,l-2)=(l-1)!(l-2)!,\\ f(l,3)=f(l,l-3)=\frac{(l-1)!(l-2)!(l-3)!}{2},\\ \end{array}$$

For example, consider $l=10$ and $1\leq k \leq 9$, then the determinant of an $n\times n$ matrix $A^{(l,k)}$ are

$$\begin{array}{ll} \det(A^{(10,1)})=\frac{1}{9!}\left( n+9 \right) \left( n+8 \right) \left( n+7 \right) \left( n+ 6 \right) \left( n+5 \right) \left( n+4 \right) \left( n+3 \right) \left( n+2 \right) \left( n+1 \right), \\ \det(A^{(10,2)})=\frac{1}{9!8!} \left( n+9 \right) \left( n+1 \right) \left( n+8 \right) ^{2} \left( n+7 \right) ^{2} \left( n+6 \right) ^{2} \left( n+5 \right) ^{ 2} \left( n+4 \right) ^{2} \left( n+3 \right) ^{2} \left( n+2 \right) ^{2},\\ \small{ \det(A^{(10,3)})=\frac{2}{9!8!7!} \left( n+9 \right) \left( n+1 \right) \left( n+8 \right) ^{2} \left( n+2 \right) ^{2} \left( n+5 \right) ^{3} \left( n+4 \right) ^{ 3} \left( n+3 \right) ^{3} \left( n+7 \right) ^{3} \left( n+6 \right) ^{3}},\\ \small{ \det(A^{(10,4)})=\frac{2}{9!8!7!5!} \left( n+9 \right) \left( n+1 \right) \left( n+8 \right) ^{2} \left( n+2 \right) ^{2} \left( n+7 \right) ^{3} \left( n+3 \right) ^{ 3} \left( n+5 \right) ^{4} \left( n+4 \right) ^{4} \left( n+6 \right) ^{4}},\\ \small{ \det(A^{(10,5)})=\frac{2}{9!8!7!5!5} \left( n+9 \right) \left( n+1 \right) \left( n+8 \right) ^{2} \left( n+2 \right) ^{2} \left( n+7 \right) ^{3} \left( n+3 \right) ^{ 3} \left( n+6 \right) ^{4} \left( n+4 \right) ^{4} \left( n+5 \right) ^{5}}, \\ \small{ \det(A^{(10,6)})=\frac{2}{9!8!7!5!} \left( n+9 \right) \left( n+1 \right) \left( n+8 \right) ^{2} \left( n+2 \right) ^{2} \left( n+7 \right) ^{3} \left( n+3 \right) ^{ 3} \left( n+5 \right) ^{4} \left( n+4 \right) ^{4} \left( n+6 \right) ^{4}},\\ \small{ \det(A^{(10,7)})=\frac{2}{9!8!7!} \left( n+9 \right) \left( n+1 \right) \left( n+8 \right) ^{2} \left( n+2 \right) ^{2} \left( n+5 \right) ^{3} \left( n+4 \right) ^{ 3} \left( n+3 \right) ^{3} \left( n+7 \right) ^{3} \left( n+6 \right) ^{3}},\\ \det(A^{(10,8)})=\frac{1}{9!8!} \left( n+9 \right) \left( n+1 \right) \left( n+8 \right) ^{2}\left( n+7 \right) ^{2} \left( n+6 \right) ^{2} \left( n+5 \right) ^{2} \left( n+4 \right) ^{2} \left( n+3 \right) ^{2} \left( n+2 \right) ^{2}, \det(A^{(10,9)})=\frac{1}{9!}\left( n+9 \right) \left( n+8 \right) \left( n+7 \right) \left( n+ 6 \right) \left( n+5 \right) \left( n+4 \right) \left( n+3 \right) \left( n+2 \right) \left( n+1 \right). \end{array}$$

I think if you can find a relation for $f(l,k)$ then by induction on $n$, you can prove the mentioned formula.

I attach its Maple source code. In Maple code, you can change the value of $l$ to see more examples!

For instance in your example the determinant of $n \times n$ matrix $A^{(2,1)}$ is $\det(A^{(2,1)})=n+1$.