## BINOMIAL MATRIX (III)

24 10 2009

If $A_n$ is an square matrix with elements:

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

Then:

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

Proof:

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

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

Example:

$A_{3}=$

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

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

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

After some trial and error puzzle, we can propose as decomposition:

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

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

If this decomposition is the correct one then the matrix product should be $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{r}{i} \binom{i+k+1}{r+k+1}$

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

$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{j+k+1}{i}\binom{j-1}{r-1}\binom{i+k+1}{r+k+1}$

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

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

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

In the last part of the proof, involving binomial coefficients, we have used: (See ref [1] and [2])

1) $\displaystyle \sum_{r}^{}{\binom{l}{r+m} \binom{s}{r+n}}=\binom{l+s}{l-m+n}$

2) $\displaystyle r\binom{i}{r}=i \binom{i-1}{r-1}$

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} \cdot u_{i,i}}=\prod_{i=1}^{n}{u_{i,i}}=\prod_{i=1}^{n}{\frac{i+k+1}{i}}=\binom{n+k+1}{n}$

Archives:

References:

[1]-Ronald L. Graham, Donald E. Knuth, and Oren Patashnik (Reading, Massachusetts: Addison-Wesley, 1994 – Concrete Mathematics – Identity (5.32) in Table 169.
[2]-Matthew Hubbard and Tom Roby – Pascal’s Triangle From Top To Bottom – the binomial coefficient website– Catalog #: 3100004.