6
$\begingroup$

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} $

  • 0
    You may find http://mathoverflow.net/questions/49878/inverse-of-a-matrix-with-binomial-coefficients helpful.2011-04-15

1 Answers 1

14

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$.

Planar network

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.)

  • 0
    Sweet answer! $$2011-09-30