Inverse of the $n$-by-$n$ matrix $(a_{jk})$ where $a_{jk} = \binom{j-1}{k-1}$

Question

I have an interesting problem which can be solved by Induction and Gaussian Elimination, but due to the nice structure of the matrix, I think there can be many more approaches.

Here's the problem :

Let $$ A = (a_{jk})_{n \times n} $$

where $\displaystyle a_{jk} = \dbinom{j-1}{k-1}$ (by convention, this is $0$ for $k>j$).

Prove that

$$ A^{-1} = ((-1)^{j+k} a_{jk})_{n \times n} $$

The small alphabets along with subscripts denote the element of the $j^{\text{th}}$ row and $k^{\text{th}}$ column of the matrix.

I think this problem might have deep links to theorems of linear algebra due to the nice structure of inverse. I'm specifically seeking an answer that makes such a connection.

Thanks in advance.

Answer 1

Here are three methods (3 is a strictly worse proof than 1, but it's amusing):

1. Combinatorics: Rearrange $$a_{ij}a_{jk}=(-1)^{j+k}\binom{i-1}{j-1}\binom{j-1}{k-1}=(-1)^{k+j}\frac{(i-1)!}{(i-j)!(j-k)!(k-1)!}$$ and to be clearer, set $\alpha=i-1,\beta=j-1,\gamma=k-1$. Then we want $$\delta_{\alpha \gamma}=\sum_\beta (-1)^{\alpha+\gamma} \binom{\alpha}{\alpha-\beta, \beta-\gamma, \gamma}=\pm \binom{\alpha}{\alpha-\gamma, 0, \gamma}\pm \binom{\alpha}{\alpha-\gamma-1, 1, \gamma}\pm \cdots$$ But this is $(-1)^\gamma$ times the number of monomials in $$(-x+y-z)^\alpha$$ with $z$-term $z^\gamma$. That is, it is the $z^\gamma$ coefficient of $$(-1+1-z)^\alpha$$ i.e. it is $\delta_{\alpha \gamma}$.
2. mercio's observation: Consider the vector space of polynomials in $x$ with degree less than $n$. Then the linear map $x\to x+1$ sends $$x^k\longrightarrow x^k+\binom{k}{1}x^{k-1}+\cdots+x^0$$ so with respect to basis $e_k=x^{k-1}$, it has matrix $$\left(\binom{i-1}{j-1}\right)_{i,j}$$ Similarly, its inverse $x\to x-1$ has matrix $$\left((-1)^{i+j}\binom{i-1}{j-1}\right)_{i,j}$$
3. Jacobi's formula: Recall that if $M$ is a matrix and $M(t)=M+tE_{\alpha \beta}$ (add $t$ to the $\alpha,\beta$ entry), then $$\frac{d \det(M(t))}{d t}=\left( \text{adj}(M)\right)_{\beta, \alpha}$$ In this case, $\det (A)=1$, so in particular, $\text{adj}A=A^{-1}$. One can show that $$\det(A+tE_{ij})=1+(-1)^{i+j}t\binom{j-1}{i-1}$$ which gives $$(A^{-1})_{i,j}=(\text{adj}(A))_{i,j}=\frac{d \det (M+tE_{ji})}{dt}=(-1)^{i+j}\binom{i-1}{j-1}$$

To prove the determinant formula, look at the matrix $A+tE_{ij}$:

The green line are the $1$'s on the diagonal and the green dot has coefficient $t$. The white is zero and the grey is mess. Its determinant is the same as the determinant of the small red square's. The red square is zoomed in to on the left:

The term in the determinant sum not including the green dot is $1$. The term involving it is $(-1)^{i+j} t \det T^{ij}$, where $T^{ij}$ is the matrix with the green column and row removed. Calculate $\det T^{ij}$ by considering which row of the last column (the pink dot) is summed over: $$\det T^{i,j}=\pm \binom{j-1}{i-1} \pm \cdots \pm \binom{j-1}{i-1+n}\det (T^{i,n+i})\pm \cdots \pm \binom{j-1}{j-2}\det (T^{i,j-1})$$ since the lower blue box has determinant $1$, and the upper, $\det (T^{i,n+i})$. By induction, $$\det T^{i,j}=\pm \binom{j-1}{i-1} \pm \cdots \pm \binom{j-1}{i-1+n}\binom{i-1+n}{i-1}\pm \cdots \pm \binom{j-1}{j-2}\binom{j-2}{i-1}$$ But (after following the signs) this is just a sum of the form as in $(1)$, with a $\binom{j-1}{i-1}$ term missing! Thus $$\det T^{i,j}=\binom{j-1}{i-1}$$