THE EIGENVECTORS OF THE RIGHT–JUSTIFIED PASCAL TRIANGLE

DAVID CALLAN AND HELMUT PRODINGER

Let R = (\binom{i−1}{n−j})_{1≤i,j≤n} denote the n × n matrix formed by right justifying the first n rows of Pascal’s triangle and let a denote the golden ratio (1 + \sqrt{5} )/2. We will show that the eigenvalues of R are λ_{j} = (−1)^{n−j}a^{2j−n−1}, 1 ≤ j ≤ n, (as conjectured in [1]), with corresponding eigenvectors u_{j} = (u_{ij})_{1≤i≤n} where

u_{ij} = (−a)^{n−j} ∑_{k=1}^{j}(−1)^{i−k}\binom{i − 1}{k − 1}\binom{n − i}{j − k}a^{2k−i−1}.

Let U = (u_{ij})_{1≤i,j≤n} denote the matrix whose columns are the eigenvectors (u_{j})_{j=1}^{n}. For example, when n = 5,

R = (\begin{matrix}0 & 0 & 0 & 0 & 1 \\ 0 & 0 & 0 & 1 & 1 \\ 0 & 0 & 1 & 2 & 1 \\ 0 & 1 & 3 & 3 & 1 \\ 1 & 4 & 6 & 4 & 1 \end{matrix}) and U = (\begin{matrix}a^{4} & −4 a^{3} & 6 a^{2} & −4 a & 1 \\ −a^{3} & 3 a^{2} − a^{4} & −3 a + 3 a^{3} & 1 − 3 a^{2} & a \\ a^{2} & −2 a + 2 a^{3} & 1 − 4 a^{2} + a^{4} & 2 a − 2 a^{3} & a^{2} \\ −a & 1 − 3 a^{2} & 3 a − 3 a^{3} & 3 a^{2} − a^{4} & a^{3} \\ 1 & 4 a & 6 a^{2} & 4 a^{3} & a^{4} \end{matrix}) .

Remarkably, the left eigenvectors of R (the eigenvectors of R^{t}) are the rows of U. This follows from the fortuitous fact that U^{2} is a scalar matrix, specifically U^{2} = (1 + a^{2})^{n−1}I_{n}. To explain, let V = (1 + a^{2})^{−(n−1)/2}U so that V is also a matrix of eigenvectors for R and V^{2} = I_{n}. Taking transposes in V^{−1} R V = diag(λ_{j})_{j=1}^{n} yields W^{−1} R^{t} W = diag(λ_{j})_{j=1}^{n} with W = (V^{−1})^{t}. In words, if a matrix R has a full set of eigenvectors forming the columns of a matrix V, then the columns of (V^{−1})^{t} are the corresponding eigenvectors for R^{t}. But here (V^{−1})^{t} is simply V^{t}. So the rows of V, as well as the rows of U (a scalar multiple of V), are eigenvectors for R^{t}.

Our proofs that Ru_{j} = λ_{j}u_{j}, 1 ≤ j ≤ n, and U^{2} = (1 + a^{2})^{n−1}I_{n} illustrate the power of generating functions [2]. Consider the generating function U_{i}(z) = z(z − a)^{n−i}(az + 1)^{i−1}.

Date: December 5, 2000.

It is immediate that

U_{i}(z) = ∑_{j=1}^{n} u_{ij}z^{j}.

We must prove that (Ru_{j})_{i} = (λ_{j}u_{j})_{i} for all i with 1 ≤ i ≤ n. Now

(Ru_{j})_{i} = [z^{j}] ∑_{k=1}^{n} R_{ik}U_{k}(z)

= [z^{j}] ∑_{k=1}^{n} \binom{i − 1}{n − k}z(z − a)^{n−k}(az + 1)^{k−1}

= [z^{j−1}](az + 1)^{n−i} ∑_{k=1}^{n} \binom{i − 1}{n − k}(z − a)^{n−k}(az + 1)^{i−1−(n−k)}

= [z^{j−1}](az + 1)^{n−i}((z − a) + (az + 1))^{i−1} = [z^{j−1}](az + 1)^{n−i}((1 + a)z + (1 − a))^{i−1}.

On the other hand,

(λ_{j}u_{j})_{i} = [z^{j}] ∑_{j=1}^{n}(−1)^{n+j}a^{2j−n−1}u_{ij}z^{j}

= [z^{j}](−1)^{n}a^{−n−1} ∑_{j=1}^{n} u_{ij}(−za^{2})^{j}

= [z^{j}](−1)^{n}a^{−n−1}U_{i}(−a^{2}z)

= [z^{j}](−1)^{n}a^{−n−1}(−a^{2}z)(−a^{2}z − a)^{n−i}(−a^{3}z + 1)^{i−1}

= [z^{j−1}](az + 1)^{n−i}(a^{2}z − \frac{1}{a})^{i−1},

and the claim follows since a^{2} = 1 + a, and −\frac{1}{a} = 1 − a.

Next, we examine the (i, k) entry of U^{2}.

(U^{2})_{ik} = ∑_{j=1}^{n}[x^{k−1}](x − a)^{n−j}(ax + 1)^{j−1} · [z^{j−1}](z − a)^{n−i}(az + 1)^{i−1}

= [x^{k−1}] ∑_{j=1}^{n}[z^{j−1}](x − a)^{n−j}(ax + 1)^{j−1}(z − a)^{n−i}(az + 1)^{i−1}

= [x^{k−1}](x − a)^{n−1} ∑_{j=1}^{n}[z^{j−1}] (\frac{ax + 1}{x − a})^{j−1} (z − a)^{n−i}(az + 1)^{i−1}

= [x^{k−1}](x − a)^{n−1} ∑_{j=1}^{n}[z^{j−1}](z \frac{ax + 1}{x − a} − a)^{n−i}(az \frac{ax + 1}{x − a} + 1)^{i−1}

= [x^{k−1}](x − a)^{n−1}(\frac{ax + 1}{x − a} − a)^{n−i}(a\frac{ax + 1}{x − a} + 1)^{i−1}

= [x^{k−1}](ax + 1 − ax + a^{2})^{n−i}(a^{2}x + a + x − a)^{i−1}

= [x^{k−1}](1 + a^{2})^{n−i}x^{i−1}(1 + a^{2})^{i−1}

= [x^{k−i}](1 + a^{2})^{n−1}

= (1 + a^{2})^{n−1}δ_{ki},

as desired.

Finally, a mild generalization. Let x be an indeterminate and let R(x) be the n × n matrix with (i, j) entry \binom{i−1}{n−j}x^{i+j−n−1}. Then the eigenvalues and eigenvectors of R(x) are precisely as above but with a a root of a^{2} − ax − 1 rather than of a^{2} − a − 1.

References

1. R. Peele and P. Stănică, “Matrix Powers of Column-Justified Pascal Triangles and Fibonacci Sequences,” arXiv:math.CO/0010186.

2. Herbert S. Wilf, generatingfunctionology, Academic Press, New York, 1990.

David Callan, Department of Statistics, University of Wisconsin-Madison, 1210 W. Dayton Street, Madison, WI 53706-1693, U.S.A., email: callan@stat.wisc.edu

Helmut Prodinger, The John Knopfmacher Centre for Applicable Analysis and Number Theory, Department of Mathematics, University of the Witwatersrand, P. O. Wits, 2050 Johannesburg, South Africa, email: helmut@gauss.cam.wits.ac.za