Pascal matrix

{{Short description|Infinite matrices with Pascal's triangle as elements}}

In matrix theory and combinatorics, a Pascal matrix is a matrix (possibly infinite) containing the binomial coefficients as its elements. It is thus an encoding of Pascal's triangle in matrix form. There are three natural ways to achieve this: as a lower-triangular matrix, an upper-triangular matrix, or a symmetric matrix. For example, the 5 × 5 matrices are:

$L_5 = \begin{pmatrix}
1 & 0 & 0 & 0 & 0 \\
1 & 1 & 0 & 0 & 0 \\
1 & 2 & 1 & 0 & 0 \\
1 & 3 & 3 & 1 & 0 \\
1 & 4 & 6 & 4 & 1
\end{pmatrix}\,\,\,$ $U_5 = \begin{pmatrix}
1 & 1 & 1 & 1 & 1 \\
0 & 1 & 2 & 3 & 4 \\
0 & 0 & 1 & 3 & 6 \\
0 & 0 & 0 & 1 & 4 \\
0 & 0 & 0 & 0 & 1
\end{pmatrix}\,\,\,$ $S_5 = \begin{pmatrix}
1 & 1 & 1 & 1 & 1 \\
1 & 2 & 3 & 4 & 5 \\
1 & 3 & 6 & 10 & 15 \\
1 & 4 & 10 & 20 & 35 \\
1 & 5 & 15 & 35 & 70
\end{pmatrix}=L_5 \times U_5$

There are other ways in which Pascal's triangle can be put into matrix form, but these are not easily extended to infinity.

Definition

The non-zero elements of a Pascal matrix are given by the binomial coefficients:

$L_{ij} = {i \choose j} = \frac{i!}{j!(i-j)!}, j \le i$

$U_{ij} = {j \choose i} = \frac{j!}{i!(j-i)!}, i \le j$

$S_{ij} = {i+j \choose i} = {i+j \choose j} = \frac{(i+j)!}{i!j!}$

such that the indices i, j start at 0, and ! denotes the factorial.

Properties

The matrices have the pleasing relationship S_n = L_nU_n. From this it is easily seen that all three matrices have determinant 1, as the determinant of a triangular matrix is simply the product of its diagonal elements, which are all 1 for both L_n and U_n. In other words, matrices S_n, L_n, and U_n are unimodular, with L_n and U_n having trace n.

The trace of S_n is given by

: $\text{tr}(S_n) = \sum^n_{i=1} \frac{ [ 2(i-1) ] !}{[(i-1)!]^2} = \sum^{n-1}_{k=0} \frac{ (2k) !}{(k!)^2}$

with the first few terms given by the sequence 1, 3, 9, 29, 99, 351, 1275, ... {{OEIS|A006134}}.

Construction

A Pascal matrix can actually be constructed by taking the matrix exponential of a special subdiagonal or superdiagonal matrix. The example below constructs a 7 × 7 Pascal matrix, but the method works for any desired n × n Pascal matrices. The dots in the following matrices represent zero elements.

: $\begin{array}{lll}
& L_7=\exp
\left (
\left [
\begin{smallmatrix}
. & . & . & . & . & . & . \\
1 & . & . & . & . & . & . \\
. & 2 & . & . & . & . & . \\
. & . & 3 & . & . & . & . \\
. & . & . & 4 & . & . & . \\
. & . & . & . & 5 & . & . \\
. & . & . & . & . & 6 & .
\end{smallmatrix}
\right ]
\right )
=
\left [
\begin{smallmatrix}
1 & . & . & . & . & . & . \\
1 & 1 & . & . & . & . & . \\
1 & 2 & 1 & . & . & . & . \\
1 & 3 & 3 & 1 & . & . & . \\
1 & 4 & 6 & 4 & 1 & . & . \\
1 & 5 & 10 & 10 & 5 & 1 & . \\
1 & 6 & 15 & 20 & 15 & 6 & 1
\end{smallmatrix}
\right ]
;\quad
\\
\\
& U_7=\exp
\left (
\left [
\begin{smallmatrix}
{\color{white}1}. & 1 & . & . & . & . & . \\
{\color{white}1}. & . & 2 & . & . & . & . \\
{\color{white}1}. & . & . & 3 & . & . & . \\
{\color{white}1}. & . & . & . & 4 & . & . \\
{\color{white}1}. & . & . & . & . & 5 & . \\
{\color{white}1}. & . & . & . & . & . & 6 \\
{\color{white}1}. & . & . & . & . & . & .
\end{smallmatrix}
\right ]
\right )
=
\left [
\begin{smallmatrix}
1 & 1 & 1 & 1 & 1 & 1 & 1 \\
. & 1 & 2 & 3 & 4 & 5 & 6 \\
. & . & 1 & 3 & 6 & 10 & 15 \\
. & . & . & 1 & 4 & 10 & 20 \\
. & . & . & . & 1 & 5 & 15 \\
. & . & . & . & . & 1 & 6 \\
. & . & . & . & . & . & 1
\end{smallmatrix}
\right ]
;
\\
\\
\therefore & S_7
=\exp
\left (
\left [
\begin{smallmatrix}
. & . & . & . & . & . & . \\
1 & . & . & . & . & . & . \\
. & 2 & . & . & . & . & . \\
. & . & 3 & . & . & . & . \\
. & . & . & 4 & . & . & . \\
. & . & . & . & 5 & . & . \\
. & . & . & . & . & 6 & .
\end{smallmatrix}
\right ]
\right )
\exp
\left (
\left [
\begin{smallmatrix}
{\color{white}i}. & 1 & . & . & . & . & . \\
{\color{white}i}. & . & 2 & . & . & . & . \\
{\color{white}i}. & . & . & 3 & . & . & . \\
{\color{white}i}. & . & . & . & 4 & . & . \\
{\color{white}i}. & . & . & . & . & 5 & . \\
{\color{white}i}. & . & . & . & . & . & 6 \\
{\color{white}i}. & . & . & . & . & . & .
\end{smallmatrix}
\right ]
\right )
=
\left [
\begin{smallmatrix}
1 & 1 & 1 & 1 & 1 & 1 & 1 \\
1 & 2 & 3 & 4 & 5 & 6 & 7 \\
1 & 3 & 6 & 10 & 15 & 21 & 28 \\
1 & 4 & 10 & 20 & 35 & 56 & 84 \\
1 & 5 & 15 & 35 & 70 & 126 & 210 \\
1 & 6 & 21 & 56 & 126 & 252 & 462 \\
1 & 7 & 28 & 84 & 210 & 462 & 924
\end{smallmatrix}
\right ].
\end{array}$

One cannot simply assume exp(A) exp(B) = exp(A + B), for n × n matrices A and B; this equality is only true when AB = BA (i.e. when the matrices A and B commute). In the construction of symmetric Pascal matrices like that above, the sub- and superdiagonal matrices do not commute, so the (perhaps) tempting simplification involving the addition of the matrices cannot be made.

A useful property of the sub- and superdiagonal matrices used for the construction is that both are nilpotent; that is, when raised to a sufficiently great integer power, they degenerate into the zero matrix. (See shift matrix for further details.) As the n × n generalised shift matrices we are using become zero when raised to power n, when calculating the matrix exponential we need only consider the first n + 1 terms of the infinite series to obtain an exact result.

Variants

Interesting variants can be obtained by obvious modification of the matrix-logarithm PL₇ and then application of the matrix exponential.

The first example below uses the squares of the values of the log-matrix and constructs a 7 × 7 "Laguerre"- matrix (or matrix of coefficients of Laguerre polynomials

: $\begin{array}{lll}
& LAG_7=\exp
\left (
\left [
\begin{smallmatrix}
. & . & . & . & . & . & . \\
1 & . & . & . & . & . & . \\
. & 4 & . & . & . & . & . \\
. & . & 9 & . & . & . & . \\
. & . & . & 16 & . & . & . \\
. & . & . & . & 25 & . & . \\
. & . & . & . & . & 36 & .
\end{smallmatrix}
\right ]
\right )
=
\left [
\begin{smallmatrix}
1 & . & . & . & . & . & . \\
1 & 1 & . & . & . & . & . \\
2 & 4 & 1 & . & . & . & . \\
6 & 18 & 9 & 1 & . & . & . \\
24 & 96 & 72 & 16 & 1 & . & . \\
120 & 600 & 600 & 200 & 25 & 1 & . \\
720 & 4320 & 5400 & 2400 & 450 & 36 & 1
\end{smallmatrix}
\right ]
;\quad
\end{array}$

The Laguerre-matrix is actually used with some other scaling and/or the scheme of alternating signs.

(Literature about generalizations to higher powers is not found yet)

The second example below uses the products v(v + 1) of the values of the log-matrix and constructs a 7 × 7 "Lah"- matrix (or matrix of coefficients of Lah numbers)

: $\begin{array}{lll}
& LAH_7 = \exp
\left (
\left [
\begin{smallmatrix}
. & . & . & . & . & . & . \\
2 & . & . & . & . & . & . \\
. & 6 & . & . & . & . & . \\
. & . &12 & . & . & . & . \\
. & . & . & 20 & . & . & . \\
. & . & . & . & 30 & . & . \\
. & . & . & . & . & 42 & .
\end{smallmatrix}
\right ]
\right )
=
\left [
\begin{smallmatrix}
1 & . & . & . & . & . & . & . \\
2 & 1 & . & . & . & . & . & . \\
6 & 6 & 1 & . & . & . & . & . \\
24 & 36 & 12 & 1 & . & . & . & . \\
120 & 240 & 120 & 20 & 1 & . & . & . \\
720 & 1800 & 1200 & 300 & 30 & 1 & . & . \\
5040 & 15120 & 12600 & 4200 & 630 & 42 & 1 & . \\
40320 & 141120 & 141120 & 58800 & 11760 & 1176 & 56 & 1
\end{smallmatrix}
\right ]
;\quad
\end{array}$

Using v(v − 1) instead provides a diagonal shifting to bottom-right.

The third example below uses the square of the original PL₇-matrix, divided by 2, in other words: the first-order binomials (binomial(k, 2)) in the second subdiagonal and constructs a matrix, which occurs in context of the derivatives and integrals of the Gaussian error function:

: $\begin{array}{lll}
& GS_7 = \exp
\left (
\left [
\begin{smallmatrix}
. & . & . & . & . & . & . \\
. & . & . & . & . & . & . \\
1 & . & . & . & . & . & . \\
. & 3 & . & . & . & . & . \\
. & . & 6 & . & . & . & . \\
. & . & . & 10 & . & . & . \\
. & . & . & . & 15 & . & .
\end{smallmatrix}
\right ]
\right )
=
\left [
\begin{smallmatrix}
1 & . & . & . & . & . & . \\
. & 1 & . & . & . & . & . \\
1 & . & 1 & . & . & . & . \\
. & 3 & . & 1 & . & . & . \\
3 & . & 6 & . & 1 & . & . \\
. & 15 & . & 10 & . & 1 & . \\
15 & . & 45 & . & 15 & . & 1
\end{smallmatrix}
\right ]
;\quad
\end{array}$

If this matrix is inverted (using, for instance, the negative matrix-logarithm), then this matrix has alternating signs and gives the coefficients of the derivatives (and by extension the integrals) of Gauss' error-function. (Literature about generalizations to greater powers is not found yet.)

Another variant can be obtained by extending the original matrix to negative values:

: $\begin{array}{lll}
& \exp
\left (
\left [
\begin{smallmatrix}
. & . & . & . & . & . & . & . & . & . & . & . \\
-5& . & . & . & . & . & . & . & . & . & . & . \\
. &-4 & . & . & . & . & . & . & . & . & . & . \\
. & . &-3 & . & . & . & . & . & . & . & . & . \\
. & . & . &-2 & . & . & . & . & . & . & . & . \\
. & . & . & . &-1 & . & . & . & . & . & . & . \\
. & . & . & . & . & 0 & . & . & . & . & . & . \\
. & . & . & . & . & . & 1 & . & . & . & . & . \\
. & . & . & . & . & . & . & 2 & . & . & . & . \\
. & . & . & . & . & . & . & . & 3 & . & . & . \\
. & . & . & . & . & . & . & . & . & 4 & . & . \\
. & . & . & . & . & . & . & . & . & . & 5 & .
\end{smallmatrix}
\right ]
\right )
=
\left [
\begin{smallmatrix}
1 & . & . & . & . & . & . & . & . & . & . & . \\
-5 & 1 & . & . & . & . & . & . & . & . & . & . \\
10 & -4 & 1 & . & . & . & . & . & . & . & . & . \\
-10 & 6 & -3 & 1 & . & . & . & . & . & . & . & . \\
5 & -4 & 3 & -2 & 1 & . & . & . & . & . & . & . \\
-1 & 1 & -1 & 1 & -1 & 1 & . & . & . & . & . & . \\
. & . & . & . & . & 0 & 1 & . & . & . & . & . \\
. & . & . & . & . & . & 1 & 1 & . & . & . & . \\
. & . & . & . & . & . & 1 & 2 & 1 & . & . & . \\
. & . & . & . & . & . & 1 & 3 & 3 & 1 & . & . \\
. & . & . & . & . & . & 1 & 4 & 6 & 4 & 1 & . \\
. & . & . & . & . & . & 1 & 5 & 10 & 10 & 5 & 1
\end{smallmatrix}
\right ]
.
\end{array}$

References

{{Citation |first1=G.S. |last1=Call |first2=D. J. |last2=Velleman |title=Pascal's matrices |journal=American Mathematical Monthly |volume=100 |issue=4 |pages=372–6 |date=April 1993 |doi=10.1080/00029890.1993.11990415 |jstor=2324960}}
{{Citation | first1 = Alan | last1 = Edelman | first2 = Gilbert | last2 = Strang | authorlink2 = Gilbert Strang | title = Pascal Matrices | journal = American Mathematical Monthly | volume = 111 | number = 3 | date = March 2004 | pages = 361–385 | doi = 10.1080/00029890.2004.11920065 | jstor = 4145127 }}
{{cite journal |first=K. |last=Endl |title=Über eine ausgezeichnete Eigenschaft der Koeffizientenmatrizen des Laguerreschen und des Hermiteschen Polynomsystems |journal=Mathematische Zeitschrift |volume=65 |issue=1 |pages=7–15 |date=1956 |doi=10.1007/BF01473866 |url=https://gdz.sub.uni-goettingen.de/id/PPN266833020_0065?tify=%7B%22pages%22%3A%5B12%2C13%5D%2C%22view%22%3A%22info%22%7D}}

External links

G. Helms [https://go.helms-net.de/math/binomial_new/01_1_binomialmatrix.pdf Pascalmatrix] in a project of compilation of facts about [https://go.helms-net.de/math/binomial/index.htm Numbertheoretical matrices]
G. Helms [https://go.helms-net.de/math/binomial/04_1_gaussmatrix.pdf Gauss-matrix]
Weisstein, Eric W. [https://mathworld.wolfram.com/GaussianFunction.html Gaussian-function]
Weisstein, Eric W. [https://mathworld.wolfram.com/Erf.html Erf-function]
Weisstein, Eric W. "Hermite Polynomial". [https://mathworld.wolfram.com/HermitePolynomial.html Hermite-polynomials]
{{OEIS el|1=A066325|2=Coefficients of unitary Hermite polynomials He_n(x)|formalname=Coefficients of unitary Hermite polynomials He_n(x)}} (Related to Gauss-matrix).

Category:Matrices (mathematics)

Category:Triangles of numbers