June 2022 – Nick Higham

The Pascal matrix $P_n\in\mathbb{R}^{n\times n}$ is the symmetric matrix defined by

$p_{ij} = \displaystyle{i+j-2 \choose j-1} = \displaystyle\frac{ (i+j-2)! }{ (i-1)! (j-1)! }.$

It contains the rows of Pascal’s triangle along the anti-diagonals. For example:

$\notag P_5 = \left[\begin{array}{ccccc} 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{array}\right].$

In MATLAB, the matrix is pascal(n).

The Pascal matrix is positive definite and has the Cholesky factorization

$\notag P_n = L_nL_n^T, \qquad(1)$

where the rows of $L_n$ are the rows of Pascal’s triangle. For example,

$\notag L_5 = \left[\begin{array}{ccccc} 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{array}\right]\\$

From (1) we have $\det(P_n) = \det(L_n)^2 = 1$ . Form this equation, or by inverting (1), it follows that $P_n^{-1}$ has integer elements. Indeed the inverse is known to have $(i,j)$ element

$\notag (-1)^{i-j} \displaystyle\sum_{k=0}^{n-i} {i+k-1 \choose k} {i+k-1 \choose i+k-j}, \quad i \ge j. \qquad(2)$

The Cholesky factor $L_n$ can be factorized as

$\notag L_n = M_{n-1} M_{n-2} \dots M_1, \qquad(3)$

where $M_i$ is unit lower bidiagonal with the first $i-1$ entries along the subdiagonal of $M_i$ zero and the rest equal to $1$ . For example,

$\notag \begin{aligned} L_5 = \left[\begin{array}{ccccc} 1 & 0 & 0 & 0 & 0\\ 0 & 1 & 0 & 0 & 0\\ 0 & 0 & 1 & 0 & 0\\ 0 & 0 & 0 & 1 & 0\\ 0 & 0 & 0 & 1 & 1 \end{array}\right] \left[\begin{array}{ccccc} 1 & 0 & 0 & 0 & 0\\ 0 & 1 & 0 & 0 & 0\\ 0 & 0 & 1 & 0 & 0\\ 0 & 0 & 1 & 1 & 0\\ 0 & 0 & 0 & 1 & 1 \end{array}\right] \left[\begin{array}{ccccc} 1 & 0 & 0 & 0 & 0\\ 0 & 1 & 0 & 0 & 0\\ 0 & 1 & 1 & 0 & 0\\ 0 & 0 & 1 & 1 & 0\\ 0 & 0 & 0 & 1 & 1 \end{array}\right] \left[\begin{array}{ccccc} 1 & 0 & 0 & 0 & 0\\ 1 & 1 & 0 & 0 & 0\\ 0 & 1 & 1 & 0 & 0\\ 0 & 0 & 1 & 1 & 0\\ 0 & 0 & 0 & 1 & 1 \end{array}\right]. \end{aligned}$

The factorization (3) shows that $P_n$ is totally positive, that is, every minor (a determinant of a square submatrix) is positive. Indeed each bidiagonal factor $M_i$ is totally nonnegative, that is, every minor is nonnegative, and the product of totally nonnegative matrices is totally nonnegative. Further results in the theory of totally positive matrices show that the product is actually totally positive.

The positive definiteness of $P_n$ implies that the eigenvalues are real and positive. The total positivity, together with the fact that $P_n$ is (trivially) irreducible, implies that the eigenvalues are distinct.

For a symmetric positive semidefinite matrix $A$ with nonnegative entries, we define $A^{\circ t} = (a_{ij}^t)$ , which is the matrix with every entry raised to the power $t\in \mathbb{R}$ . We say that $A$ is infinitely divisible if $A^{\circ t}$ is positive semidefinite for all nonnegative $t$ . The Pascal matrix is infinitely divisible.

It is possible to show that

$\notag L_n^{-1} = DL_nD, \qquad (4)$

where $D = \mathrm{diag}((-1)^i)$ . In other words, $Y_n = L_nD$ is involutory, that is, $Y_n^2 = I$ . It follows from $P_n = Y_n Y_n^T$ that

