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:[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.
 
  

Advertisements

Actions

Information




%d bloggers like this: