KAIST POW 2012-20 : the Inverse of an Upper Triangular Matrix

the Inverse of an Upper Triangular Matrix

 Let $A=(a_{ij})$ be an $n \times n$ upper triangular matrix such that $$a_{ij} = \binom{n-i+1}{j-i}$$ for all $i \leq j$. Find the inverse matrix of $A$.

 Lemma. For $i < n$, $$\sum_{k=i}^n (-1)^{n-k}\binom{k}{i} \binom{n}{k} = 0$$

 Proof. Let $B=(b_{ij})$ be an $n \times n$ upper triangular matrix such that $$b_{ij} = (-1)^{j-i} \binom{n-i+1}{j-i}$$ for all $i \leq j$. Our claim is that $B$ is the inverse matrix of $A$. Let $C=AB=(c_{ij})$. This is clear to show that $C$ is upper triangular and its diagonal entries are 1. So it is enough to show that $c_{ij}=0$ for all $i < j$. Note that $$c_{ij}=\sum_{k=i}^{j} (-1)^{k-i}\binom{n-i+1}{k-i} \binom{n-k+1}{j-k}$$ By letting $m=n-k+1$, we have $$c_{ij}= \sum_{m=n-j+1}^{n-i+1} (-1)^{n-m+1-i} \binom{n-i+1}{n-i+1-m} \binom{m}{m-n+j-1}$$$$ =\sum_{m=n-j+1}^{n-i+1} (-1)^{n-m+1-i} \binom{n-i+1}{m} \binom{m}{n-j+1}=0$$ by lemma above. That is, $C=AB=I_n$. Therefore, $B=A^{-1}$

 Proof of lemma. By binomial theorem, $$(x-1)^n = \sum_{k=0}^n (-1)^k \binom{n}{k} x^k $$ Differentiating $i$ times, we get $$n(n-1)\cdots (n-i+1)(x-1)^{n-i} = \sum_{k=i}^n (-1)^{n-k} k(k-1)\cdots (k-i+1) \binom{n}{k} x^k$$ Substituting $x=1$ and dividing by $i!$, we get the equation we want.