Saturday 24 October 2009

BINOMIAL MATRIX (III)

If $latex A_n$ is an square matrix with elements:

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

Then:

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

Proof:

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

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

Example:

$latex \displaystyle A_{3}=\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)$

$latex \displaystyle L_{3}= \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)$

$latex \displaystyle U_{3}=\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:

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

$latex \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 $latex a_{i,j}$:

$latex \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:

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

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

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

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

$latex \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}} = $

$latex \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}=$

$latex \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) $latex \displaystyle \sum_{r}^{}{\binom{l}{r+m} \binom{s}{r+n}}=\binom{l+s}{l-m+n}$

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


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

$latex \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:
[a]-092609-Binomial Matrix (III).nb

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.