What Is the Pascal Matrix? – Nick Higham

September 13, 2022

221

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).

References

Rajendra Bhatia, Infinitely Divisible Matrices, Amer. Math. Month-to-month 113, 221–235, 2006
Gregory Name and Daniel Velleman, Pascal’s Matrices, Amer. Math. Month-to-month 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. Month-to-month 111, 189–197, 2004.
Shaun Fallat and Charles Johnson, Completely Nonnegative Matrices, Princeton College Press, 2011.
H. W. Turnbull, The Matrix Sq. and Dice Roots of Unity, J. London Math. Soc. 2, 242–244, 1927.

Previous articleFind out how to Improve to React 18 – React Weblog

Next articleSimplify Your File Dealing with With Filestack Workflows

What Is the Pascal Matrix? – Nick Higham

Notes

References

What’s the Polar Decomposition? – Nick Higham

Pole Vault – 2024 Olympics replace » Man on Simulink

Inspiring Younger Communications Engineers: The Air Power Analysis Lab’s SDR Problem » Scholar Lounge

LEAVE A REPLY Cancel reply

Most Popular

Starbucks DVD peddlers with Emily Freeman & Justin Garrison (Changelog & Mates #60)

How one can Deploy Flask Purposes on Vultr — SitePoint

(Mounted) Thrive Optimize Not Working – Hundreds Clean Web page – Be on the Proper Aspect of Change

The right way to Create a PS1-Impressed Jitter Shader with React-Three-Fiber

Recent Comments

ABOUT US

POPULAR POSTS

Starbucks DVD peddlers with Emily Freeman & Justin Garrison (Changelog & Mates #60)

How one can Deploy Flask Purposes on Vultr — SitePoint

(Mounted) Thrive Optimize Not Working – Hundreds Clean Web page – Be on the Proper Aspect of Change

POPULAR CATEGORY