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} $$
inverse of a matrix
-
7That matrix has $N+1$ rows and $N$ columns. – 2011-04-15
-
7Now it has $N$ rows and $N+1$ columns... – 2011-04-15
-
0What's the motivation and the background of the question? – 2011-04-15
-
0Sorry 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 http://math.stackexchange.com/questions/32490/any-pattern-here-revised – 2011-04-15
-
0You may find http://mathoverflow.net/questions/49878/inverse-of-a-matrix-with-binomial-coefficients helpful. – 2011-04-15
1 Answers
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.)
-
2@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. – 2011-04-15
-
0Sweet answer! $$$$ – 2011-09-30