## BINOMIAL MATRIX (I)

22 09 2009

If we use yesterday´s idea, with little variations, we can create new expressions for matrices with elements related to binomial coefficients, for instance:

Let be $U_n$ an square matrix with elements:

$\displaystyle u_{i,j}=\binom{j}{i}$

$U_n$ is an upper triangular matrix with all its diagonal elements equal to $1$, and similar to Pascal´s triangle.(That I prefer to name Tartaglia´s Triangle)

Example:

$U_{10}= \left( \begin{array}{cccccccccc} 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 \\ 0 & 1 & 3 & 6 & 10 & 15 & 21 & 28 & 36 & 45\\ 0 & 0 & 1 & 4 & 10 & 20 & 35 & 56 & 84 & 120 \\ 0 & 0 & 0 & 1 & 5 & 15 & 35 & 70 & 126 & 210 \\ 0 & 0 & 0 & 0 & 1 & 6 & 21 & 56 & 126 & 252 \\ 0 & 0 & 0 & 0 & 0 & 1 & 7 & 28 & 84 & 210 \\ 0 & 0 & 0 & 0 & 0 & 0 & 1 & 8 & 36 & 120 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 9 & 45 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 10 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 \end{array} \right)$

And, of course:

$|U_{n}|=1$

If we multiply this matrix by its transposed one, then we get a symmetrical matrix with:

$|A_{n}|=|U_{n}^{T}*U_{n}|=|U_{n}|^2=1$

Example:

$A_{10}=U_{10}^{T}*U_{10}$

$\displaystyle A_{10}=\\ \\ \left( \begin{array}{cccccccccc} 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 \\ 2 & 5 & 9 & 14 & 20 & 27 & 35 & 44 & 54 & 65 \\ 3 & 9 & 19 & 34 & 55 & 83 & 119 & 164 & 219 & 285 \\ 4 & 14 & 34 & 69 & 125 & 209 & 329 & 494 & 714 & 1000 \\ 5 & 20 & 55 & 125 & 251 & 461 & 791 & 1286 & 2001 & 3002 \\ 6 & 27 & 83 & 209 & 461 & 923 & 1715 & 3002 & 5004 & 8007 \\ 7 & 35 & 119 & 329 & 791 & 1715 & 3431 & 6434 & 11439 & 19447 \\ 8 & 44 & 164 & 494 & 1286 & 3002 & 6434 & 12869 & 24309 & 43757 \\ 9 & 54 & 219 & 714 & 2001 & 5004 & 11439 & 24309 & 48619 & 92377 \\ 10 & 65 & 285 & 1000 & 3002 & 8007 & 19447 & 43757 & 92377 & 184755 \end{array}\right)$

So we have constructed a new matrix with determinant equal to one:

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

$\displaystyle a_{i,j}=\sum_{r=1}^{min(i,j)}{\binom{i}{r} \binom{j}{r}}=-1+\sum_{r=0}^{i}{\binom{i}{r} \binom{j}{r}}=\binom{i+j}{i}-1=\binom{i+j}{j}-1$

Note(i): For a proof on binomial identity see references [1] or [2]

OEIS Related Sequences:

 Row/Column Sequence 1 A000027 2 A000096 3 A062748 4 A063258 5 A062988 6 A124089 7 A124090 8 A165618 9 A035927 10 –

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.