$\notag \begin{aligned} P_n^{-1} = Y_n^{-T} Y_n^{-1} = Y_n^T Y_n = Y_n^{-1} (Y_n Y_n^T) Y_n = Y_n^{-1} P_n Y_n, \end{aligned}$

so $P_n$ and $P_n^{-1}$ are similar and hence have the same eigenvalues. This means that the eigenvalues of $P_n$ appear in reciprocal pairs and that the characteristic polynomial is palindromic. Here is an illustration in MATLAB:

>> P = pascal(5); evals = eig(P); [evals 1./evals], coeffs = charpoly(P)
ans =
   1.0835e-02   9.2290e+01
   1.8124e-01   5.5175e+00
   1.0000e+00   1.0000e+00
   5.5175e+00   1.8124e-01
   9.2290e+01   1.0835e-02
coeffs =
     1   -99   626  -626    99    -1

Now

$p_{nn} \le \|P\|_2 \le (\|P\|_1 \|P\|_{\infty})^{1/2} = \biggl(\displaystyle\frac{2n-1}{n}\biggr) p_{nn},$

where for the equality we used a binomial coefficient summation identity. The fact that $P_n$ is positive definite with reciprocal eigenvalues implies that $\kappa_2(P) = \|P\|_2^2$ . Hence, using Stirling’s approximation ( $n! \sim \sqrt{2\pi n} (n/\mathrm{e})^n$ ),

$\kappa_2(P_n) \sim p_{nn}^2 \sim\left( \displaystyle\frac{ (2n)! }{ (n!)^2 } \right)^2 \sim \displaystyle\frac{16^n}{n \pi}.$

Thus $P_n$ is exponentially ill conditioned as $n\to\infty$ .

The matrix $Y_n$ is obtained in MATLAB with pascal(n,1); this is a lower triangular square root of the identity matrix. Turnbull (1927) noted that by rotating $Y_n$ through 90 degrees one obtains a cube root of the identity matrix. This matrix is returned by pascal(n,2). For example, with $n = 5$ :

$\notag \hspace*{-1cm} X = \left[\begin{array}{rrrrr} 1 & 1 & 1 & 1 & 1\\ -4 & -3 & -2 & -1 & 0\\ 6 & 3 & 1 & 0 & 0\\ -4 & -1 & 0 & 0 & 0\\ 1 & 0 & 0 & 0 & 0 \end{array}\right], \quad X^2 = \left[\begin{array}{rrrrr} 0 & 0 & 0 & 0 & 1\\ 0 & 0 & 0 & -1 & -4\\ 0 & 0 & 1 & 3 & 6\\ 0 & -1 & -2 & -3 & -4\\ 1 & 1 & 1 & 1 & 1 \end{array}\right], \quad X^3 = I.$

The logarithm of $L_n$ is explicitly known: it is the upper bidiagonal matrix

$\notag \log L_n = \left[\begin{array}{ccccc} 0 & 1 & & & \\ & 0 & 2 & & \\[-5pt] & & 0 & \ddots & \\[-5pt] & & & \ddots & n-1\\ & & & & 0 \end{array}\right]. \qquad (5)$

Notes

For proofs of (2) and (4) see Cohen (1975) and Call and Velleman (1993). respectively. For (5), see Edelman and Strang (2004). The infinite divisibility of the Pascal matrix is infinitely is shown by Bhatia (2006). For the total positivity property see Fallat and Johnson (2011).

References

Rajendra Bhatia, Infinitely Divisible Matrices, Amer. Math. Monthly 113, 221–235, 2006
Gregory Call and Daniel Velleman, Pascal’s Matrices, Amer. Math. Monthly 100, 372–376, 1993
A. M. Cohen, The Inverse of a Pascal Matrix, Math, Gaz. 59(408), 111–112, 1975.
Alan Edelman and Gilbert Strang, Pascal Matrices, Amer. Math. Monthly 111, 189–197, 2004.
Shaun Fallat and Charles Johnson, Totally Nonnegative Matrices, Princeton University Press, 2011.
H. W. Turnbull, The Matrix Square and Cube Roots of Unity, J. London Math. Soc. 2, 242–244, 1927.

Month: June 2022

What Is the Pascal Matrix?

Notes

References

Related Blog Posts

Notes

References

Related Blog Posts

Share this: