Sunday, October 2, 2022
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).

References

RELATED ARTICLES

LEAVE A REPLY

Please enter your comment!
Please enter your name here

Most Popular

Recent Comments