\documentclass[12pt,reqno]{article}

\usepackage[usenames]{color}

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

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

\usepackage{color}
\usepackage{fullpage}
\usepackage{float}

%\usepackage{psfig}
%\usepackage{graphics,amsmath,amssymb}
%\usepackage{epsf}

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

\newcommand{\seqnum}[1]{\href{http://www.research.att.com/cgi-bin/access.cgi/as/~njas/sequences/eisA.cgi?Anum=#1}{\underline{#1}}}

\usepackage{epsfig}
\usepackage{latexsym}
\usepackage{amsfonts}

\usepackage{exptex}
\usepackage{expthmi}

\begin{document}

\begin{center}
\epsfxsize=4in
\leavevmode\epsffile{logo129.eps}
\end{center}

\begin{center}
\vskip 1cm {\LARGE\bf Matrix Transformations of Integer Sequences}
\vskip .3in
\large
Clark Kimberling \\
Department of Mathematics \\
University of Evansville \\
1800 Lincoln Avenue \\
Evansville, IN 47722 \\
\href{mailto:ck6@evansville.edu}{ck6@evansville.edu}\\
\end{center}

\vskip .25in

\textbf{Abstract:} \ The integer sequences with first term $1$ comprise a
group $\mathcal{G}$ under convolution, namely, the Appell group, and the
lower triangular infinite integer matrices with all diagonal entries $1$
comprise a group $\mathbb{G}$ under matrix multiplication. \ If $A\in 
\mathcal{G}$ and $M\in \mathbb{G},$ then $MA\in \mathcal{G}.$ \ The groups $%
\mathcal{G}$ and $\mathbb{G}$ and various subgroups are discussed. \ These
include the group $\mathbb{G}^{(1)}$ of matrices whose columns are identical
except for initial zeros, and also the group $\mathbb{G}^{(2)}$ of matrices
in which the odd-numbered columns are identical except for initial zeros and
the same is true for even-numbered columns. \ Conditions are determined for
the product of two matrices in $\mathbb{G}^{(m)}$ to be in $\mathbb{G}%
^{(1)}. $ \ Conditions are also determined for two matrices in $\mathbb{G}%
^{(2)}$ to commute.\bigskip

\section{Introduction}

Let $\mathcal{G}$ be the set of integer sequences $(a_{1},a_{2},a_{3},\ldots
)$ for which $a_{1}=1.$ $\ $The notations $A=(a_{1},a_{2},a_{3},\ldots ),$ $%
B=(b_{1},b_{2},b_{3},\ldots ),$ $C=(c_{1},c_{2},c_{3},\ldots )\ $will always
refer to elements of $\mathcal{G}.\ $\ The finite sequence $%
(a_{1},a_{2},a_{3},\ldots ,a_{n})$ will be denoted by $A_{n},$ and likewise
for $B_{n}$ and $C_{n}.$ \ Let $\star $ denote convolution; i.e., if $%
C=A\star B,$ then%
\begin{equation*}
c_{n}=\sum_{k=1}^{n}a_{k}b_{n-k+1},
\end{equation*}%
which we shall sometimes write as $A_{n}\circledast B_{n}$, so that $A\star
B $ is the sequence having $A_{n}\circledast B_{n}$ as $n$th term. \
Formally,%
\begin{equation*}
\sum_{k=1}^{\infty }c_{k}x^{k-1}=\left( \sum_{k=1}^{\infty
}a_{k}x^{k-1}\right) \left( \sum_{k=1}^{\infty }b_{k}x^{k-1}\right) .
\end{equation*}%
In particular, if $c_{1}=1$ and $c_{k}=0$ for $k\geq 2,$ then the sequence $%
B $ has generating function $1/(a_{1}+a_{2}x+a_{3}x^{2}+\cdots ),$ and $A$
and $B$ are a pair of convolutory inverses.

Let $\mathcal{G}_{n}$ denote the group of finite sequences $A_{n}$ under $%
\star ;$ the identity is $I_{n}=(1,0,0,\ldots ,0),$ and $A_{n}^{-1}$ is the
sequence $B_{n}$ given inductively by $b_{1}=1$ and%
\begin{equation}
b_{n}=-\sum_{k=1}^{n-1}a_{n-k+1}b_{k}.
\end{equation}%
for $n\geq 2.$ \ The algebraic system $(\mathcal{G},\star )$ is a
commutative group known as the Appell subgroup of the Riordan group. $\ $\
Its elements, the Appell sequences, are special cases of the Sheffler
sequences, which play a leading role in the umbral calculus \cite[Chapter 4]{ref2};
however, the umbral developments are not used in this paper. \ In $\mathcal{G%
},$ the identity and $A^{-1}$ are the limits of $I_{n}$ and $A_{n}^{-1}.$ \
(Here, limits are of the combinatorial kind: \ suppose $j_{1},j_{2},j_{3},%
\ldots $ is an unbounded nondecreasing sequence of positive integers and $%
\{a_{i,j}\}$ is a sequence of sequences such for each $i,$%
\begin{equation*}
(a_{k,1},a_{k,2},a_{k,3},\ldots
,a_{k,j_{i}})=(a_{i,1},a_{i,2},a_{i,3},\ldots ,a_{i,j_{i}})
\end{equation*}%
for every $k>i.$ \ Then%
\begin{equation*}
\lim_{i\rightarrow \infty }(a_{i,1},a_{i,2},a_{i,3},\ldots )
\end{equation*}%
is defined as the sequence $(a_{1},a_{2},a_{3},\ldots )$ such that for every 
$n$ there exists $i_{0}$ such that if $i>i_{0},$ then%
\begin{equation*}
(a_{1},a_{2},a_{3},\ldots ,a_{n})=(a_{i,1},a_{i,2},a_{i,3},\ldots ,a_{i,n}).%
\text{)}
\end{equation*}%
The study of the group $(\mathcal{G},\star )$, we shall soon see, is
essentially that of a certain group of matrices. \ However, we shall
consider first a more general group of matrices.

For any positive integer $n$, let $\mathbb{G}_{n}$ be the set of lower
triangular $n\times n$ integer matrices with all diagonal entries $1,$ and
let $\cdot $ denote matrix multiplication. \ Then $(\mathbb{G}_{n},\cdot )$
is a noncommutative group. \ Now let $\mathbb{G}$ denote the set of lower
triangular infinite integer matrices with all diagonal entries $1.$ \ In
such a matrix, every column, excluding the zeros above the diagonal, is an
element of $\mathcal{G},$ and $(\mathbb{G},\cdot )$ is a noncommutative
group. \ Properties of matrices in $\mathbb{G}$ arise via limits of those of
matrices in $\mathbb{G}_{n}.$ \ For example, if $M=(m_{ij})\in \mathbb{G}$,
then the matrix $M_{n}:=(m_{ij})$, where $1\leq i\leq n$ and $1\leq j\leq n,$
is an element of $\mathbb{G}_{n},$ and%
\begin{equation*}
M^{-1}=\lim_{n\rightarrow \infty }M_{n}^{-1}.
\end{equation*}%
It is easy to check that if $A\in \mathcal{G}$ and $M\in \mathbb{G},$ then $%
M\cdot A\in \mathcal{G};$ here $A$ is regarded as an infinite column vector.

Among subgroups of $\mathbb{G}$ is the Riordan group\ (in the case that the
coefficients are all integers) introduced in \cite{ref3}. \ Although the Riordan
group will not be further discussed in this paper, the reader may wish to
consult the references listed at A053121 (the Catalan triangle) in \cite{ref4}.

Suppose $T=(t_{1},t_{2},t_{3},\ldots )\in \mathcal{G}.$ \ Let $\mathbb{T}$
be the matrix in $\mathbb{G}$ whose $i$th row is%
\begin{equation*}
t_{i},t_{i-1},\ldots ,t_{1},0,0\ldots ,
\end{equation*}%
so that the first column of $\mathbb{T}\ $is $T$, and each subsequent column
contains $T$ as a subsequence. \ Let $\mathbb{G}^{(1)}$ be the set of all
such matrices $\mathbb{T}$. \ If $\mathbb{T}$ and $\mathbb{U}$ in $\mathbb{G}%
^{(1)}$ have first columns $T$ and $U,$ respectively, then the first column
of $\mathbb{T\cdot U}$ is the sequence $T\star U,$ and $\mathbb{T\cdot U\in G%
}^{(1)}.$ \ Clearly, $(\mathbb{G}^{(1)},\cdot )$ is isomorphic to $(\mathcal{%
G},\star ).$ \ Matrices in $\mathbb{G}^{(1)}$ will be called \textit{%
sequential matrices.}

One more property of the group $\mathbb{G},$ with easy and omitted proof,
will be useful: \ if $M=(m_{ij})\in \mathbb{G}$ and $%
f(M):=((-1)^{i+j}m_{ij}),$ then%
\begin{equation}
(f(M))^{-1}=f(M^{-1}).
\end{equation}

\section{The Appell group $(\mathcal{G},\star )$}

The first theorem in this section concerns the convolutory inverse of a
linear recurrence sequence of order $m\geq 2$.\bigskip

\noindent\textbf{Theorem 1.} \ \textit{Suppose }$m\geq 2,$\textit{\ and }$%
a_{1}=1,a_{2},\ldots ,a_{m}$\textit{\ are initial values of an }$m$\textit{%
th order recurrence sequence given by}%
\begin{equation}
a_{n}=u_{1}a_{n-1}+u_{2}a_{n-2}+\cdots +u_{m}a_{n-m}+r_{n-m}
\end{equation}%
\textit{for }$n\geq m+1,$\textit{\ where }$u_{1},u_{2},\ldots ,u_{m}$\textit{%
\ and }$r_{1},r_{2},r_{3},\ldots $\textit{\ are integers and }$u_{m}\neq 0$%
\textit{. \ Then the convolutory inverse, }$B$\textit{, of }$A,$\textit{\ is
a sequence}%
\begin{equation*}
(1,b_{2},\ldots ,b_{m},b_{m+1},b_{m+2},\ldots )
\end{equation*}%
\textit{for which the subsequence }$(b_{m+2},b_{m+3},\ldots )$\textit{\
satisfies}%
\begin{equation*}
b_{n}=\sum_{k=1}^{m-1}b_{n-k}c_{k}-B_{n-m}\circledast R_{n-m},
\end{equation*}%
\textit{where}%
\begin{equation*}
c_{k}=-a_{k+1}+\sum_{j=1}^{k}u_{j}a_{k+1-j}
\end{equation*}%
\textit{for }$n\geq m+2.$\medskip 

\noindent\textit{Proof:} \ By (1), $b_{1}=a_{1}=1.$ \ Also, $b_{2}=-a_{2},$ and%
\begin{equation*}
b_{n}=-a_{n}b_{1}-a_{n-1}b_{2}-\cdots -a_{2}b_{n-1}
\end{equation*}%
for $n\geq 3.$ \ For the rest of this proof, assume that $n\geq m+2,$ and
for later convenience, let%
\begin{equation*}
s_{n}=-a_{n}b_{1}-a_{n-1}b_{2}-\cdots -a_{m+2}b_{n-m-1}.
\end{equation*}%
For $n\geq m+2$ (but not generally for $n=m+1),$ the recurrence (1) gives%
\begin{equation*}
\sum_{k=1}^{m}u_{k}b_{n-k}=-\sum_{j=1}^{n-m-1}b_{j}%
\sum_{k=1}^{m}u_{k}a_{n-k-j+1}-U,
\end{equation*}%
where%
\begin{equation*}
U=\sum_{k=1}^{m-1}u_{k}\sum_{j=2}^{m-k+1}a_{j}b_{n-k-j+1}.
\end{equation*}%
Then%
\begin{eqnarray*}
\sum_{k=1}^{m}u_{k}b_{n-k}
&=&-\sum_{j=1}^{n-m-1}b_{j}(a_{n+1-j}-r_{n+1-j-m})-U \\
&=&s_{n}+\sum_{j=1}^{n-m-1}b_{j}r_{n+1-j-m}-U \\
&=&b_{n}+\sum_{j=2}^{m+1}a_{j}b_{n+1-j}+\sum_{j=1}^{n-m-1}b_{j}r_{n+1-j-m}-U,
\end{eqnarray*}%
so that%
\begin{equation}
b_{n}=\sum_{k=1}^{m}u_{k}b_{n-k}-\sum_{j=2}^{m+1}a_{j}b_{n+1-j}-%
\sum_{j=1}^{n-m-1}b_{j}r_{n+1-j-m}+U.
\end{equation}%
Now put $n=m+1$ into (3) and substitute in (4) for $a_{m+1}.$ \ The
resulting coefficient of $b_{n-m}$ is $-r_{1},$ and (4) simplifies to%
\begin{eqnarray*}
b_{n}
&=&\sum_{k=1}^{m-1}u_{k}b_{n-k}-\sum_{j=2}^{m}a_{j}b_{n+1-j}+%
\sum_{k=1}^{m-2}u_{k}\sum_{j=2}^{m-k}a_{j}b_{n-k-j+1}-%
\sum_{j=1}^{n-m}b_{j}r_{n+1-j-m} \\
&=&\sum_{k=1}^{m-1}b_{n-k}(-a_{k+1}+\sum_{j=1}^{k}u_{j}a_{k+1-j})-%
\sum_{j=1}^{n-m}b_{j}r_{n+1-j-m.}\text{ \ \ \ \ \ \ \ \ \ }\blacksquare
\end{eqnarray*}%
\bigskip

\noindent\textbf{Corollary 1.}
\ If the recurrence for $A$ in (3) is homogeneous of
order $m\geq 2$, then the recurrence for the sequence $(b_{4},b_{5},b_{6},%
\ldots )$ is of order $m-1.$ \ If $m=2,$ then the convolutory inverse of $A$
is the sequence%
\begin{equation*}
(b_{1},b_{2},b_{3},\ldots )=(1,\text{ }-a_{2},\text{ }f,\text{ }%
(u_{1}-a_{2})f,\text{ }(u_{1}-a_{2})^{2}f,\text{ }(u_{1}-a_{2})^{3}f,\ldots
),
\end{equation*}%
where $f=a_{2}^{2}-a_{3}.$\bigskip

\noindent\textit{Proof:}
\ Homogeneity of $a$ means that $r_{n}=0$ for $n\geq 1,$ so
that $b_{n}=\sum_{k=1}^{m-1}c_{k}b_{n-k}$ for $n\geq m+2.$ \ \ \ \ \ \ \ \ \ 
$\blacksquare $\bigskip

\noindent\textbf{Example 1.}
\ The Fibonacci sequence, $A=(1,1,2,3,5,8,\ldots ),$ has
inverse $(1,-1,-1,0,0,0,0,0,\ldots )$.\bigskip

\noindent\textbf{Example 2.} \ The Lucas sequence, $A=(1,3,4,7,11,18,\ldots ),$ has
inverse, $(1,-3,5,-10,20,-40,80,\ldots ),$ recurrent with order $1$
beginning at the third term.\bigskip

\noindent\textbf{Example 3.} \ Let $A$ be the $2$nd-order nonhomogeneous sequence
given by $a_{1}=1,$ $a_{2}=1,$ and $a_{n}=a_{n-1}+a_{n-2}+n-2$ for $n\geq 3.$
\ The inverse of $A$ is the sequence $B=(1,-1,-2,-1,1,4,6,4,-4,-11,\ldots )$
given for $n\geq 4$ by%
\begin{equation*}
b_{n}=-B_{n-2}\circledast R_{n-2}=-(b_{1},b_{2},\cdots ,b_{n-2})\star
(1,2,3,\ldots ,n-2).
\end{equation*}

\noindent\textbf{Example 4.}
\ Suppose that $A$ and $C$ are sequences in $\mathcal{G}%
. $ \ Since $\mathcal{G}$ is a group, there exists $B$ in $\mathcal{G}$ such
that $A=B\star C.$ \ For example, if $A$ and $C$ are the Fibonacci and Lucas
sequences of Examples 1 and 2, then%
\begin{equation*}
B=A\star C^{-1}=(1,-2,4,-8,16,\ldots ),
\end{equation*}%
a $1$st-order sequence.\bigskip

\noindent\textbf{Theorem 2.} \ \textit{Let }$B=(1,b_{2},b_{3},\ldots )$\textit{\ be
the convolutory inverse of }$A=(1,a_{2},a_{3},\ldots ),$\textit{\ and let }$%
\widehat{A}=(1,-a_{2},a_{3},-a_{4},a_{5},-a_{6},\ldots ).$\textit{\ \ Then
the convolutory inverse of }$\widehat{A}$\textit{\ is the sequence }$%
\widehat{B}=(1,-b_{2},b_{3},-b_{4},b_{5},-b_{6},\ldots ).$\bigskip 

\noindent\textit{Proof:}
\ Apply (2) to the subgroup $\mathbb{G}^{(1)}$ of sequential
matrices. \ \ \ \ \ \ \ \ \ $\blacksquare $\bigskip

\noindent\textbf{Example 5.}
\ Let $A$ be the sequence given by $a_{n}=\lfloor n\tau
\rfloor ,$ where $\tau =(1+\sqrt{5})/2.$ \ Then%
\begin{equation*}
A=(1,3,4,6,8,9,11,12,\ldots )\text{ \ \ and \ \ }%
A^{-1}=(1,-3,5,-9,17,-30,52,-90,\ldots ).
\end{equation*}

Let $A$ be the sequence given by $a_{n}=(-1)^{n-1}\lfloor n\tau \rfloor .$ \
Then%
\begin{equation*}
A=(1,-3,4,-6,8,-9,11,-12,\ldots )\text{ \ \ and \ \ }%
A^{-1}=(1,3,5,9,17,30,52,90,\ldots ).
\end{equation*}

\noindent\textbf{Example 6.}
\ Let $A$ be the Catalan sequence, given by $a_{n}=\frac{%
1}{n}\left( 
\begin{array}{c}
2n-2 \\ 
n-1%
\end{array}%
\right) .$\ \ Then%
\begin{eqnarray*}
A &=&(1,1,2,5,14,42,132,429,1430,\ldots ) \\
A^{-1} &=&(1,-1,-1,-2,-5,-14,-42,-132,\ldots ).
\end{eqnarray*}

\noindent\textbf{Example 7.} \ Let $A$ be the sequence of central binomial
coefficients, given by $a_{n}=\left( 
\begin{array}{c}
2n-2 \\ 
n-1%
\end{array}%
\right) ,$ Then%
\begin{equation*}
A=(1,2,6,20,70,252,924,\ldots )\text{ \ \ and \ \ }%
A^{-1}=(1,-2,-2,-4,-10,-28,-84,-264,\ldots ),
\end{equation*}%
with obvious connections to the Catalan sequence.\bigskip

Certain operations on sequences in $\mathcal{G}$ are easily expressed in
terms of convolution. \ Two of these operations are given as follows. \
Suppose $x$ is an integer, and $A=(1,a_{2},a_{3},\ldots )$ is a sequence in $%
\mathcal{G},$ with inverse $B=(1,b_{2},b_{3},\ldots ).$ \ Then%
\begin{equation*}
(1,\text{ }xa_{2},\text{ }xa_{3},\text{ }xa_{4,}\ldots )=(1,\text{ }%
(1-x)b_{2},\text{ }(1-x)b_{3},\text{ }(1-x)b_{4},\ldots )\star A
\end{equation*}%
and 
\begin{equation*}
(1,\text{ }x,\text{ }a_{2},\text{ }a_{3},\ldots )=(1,\text{ }x+b_{2},\text{ }%
(x-1)b_{2}+b_{3},\text{ }(x-1)b_{3}+b_{4},\ldots )\star A.
\end{equation*}%
Stated in terms of power series%
\begin{equation*}
a(t)=1+a_{2}t+a_{3}t^{2}+\cdots \text{ \ and \ }%
1/a(t)=b(t)=1+b_{2}t+b_{3}t^{2}+\cdots ,
\end{equation*}%
the two operations correspond to the identities%
\begin{eqnarray*}
xa(t)+1-x &=&[(1-x)b(t)+x]a(t); \\
ta(t)+1+(x-1)t &=&\{b(t)+[(x-1)b(t)+1]t\}a(t).
\end{eqnarray*}

\section{The group $(\mathbb{G}^{(m)},\cdot )$}

Recall that the set $\mathbb{G}$ consists of the lower triangular infinite
integer matrices with all diagonal entries $1$. \ Define $^{\prime }$ on $%
\mathbb{G}$ as follows: \ if $A\in \mathbb{G}$, then $A^{\prime }$ is the
matrix that remains when row $1$ and column $1$ of $A$ are removed. \
Clearly $A^{\prime }\in \mathbb{G}$. \ Define%
\begin{equation*}
A^{(0)}=A,\text{ \ \ \ \ \ \ \ \ \ \ }A^{(n)}=(A^{(n-1)})^{\prime }
\end{equation*}%
for $n\geq 1.$ \ Let%
\begin{equation*}
\mathbb{G}^{(m)}=\{A\in \mathbb{G}:A^{(m)}=A\}
\end{equation*}%
for $m\geq 0.$ \ Note that $(\mathbb{G}^{(1)},\cdot )$ is the group of
sequential matrices introduced in Section 1, and $\mathbb{G}^{(m)}\subset 
\mathbb{G}^{(d)}$ if and only if $d|m.$\bigskip

\noindent\textbf{Theorem 3.}
\ $(G^{(m)},\cdot )$\textit{\ is a group for }$m\geq 0.$%
\bigskip 

\noindent\textit{Proof:} \ $(\mathbb{G}^{(0)},\cdot )$ is the group $(\mathbb{G}%
,\cdot ).$ \ For $m\geq 1,$ first note that $(AB)^{\prime }=A^{\prime
}B^{\prime },$ so that, inductively, $(AB)^{(q)}=A^{(q)}B^{(q)}$ for all $%
q\geq 1.$ \ In particular, if $A$ and $B$ are in $\mathbb{G}^{(m)},$ then%
\begin{equation*}
(AB)^{(m)}=A^{(m)}B^{(m)}=AB,
\end{equation*}%
so that $AB\in \mathbb{G}^{(m)}.$ \ Moreover,%
\begin{equation*}
(A^{-1})^{(m)}=(A^{(m)})^{-1}=A^{-1},
\end{equation*}%
so that $A^{-1}\in \mathbb{G}^{(m)}.$ \ \ \ \ \ \ \ \ \ $\blacksquare $%
\bigskip

\section{The group $(\mathbb{G}^{(2)},\cdot )$}

Suppose that $A,B,C,D$ are sequences in $\mathcal{G}.$ \ Let $\left\langle
A;B\right\rangle $ denote the matrix in $\mathbb{G}^{(2)}$ whose first
column is $A=(a_{1},a_{2},\ldots )$ and whose second column is $%
(0,b_{1},b_{2},\ldots ),$ where $a_{1}=b_{1}=1.$ \ We shall see that the
product $\left\langle A;B\right\rangle \cdot \left\langle C;D\right\rangle $
is given by certain ``mixed convolutions.'' \ Write $\left\langle
A;B\right\rangle \cdot \left\langle C;D\right\rangle $ as $\left\langle
U;V\right\rangle .$ \ Then%
\begin{equation*}
u_{n}=\left\{ 
\begin{tabular}{ll}
$(a_{1},b_{2},a_{3},\ldots ,b_{n-1},a_{n})\star (c_{1},c_{2},\ldots ,c_{n})$,
& if $n$ is odd; \\ 
$(b_{1},a_{2},b_{3},\ldots ,b_{n-1},a_{n})\star (c_{1},c_{2},\ldots ,c_{n})$,
& if $n$ is even;%
\end{tabular}%
\right.
\end{equation*}%
\begin{equation*}
v_{n}=\left\{ 
\begin{tabular}{ll}
$(b_{1},a_{2},b_{3},\ldots ,a_{n-1},b_{n})\star (d_{1},d_{2},\ldots ,d_{n}),$
& if $n$ is odd; \\ 
$(a_{1},b_{2},a_{3},\ldots ,a_{n-1},b_{n})\star (d_{1},d_{2},\ldots ,d_{n}),$
& if $n$ is even.%
\end{tabular}%
\right.
\end{equation*}%
In particular $\left\langle A;B\right\rangle \cdot \left\langle
B;A\right\rangle $ is the sequential matrix of the sequence $A\star B.$

Recursive formulas for columns of $\left\langle A;B\right\rangle ^{-1}$ can
also be given: \ write $\left\langle A;B\right\rangle ^{-1}$ as $%
\left\langle X;Y\right\rangle ,$ so that $\left\langle A;B\right\rangle
\cdot $ $\left\langle X;Y\right\rangle $ is the identity matrix. \ Each
nondiagonal entry of $\left\langle A;B\right\rangle \cdot $ $\left\langle
X;Y\right\rangle $ is zero, so that, solving inductively for $%
x_{1},x_{2},x_{3},\ldots $ and $y_{1},y_{2},y_{3},\ldots $ gives%
\begin{equation}
x_{n}=\left\{ 
\begin{tabular}{ll}
$-a_{n}-b_{n-1}x_{2}-a_{n-2}x_{3}-\cdots -b_{2}x_{n-1}$, & if $n$ is odd; \\ 
$-a_{n}-b_{n-1}x_{2}-a_{n-2}x_{3}-\cdots -a_{2}x_{n-1}$, & if $n$ is even;%
\end{tabular}%
\right.
\end{equation}%
\begin{equation}
y_{n}=\left\{ 
\begin{tabular}{ll}
$-b_{n}-a_{n-1}y_{2}-b_{n-2}y_{3}-\cdots -a_{2}y_{n-1}$, & if $n$ is odd; \\ 
$-b_{n}-a_{n-1}y_{2}-b_{n-2}y_{3}-\cdots -b_{2}y_{n-1}$, & if $n$ is even.%
\end{tabular}%
\right.
\end{equation}

\noindent\textbf{Example 8.} \ Example 6 shows that the Catalan sequence satisfies
the equation%
\begin{equation*}
(1,a_{2},a_{3},\ldots )^{-1}=(1,-1,-a_{2},-a_{3},\ldots ),
\end{equation*}%
which we abbreviate as $A^{-1}=(1,-A).$\ \ It is natural to ask whether
there are sequences $A$ and $B$ for which%
\begin{equation}
\left\langle A;B\right\rangle ^{-1}=\left\langle 1,-A;B\right\rangle .
\end{equation}%
This problem is solved as follows. \ Write the first and second columns of $%
\left\langle 1,-A;B\right\rangle $ as $(1,x_{2},x_{3},\ldots )$ and $%
(0,1,y_{2},y_{3},\ldots ),$ respectively. \ Equation (7) implies $%
x_{n}=-a_{n-1}$ and $y_{n}=b_{n}$ for $n\geq 2$. \ Thus, $b_{2}=y_{2}$, but
also, by (6), $y_{2}=-b_{2},$ so that $b_{2}=0.$ \ Inductively, (6) and (7)
imply $b_{n}=0$ for all $n\geq 3,$ so that $B$ is the convolutory identity
sequence: \ $B=(1,0,0,0,\ldots ).$ \ Using this fact together with (5) gives%
\begin{equation*}
x_{n}=\left\{ 
\begin{tabular}{ll}
$-a_{n}-a_{n-2}x_{3}-a_{n-4}x_{5}-\cdots -a_{2}x_{n-1}$, & if $n$ is even; \\ 
$-a_{n}-a_{n-2}x_{3}-a_{n-4}x_{5}-\cdots -a_{3}x_{n-2}$, & if $n$ is odd;%
\end{tabular}%
\right.
\end{equation*}%
so that, substituting $x_{k}=-a_{k-1},$ we have a recurrence for $A$:%
\begin{equation*}
a_{n}=\left\{ 
\begin{tabular}{ll}
$a_{n-1}+a_{n-2}a_{2}+a_{n-4}a_{4}+\cdots +a_{2}a_{n-2}$ & if $n$ is even; \\ 
$a_{n-1}+a_{n-2}a_{2}+a_{n-4}a_{4}+\cdots +a_{3}a_{n-3}$ & if $n$ is odd;%
\end{tabular}%
\right.
\end{equation*}%
with intial values $a_{1}=1,$ $a_{2}=1.$ \ This sequence, listed as A047749
in [4], is given by%
\begin{equation*}
a_{n}=\left\{ 
\begin{tabular}{ll}
$\frac{1}{2m+1}\left( 
\begin{array}{c}
3m \\ 
m%
\end{array}%
\right) $, & if $n=2m$; \\ 
$\frac{1}{2m+1}\left( 
\begin{array}{c}
3m+1 \\ 
m+1%
\end{array}%
\right) $, & if $n=2m+1.$%
\end{tabular}%
\right.
\end{equation*}%
\bigskip

\noindent\textbf{Example 9.}
\ Let $a_{n}=1$ and $b_{n}=F_{n}$ for $n\geq 1,$ where $%
F_{n}$ denotes the Fibonacci sequence in Example 1. \ Let $C$ be the
sequence given by $c_{1}=1,$ $c_{2}=-1,$ $c_{3}=0,$ $c_{4}=1,$ and $%
c_{n}=2^{\lfloor (n-5)/2\rfloor }$ for $n\geq 5.$ \ Let $D$ be the sequence
given by $d_{1}=1,$ $d_{2}=-1,$ $d_{3}=-1,$ and $d_{n}=-c_{n+1}$ for $n\geq
d_{4}.$ \ Then $\left\langle A;B\right\rangle ^{-1}=\left\langle
C;D\right\rangle .$\bigskip

\noindent\textbf{Theorem 4.} \ \textit{If any three of four sequences }$A,B,C,D$%
\textit{\ in }$G$\textit{\ are given, then the fourth sequence is uniquely
determined by the condition that }$\left\langle A;B\right\rangle \cdot
\left\langle C;D\right\rangle $\textit{\ be a sequential matrix.}\bigskip 

\noindent\textit{Proof:} \ The requirement that $\left\langle A;B\right\rangle \cdot
\left\langle C;D\right\rangle $ be a sequential matrix is equivalent to an
infinite system of equations, beginning with%
\begin{eqnarray*}
d_{1} &=&1 \\
b_{2}+d_{2} &=&a_{2}+c_{2} \\
b_{3}+a_{2}d_{2}+d_{3} &=&a_{3}+b_{2}c_{2}+c_{3}.
\end{eqnarray*}%
For $n\geq 3,$ the system can be expressed as follows:%
\begin{eqnarray}
&&b_{n}+a_{n-1}d_{2}+b_{n-2}d_{3}+\cdots +h_{2}d_{n-1}+d_{n}  \notag \\
&=&a_{n}+b_{n-1}c_{2}+a_{n-2}c_{3}+\cdots +h_{2}^{\prime }c_{n-1}+c_{n},
\end{eqnarray}%
where $h_{2}=a_{2}$ if $n$ is odd, $h_{2}=b_{2}$ if $n$ is even; and $%
h_{2}^{\prime }=b_{2}$ if $n$ is odd, $h_{2}^{\prime }=a_{2}$ if $n$ is even.

Equations (8) show that each of the four sequences is determined by the
other three. \ \ \ \ \ \ \ \ \ $\blacksquare $\bigskip

\noindent\textbf{Example 10.}
\ By (8), $D$ is determined by $A,B,C$ in accord with
the recurrence%
\begin{eqnarray}
d_{n} &=&a_{n}+c_{2}b_{n-1}+c_{3}a_{n-2}+c_{4}b_{n-3}+\cdots
+c_{n-1}h_{2}^{\prime }+c_{n}  \notag \\
&&-b_{n}-d_{2}a_{n-1}-d_{3}b_{n-2}-d_{4}a_{n-3}\cdots -d_{n-1}h_{2}.
\end{eqnarray}%
Suppose $a_{n}=b_{n}=c_{n-2}=0$ for $n\geq 3.$ \ Then by (9),%
\begin{equation*}
d_{n}=\left\{ 
\begin{tabular}{ll}
$-b_{2}d_{n-1}-a_{3}d_{n-2}$, & if $n$ is even; \\ 
$-a_{2}d_{n-1}-b_{3}d_{n-2}$, & if $n$ is odd; %
\end{tabular}%
\right.
\end{equation*}%
for $n\geq 4,$ with $d_{1}=1,$ $d_{2}=a_{2}-b_{2},$ $%
d_{3}=a_{3}-a_{2}d_{2}-b_{3}d_{1}.$ \ If $(a_{1},a_{2},a_{3})=(1,-1,-1)$ and 
$(b_{1},b_{2},b_{3})=(1,-2,-1)$ and $c_{1}=1,$ then%
\begin{equation*}
D=(1,1,1,3,4,11,15,41,56,153,\ldots ),
\end{equation*}%
which, except for the initial $1$, is the sequence of denominators of the
convergents to $\sqrt{3},$ indexed in [4] as A002530. \ In this example, $%
\left\langle A;B\right\rangle \cdot \left\langle C;D\right\rangle $ is the
sequential matrix with first three terms $1,-1,-1$ and all others
zero.\bigskip

\noindent\textbf{Theorem 5.} \ \textit{If }$A,B,C$\textit{\ in }$G$\textit{\ are
given and }$|a_{2}|=1,$\textit{\ then there exists a unique sequence }$D$%
\textit{\ in }$G$\textit{\ such that }$\left\langle A;B\right\rangle \cdot
\left\langle C;D\right\rangle =\left\langle C;D\right\rangle \cdot
\left\langle A;B\right\rangle $\textit{.}\bigskip 

\noindent\textit{Proof:} \ Write $\left\langle A;B\right\rangle \cdot \left\langle
C;D\right\rangle $ as $(s_{ij})$ and $\left\langle C;D\right\rangle \cdot
\left\langle A;B\right\rangle $ as $(t_{ij}).$ \ Equating $s_{n+1,1}$ and $%
t_{n+1,1}$ and solving for $d_{n}$ give%
\begin{equation}
d_{n}=\frac{1}{a_{2}}(u_{n}-v_{n})
\end{equation}%
for $n\geq 3,$ where%
\begin{eqnarray*}
u_{n} &=&\left\{ 
\begin{tabular}{ll}
$c_{2}b_{n}+c_{3}a_{n-1}+c_{4}b_{n-2}+\cdots +c_{n}a_{2}$, & if $n$ is odd; \\ 
$c_{2}b_{n}+c_{3}a_{n-1}+c_{4}b_{n-2}+\cdots +c_{n}b_{2}$, & if $n$ is even;%
\end{tabular}%
\right. \\
v_{n} &=&\left\{ 
\begin{tabular}{ll}
$a_{3}c_{n-1}+a_{4}d_{n-2}+\cdots +a_{n}c_{2}$, & if $n$ is odd; \\ 
$a_{3}c_{n-1}+a_{4}d_{n-2}+\cdots +a_{n}d_{2}$, & if $n$ is even;%
\end{tabular}%
\right.
\end{eqnarray*}%
with $d_{1}=1,$ $d_{2}=b_{2}c_{2}/a_{2}.$ \ A sequence $D$ is now determined
by (10); we shall refer to the foregoing as part 1.

It is necessary to check that the equations $s_{n+1,2}=t_{n+1,2}$ implied by%
\begin{equation*}
\left\langle A;B\right\rangle \cdot \left\langle C;D\right\rangle
=\left\langle C;D\right\rangle \cdot \left\langle A;B\right\rangle
\end{equation*}%
do not impose requirements on the sequence $D$ that are not implied by those
already shown to determine $D$. \ In fact, the equations $%
s_{n+1,2}=t_{n+1,2} $ with initial value $d_{1}=1$ determine exactly the
same sequence $D$. \ To see that this is so, consider the mapping $%
\left\langle A;B\right\rangle ^{\prime }=\left\langle B;A\right\rangle .$ \
It is easy to prove the following lemma:%
\begin{equation*}
(\left\langle A;B\right\rangle \cdot \left\langle C;D\right\rangle )^{\prime
}=\left\langle B;A\right\rangle \cdot \left\langle D;C\right\rangle .
\end{equation*}%
By part 1 applied to $\left\langle B;A\right\rangle \cdot \left\langle
D;C\right\rangle $ and $\left\langle D;C\right\rangle \cdot \left\langle
B;A\right\rangle ,$ the first column of $\left\langle B;A\right\rangle \cdot
\left\langle D;C\right\rangle $ equals the first column of $\left\langle
D;C\right\rangle \cdot \left\langle B;A\right\rangle .$ \ Therefore, by the
lemma, the second column of $\left\langle A;B\right\rangle \cdot
\left\langle C;D\right\rangle $ equals the second column of $\left\langle
C;D\right\rangle \cdot \left\langle A;B\right\rangle ,$ which is to say that
the equations $s_{n+1,2}=t_{n+1,2}$ hold. \ \ \ \ \ \ \ \ \ $\blacksquare $%
\bigskip

\noindent\textbf{Example 11.}
\ Let $a_{1}=1,$ $a_{2}=1,$ and $a_{n}=0$ for $n\geq 3.$
\ Let $B$ be the Fibonacci sequence. \ Let $C=(1,1,0,1,0,0,\ldots ),$ with $%
c_{n}=0$ for $n\geq 5.$ \ Then $D$ is given by $d_{1}=1,$ $d_{2}=1,$ $%
d_{3}=2,$ and $d_{n}=L_{n-1}$ for $n\geq 4,$ where $(L_{n})$ is the Lucas
sequence, as in Example 1. \ Writing $\left\langle A;B\right\rangle \cdot
\left\langle C;D\right\rangle $ as $\left\langle U,V\right\rangle ,$ we have 
$\left\langle U,V\right\rangle =\left\langle C;D\right\rangle \cdot
\left\langle A;B\right\rangle $, where $U=(1,2,1,3,4,7,11,18,\ldots )$ and $%
V=(1,2,5,9,20,32,66,105,207,\ldots ).$\bigskip

\section{Generalization of Theorem 4}

It is natural to ask what sort of generalization Theorem 4 has for $m\geq 3.$
\ The notation $\left\langle A;B\right\rangle $ used for matrices in $%
\mathbb{G}^{(2)}$ is now generalized in the obvious manner to $\left\langle
A_{1},A_{2},\ldots ,A_{m}\right\rangle $ in $\mathbb{G}^{(m)},$ where $A_{i}$
is a sequence $(a_{i1},a_{i2},\ldots )$ having $a_{i1}=1,$ for $i=1,2,\ldots
,m.$\bigskip

\noindent\textbf{Theorem 4A.}
\ \textit{Suppose }$A_{1},A_{2},\ldots ,A_{m}$\textit{\
and }$B_{i}$\textit{\ for some }$i$\textit{\ satisfying }$1\leq i\leq m$%
\textit{\ are given. }$\ $\textit{Then sequences }$B_{j}$\textit{\ for }$%
j\neq i$\textit{\ are uniquely determined by the condition that }$%
\left\langle A_{1},A_{2},\ldots ,A_{m}\right\rangle \cdot \left\langle
B_{1},B_{2},\ldots ,B_{m}\right\rangle $\textit{\ be a sequential matrix. \
Conversely, suppose }$B_{1},B_{2},\ldots ,B_{m}$\textit{\ and }$A_{i}$%
\textit{\ for some }$i$\textit{\ satisfying }$1\leq i\leq m$\textit{\ are
given. }$\ $\textit{Then sequences }$A_{j}$\textit{\ for }$j\neq i$\textit{\
are uniquely determined by the condition that }$\left\langle
A_{1},A_{2},\ldots ,A_{m}\right\rangle \cdot \left\langle B_{1},B_{2},\ldots
,B_{m}\right\rangle $\textit{\ be a sequential matrix.}\smallskip 

\noindent\textit{Proof:}
\ Let\ $U=AB.$ \ For given $A,$ each column of $B$ uniquely
determines the corresponding column of $U$, and each column of $U$
determines the corresponding column of $B.$ \ Thus, under the hypothesis
that a particular column $B_{i}$ of $B$ is given, the equation $U=AB$
determines the corresponding column of $U$. \ Consequently, as $U$ is a
sequential matrix, every column of $U$ is determined, and this implies that
every column of $B$ is determined.

For the converse, suppose $B,$ together with just one column $A_{i}$ of $A,$
are given, and that the product $U=AB$ is sequential. \ As a first induction
step,%
\begin{equation}
a_{21}b_{11}+a_{22}b_{21}=a_{32}b_{22}+a_{33}b_{32}=\cdots \text{ }.
\end{equation}%
As $a_{i+1,i}$ is given, equations (11) show that $a_{h+1,h}$ is determined
for all $h\geq 1.$ \ Assume for arbitrary $k\geq 1$ that $a_{h+j,h}$ is
determined for all $j$ satisfying $1\leq j\leq k,$ for all $h\geq 1.$ \ As $%
U $ is sequential,%
\begin{eqnarray}
&&a_{k+1,1}b_{11}+a_{k+1,2}b_{21}+\cdots +a_{k+1,k+1}b_{k+1,1}  \notag \\
&=&a_{k+2,2}b_{22}+a_{k+2,3}b_{32}+\cdots +a_{k+2,k+2}b_{k+2,2}  \notag \\
&=&\cdots \text{ .}
\end{eqnarray}%
As $a_{k+i,i}$ is given, equations (12) and the induction hypothesis show
that $a_{k+h,h}$ is determined for all $h\geq 1.$ \ Thus, by induction, $A$
is determined. \ \ \ \ \ \ \ \ \ $\blacksquare $\bigskip

Theorem 4A shows that Theorem 4 extends to $\mathbb{G}^{(m)}.$ \ The method
of proof of Theorem 4A clearly applies to $\mathbb{G},$ so that Theorem 4A
extends to $\mathbb{G}$.

\section{Transformations involving divisors}

We return to the general group $(\mathbb{G},\cdot )$ for a discussion of
several specific matrix transformations involving divisors of integers. \
The first is given by the left summatory matrix,%
\begin{equation*}
T(n,k)=\left\{ 
\begin{tabular}{ll}
$1$, & if $k|n$; \\ 
$0$, & otherwise.%
\end{tabular}%
\right.
\end{equation*}%
The inverse of $T$ is the left M\"{o}bius transformation matrix. \ The
matrices $T$ and $T^{-1}$ are indexed as A077049 and A077050 in \cite{ref4}, where
transformations by $T$ and $T^{-1}$ of selected sequences in $\mathcal{G}$
are referenced. \ In general, if $A$ is a sequence written as an infinite
column vector, then%
\begin{equation*}
T\cdot A=\{\sum_{k|n}a_{k}\}\text{ \ \ \ \ \ \ and \ \ \ \ \ \ }T^{-1}\cdot
A=\{\sum_{k|n}\mu (k)a_{k}\},
\end{equation*}%
that is, the summatory sequence of $A$ and the M\"{o}bius transform of $A,$
respectively.

Next, define the \textit{left summing matrix }$S=\{s(n,k)\}$ and the \textit{%
left differencing matrix }$D=\{d(n,k)\}$ by%
\begin{eqnarray*}
s(n,k) &=&\left\{ 
\begin{tabular}{ll}
$1$, & if $k\leq n$; \\ 
$0$, & otherwise.%
\end{tabular}%
\right. \\
d(n,k) &=&\left\{ 
\begin{tabular}{ll}
$(-1)^{n+k}$, & if $k=n$ or $k=n-1$; \\ 
$0$, & otherwise.%
\end{tabular}%
\right.
\end{eqnarray*}%
Note that $D=S^{-1}.$\bigskip

\noindent\textbf{Example 12.}
\ Suppose that a sequence $C=(1,c_{2},c_{3},\ldots )$
in $\mathcal{G}$ is transformed to a sequence $A=(1,a_{2},a_{3},\ldots )$ by
the sums $a_{n}=\sum_{k=1}^{n}c_{k}\lfloor n/k\rfloor .$ \ In order to solve
this system of equations, let $U(n,k)=\lfloor n/k\rfloor $ for $k\geq 1,$ $%
n\geq 1.$ \ Then $U=S\cdot T,$ so that $U^{-1}=T^{-1}\cdot D,$ which means
that%
\begin{equation*}
c_{n}=\sum_{d|n}\mu (d)(a_{n/d}-a_{n/d-1}),
\end{equation*}%
where $a_{0}:=0.$ \ If $a_{n}=1$ for every $n\geq 1$, then $c_{n}=\mu (n).$
\ If $a_{n}=n$, then $C$ is the convolutory identity, $(1,0,0,0,\ldots ).$ $%
\ $If $a_{n}=\left( 
\begin{array}{c}
n+1 \\ 
2%
\end{array}%
\right) ,$ then $c_{n}=\varphi (n)$. $\ $If $a_{n}=\left( 
\begin{array}{c}
n+2 \\ 
3%
\end{array}%
\right) ,$ then $C$ is the sequence indexed as A000741 in \cite{ref4} and discussed
in \cite{ref1} in connection with compositions of integers with relatively prime
summands.\bigskip \bigskip \bigskip

\begin{thebibliography}{9}

\bibitem{ref1}
H. W. Gould, Binomial coefficients, the bracket function, and
compositions with relatively prime summands, \textit{Fibonacci
Quart.} \textbf{2} (1964) 241--260. 

\bibitem{ref2}
Steven Roman, \textit{The Umbral Calculus, }Academic Press, \textit{New
York, 1984.}

\bibitem{ref3}
Louis W. Shapiro, Seyoum Getu, Wen-Jin Woan, and Leon C. Woodson, The
Riordan group, \textit{Disc.\ Appl.\ Math.} \textbf{34} (1991)
229--239.

\bibitem{ref4}
N. J. A. Sloane \textit{The On-Line Encyclopedia of
Integer Sequences},
\href{http://www.research.att.com/~njas/sequences}{\texttt{http://www.research.att.com/\symbol{126}njas/sequences}}.

\end{thebibliography}

\bigskip
\hrule
\bigskip

\noindent 2000 {\it Mathematics Subject Classification}:
Primary 11A25.\ \

\noindent \emph{Keywords: Appell sequence,
convolution,
Fibonacci sequence,
linear recurrence,
Riordan group,
sequential matrix.
}


\bigskip
\hrule
\bigskip

\noindent (Concerned with sequences
\seqnum{A000045},
\seqnum{A000108}
\seqnum{A000142}
\seqnum{A000201}
\seqnum{A000204}
\seqnum{A000741}
\seqnum{A000984}
\seqnum{A002530}
\seqnum{A047749}
\seqnum{A077049}
\seqnum{A077050}
\seqnum{A077605}
\seqnum{A077606}.)

\bigskip
\hrule
\bigskip

\vspace*{+.1in}
\noindent
Received November 13, 2002;
revised versions received  January 28, 2003;
September 2, 2003.
Published in {\it Journal of Integer Sequences},
September 8, 2003.
\bigskip
\hrule
\bigskip

\noindent
Return to
\htmladdnormallink{Journal of Integer Sequences home page}{http://www.math.uwaterloo.ca/JIS/}.
\vskip .1in


\end{document}