14
$\begingroup$

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.

$\endgroup$
9
  • 3
    $\begingroup$ When asked to prove one matrix is the inverse of another, just check their product is the identity. In this case, you only need prove a combinatorial identity. $\endgroup$
    – J.G.
    Commented Apr 6, 2018 at 6:46
  • $\begingroup$ @J.G. That's not what I'm looking for. How would you derive it and what's the reason for this neat expression. I'm thinking it is related to some theorem of Linear Algebra. $\endgroup$
    – Henry
    Commented Apr 6, 2018 at 9:03
  • $\begingroup$ How to understand $a_{jk}$ if $k>j$, for example $2 \choose 4$ ? $\endgroup$
    – Widawensen
    Commented Apr 6, 2018 at 9:32
  • 8
    $\begingroup$ aren't those the matrices associated to the maps induced by $x \mapsto x \pm 1$ on the space of polynomials of degree less than $n$ ? $\endgroup$
    – mercio
    Commented Apr 6, 2018 at 11:17
  • 1
    $\begingroup$ @Henry: OK, had a brief look. It seems the answer of Meow has it pretty well covered, but I'll give it some thought and if I can add anything else, I'll post. Thanks again. Cheers! $\endgroup$ Commented Apr 6, 2018 at 19:51

1 Answer 1

15
+25
$\begingroup$

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}$: enter image description here

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:

enter image description here 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}$$

$\endgroup$
2
  • $\begingroup$ your method 3 gives a result that is way too strong to be true. $\det(M+tE_{ij})$ has more then two terms. $\endgroup$
    – mercio
    Commented Apr 7, 2018 at 7:29
  • $\begingroup$ @mercio I've corrected it, and it seems better now. $\endgroup$
    – Pulcinella
    Commented Apr 7, 2018 at 11:22

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .