BINOMIAL MATRIX (I)

A matrix related to Pascal’s triangle, also known as Tartaglia’s triangle
Math
Matrices
Combinatorics
Author

Enrique Pérez Herrero

Published

September 22, 2009

Figure 1: Niccolò Tartaglia (1572) [1]

1 Introduction

By applying yesterday’s idea1 with slight variations, we can derive new expressions for matrices whose elements are related to binomial coefficients.

Let U_n be a square matrix with entries:

u_{i,j} = \binom{j}{i} \tag{1}

U_n is an upper triangular matrix with all diagonal entries equal to 1, and it closely resembles Pascal’s triangle (which I prefer to call Tartaglia’s triangle)2.

2 Example matrix U_{10}

U_{10} = \begin{pmatrix} 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{pmatrix} \tag{2}

And, of course:

|U_{n}|=1 \tag{3}

Or in element wise notation:

\det\!\left[ \binom{i}{i} \right]_{i,j=1}^{n} = 1 \tag{4}

If we multiply this matrix by its transpose, we obtain a symmetric matrix with:

|A_{n}| = |U_{n}^{T} * U_{n}| = |U_{n}^{2}|=1 \tag{5}

3 Example matrix A_{10}

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) \\ \tag{6}

The most remarkable property of this symmetric matrix is that its determinant equals 1, making it a unimodular matrix.

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

\begin{aligned} 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} \\ &= \sum_{r=1}^{\min(i,j)} \binom{i}{r} \binom{j}{r} \\ &= -1 + \sum_{r=0}^{\min(i,j)} \binom{i}{r} \binom{j}{r} \\ &= -1 + \sum_{r=0}^{i} \binom{i}{r} \binom{j}{r} \\ &= -1 + \binom{i+j}{i} \\ &= \binom{i+j}{i} - 1 \end{aligned} \tag{7}

Alternatively, in element-wise notation:

\det\!\left[ \binom{i+j}{i} - 1 \right]_{i,j=1}^{n} = 1 \tag{8}

Note: For a proof of the binomial identity used above, see references [3] or [4].

References

1.
Galle P, Montanus BA, Plantijn C (1572) Portret van niccolò tartaglia. Nicolavs tartaglia brixianvs.
2.
Psychedelic Geometry (2009) Binomial matrix (i), 2009. Available from: https://psychedelic-geometry.blogspot.com/2009/09/binomial-matrix-i.html.
3.
Graham RL, Knuth DE, Patashnik O (1994) Concrete mathematics: A foundation for computer science, Reading, MA, Addison-Wesley.
4.
Hubbard M, Roby T (2006) Pascal’s triangle from top to bottom, 2006. Available from: https://www.merlot.org/merlot/viewMaterial.htm?id=86655.
5.
OEIS (1991) A000027: The positive integers. Also called the natural numbers, the whole numbers or the counting numbers, but these terms are ambiguous.
6.
OEIS (1991) A000096: A(n) = n*(n+3)/2.
7.
OEIS (2003) A062748: Fourth column (r=3) of FS(3) staircase array A062745.
8.
OEIS (2003) A063258: A(n) = binomial(n+5,4) - 1.
9.
OEIS (2003) A062988: A(n) = binomial(n+6,5) - 1.
10.
OEIS (2006) A124089: A(n) = binomial(n,6)-1.
11.
OEIS (2006) A124090: C(n,7)-1.
12.
OEIS (2010) A165618: A(n) = binomial(n+8,8) - 1.
13.
OEIS (1999) A035927: One less than number of n-multisets chosen from a 10-set.

Footnotes

  1. This article is a translation and update of the original post entitled BINOMIAL MATRIX (I), published on Tuesday, September 22, 2009, on the blog Psychedelic Geometry [2].↩︎

  2. Portret van Niccolò Tartaglia (1572). Gravure por Philips Galle. under CC0 1.0 Public Domain Dedication, Rijksmuseum y Wikimedia Commons, [1]↩︎