
\documentclass[11pt]{amsart}
\parskip=0.3cm
\parindent=0.5cm
\renewcommand{\baselinestretch}{1.3}
\pagestyle{plain}
\setlength{\textwidth}{6.0in}
\setlength{\textheight}{8.5in}
\setlength{\topmargin}{0cm}
\setlength{\oddsidemargin}{0cm}
\setlength{\evensidemargin}{0cm}
\def\j{\bold{j}}
\def\fl#1{\left\lfloor#1\right\rfloor}
\def\a{\alpha}

\newtheorem{theorem}{Theorem}%[section]
\newtheorem{proposition}{Proposition}%[section]
\newtheorem{lemma}{Lemma}%[section]
\newtheorem{cor}{Corollary}
\renewcommand{\thecor}{}
\def\la{\lambda}
\def\bu{\mathbf{u}}
\allowdisplaybreaks
\title[The Eigenvectors of the Right--Justified Pascal Triangle]
{The Eigenvectors of the Right--Justified Pascal Triangle}
\author{David Callan}
\author{Helmut Prodinger}



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

\address{ 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:
{\tt helmut@gauss.cam.wits.ac.za}
}

\date{\today}

\begin{document}




\maketitle



Let $R = \left( \binom{i-1}{n-j} \right)_{1 \leq i,j \leq n}
$ denote the $n \times 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 $\la_{j} =
(-1)^{n-j}a^{2j-n-1},\ 1 \leq j \le n,$ (as conjectured in \cite{peele}),
with corresponding eigenvectors $\mathbf{u}_{j} = (u_{ij})_{1 \le i \le
n}$ where \[ u_{ij} = (-a)^{n-j}\sum_{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 \le i,j \le n}$ denote the matrix whose columns are the
 eigenvectors $(\mathbf{u}_{j})_{j=1}^{n}$. For example, when $n=5$,
\[ R = \left(
\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} \right)
\quad \mathrm{and} \quad 
U = \left(
\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}\right).
\] 


Remarkably, the left eigenvectors of $R$ (the eigenvectors 
of $R^{t}$) are the \emph{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=\mathrm{diag}(\la_{j})_{j=1}^{n}$ yields 
$W^{-1}\,R^{t}\,W=\mathrm{diag}(\la_{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 $R\bu_{j}=\la_{j}\bu_{j}, \ 1 \le j \le n$,  and $U^{2}=
(1+a^{2})^{n-1}I_{n}$ illustrate the power of generating functions 
\cite{wilf}.
Consider the generating function
$U_i(z)=z(z-a)^{n-i}(az+1)^{i-1}$. It is immediate that
\begin{equation*}
U_i(z)=\sum_{j=1}^{n} u_{ij}z^j.
\end{equation*}
We must prove that $(R\bu_j)_i=(\la_j\bu_j)_i$ for all $i$ with
$1\le i\le n$. Now
\begin{align*}
(R\bu_j)_i&=[z^j]\sum_{k=1}^nR_{ik}U_k(z)\\
&=[z^j]\sum_{k=1}^n\binom{i-1}{n-k}z(z-a)^{n-
k}(az+1)^{k-1}\\
&=[z^{j-1}](az+1)^{n-i}\sum_{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}\big((z-a)+(az+1)\big)^{i-1} \\ 
&=[z^{j-1}](az+1)^{n-i}\big((1+a)z+(1-a)\big)^{i-1}.
\end{align*}
On the other hand, 
\begin{align*}
(\la_j\bu_j)_i&=[z^j]\sum_{j=1}^n(-1)^{n+j}a^{2j-n-
1}u_{ij}z^j\\
&=[z^j](-1)^{n}a^{-n-1}\sum_{j=1}^nu_{ij}(-za^2)^j\\
&=[z^j](-1)^{n}a^{-n-1}U_i(-a^2z)\\
&=[z^j](-1)^{n}a^{-n-1}(-a^2z)(-a^2z-a)^{n-i}(-a^3z+1)^{i-
1}\\
&=[z^{j-1}](az+1)^{n-i}\Big(a^2 z-\frac{1}{a}\Big)^{i-1},\\
\end{align*}
and the claim follows since $a^2=1+a$, and $-\frac{1}{a}=1-a$.

%\bigskip

Next, we examine the $(i,k)$ entry of $U^{2}$.
\begin{align*}
(U^2)_{ik}&=\sum_{j=1}^{n}[x^{k-1}](x-a)^{n-j}(ax+1)^{j-
1}
\cdot[z^{j-1}](z-a)^{n-i}(az+1)^{i-1}\\
&=[x^{k-1}]\sum_{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}\sum_{j=1}^{n}[z^{j-
1}]\left(\frac{ax+1}{x-a}\right)^{j-1}
(z-a)^{n-i}(az+1)^{i-1}\\
&=[x^{k-1}](x-a)^{n-1}\sum_{j=1}^{n}[z^{j-1}]
\Big(z\frac{ax+1}{x-a}-a\Big)^{n-i}\Big(az\frac{ax+1}{x-a}+1\Big)^{i-
1}\\
&=[x^{k-1}](x-a)^{n-1}
\Big(\frac{ax+1}{x-a}-a\Big)^{n-i}\Big(a\frac{ax+1}{x-a}+1\Big)^{i-1}\\
&=[x^{k-1}]({ax+1}-ax+a^2)^{n-i}(a^2x+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}\delta_{ki},\\
\end{align*}
as desired.



Finally, a mild generalization. Let $x$ be an indeterminate and let $R(x)$
be the $n \times 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$.






\bibliographystyle{amsplain}



\begin{thebibliography}{1}


\bibitem{peele}	R.~Peele and P.~St\u{a}nic\u{a}, ``Matrix Powers of
Column-Justified Pascal	Triangles and Fibonacci	Sequences,''
arXiv:math.CO/0010186.

\bibitem{wilf} Herbert S. Wilf, \emph{generatingfunctionology}, 
Academic Press, New York, 1990.

\end{thebibliography}







\end{document}






