## BINOMIAL MATRIX (II)

24 09 2009

If $A_n$ is an square matrix with elements:

$\displaystyle a_{i,j}=\binom{i+k}{j}$

Then:

$\displaystyle |A_{n}|=\binom{n+k}{n}$

Proof:

The $\displaystyle A_{n}$ matrix can be decomposed as the product of a lower triangular matrix, $\displaystyle L_{n}$, and an upper triangular matrix, $\displaystyle U_{n}$:

$\displaystyle A_{n}=L_{n}*U_{n}$

Example:

$\displaystyle A_{3}=\left(\begin{array}{ccc} 1+k & \frac{1}{2} k (1+k) & \frac{1}{6} (-1+k) k (1+k) \\ 2+k & \frac{1}{2} (1+k) (2+k) & \frac{1}{6} k (1+k) (2+k) \\ 3+k & \frac{1}{2} (2+k) (3+k) & \frac{1}{6} (1+k) (2+k) (3+k) \end{array} \right)$

$\displaystyle L_{3}=\left(\begin{array}{ccc} 1 & 0 & 0 \\ \frac{2+k}{1+k} & 1 & 0 \\ \frac{3+k}{1+k} & \frac{2 (3+k)}{2+k} & 1 \end{array} \right)$

$\displaystyle U_{3}=\left( \begin{array}{ccc} 1+k & \frac{1}{2} k (1+k) & \frac{1}{6} (-1+k) k (1+k) \\ 0 & \frac{2+k}{2} & \frac{1}{3} k (2+k) \\ 0 & 0 & \frac{3+k}{3}\end{array} \right)$

After some math “plumbing”, we can propose as decomposition:

$\displaystyle l_{i,j}=\frac{i + k}{j + k} \binom{i - 1}{j - 1}$

$\displaystyle u_{i,j}=\binom{j - 1}{i - 1} \binom{i + k}{j} {\binom{k + i - 1}{i - 1}}^{-1}$

If this decomposition is correct then the matrix product should be $\displaystyle a_{i,j}$:

$\displaystyle \sum_{r=1}^n{l_{i,r} \cdot u_{r,j}}=\sum_{r=1}^{min(i,j)}{l_{i,r} \cdot u_{r,j}}$

Where:

$\displaystyle l_{i,r}=\frac{i + k}{r + k} \binom{i - 1}{r - 1}$

$\displaystyle u_{r,j}=\binom{j - 1}{r - 1} \binom{r + k}{j} {\binom{k + r - 1}{r - 1}}^{-1}$

$\displaystyle l_{i,r} \cdot u_{r,j}$, can be simplified, changing the binomial coefficient to the gamma function, as:

$\displaystyle l_{i,r} \cdot u_{r,j}=\frac{(i+k)\cdot r}{i \cdot j}\cdot\binom{i}{r}\binom{k}{j-r}$

$\displaystyle \sum_{r=1}^{min(i,j)}{l_{i,r} \cdot u_{r,j}}=\sum_{r=1}^{min(i,j)}{\frac{(i+k) r}{i \cdot j}\cdot\binom{i}{r}\binom{k}{j-r}}=\\ \frac{(i+k)}{i \cdot j} \cdot \sum_{r=1}^{min(i,j)}{r\binom{i}{r}\binom{k}{j-r}}$

This last expression can be simplified, with the help of:

$\displaystyle r\binom{i}{r}=i \binom{i-1}{r-1}$, the Vandermonde´s convolution (see reference [2]), and the absortion formula (see reference [3]), to:

$\displaystyle \sum_{r=1}^{min(i,j)}{l_{i,r} \cdot u_{r,j}}=\binom{i+k}{j}=a_{i,j}$

Now we can calculate easily $|A_n|$, because the LU-decomposition used is the so called Doolittle decomposition, where the matrix $L_{n}$ has all ones on its diagonal.

$\displaystyle |A_{n}|=\prod_{i=1}^{n}{l_{i,i}*u_{i,i}}=\prod_{i=1}^{n}{u_{i,i}}=\prod_{i=1}^{n}{\frac{i+k}{i}}=\binom{n+k}{k}=\binom{n+k}{n}$

Archives:

References:

[1]-John H. Mathews and Kurtis Fink, 2004 – Module for PA = LU Factorization with Pivoting
[2]-Matthew Hubbard and Tom Roby – Pascal’s Triangle From Top To Bottom – the binomial coefficient website– Catalog #: 3100003.
[3]-Matthew Hubbard and Tom Roby – Pascal’s Triangle From Top To Bottom – the binomial coefficient website– Catalog #: 2400002.