Pascal matrix

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: lower triangular: symmetric:

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_n" is given by:$mbox\{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, ... (Sloane's [http://www.research.att.com/~njas/sequences/A006134 A006134] ).

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

:

end{smallmatrix} ight ] ight )=left [egin{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} ight ] ;quad\\& U_7=mbox{exp}left (left [egin{smallmatrix}. & 1 & . & . & . & . & . \. & . & 2 & . & . & . & . \. & . & . & 3 & . & . & . \. & . & . & . & 4 & . & . \. & . & . & . & . & 5 & . \. & . & . & . & . & . & 6 \. & . & . & . & . & . & . end{smallmatrix} ight ] ight )=left [egin{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} ight ] ;\\

herefore & S_7=mbox{exp}left (left [egin{smallmatrix}. & . & . & . & . & . & . \1 & . & . & . & . & . & . \. & 2 & . & . & . & . & . \. & . & 3 & . & . & . & . \. & . & . & 4 & . & . & . \. & . & . & . & 5 & . & . \. & . & . & . & . & 6 & .

end{smallmatrix} ight ] ight )mbox{exp}left (left [egin{smallmatrix}. & 1 & . & . & . & . & . \. & . & 2 & . & . & . & . \. & . & . & 3 & . & . & . \. & . & . & . & 4 & . & . \. & . & . & . & . & 5 & . \. & . & . & . & . & . & 6 \. & . & . & . & . & . & . end{smallmatrix} ight ] ight )=left [egin{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 & 924end{smallmatrix} ight ] .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 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.

ee also

*Pascal's triangle
*LU decomposition

References

* G. S. Call and D. J. Velleman, "Pascal's matrices", "American Mathematical Monthly", volume 100, (April 1993) pages 372–376
* Alan Edelman and Gilbert Strang, "Pascal Matrices", "American Mathematical Monthly", volume 111, (March 2004), pages 361–385