Sunday, September 8, 2024
HomeMatlabWhat Is the Pascal Matrix? – Nick Higham

# What Is the Pascal Matrix? – Nick Higham

The Pascal matrix $P_ninmathbb{R}^{ntimes n}$ is the symmetric matrix outlined by

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

It comprises the rows of Pascal’s triangle alongside the anti-diagonals. For instance:

$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 constructive particular and has the Cholesky factorization

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

the place the rows of $L_n$ are the rows of Pascal’s triangle. For instance,

$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’ve got $det(P_n) = det(L_n)^2 = 1$. Kind this equation, or by inverting (1), it follows that $P_n^{-1}$ has integer parts. Certainly the inverse is thought to have $(i,j)$ aspect

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

The Cholesky issue $L_n$ will be factorized as

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

the place $M_i$ is unit decrease bidiagonal with the primary $i-1$ entries alongside the subdiagonal of $M_i$ zero and the remaining equal to $1$. For instance,

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) exhibits that $P_n$ is completely constructive, that’s, each minor (a determinant of a sq. submatrix) is constructive. Certainly every bidiagonal issue $M_i$ is completely nonnegative, that’s, each minor is nonnegative, and the product of completely nonnegative matrices is completely nonnegative. Additional ends in the idea of completely constructive matrices present that the product is definitely completely constructive.

The constructive definiteness of $P_n$ implies that the eigenvalues are actual and constructive. The whole positivity, along with the truth that $P_n$ is (trivially) irreducible, implies that the eigenvalues are distinct.

For a symmetric constructive semidefinite matrix $A$ with nonnegative entries, we outline $A^{circ t} = (a_{ij}^t)$, which is the matrix with each entry raised to the facility $tin mathbb{R}$. We are saying that $A$ is infinitely divisible if $A^{circ t}$ is constructive semidefinite for all nonnegative $t$. The Pascal matrix is infinitely divisible.

It’s attainable to point out that

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

the place $D = mathrm{diag}((-1)^i)$. In different phrases, $Y_n = L_nD$ is involutory, that’s, $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 comparable and therefore have the identical eigenvalues. Which means the eigenvalues of $P_n$ seem in reciprocal pairs and that the attribute polynomial is palindromic. Right 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(displaystylefrac{2n-1}{n}biggr) p_{nn},$

the place for the equality we used a binomial coefficient summation id. The truth that $P_n$ is constructive particular with reciprocal eigenvalues implies that $kappa_2(P) = |P|_2^2$. Therefore, utilizing Stirling’s approximation ($n! sim sqrt{2pi n} (n/mathrm{e})^n$),

$kappa_2(P_n) sim p_{nn}^2 simleft( displaystylefrac{ (2n)! }{ (n!)^2 } right)^2 sim displaystylefrac{16^n}{n pi}.$

Thus $P_n$ is exponentially in poor health conditioned as $ntoinfty$.

The matrix $Y_n$ is obtained in MATLAB with `pascal(n,1)`; this can be a decrease triangular sq. root of the id matrix. Turnbull (1927) famous that by rotating $Y_n$ by way of 90 levels one obtains a dice root of the id matrix. This matrix is returned by `pascal(n,2)`. For instance, 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 recognized: it’s the higher 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 Name and Velleman (1993). respectively. For (5), see Edelman and Strang (2004). The infinite divisibility of the Pascal matrix is infinitely is proven by Bhatia (2006). For the entire positivity property see Fallat and Johnson (2011).

RELATED ARTICLES