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:[a]-092609-Binomial Matrix (II).nb


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. 
   

Advertisements

Actions

Information




%d bloggers like this: