Pascal matrix

From Wikipedia, the free encyclopedia

In mathematics, particularly matrix theory and combinatorics, the Pascal matrix is an infinite matrix containing the binomial coefficients as its elements. There are 3 ways this can be achieved - either as an upper-triangular matrix, a lower-triangular matrix, or as 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 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 elements of the symmetric Pascal matrix are the binomial coefficients, i.e.

$S_{ij} = {n \choose r} = \frac{n!}{r!(n-r)!},\quad \mbox{where}\quad n=i+j-2,\quad r=i-1$

In other words,

$S_{ij} = { }^{i+j-2}\mathbf{C}_{i-1} = \frac{(i+j-2)!}{(i-1)!(j-1)!}.$

Thus the trace of S is given by

$\mbox{tr}(S_{n\times n}) = \sum^n_{i=1} \frac{ [ 2(i-1) ] !}{[(i-1)!]^2} = \sum^{n-1}_{k=0} \frac{ (2k) !}{(k!)^2} = \{1,3,9,29,99,351,1275,...\}$ (Sloane's A006134).

[edit] Construction

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 below matrices represent zero elements.)

$\begin{array}{lll} & L_7=\mbox{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=\mbox{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 =\mbox{exp} \left ( \left [ \begin{smallmatrix} . & . & . & . & . & . & . \\ 1 & . & . & . & . & . & . \\ . & 2 & . & . & . & . & . \\ . & . & 3 & . & . & . & . \\ . & . & . & 4 & . & . & . \\ . & . & . & . & 5 & . & . \\ . & . & . & . & . & 6 & . \end{smallmatrix} \right ] \right ) \mbox{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 you 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. 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 a 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.