Pascal matrix

From Wikipedia, the free encyclopedia
Jump to: navigation, search

In mathematics, particularly matrix theory and combinatorics, the Pascal matrix is an infinite matrix containing the binomial coefficients as its elements. There are three ways to achieve this: as either an upper-triangular matrix, a lower-triangular matrix, or a symmetric matrix. The 5×5 truncations of these are shown below.

Upper triangular: 
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};\,\,\,  lower triangular: 
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};\,\,\,  symmetric: 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}.

These matrices have the pleasing relationship Sn = LnUn. 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 Ln and Un. In other words, matrices Sn, Ln, and Un are unimodular, with Ln and Un having trace n.

The elements of the symmetric Pascal matrix are the binomial coefficients, i.e.

S_{ij} = {n \choose r} = \frac{n!}{r!(n-r)!},\text{ where }n=i+j,\quad r=i.

In other words,

S_{ij} = { }_{i+j}\mathbf{C}_{i} = \frac{(i+j)!}{(i)!(j)!}.

Thus the trace of Sn 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, … (sequence A006134 in OEIS).

Construction[edit]

The Pascal matrix can actually be constructed by taking the matrix exponential of a special subdiagonal or superdiagonal matrix. The example below constructs a 7-by-7 Pascal matrix, but the method works for any desired n×n Pascal matrices. (Note that 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}
. & 1 & . & . & . & . & . \\
. & . & 2 & . & . & . & . \\
. & . & . & 3 & . & . & . \\
. & . & . & . & 4 & . & . \\
. & . & . & . & . & 5 & . \\
. & . & . & . & . & . & 6 \\
. & . & . & . & . & . & . 
\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}
. & 1 & . & . & . & . & . \\
. & . & 2 & . & . & . & . \\
. & . & . & 3 & . & . & . \\
. & . & . & . & 4 & . & . \\
. & . & . & . & . & 5 & . \\
. & . & . & . & . & . & 6 \\
. & . & . & . & . & . & . 
\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}

It is important to note that one cannot simply assume exp(A)exp(B) = exp(A + B), for A and B n×n matrices. Such an identity only holds 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 in the construction is that both are nilpotent; that is, when raised to a sufficiently high 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[edit]

Interesting variants can be obtained by obvious modification of the matrix-logarithm PL7 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-by-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-by-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 PL7-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 the Gauss' error-function . (Literature about generalizations to higher 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}

See also[edit]

References[edit]

External links[edit]