<html><head><meta name="color-scheme" content="light dark"></head><body><pre style="word-wrap: break-word; white-space: pre-wrap;">\documentclass[11pt]{article}

\usepackage[usenames]{color}

\usepackage{url}

\usepackage[colorlinks=true,
linkcolor=webgreen,
filecolor=webbrown,
citecolor=webgreen]{hyperref}

\definecolor{webgreen}{rgb}{0,.5,0}
\definecolor{webbrown}{rgb}{.6,0,0}

\usepackage{amsthm,amssymb}
\usepackage{psfig,epsf}

\setlength{\textwidth}{6.5in}
\setlength{\oddsidemargin}{.1in}
\setlength{\topmargin}{-.5in}
\setlength{\textheight}{8.9in}

\newcommand{\rk}{{\rm rk}}

\newcommand{\bbox}{\nopagebreak[4] \hfill\rule{2mm}{2mm}}
\newcounter{resno}
\newenvironment{Proof}{{\sc Proof.\ }}{\hfill\bbox\bigskip}


\newcommand{\seqnum}[1]{\href{http://oeis.org/#1}{\underline{#1}}}



\begin{document}

\begin{center}
\epsfxsize=4in
\leavevmode\epsffile{logo112.eps}
\vskip 1cm

{\LARGE \bf Hankel Matrices and Lattice Paths}
\vskip 1.5cm

{\large Wen-jin Woan} \smallskip \\
Department of Mathematics \\
Howard University \\
Washington, D.C. 20059, USA \medskip \\
Email address: \href{mailto:wwoan@howard.edu}{wwoan@howard.edu} \\
\vskip2.5cm

{\bf Abstract}
\end{center}

Let $H$ be the Hankel matrix formed from a sequence of real numbers $%
S=\{a_0=1,a_1,a_2,a_3,...\},$ and let $L$ denote the lower triangular matrix
obtained from the Gaussian column reduction of $H.$ This paper gives a
matrix-theoretic proof that the associated Stieltjes matrix $S_L$
is a tri-diagonal matrix. It is also shown that for any sequence (of nonzero real numbers) $%
T=\{d_0=1,d_1,d_2\ ,d_3,...\}$ there are infinitely many sequences such that
the determinant sequence of the Hankel matrix formed from those sequences is 
$T$.

\bigskip

{\bf 1. Introduction}. In this paper we give a matrix-theoretic proof
(Theorem 2.1) of one of the main theorems in \cite{PW}. In Section 2 we discuss
the connection between the decomposition of a Hankel matrix and Stieltjes
matrices, and in Section 3 we discuss the connection between certain lattice
paths and Hankel matrices. Section 4 presents an explicit formula for
the decomposition of a Hankel matrix.

\bigskip

{\bf Definition 1.1.} Let $S=\{a_0=1,a_1,a_2,a_3,...\}$ be a sequence of
real numbers. The Hankel matrix generated by $S$ is the infinite
matrix

\begin{center}
\[
H=\left[ 
\begin{array}{cccccc}
1 &amp; a_1\  &amp; a_2\  &amp; a_3\  &amp; a_4\  &amp; . \\ 
a_1\  &amp; a_2 &amp; a_3\  &amp; a_4\  &amp; a_5\  &amp; . \\ 
a_2 &amp; a_3 &amp; a_4\  &amp; a_5\  &amp; a_6\  &amp; . \\ 
a_3 &amp; a_4\  &amp; a_5\  &amp; a_6\  &amp; a_7\  &amp; . \\ 
a_4\  &amp; a_5\  &amp; a_6\  &amp; a_7\  &amp; a_8 &amp; . \\ 
. &amp; . &amp; . &amp; . &amp; . &amp; .
\end{array}
\right] . 
\]
\ 
\end{center}

{\bf Definition 1.2}. A lower triangular matrix

\[
L=\left[ 
\begin{array}{cccccc}
1 &amp; 0 &amp; 0 &amp; 0 &amp; 0 &amp; . \\ 
l_{10} &amp; 1 &amp; 0 &amp; 0 &amp; 0 &amp; . \\ 
l_{20} &amp; l_{21} &amp; 1 &amp; 0 &amp; 0 &amp; . \\ 
l_{30} &amp; l_{31} &amp; l_{32} &amp; 1 &amp; 0 &amp; . \\ 
l_{40} &amp; l_{41} &amp; l_{42} &amp; l_{43} &amp; 1 &amp; . \\ 
. &amp; . &amp; . &amp; . &amp; . &amp; .
\end{array}
\right] . 
\]

\noindent is said to be a Riordan matrix if
there exist Taylor series 
$g(x)=1+a_1x+a_2x^2+...+a_nx^n+...$ and $f(x)=x+b_2x^2+b_3x^3+...+b_nx^n+....$
such that
for every $k \geq 0$ the $k$-th column has ordinary generating function
$g(x)(f(x))^k$.

{\bf Definition 1.3}. The Stieltjes matrix $\ $of a lower triangular matrix $%
L$ is the matrix $S_L$ which satisfies $LS_L=L^r\;$where $L^r\;$is the
matrix obtained from $L$ by deleting the first row of $L.$

Thus

\[
\left[ 
\begin{array}{cccccc}
1 &amp; 0 &amp; 0 &amp; 0 &amp; 0 &amp; . \\ 
l_{10} &amp; 1 &amp; 0 &amp; 0 &amp; 0 &amp; . \\ 
l_{20} &amp; l_{21} &amp; 1 &amp; 0 &amp; 0 &amp; . \\ 
l_{30} &amp; l_{31} &amp; l_{32} &amp; 1 &amp; 0 &amp; . \\ 
l_{40} &amp; l_{41} &amp; l_{42} &amp; l_{43} &amp; 1 &amp; . \\ 
. &amp; . &amp; . &amp; . &amp; . &amp; .
\end{array}
\right] S_L=\left[ 
\begin{array}{cccccc}
l_{10} &amp; 1 &amp; 0 &amp; 0 &amp; 0 &amp; . \\ 
l_{20} &amp; l_{21} &amp; 1 &amp; 0 &amp; 0 &amp; . \\ 
l_{30} &amp; l_{31} &amp; l_{32} &amp; 1 &amp; 0 &amp; . \\ 
l_{40} &amp; l_{41} &amp; l_{42} &amp; l_{43} &amp; 1 &amp; . \\ 
. &amp; . &amp; . &amp; . &amp; . &amp; .
\end{array}
\right] 
\]

and so

\[
S_L=L^{-1}L^r=\ \left[ 
\begin{array}{cccccc}
1 &amp; 0 &amp; 0 &amp; 0 &amp; 0 &amp; . \\ 
-l_{10} &amp; 1 &amp; 0 &amp; 0 &amp; 0 &amp; . \\ 
\times &amp; -l_{21} &amp; 1 &amp; 0 &amp; 0 &amp; . \\ 
\times &amp; \times &amp; -l_{32} &amp; 1 &amp; 0 &amp; . \\ 
\times &amp; \times &amp; \times &amp; -l_{43} &amp; 1 &amp; . \\ 
. &amp; . &amp; . &amp; . &amp; . &amp; .
\end{array}
\right] \left[ 
\begin{array}{cccccc}
l_{10} &amp; 1 &amp; 0 &amp; 0 &amp; 0 &amp; . \\ 
l_{20} &amp; l_{21} &amp; 1 &amp; 0 &amp; 0 &amp; . \\ 
l_{30} &amp; l_{31} &amp; l_{32} &amp; 1 &amp; 0 &amp; . \\ 
l_{40} &amp; l_{41} &amp; l_{42} &amp; l_{43} &amp; 1 &amp; . \\ 
. &amp; . &amp; . &amp; . &amp; . &amp; .
\end{array}
\right] 
\]

\[
=\left[ 
\begin{array}{cccccc}
b_0 &amp; 1 &amp; 0 &amp; 0 &amp; 0 &amp; . \\ 
c_0 &amp; b_1 &amp; 1 &amp; 0 &amp; 0 &amp; . \\ 
\times &amp; c_1 &amp; b_2 &amp; 1 &amp; 0 &amp; . \\ 
\times &amp; \times &amp; c_2 &amp; b_3 &amp; 1 &amp; . \\ 
\times &amp; \times &amp; \times &amp; c_3 &amp; b_4 &amp; . \\ 
. &amp; . &amp; . &amp; . &amp; . &amp; .
\end{array}
\right] 
\]
\ 

\noindent where

\[
b_0=l_{10,}\ b_k=l_{k+1,k}-l_{k,k-1},\;k&gt;0, 
\]

\[
c_0=l_{2,0}-l_{1,0}^2,%
\;c_k=(l_{k,k-1}l_{k+1,k}-l_{k+1,k-1})-l_{k+1,k}^2+l_{k+2,k},\ k&gt;0. 
\]

{\bf Definition 1.4}. Let $L$ and $S_L$ be as in Definition 1.3. We
define

\[
D_L=\left[ 
\begin{array}{cccccc}
d_0 &amp; 0 &amp; 0 &amp; 0 &amp; 0 &amp; . \\ 
0 &amp; d_1 &amp; 0 &amp; 0 &amp; 0 &amp; . \\ 
0 &amp; 0 &amp; d_2 &amp; 0 &amp; 0 &amp; . \\ 
0 &amp; 0 &amp; 0 &amp; d_3 &amp; 0 &amp; . \\ 
0 &amp; 0 &amp; 0 &amp; 0 &amp; d_4 &amp; . \\ 
. &amp; . &amp; . &amp; . &amp; . &amp; .
\end{array}
\right] 
\]

\noindent to be the diagonal matrix with diagonal entries given by $d_0=1,$ $%
d_{k+1}=d_kc_k$ for $k&gt;0$.\bigskip\ 

{\bf 2. Stieltjes and Hankel Matrices.}

The following two theorems are proved in \cite{PW}.

{\bf Theorem 2.1}. Let $L$ be a lower triangular matrix and let $D=D_L$ be
the diagonal matrix with nonzero diagonal entries $\{d_i\}\;$as in
Definition 1.4. Then $LDL^t$ is a Hankel matrix if and only if $S_L$ is a
tri-diagonal matrix, i.e. if and only if

\[
S_L=\left[ 
\begin{array}{cccccc}
b_0 &amp; 1 &amp; 0 &amp; 0 &amp; 0 &amp; . \\ 
c_0 &amp; b_1 &amp; 1 &amp; 0 &amp; 0 &amp; . \\ 
0 &amp; c_1 &amp; b_2 &amp; 1 &amp; 0 &amp; . \\ 
0 &amp; 0 &amp; c_2 &amp; b_3 &amp; 1 &amp; . \\ 
0 &amp; 0 &amp; 0 &amp; c_3 &amp; b_4 &amp; . \\ 
. &amp; . &amp; . &amp; . &amp; . &amp; .
\end{array}
\right] 
\]
where $\ b_0=l_{1,0}\;,\quad c_0=d_1\;,\quad b_k=l_{k+1,k}-l_{k,k-1}\;,\quad
c_k=\frac{d_{k+1}}{d_k}\;,\quad k\geq 1.$

\begin{Proof}
Let $H=LDL^t$ be a Hankel matrix. Then

$\ L=H(DL^t)^{-1},\ $

$L^r=(H(DL^t)^{-1})^r=H^r(DL^t)^{-1},\ $

$S_L=L^{-1}L^r=L^{-1}(H^r(DL^t)^{-1})=(L^{-1}H^r)(DL^t)^{-1}.$

$\ $Since $H$ is a Hankel matrix, deleting the first row has the same effect
as deleting the first column.

\[
L^{-1}H=DL^t=\left[ 
\begin{tabular}{llllll}
$d_0$ &amp; $d_0l_{10}$ &amp; $d_0l_{20}$ &amp; $d_0l_{3,0}$ &amp; $d_0l_{4,0}$ &amp; . \\ 
$0$ &amp; $d_1\ $ &amp; $d_1l_{21}$ &amp; $d_1l_{31}$ &amp; $d_1l_{41}$ &amp; . \\ 
$0$ &amp; $0$ &amp; $d_2$ &amp; $d_2l_{32}$ &amp; $d_2l_{42}$ &amp; . \\ 
$0$ &amp; $0$ &amp; $0$ &amp; $d_3$ &amp; $d_3l_{43}$ &amp; . \\ 
$0$ &amp; $0$ &amp; $0$ &amp; $0$ &amp; $d_4$ &amp; . \\ 
. &amp; . &amp; . &amp; . &amp; . &amp; .
\end{tabular}
\right] , 
\]
\ 

\[
L^{-1}H^r=L^{-1}H^c=(L^{-1}H)^c=\left[ 
\begin{tabular}{lllll}
$d_0l_{10}$ &amp; $d_0l_{20}$ &amp; $d_0l_{30}$ &amp; $d_0l_{4,0}$ &amp; . \\ 
$d_1\ $ &amp; $d_1l_{21}$ &amp; $d_1l_{31}$ &amp; $d_1l_{41}$ &amp; . \\ 
$0$ &amp; $d_2$ &amp; $d_2l_{32}$ &amp; $d_2l_{42}$ &amp; . \\ 
$0$ &amp; $0$ &amp; $d_3$ &amp; $d_3l_{43}$ &amp; . \\ 
$0$ &amp; $0$ &amp; $0$ &amp; $d_4$ &amp; . \\ 
. &amp; . &amp; . &amp; . &amp; .
\end{tabular}
\right] , 
\]

\[
S_L=(L^{-1}H)^c(DL^t)^{-1}=\left[ 
\begin{tabular}{lllll}
$d_0l_{10}$ &amp; $d_0l_{20}$ &amp; $d_0l_{30}$ &amp; $d_0l_{4,0}$ &amp; . \\ 
$d_1\ $ &amp; $d_1l_{21}$ &amp; $d_1l_{31}$ &amp; $d_1l_{41}$ &amp; . \\ 
$0$ &amp; $d_2$ &amp; $d_2l_{32}$ &amp; $d_2l_{42}$ &amp; . \\ 
$0$ &amp; $0$ &amp; $d_3$ &amp; $d_3l_{43}$ &amp; . \\ 
$0$ &amp; $0$ &amp; $0$ &amp; $d_4$ &amp; . \\ 
. &amp; . &amp; . &amp; . &amp; .
\end{tabular}
\right] \left[ 
\begin{tabular}{llllll}
$\frac 1{d_0}$ &amp; $\times $ &amp; $\times $ &amp; $\times $ &amp; $\times $ &amp; . \\ 
$0$ &amp; $\frac 1{d_1}\ $ &amp; $\times $ &amp; $\times $ &amp; $\times $ &amp; . \\ 
$0$ &amp; $0$ &amp; $\frac 1{d_2}$ &amp; $\times $ &amp; $\times $ &amp; . \\ 
$0$ &amp; $0$ &amp; $0$ &amp; $\frac 1{d_3}$ &amp; $\times $ &amp; . \\ 
$0$ &amp; $0$ &amp; $0$ &amp; $0$ &amp; $\frac 1{d_4}$ &amp; . \\ 
. &amp; . &amp; . &amp; . &amp; . &amp; .
\end{tabular}
\right] 
\]
\ 

\[
=\left[ 
\begin{array}{cccccc}
b_0 &amp; 1 &amp; 0 &amp; 0 &amp; 0 &amp; . \\ 
c_0 &amp; b_1 &amp; 1 &amp; 0 &amp; 0 &amp; . \\ 
0 &amp; c_1 &amp; b_2 &amp; 1 &amp; 0 &amp; . \\ 
0 &amp; 0 &amp; c_2 &amp; b_3 &amp; 1 &amp; . \\ 
0 &amp; 0 &amp; 0 &amp; c_3 &amp; b_4 &amp; . \\ 
. &amp; . &amp; . &amp; . &amp; . &amp; .
\end{array}
\right] 
\]
\ 

\noindent where

\[
b_0=l_{1,0}\;,\quad c_0=\frac{d_1}{d_0}=d_1\;,\quad
b_k=l_{k+1,k}-l_{k,k-1}\;,\quad c_k=\frac{d_{k+1}}{d_k}\;,\quad k\geq 1. 
\]

$\;\;\;\;\;\;$Conversely$,$ let $S_L\;$be a tri-diagonal matrix and let $%
H=LDL^t.$ Then

$L^{-1}H^r=L^{-1}(LDL^t)^r=L^{-1}(L^rDL^t)=(L^{-1}L^r)DL^t=S_LDL^t$

\[
=\left[ 
\begin{array}{cccccc}
b_0 &amp; 1 &amp; 0 &amp; 0 &amp; 0 &amp; . \\ 
c_0 &amp; b_1 &amp; 1 &amp; 0 &amp; 0 &amp; . \\ 
0 &amp; c_1 &amp; b_2 &amp; 1 &amp; 0 &amp; . \\ 
0 &amp; 0 &amp; c_2 &amp; b_3 &amp; 1 &amp; . \\ 
0 &amp; 0 &amp; 0 &amp; c_3 &amp; b_4 &amp; . \\ 
. &amp; . &amp; . &amp; . &amp; . &amp; .
\end{array}
\right] \left[ 
\begin{tabular}{llllll}
$d_0$ &amp; $d_0l_{10}$ &amp; $d_0l_{20}$ &amp; $d_0l_{3,0}$ &amp; $d_0l_{4,0}$ &amp; . \\ 
$0$ &amp; $d_1\ $ &amp; $d_1l_{21}$ &amp; $d_1l_{31}$ &amp; $d_1l_{41}$ &amp; . \\ 
$0$ &amp; $0$ &amp; $d_2$ &amp; $d_2l_{32}$ &amp; $d_2l_{42}$ &amp; . \\ 
$0$ &amp; $0$ &amp; $0$ &amp; $d_3$ &amp; $d_3l_{43}$ &amp; . \\ 
$0$ &amp; $0$ &amp; $0$ &amp; $0$ &amp; $d_4$ &amp; . \\ 
. &amp; . &amp; . &amp; . &amp; . &amp; .
\end{tabular}
\right] . 
\]

Therefore\ 

$(L^{-1}H^r)_{n,k}=c_{n-1}d_{n-1}l_{k,n-1}+b_nd_nl_{k,n}+d_{n+1}l_{k,n+1}$

$=\frac{d_n}{d_{n-1}}d_{n-1}l_{k,n-1}+b_nd_nl_{k,n}+c_nd_nl_{k,n+1}$

$=d_n(l_{k,n-1}+b_nl_{k,n}+c_nl_{k,n+1})$

$%
=d_nl_{k+1,n}=(DL^t)_{n,k+1}=(DL^t)_{n,k}^c=(L^{-1}H)_{n,k}^c=(L^{-1}H^c)_{n,k}. 
$

We have shown that $L^{-1}H^r=L^{-1}H^c,$ and so $H^r=H^c.$\ Hence $H$ is a
Hankel matrix.
\end{Proof}

{\bf Theorem 2.2}. $L$ is a Riordan matrix (i.e. $b_k=b_1=b$ and $c_k=c_1=c$
for $k\geq 1)$ if and only if $f=x(1+bf+cf^2)\;$and
\[
g=\frac 1{1-xb_0-xc_0f} ~,
\]
where $f,g$ are as in Definition 1.2.

See \cite{PW} for the proof.

{\bf Corollary 2.3}. Let $T=\{d_0=1,d_1,d_2\ ,d_3,...\}$ be any sequence of (nonzero)
real numbers. Then there exists a sequence $S=\{a_0=1,a_1,a_2,a_3,...\}$
such that $T$ is equal to the sequence of diagonal  
entries of $D$ in the decomposition $H=LDL^t$ of the
Hankel matrix generated by $S$ .

\begin{Proof}
As in Theorem 2.1, let $\ c_0=d_1\;,c_k=\frac{d_{k+1}}{d_k}\;,
k\geq 1,\;$and form the Stieltjes matrix 
\[
S_L=\left[ 
\begin{array}{cccccc}
b_0 &amp; 1 &amp; 0 &amp; 0 &amp; 0 &amp; . \\ 
c_0 &amp; b_1 &amp; 1 &amp; 0 &amp; 0 &amp; . \\ 
0 &amp; c_1 &amp; b_2 &amp; 1 &amp; 0 &amp; . \\ 
0 &amp; 0 &amp; c_2 &amp; b_3 &amp; 1 &amp; . \\ 
0 &amp; 0 &amp; 0 &amp; c_3 &amp; b_4 &amp; . \\ 
. &amp; . &amp; . &amp; . &amp; . &amp; .
\end{array}
\right] 
\]
\noindent where the $b_i$s are arbitrary. By Definition 1.3
there is a lower triangular matrix $L$ such that $LS_L=L^r$. Let $S$ be the
sequence formed by the first column of $L$ and let $H$ denote the Hankel
matrix generated by $S$. By Theorem 2.1 the diagonal entries of $D$ in the
decomposition $H=LDL^t$ form the sequence $T$.
\end{Proof}

{\bf Example 2.4.} Let $T=\{1,1,2,5,14,42,132,...\}$ be the Catalan sequence
(\seqnum{A000108} in \cite{OEIS})
and let

\[
\ \ S_L=\left[ 
\begin{array}{cccccc}
0 &amp; 1 &amp; 0 &amp; 0 &amp; 0 &amp; . \\ 
1 &amp; 0 &amp; 1 &amp; 0 &amp; 0 &amp; . \\ 
0 &amp; 2 &amp; 0 &amp; 1 &amp; 0 &amp; . \\ 
0 &amp; 0 &amp; \frac 52 &amp; 0 &amp; 1 &amp; . \\ 
0 &amp; 0 &amp; 0 &amp; \frac{14}5 &amp; 0 &amp; . \\ 
. &amp; . &amp; . &amp; . &amp; . &amp; .
\end{array}
\right] . 
\]
$\ $Then

\[
L=\left[ 
\begin{array}{cccccc}
1 &amp; 0 &amp; 0 &amp; 0 &amp; 0 &amp; . \\ 
0 &amp; 1 &amp; 0 &amp; 0 &amp; 0 &amp; . \\ 
1 &amp; 0 &amp; 1 &amp; 0 &amp; 0 &amp; . \\ 
0 &amp; 3 &amp; 0 &amp; 1 &amp; 0 &amp; . \\ 
3 &amp; 0 &amp; \frac{11}2 &amp; 0 &amp; 1 &amp; . \\ 
. &amp; . &amp; . &amp; . &amp; . &amp; .
\end{array}
\right] , 
\]

\[
LDL^t=\left[ 
\begin{array}{cccccc}
1 &amp; 0 &amp; 0 &amp; 0 &amp; 0 &amp; . \\ 
0 &amp; 1 &amp; 0 &amp; 0 &amp; 0 &amp; . \\ 
1 &amp; 0 &amp; 1 &amp; 0 &amp; 0 &amp; . \\ 
0 &amp; 3 &amp; 0 &amp; 1 &amp; 0 &amp; . \\ 
3 &amp; 0 &amp; \frac{11}2 &amp; 0 &amp; 1 &amp; . \\ 
. &amp; . &amp; . &amp; . &amp; . &amp; .
\end{array}
\right] \left[ 
\begin{array}{cccccc}
1 &amp; 0 &amp; 0 &amp; 0 &amp; 0 &amp; . \\ 
0 &amp; 1 &amp; 0 &amp; 0 &amp; 0 &amp; . \\ 
0 &amp; 0 &amp; 2 &amp; 0 &amp; 0 &amp; . \\ 
0 &amp; 0 &amp; 0 &amp; 5 &amp; 0 &amp; . \\ 
0 &amp; 0 &amp; 0 &amp; 0 &amp; 14 &amp; . \\ 
. &amp; . &amp; . &amp; . &amp; . &amp; .
\end{array}
\right] \left[ 
\begin{array}{cccccc}
1 &amp; 0 &amp; 1 &amp; 0 &amp; 3 &amp; . \\ 
0 &amp; 1 &amp; 0 &amp; 3 &amp; 0 &amp; . \\ 
0 &amp; 0 &amp; 1 &amp; 0 &amp; \frac{11}2 &amp; . \\ 
0 &amp; 0 &amp; 0 &amp; 1 &amp; 0 &amp; . \\ 
0 &amp; 0 &amp; 0 &amp; 0 &amp; 1 &amp; . \\ 
. &amp; . &amp; . &amp; . &amp; . &amp; .
\end{array}
\right] 
\]
\ 

\[
=\left[ 
\begin{array}{cccccc}
1 &amp; 0 &amp; 1 &amp; 0 &amp; 3 &amp; . \\ 
0 &amp; 1 &amp; 0 &amp; 3 &amp; 0 &amp; . \\ 
1 &amp; 0 &amp; 3 &amp; 0 &amp; 14 &amp; . \\ 
0 &amp; 3 &amp; 0 &amp; 14 &amp; 0 &amp; . \\ 
3 &amp; 0 &amp; 14 &amp; 0 &amp; \frac{167}2 &amp; . \\ 
. &amp; . &amp; . &amp; . &amp; . &amp; .
\end{array}
\right] =H.\ 
\]

{\bf 3. Lattice Paths and Hankel Matrices}

We consider those lattice paths in the Cartesian plane running from $(0,0)$
that use steps from $S=\{u=(1,1),\;h=(1,0),\;d=(1,-1)\}$ with assigned
weights $1$ for $u$, $w_1$ for $h$ and $w_2$ for $d$. Let $L(n,k)$ be the
set of paths that never go below the $x$-axis and end at $(n,k)$. The weight
of a path is the product of the weights of its steps. Let $l_{n,k}\;$be\ the
sum of the weights of all the paths in $L(n,k).$ See also \cite{Su}, \cite{We}.

{\bf Theorem 3.1}. Let $L=(l_{n,k})_{n,k\geq 0}.$ Then $L$ is a lower
triangular matrix, the Stieltjes matrix of $L$ is

\[
S_L=\left[ 
\begin{array}{cccccc}
w_1 &amp; 1 &amp; 0 &amp; 0 &amp; 0 &amp; . \\ 
w_2 &amp; w_1 &amp; 1 &amp; 0 &amp; 0 &amp; . \\ 
0 &amp; w_2 &amp; w_1 &amp; 1 &amp; 0 &amp; . \\ 
0 &amp; 0 &amp; w_2 &amp; w_1 &amp; 1 &amp; . \\ 
0 &amp; 0 &amp; 0 &amp; w_2 &amp; w_1 &amp; . \\ 
. &amp; . &amp; . &amp; . &amp; . &amp; .
\end{array}
\right] 
\]
\ 

\noindent and $H=LDL^t\;$is the Hankel matrix generated by the first column
of $L$ and $d_k=w_2^k$ for $k&gt;0.$

\begin{Proof}
From Theorem 2.1.
\end{Proof}

{\bf Example 3.2.} For $w_1=0,\;w_2=1,$ $L$ is the Catalan matrix. For $%
w_1=t,\;w_2=1$, $L$ is the $t$-Motzkin matrix. In both cases $D$ is the
identity matrix. For example, when $t=1$,

\[
L\ =\left[ 
\begin{tabular}{llllll}
$1$ &amp; $0$ &amp; $0$ &amp; $0$ &amp; $0$ &amp; . \\ 
$1$ &amp; $1$ &amp; $0$ &amp; $0$ &amp; $0$ &amp; . \\ 
$2$ &amp; $2$ &amp; $1$ &amp; $0$ &amp; $0$ &amp; . \\ 
$4$ &amp; $5$ &amp; $3$ &amp; $1$ &amp; $0$ &amp; . \\ 
$9$ &amp; $12$ &amp; $9$ &amp; $4$ &amp; $1$ &amp; . \\ 
. &amp; . &amp; . &amp; . &amp; . &amp; .
\end{tabular}
\right] \ , 
\]
\ 

\[
\ \ LDL^t=\left[ 
\begin{tabular}{llllll}
$1$ &amp; $1$ &amp; $2$ &amp; $4$ &amp; $9$ &amp; . \\ 
$1$ &amp; $2$ &amp; $4$ &amp; $9$ &amp; $21$ &amp; . \\ 
$2$ &amp; $4$ &amp; $9$ &amp; $21$ &amp; $51$ &amp; . \\ 
$4$ &amp; $9$ &amp; $21$ &amp; $51$ &amp; $127$ &amp; . \\ 
$9$ &amp; $21$ &amp; $51$ &amp; $127$ &amp; $323$ &amp; . \\ 
. &amp; . &amp; . &amp; . &amp; . &amp; .
\end{tabular}
\right] =H 
\]
\ 

\noindent where $S=\{1,1,2,4,9,21,51,...\}$ is the Motzkin sequence 
\seqnum{A001006}.

{\bf Theorem 3.3.} If $w_1,$ $w_2\;$depend on the height $k$, i.e. $%
w_1(k)=b_k$ and $w_2(k+1)=c_k,$ then

\[
S_L=\left[ 
\begin{array}{cccccc}
b_0 &amp; 1 &amp; 0 &amp; 0 &amp; 0 &amp; . \\ 
c_0 &amp; b_1 &amp; 1 &amp; 0 &amp; 0 &amp; . \\ 
0 &amp; c_1 &amp; b_2 &amp; 1 &amp; 0 &amp; . \\ 
0 &amp; 0 &amp; c_2 &amp; b_3 &amp; 1 &amp; . \\ 
0 &amp; 0 &amp; 0 &amp; c_3 &amp; b_4 &amp; . \\ 
. &amp; . &amp; . &amp; . &amp; . &amp; .
\end{array}
\right] 
\]

\noindent and $H=LDL^t$ is the Hankel matrix generated by the first column
of $L$ and $d_k=\Pi _{i\leq k}c_i.$

\begin{Proof}
From Theorem 2.1.
\end{Proof}

\noindent See Example 2.4 for an illustration.

{\bf 4. Gaussian Column Reduction }

\ \ Let $S=\{a_0=1,a_1,a_2,a_3,...\}$ be a sequence of real numbers and let $%
H$ denote the Hankel matrix generated by $S$. All the results in this
section are well-known in matrix theory. We shall express the entries of $L$
in term of $S$. We assume that $H$ is positive definite.

{\bf Lemma 4.1}. The decomposition of a positive definite Hankel matrix $%
H=LDU$ is unique and $U=L^t$, where $L$ is a lower triangular matrix with
diagonal entries 1, $D$ is a diagonal matrix and $U$ is an upper triangular
matrix with diagonal entries 1.

\begin{Proof}
Let $LDU=H=L_1D_1U_1.$ Then $DUU_1^{-1}=L^{-1}L_1D_1$ is both an upper
and lower triangular matrix, hence $UU_1^{-1}=L^{-1}L_1=I$ is the infinite
identity matrix.
\end{Proof}

Let $H_n$ be the truncated submatrix of $H$ with $n\geq 0$ . For example,

\begin{center}
\[
H_3=\left[ 
\begin{array}{cccc}
1 &amp; a_1\  &amp; a_2\  &amp; a_3 \\ 
a_1\  &amp; a_2\  &amp; a_3 &amp; a_4\  \\ 
a_2\  &amp; a_3 &amp; a_4\  &amp; a_5\  \\ 
a_3 &amp; a_4\  &amp; a_5\  &amp; a_6\ 
\end{array}
\right] ,\;\;\;\;\;H_4=\left[ 
\begin{array}{ccccc}
1 &amp; a_1\  &amp; a_2\  &amp; a_3 &amp; a_4\  \\ 
a_1\  &amp; a_2\  &amp; a_3 &amp; a_4\  &amp; a_5\  \\ 
a_2\  &amp; a_3 &amp; a_4\  &amp; a_5\  &amp; a_6\  \\ 
a_3 &amp; a_4\  &amp; a_5\  &amp; a_6\  &amp; a_7\  \\ 
a_4\  &amp; a_5\  &amp; a_6\  &amp; a_7\  &amp; a_8
\end{array}
\right] . 
\]
\ 
\end{center}

Let $H_n(k)$ be the matrix obtained from $H_n$ by replacing the last column
of $H_n$ by $a_k,a_{k+1},a_{k+2},...,a_{k+n}.$ For example,

\[
H_3(1)=\left[ 
\begin{array}{cccc}
1 &amp; a_1\  &amp; a_2\  &amp; a_1 \\ 
a_1\  &amp; a_2\  &amp; a_3 &amp; a_2\  \\ 
a_2\  &amp; a_3 &amp; a_4\  &amp; a_3\  \\ 
a_3 &amp; a_4\  &amp; a_5\  &amp; a_4\ 
\end{array}
\right] ,\;\;\;\;\;\;H_3(5)=\left[ 
\begin{array}{cccc}
1 &amp; a_1\  &amp; a_2\  &amp; a_5 \\ 
a_1\  &amp; a_2\  &amp; a_3 &amp; a_6\  \\ 
a_2\  &amp; a_3 &amp; a_4\  &amp; a_7\  \\ 
a_3 &amp; a_4\  &amp; a_5\  &amp; a_8
\end{array}
\right] . 
\]
.\ 

Let $h_i=\det H_i\;$and define an infinite upper triangular matrix $%
R=(r_{n,k})$ in term of $(n,k)$-cofactor of $H_k$ by $r_{n,k}=0\;$for $k&lt;n,$
and

\[
r_{n,k}\ =\frac 1{h_{k-1}}(-1)^{_{n+k+2}}~\det \left[ 
\begin{array}{ccccc}
1 &amp; a_1 &amp; a_2 &amp; . &amp; a_{k-1} \\ 
a_1 &amp; a_2 &amp; a_3 &amp; .. &amp; a_k \\ 
a_2 &amp; a_3 &amp; a_4 &amp; . &amp; a_{k+1} \\ 
. &amp; . &amp; . &amp; . &amp; .. \\ 
a_{n-1} &amp; a_n &amp; a_{n+1} &amp; . &amp; a_{k+n-2} \\ 
a_{n+1} &amp; a_{n+2} &amp; a_{n+3} &amp; . &amp; a_{k+n} \\ 
. &amp; . &amp; . &amp; . &amp; . \\ 
a_k &amp; a_{k+1} &amp; a_{k+2} &amp; . &amp; a_{k+k}
\end{array}
\right] 
\]

for $k\geq n.$
For example, 
\[
r_{2,4}=\frac 1{h_3}(-1)^{(2+4)+2}\det \left[ 
\begin{array}{cccc}
1 &amp; a_1\  &amp; a_2\  &amp; a_3 \\ 
a_1\  &amp; a_2\  &amp; a_3 &amp; a_4\  \\ 
a_3 &amp; a_4\  &amp; a_5\  &amp; a_6\  \\ 
a_4\  &amp; a_5\  &amp; a_6\  &amp; a_7\ 
\end{array}
\right] . 
\]
\ 

{\bf Remark 4.2}. $HR=LD,$ where $L=(l_{n,k})$ is the Gaussian column
reduction of the Hankel matrix $H\;$and $D$ is the diagonal matrix with
diagonal entries $\{d_i\},$ $R^{-1}=L^t$ with $d_i=\frac{h_i}{h_{i-1}}$ and $%
l_{n,k}=\frac 1{h_{k-1}}\det H_k(n).$

{\bf Remark 4.3}. If $L$ is a Riordan matrix, then for $i\geq 1,$ $c=c_i=%
\frac{d_{i+1}}{d_i}=\frac{h_{i+1}h_{i-1}}{h_ih_i}$ and $%
b=b_i=l_{i+1,i}-l_{i,i-1}=\frac 1{h_{i-1}}\det H_i(i+1)-\frac 1{h_{i-2}}\det
H_{i-1}(i)$ is a recurrence relation for the sequence $S$.

{\bf Example 4.4}. Let $S=\{1,3,13,63,321,1683,8989,48639,265729,...\}$ be
the central Delannoy numbers 
\seqnum{A001850}
and let $H$ be the Hankel matrix
generated by $S.$ Then

\[
\ H=\left[ 
\begin{array}{ccccc}
1 &amp; 3 &amp; 13 &amp; 63 &amp; . \\ 
3 &amp; 13 &amp; 63 &amp; 321 &amp; . \\ 
13 &amp; 63 &amp; 321 &amp; 1683 &amp; . \\ 
63 &amp; 321 &amp; 1683 &amp; 8989 &amp; . \\ 
. &amp; . &amp; . &amp; . &amp; .
\end{array}
\right] , 
\]
$\ \ $\ \ $\;\;\;\;\;$

\[
R=\left[ 
\begin{array}{ccccc}
1 &amp; -3 &amp; 5 &amp; -9 &amp; . \\ 
0 &amp; 1 &amp; -6 &amp; 21 &amp; . \\ 
0 &amp; 0 &amp; 1 &amp; -9 &amp; . \\ 
0 &amp; 0 &amp; 0 &amp; 1 &amp; . \\ 
. &amp; . &amp; . &amp; . &amp; .
\end{array}
\right] , 
\]
\ 

\[
LD=HR=\left[ 
\begin{array}{ccccc}
1 &amp; 0 &amp; 0 &amp; 0 &amp; . \\ 
3 &amp; 4 &amp; 0 &amp; 0 &amp; . \\ 
13 &amp; 24 &amp; 8 &amp; 0 &amp; . \\ 
63 &amp; 132 &amp; 72 &amp; 16 &amp; . \\ 
. &amp; . &amp; . &amp; . &amp; .
\end{array}
\right] , 
\]
\ 

\[
R^tHR=D=\left[ 
\begin{array}{ccccc}
1 &amp; 0 &amp; 0 &amp; 0 &amp; . \\ 
0 &amp; 4 &amp; 0 &amp; 0 &amp; . \\ 
0 &amp; 0 &amp; 8 &amp; 0 &amp; . \\ 
0 &amp; 0 &amp; 0 &amp; 16 &amp; . \\ 
. &amp; . &amp; . &amp; . &amp; .
\end{array}
\right] , 
\]
\ 

\[
L=HRD^{-1}=\left[ 
\begin{array}{ccccc}
1 &amp; 0 &amp; 0 &amp; 0 &amp; . \\ 
3 &amp; 1 &amp; 0 &amp; 0 &amp; . \\ 
13 &amp; 6 &amp; 1 &amp; 0 &amp; . \\ 
63 &amp; 33 &amp; 9 &amp; 1 &amp; . \\ 
. &amp; . &amp; . &amp; . &amp; .
\end{array}
\right] , 
\]

\[
S_L=L^{-1}L^r=R^tL^r=\left[ 
\begin{tabular}{lllll}
$1$ &amp; $0$ &amp; $0$ &amp; $0$ &amp; . \\ 
$-3$ &amp; $1$ &amp; $0$ &amp; $0$ &amp; . \\ 
$5$ &amp; $-6$ &amp; $1$ &amp; $0$ &amp; . \\ 
$-9$ &amp; $21$ &amp; $-9$ &amp; $1$ &amp; . \\ 
. &amp; . &amp; . &amp; . &amp; .
\end{tabular}
\right] \left[ 
\begin{tabular}{llllll}
$3$ &amp; $1$ &amp; $0$ &amp; $0$ &amp; $0$ &amp; . \\ 
$13$ &amp; $6$ &amp; $1$ &amp; $0$ &amp; $0$ &amp; . \\ 
$63$ &amp; $33$ &amp; $9$ &amp; $1$ &amp; $0$ &amp; . \\ 
$321$ &amp; $180$ &amp; $62$ &amp; $12$ &amp; $1$ &amp; . \\ 
. &amp; . &amp; . &amp; . &amp; . &amp; .
\end{tabular}
\right] 
\]

\[
=\left[ 
\begin{array}{ccccc}
3 &amp; 1 &amp; 0 &amp; 0 &amp; . \\ 
4 &amp; 3 &amp; 1 &amp; 0 &amp; . \\ 
0 &amp; 2 &amp; 3 &amp; 1 &amp; . \\ 
0 &amp; 0 &amp; 2 &amp; 3 &amp; . \\ 
. &amp; . &amp; . &amp; . &amp; .
\end{array}
\right] , 
\]

\[
LDL^t=\left[ 
\begin{array}{ccccc}
1 &amp; 0 &amp; 0 &amp; 0 &amp; . \\ 
3 &amp; 1 &amp; 0 &amp; 0 &amp; . \\ 
13 &amp; 6 &amp; 1 &amp; 0 &amp; . \\ 
63 &amp; 33 &amp; 9 &amp; 1 &amp; . \\ 
. &amp; . &amp; . &amp; . &amp; .
\end{array}
\right] \left[ 
\begin{array}{ccccc}
1 &amp; 0 &amp; 0 &amp; 0 &amp; . \\ 
0 &amp; 4 &amp; 0 &amp; 0 &amp; . \\ 
0 &amp; 0 &amp; 8 &amp; 0 &amp; . \\ 
0 &amp; 0 &amp; 0 &amp; 16 &amp; . \\ 
. &amp; . &amp; . &amp; . &amp; .
\end{array}
\right] \left[ 
\begin{array}{ccccc}
1 &amp; 3 &amp; 13 &amp; 63 &amp; . \\ 
0 &amp; 1 &amp; 6 &amp; 33 &amp; . \\ 
0 &amp; 0 &amp; 1 &amp; 9 &amp; . \\ 
0 &amp; 0 &amp; 0 &amp; 1 &amp; . \\ 
. &amp; . &amp; . &amp; . &amp; .
\end{array}
\right] 
\]
\ 

\[
=\left[ 
\begin{array}{ccccc}
1 &amp; 3 &amp; 13 &amp; 63 &amp; . \\ 
3 &amp; 13 &amp; 63 &amp; 321 &amp; . \\ 
13 &amp; 63 &amp; 321 &amp; 1683 &amp; . \\ 
63 &amp; 321 &amp; 1683 &amp; 8989 &amp; . \\ 
. &amp; . &amp; . &amp; . &amp; .
\end{array}
\right] =H. 
\]
\ 

{\bf \ Remark 4.5.} If $H$ is the Hankel matrix corresponding to a sequence
$S$, then by Theorem 3.1 and Theorem 3.3 we may use lattice paths to find $L$,
the Gaussian column reduction of $H$.

{\bf Acknowledgment.} The author would like to thank Professor Ralph Turner
for his help in rewriting the paper.

\begin{thebibliography}{20}


\bibitem{PW}
P. Peart and W. J. Woan, Generating functions via Hankel and Stieltjes matrices,
{\em J. of Integer Sequences}, {\bf 3} (2) (2000),
\href{https://cs.uwaterloo.ca/journals/JIS/VOL3/PEART/peart1.html}{Article 00.2.1}.

\bibitem{OEIS}
Sloane, N. J. A.
The On-Line Encyclopedia of Integer Sequences.
Published electronically at \url{http://www.oeis.org}.

\bibitem{Su} R. Sulanke, Moments of generalized Motzkin paths,
{\em J. Integer Sequences} {\bf 3} (1) (2000),
\href{https://cs.uwaterloo.ca/journals/JIS/VOL3/SULANKE/sulanke.html}{Article 00.1.1}.

\bibitem{We} J. G. Wendel, Left-continuous random walk and the
Lagrange expansion, {\em Amer. Math. Monthly} {\bf 82}
(1975), 494--499.

\end{thebibliography}

\vspace*{+.5in}
\centerline{\rule{6.5in}{.01in}}

\vspace*{+.1in}
\noindent
{\small
(Mentions sequences
\seqnum{A000108},
\seqnum{A001006}, and
\seqnum{A001850}.)

\centerline{\rule{6.5in}{.01in}}

\vspace*{+.1in}
\noindent
Received September 19, 2000;
published in Journal of Integer Sequences, April 24, 2001.

\centerline{\rule{6.5in}{.01in}}

\vspace*{+.1in}

\noindent
Return to \htmladdnormallink{Journal of Integer Sequences home
page}{http://www.research.att.com/~njas/sequences/JIS/}.

\centerline{\rule{6.5in}{.01in}}

\end{document}
</pre></body></html>