# inverse of a matrix

What is the inverse of the following matrix ? $$\begin{bmatrix} \binom{N}{0} &\binom{N+1}{0} &... &\binom{2N-1}{0} \\ \binom{N}{1} &\binom{N+1}{1} &... &\binom{2N-1}{1}\\ ...& ... &... &... \\ \binom{N}{N-1} &\binom{N+1}{N-1} &... &\binom{2N-1}{N-1} \end{bmatrix}$$

-
That matrix has $N+1$ rows and $N$ columns. –  Jonas Meyer Apr 15 '11 at 2:53
Now it has $N$ rows and $N+1$ columns... –  Sangchul Lee Apr 15 '11 at 3:22
What's the motivation and the background of the question? –  Jack Apr 15 '11 at 4:27
Sorry folks. I Hope it is now N*N, if not feel free to add/remove few columns at the end :) @Jack: It came up in an optimization problem, and I got fascinated by the fact that the inverse elements are also integers. (at least for some specific N), for some related problems please see this math.stackexchange.com/questions/32490/any-pattern-here-revised –  mghandi Apr 15 '11 at 5:11
You may find mathoverflow.net/questions/49878/… helpful. –  Gerry Myerson Apr 15 '11 at 6:13

## 1 Answer

Your matrix, call it $A_N$, can be factorized as $B_N C_N$, where $$B_N = \left[ \binom{N}{i-j} \right]_{i,j=0,\dots,N-1}$$ and $$C_N = \left[ \binom{j}{j-i} \right]_{i,j=0,\dots,N-1}.$$ For example, for $N=5$ this will be $$\left( \begin{array}{lllll} 1 & 1 & 1 & 1 & 1 \\ 5 & 6 & 7 & 8 & 9 \\ 10 & 15 & 21 & 28 & 36 \\ 10 & 20 & 35 & 56 & 84 \\ 5 & 15 & 35 & 70 & 126 \end{array} \right) = \left( \begin{array}{lllll} 1 & 0 & 0 & 0 & 0 \\ 5 & 1 & 0 & 0 & 0 \\ 10 & 5 & 1 & 0 & 0 \\ 10 & 10 & 5 & 1 & 0 \\ 5 & 10 & 10 & 5 & 1 \end{array} \right) \left( \begin{array}{lllll} 1 & 1 & 1 & 1 & 1 \\ 0 & 1 & 2 & 3 & 4 \\ 0 & 0 & 1 & 3 & 6 \\ 0 & 0 & 0 & 1 & 4 \\ 0 & 0 & 0 & 0 & 1 \end{array} \right).$$ The inverses of these factors are $$B_N^{-1} = \left[ (-1)^{i+j} \binom{N-1+i-j}{N-1} \right]_{i,j=0,\dots,N-1}$$ and $$C_N^{-1} = \left[ (-1)^{i+j} \binom{j}{j-i} \right]_{i,j=0,\dots,N-1}.$$ Then $A_N^{-1}=C_N^{-1} B_N^{-1}$ of course, but I don't know if that simplifies to something nice. (I didn't find any hits in OEIS.) In any case, the fact that $B_N$ and $C_N$ have determinant one (since they are triangular with ones on the diagonal) explains why $A_N^{-1}$ has integer entries.

Edit: Here's the picture promised in my comment. It illustrates the situation for $N=5$.

Entry $(i,j)$ (counting from zero) in the matrix $A_5 = B_5 C_5$ equals the number of paths through the directed graph from source number $i$ on the left to sink number $j$ on the right.

Incidentally, the network shows that $B_N$ can be factorized further, just for fun: $$B_5 = \left( \begin{array}{lllll} 1 & 0 & 0 & 0 & 0 \\ 4 & 1 & 0 & 0 & 0 \\ 6 & 4 & 1 & 0 & 0 \\ 4 & 6 & 4 & 1 & 0 \\ 1 & 4 & 6 & 4 & 1 \end{array} \right) \left( \begin{array}{lllll} 1 & 0 & 0 & 0 & 0 \\ 1 & 1 & 0 & 0 & 0 \\ 1 & 2 & 1 & 0 & 0 \\ 1 & 3 & 3 & 1 & 0 \\ 1 & 4 & 6 & 4 & 1 \end{array} \right).$$ (The first factor corresponds to the first four blue arrows, and the second factor to the next four blue arrows.)

-
+1: very nice :-) –  joriki Apr 15 '11 at 10:06
@joriki: Thanks! Another nice thing is that these matrices are path matrices for planar networks, so that one can compute subdeterminants using the Karlin–McGregor–Lindström–Gessel–Viennot Theorem (or whatever one wants to call it), and the factorization corresponds to concatenating the networks. I'll see if I can make a picture to explain that later. –  Hans Lundmark Apr 15 '11 at 10:28
Sweet answer!  –  The Chaz 2.0 Sep 30 '11 at 1:48