# 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

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.)
Sweet answer!  – The Chaz 2.0 Sep 30 '11 at 1:48