On the Hurwitz Transform of Sequences

Paul Barry School of Science Waterford Institute of Technology Ireland

                         pbarry@wit.ie

Abstract Based on classical concepts, we introduce and study the Hurwitz transform of sequences, relating this transform to the Hankel transform of sequences. We also define and study associated polynomials, including links to related families of orthogonal polynomials. Examples of these associated polynomials are given within the context of Riordan arrays.

1 Introduction

Given a sequence a_{n}, we denote by h_{n} the general term of the sequence with h_{n} = |a_{i+j}|_{0≤i,j≤n}. The sequence h_{n} is called the Hankel transform of a_{n} [19, 20, 21]. This sequence of Hankel determinants has attracted much attention of late amongst those working in the area of integer and polynomial sequences in particular [7, 18, 24, 32]. In this note we shall introduce the notion of a related Hurwitz transform, and we shall study some of its properties. As with the Hankel transform, this transform is based on classical results which have a rich literature. Part of this literature is captured in the review article by Holtz and Tyaglov [17], which forms a good background to this note. Our Hurwitz transform will give rise to a sequence of determinant values, which can be related to the Hankel transform.

In the sequel, we shall be mainly concerned with integer sequences. Known integer sequences are often referred to by their OEIS number [26, 27]. For instance, the sequence of Catalan numbers C_{n} = \frac{1}{n+1} \binom{2n}{n} is \underline{A000108}. Its generating function, defined by ∑_{n=0}^{∞} C_{n}x^{n}, is equal to c(x) = \frac{1−\sqrt{1−4x}}{2x}. Its first elements are

1, 1, 2, 5, 14, 42, 132, ….

This sequence finds many applications in combinatorics [29, 30]. It is the unique sequence whose Hankel transform, along with that of its first shift C_{n+1}, is the all 1’s sequence [4, 22]. We use it in many of our examples, partly because of these properties.

We recall the following notational elements. For an integer sequence a_{n}, that is, an element of ℤ^{ℕ}, the power series f(x) = ∑_{k=0}^{∞} a_{n}x^{n} is called the ordinary generating function or g.f. of the sequence. a_{n} is thus the coefficient of x^{n} in this series. We denote this by a_{n} = [x^{n}]f(x) [23]. For instance, F_{n} = [x^{n}]\frac{x}{1−x−x^{2}} is the n-th Fibonacci number \underline{A000045}, while C_{n} = [x^{n}]\frac{1−\sqrt{1−4x}}{2x}. We use the notation 0^{n} = [x^{n}]1 for the sequence 1, 0, 0, 0, …, \underline{A000007}. Thus 0^{n} = [n = 0] = δ_{n,0} = \binom{0}{n}. Here, we have used the Iverson bracket notation [13], defined by [P] = 1 if the proposition P is true, and [P] = 0 if P is false.

For a power series f(x) = ∑_{n=0}^{∞} a_{n}x^{n} with f(0) = 0 we define the reversion or compositional inverse of f to be the power series f̄(x) such that f(f̄(x)) = x.

2 Definition of the Hurwitz transform

We consider two sequences a_{n} and b_{n}, and define the Hurwitz matrix of order n defined by these sequences as follows. If n is even, n = 2m, then the Hurwitz matrix of order n is defined to be the matrix

H_{n} = ( \begin{matrix}a_{0} & a_{1} & a_{2} & ⋯ & a_{m} & ⋯ & a_{2m} \\ b_{0} & b_{1} & b_{2} & ⋯ & b_{m} & ⋯ & b_{2m} \\ 0 & a_{0} & a_{1} & ⋯ & a_{m−1} & ⋯ & a_{2m−1} \\ 0 & b_{0} & b_{1} & ⋯ & b_{m−1} & ⋯ & b_{2m−1} \\ ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ⋮ \\ 0 & 0 & 0 & ⋯ & a_{0} & ⋯ & a_{m} \end{matrix} ) .

If n is odd, n = 2m + 1, then the Hurwitz matrix of order n is defined to be the matrix

H_{n} = ( \begin{matrix}a_{0} & a_{1} & a_{2} & ⋯ & a_{m} & ⋯ & a_{2m+1} \\ b_{0} & b_{1} & b_{2} & ⋯ & b_{m} & ⋯ & b_{2m+1} \\ 0 & a_{0} & a_{1} & ⋯ & a_{m−1} & ⋯ & a_{2m} \\ 0 & b_{0} & b_{1} & ⋯ & b_{m−1} & ⋯ & b_{2m} \\ ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ⋮ \\ 0 & 0 & 0 & ⋯ & a_{0} & ⋯ & a_{m+1} \\ 0 & 0 & 0 & ⋯ & b_{0} & ⋯ & b_{m+1} \end{matrix} ) .

We shall call the sequence of determinants ℍ_{n} = |H_{n}| the Hurwitz transform of the sequences a_{n} and b_{n} (in that order). We shall sometimes write ℍ_{n}(a_{n}, b_{n}) or ℍ_{n}(a, b) for the transform of a_{n} and b_{n}, to make the dependence on a_{n} and b_{n} more explicit. By the definition, it is clear that if a_{n} and b_{n} are integer sequences, then ℍ_{n} is an integer sequence. We have

ℍ_{n}(a, a) = a_{0}0^{n} = \begin{cases}a_{0}, & if n = 0; \\ 0, & n > 0. \end{cases}

Note that we can express the general term H_{i,j} of the Hurwitz matrix in the following manner.

H_{i,j} = \begin{cases}0, & if 2j + 2 ≤ i; \\ a_{j− \frac{i}{2}} , & if 2|i; \\ b_{j− \frac{i−1}{2}} , & otherwise. \end{cases}  (1)

We can associate a sequence s_{n} with the two sequences a_{n} and b_{n} in the following manner. We can define s_{n} implicity by the relations

a_{n} = ∑_{k=0}^{n} s_{k}b_{n−k},

which is a convolution equation for s_{n}. If b_{0} ≠ 0 (which we will assume henceforth), we have

s_{n} = [x^{n}]\frac{∑_{j=0}^{∞} a_{j}x^{j}}{∑_{j=0}^{∞} b_{j}x^{j}} .

That is, s_{n} is the sequence whose generating function is the quotient of the generating function f(x) = ∑_{n=0}^{∞} a_{n}x^{n} of a_{n} and of the generating function g(x) = ∑_{n=0}^{∞} b_{n}x^{n} of b_{n}. Using generating functions allows us to express the elements of the Hurwitz matrix as follows.

H_{j,i} = \begin{cases}[x^{i}]x^{\frac{j}{2}} f(x), & if 2|j; \\ [x^{i}]x^{\frac{j−1}{2}} g(x), & otherwise. \end{cases}  (2)

We let h_{n} denote the Hankel transform of s_{n} and we let h_{n}^{∗} denote the Hankel transform of the shifted sequence s_{n}^{∗} = s_{n+1}. Then we have the following proposition characterizing ℍ_{n}. Proposition 1. We have

ℍ_{2n} = b_{0}^{2n+1}h_{n}, ℍ_{2n+1} = (−1)^{n+1}b_{0}^{2n+2}h_{n}^{∗}.

Proof. We take the case n = 2m. Beginning with the original matrix, we carry out the following steps.

1. Factor b_{0} out of column 0.

2. Subtract b_{j} times column 0 from column j for 1 ≤ j ≤ 2m.

3. Factor b_{0} out of column 1.

4. Subtract b_{j−1} times column 1 from column j for 2 ≤ j ≤ 2m.

5. Factor b_{0} out of column 2.

6. Subtract b_{j−2} times column 2 from column j for 3 ≤ j ≤ 2m.

7. etc.

One has now factored b_{0} out 2m + 1 times, and the resulting matrix is

( \begin{matrix}s_{0} & s_{1} & s_{2} & ⋯ & s_{m−1} & s_{m} & ⋯ & s_{2m} \\ 1 & 0 & 0 & ⋯ & 0 & 0 & ⋯ & 0 \\ 0 & s_{0} & s_{1} & ⋯ & s_{m−2} & s_{m−1} & ⋯ & s_{2m−1} \\ 0 & 1 & 0 & ⋯ & 0 & 0 & ⋯ & 0 \\ 0 & 0 & s_{0} & ⋯ & s_{m−3} & s_{m−2} & ⋯ & s_{2m−2} \\ 0 & 0 & 1 & ⋯ & 0 & 0 & ⋯ & 0 \\ ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ⋮ \\ 0 & 0 & 0 & ⋯ & 1 & 0 & ⋯ & 0 \\ 0 & 0 & 0 & ⋯ & 0 & s_{0} & ⋯ & s_{m} \end{matrix} ) .

Expanding iteratively along the rows with a single 1 we get an “upside-down” Hankel determinant

| \begin{matrix}s_{m} & ⋯ & s_{2m} \\ s_{m−1} & ⋯ & s_{2m−1} \\ ⋮ & ⋮ & ⋮ \\ s_{0} & ⋯ & s_{m} \end{matrix} | .

Now looking at the case n = 2m + 1, we get the matrix

( \begin{matrix}s_{0} & s_{1} & s_{2} & ⋯ & s_{m−1} & s_{m} & s_{m+1} & ⋯ & s_{2m+1} \\ 1 & 0 & 0 & ⋯ & 0 & 0 & 0 & ⋯ & 0 \\ 0 & s_{0} & s_{1} & ⋯ & s_{m−2} & s_{m−1} & s_{m} & ⋯ & s_{2m} \\ 0 & 1 & 0 & ⋯ & 0 & 0 & 0 & ⋯ & 0 \\ 0 & 0 & s_{0} & ⋯ & s_{m−3} & s_{m−2} & s_{m−1} & ⋯ & s_{2m−1} \\ 0 & 0 & 1 & ⋯ & 0 & 0 & 0 & ⋯ & 0 \\ ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ⋮ \\ 0 & 0 & 0 & ⋯ & 0 & s_{0} & s_{1} & ⋯ & s_{m+1} \\ 0 & 0 & 0 & ⋯ & 0 & 1 & 0 & ⋯ & 0 \end{matrix} ) .

Again, expanding iteratively along the rows with a single 1 we get an “upside-down” Hankel determinant

| \begin{matrix}s_{m+1} & ⋯ & s_{2m+1} \\ s_{m} & ⋯ & s_{2m} \\ ⋮ & ⋮ & ⋮ \\ s_{1} & ⋯ & s_{m+1} \end{matrix} | .

Keeping track of signs now yields the result.

By looking at the transposed matrix, (H_{i,j})^{T}, we can interpret the above operations as follows, where we use the notation of Riordan arrays (see the section on Riordan arrays).

We have

(g(x), x)^{−1} · (H_{i,j})^{T} = (\frac{1}{g(x)}, x) · (H_{j,i})

= (\frac{1}{g(x)}, x) · (\begin{cases}[x^{i}]x^{\frac{j}{2}} f(x), & if 2|j; \\ [x^{i}]x^{\frac{j−1}{2}} g(x), & otherwise. \end{cases})

= (\begin{cases}[x^{i}]x^{\frac{j}{2}} \frac{f(x)}{g(x)}, & if 2|j; \\ [x^{i}]x^{\frac{j−1}{2}} \frac{g(x)}{g(x)}, & otherwise. \end{cases})

= (\begin{cases}[x^{i}]x^{\frac{j}{2}} \frac{f(x)}{g(x)}, & if 2|j; \\ [x^{i}]x^{\frac{j−1}{2}} , & otherwise. \end{cases})

= (\begin{cases}[x^{i}]x^{\frac{j}{2}} s(x), & if 2|j; \\ [x^{i}]x^{\frac{j−1}{2}} , & otherwise. \end{cases}) .

Transposing and taking the first n + 1 rows and columns (for n = 2m and n = 2m + 1) brings us back to the above cases. Note that the determinant of (g(x), x)_{n}^{−1} is \frac{1}{b_{0}^{n+1}} .

We thus have

( \begin{matrix}b_{0} & & & & ⋯ \\ b_{1} & b_{0} & & & ⋯ \\ b_{2} & b_{1} & b_{0} & & ⋯ \\ b_{3} & b_{2} & b_{1} & b_{0} & ⋯ \\ ⋮ & ⋮ & ⋮ & ⋮ & ... \end{matrix} )^{−1} · ( \begin{matrix}a_{0} & b_{0} & 0 & 0 & ⋯ \\ a_{1} & b_{1} & a_{0} & b_{0} & ⋯ \\ a_{2} & b_{2} & a_{1} & b_{1} & ⋯ \\ a_{3} & b_{3} & a_{2} & b_{2} & ⋯ \\ ⋮ & ⋮ & ⋮ & ⋮ & ... \end{matrix} ) = ( \begin{matrix}s_{0} & 1 & 0 & 0 & ⋯ \\ s_{1} & 0 & s_{0} & 1 & ⋯ \\ s_{2} & 0 & s_{1} & 0 & ⋯ \\ s_{3} & 0 & s_{2} & 0 & ⋯ \\ ⋮ & ⋮ & ⋮ & ⋮ & ... \end{matrix} )

and hence

( \begin{matrix}a_{0} & b_{0} & 0 & 0 & ⋯ \\ a_{1} & b_{1} & a_{0} & b_{0} & ⋯ \\ a_{2} & b_{2} & a_{1} & b_{1} & ⋯ \\ a_{3} & b_{3} & a_{2} & b_{2} & ⋯ \\ ⋮ & ⋮ & ⋮ & ⋮ & ... \end{matrix} ) = ( \begin{matrix}b_{0} & & & & ⋯ \\ b_{1} & b_{0} & & & ⋯ \\ b_{2} & b_{1} & b_{0} & & ⋯ \\ b_{3} & b_{2} & b_{1} & b_{0} & ⋯ \\ ⋮ & ⋮ & ⋮ & ⋮ & ... \end{matrix} ) · ( \begin{matrix}s_{0} & 1 & 0 & 0 & ⋯ \\ s_{1} & 0 & s_{0} & 1 & ⋯ \\ s_{2} & 0 & s_{1} & 0 & ⋯ \\ s_{3} & 0 & s_{2} & 0 & ⋯ \\ ⋮ & ⋮ & ⋮ & ⋮ & ... \end{matrix} ) .

Example 2. It is possible to gain further insight into this result by using Gaussian elimination in the following way. Let s(x) be the g.f. of s_{n}. Then we have

s(x) = \frac{f(x)}{g(x)} ⇒ f(x) = s(x)g(x).

That is

∑_{n=0}^{∞} a_{n}x^{n} = (∑_{n=0}^{∞} s_{n}x^{n}) (∑_{n=0}^{∞} b_{n}x^{n}) = ∑_{n=0}^{∞} ∑_{k=0}^{n} s_{k}b_{n−k}x^{n},

or

a_{n} = ∑_{k=0}^{n} s_{k}b_{n−k}.

We now substitute for a_{n} in the definitions of H_{n}. For instance, we get

H_{n} = ( \begin{matrix}s_{0}b_{0} & s_{0}b_{1} + s_{1}b_{0} & s_{0}b_{2} + s_{1}b_{1} + s_{2}b_{0} & ⋯ & s_{0}b_{m} + … & ⋯ & s_{0}b_{2m} + … \\ b_{0} & b_{1} & b_{2} & ⋯ & b_{m} & ⋯ & b_{2m} \\ 0 & s_{0}b_{0} & s_{0}b_{1} + s_{1}b_{0} & ⋯ & s_{0}b_{m−1} + … & ⋯ & s_{0}b_{2m−1} + … \\ 0 & b_{0} & b_{1} & ⋯ & b_{m−1} & ⋯ & b_{2m−1} \\ ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ⋮ \\ 0 & 0 & 0 & ⋯ & s_{0}b_{0} & ⋯ & s_{0}b_{m+1} + … \end{matrix} )

for n = 2m. For instance, assuming that s_{0} ≠ 0, s_{1} ≠ 0, we have

ℍ_{2} = | \begin{matrix}s_{0}b_{0} & s_{0}b_{1} + s_{1}b_{0} & s_{0}b_{2} + s_{1}b_{1} + s_{2}b_{0} \\ b_{0} & b_{1} & b_{2} \\ 0 & s_{0}b_{0} & s_{0}b_{1} + s_{1}b_{0} \end{matrix} |

= \frac{1}{s_{0}} | \begin{matrix}s_{0}b_{0} & s_{0}b_{1} + s_{1}b_{0} & s_{0}b_{2} + s_{1}b_{1} + s_{2}b_{0} \\ s_{0}b_{0} & s_{0}b_{1} & s_{0}b_{2} \\ 0 & s_{0}b_{0} & s_{0}b_{1} + s_{1}b_{0} \end{matrix} |

= \frac{1}{s_{0}} | \begin{matrix}s_{0}b_{0} & s_{0}b_{1} + s_{1}b_{0} & s_{0}b_{2} + s_{1}b_{1} + s_{2}b_{0} \\ 0 & −s_{1}b_{0} & −s_{1}b_{1} − s_{2}b_{0} \\ 0 & s_{0}b_{0} & s_{0}b_{1} + s_{1}b_{0} \end{matrix} |

= \frac{1}{s_{0}^{2}s_{1}} | \begin{matrix}s_{0}b_{0} & s_{0}b_{1} + s_{1}b_{0} & s_{0}b_{2} + s_{1}b_{1} + s_{2}b_{0} \\ 0 & −s_{0}s_{1}b_{0} & −s_{0}s_{1}b_{1} − s_{0}s_{2}b_{0} \\ 0 & 0 & (s_{1}^{2} − s_{0}s_{2})b_{0} \end{matrix} |

= b_{0}^{3}(s_{0}s_{2} − s_{1}^{2})

= b_{0}^{3} | \begin{matrix}s_{0} & s_{1} \\ s_{1} & s_{2} \end{matrix} | .

Similarly, we obtain

ℍ_{3} = \frac{1}{s_{0}^{4}s_{1}^{2}(s_{1}^{2} − s_{0}s_{2})} | \begin{matrix}s_{0}b_{0} & … & … & … \\ 0 & −s_{0}s_{1}b_{0} & … & … \\ 0 & 0 & s_{0}s_{1}(s_{1}^{2} − s_{0}s_{2})b_{0} & … \\ 0 & 0 & 0 & s_{0}s_{1}(s_{2}^{2} − s_{1}s_{3})b_{0} \end{matrix} | ,

and hence we have

ℍ_{3} = b_{0}^{4}(s_{2}^{2} − s_{1}s_{3}) = b_{0}^{4} | \begin{matrix}s_{1} & s_{2} \\ s_{2} & s_{3} \end{matrix} | .

Finally we note that

ℍ_{n}(αa_{n}, βb_{n}) = α^{⌊ \frac{n+2}{2} ⌋}β^{⌊ \frac{n+1}{2} ⌋}ℍ_{n}(a_{n}, b_{n}).

Example 3. It is well-known that the Hankel transform of the Catalan numbers C_{n}, along with that of the shifted sequence C_{n+1}, is given by the all 1’s sequence. We thus turn to the Catalan numbers to provide an example of a pair of sequences whose Hurwitz transform is the all 1’s sequence. We recall that the sequence C_{n} has generating function

c(x) = \frac{1 − \sqrt{1 − 4x}}{2x}.

We define C_{−1} = 0. Then the Hurwitz transform of the pair

a_{n} = (−1)^{n}(C_{n} + C_{n−1}), b_{n} = (−1)^{n}\binom{1}{n}

is such that

ℍ_{n} = 1 for all n.

This follows since in this case,

f(x) = (1 − x)c(−x), g(x) = 1 − x.

Then

\frac{f(x)}{g(x)} = \frac{(1 − x)c(−x)}{1 − x} = c(−x),

which is the generating function of (−1)^{n}C_{n}. The Hankel transform of (−1)^{n}C_{n} is 1, 1, 1, … while that of (−1)^{n+1}C_{n+1} is (−1)^{n+1}, hence the result.

It is clear that any pair of sequences a_{n}, b_{n} such that \frac{f(x)}{g(x)} = c(−x) will furnish a Hurwitz transform consisting of the all 1’s sequence. Thus, as with the Hankel transform, the Hurwitz transform is not injective.

Example 4. We now look at an example where b_{0} ≠ 1. Thus we take

a_{n} = C_{n}, b_{n} = C_{n} + C_{n+1},

with

f(x) = c(x), g(x) = c(x) + c(x)^{2}, s(x) = \frac{1}{1 + c(x)} = \frac{1 + 2x + \sqrt{1 − 4x}}{2(x + 2)}.

We have b_{0} = 2. In this case, we find that

s_{n} = \frac{1}{2^{n+1}} ∑_{k=0}^{n−1} \frac{n − k}{n} \binom{n + k − 1}{k}2^{k},

which begins

\frac{1}{2}, −\frac{1}{4}, −\frac{3}{8}, −\frac{13}{16}, −\frac{67}{32}, −\frac{381}{64}, ….

We find that

2^{2n+1}h_{n} = (−1)^{n}(n + 1), 2^{2n+2}(−1)^{n+1}h_{n}^{∗} = 1,

and so the Hurwitz transform ℍ_{n}(C_{n}, C_{n} + C_{n+1}) is given by

1, 1, −2, 1, 3, 1, −4, 1, 5, 1, −6, ….

Example 5. This example uses the Motzkin numbers \underline{A001006}

M_{n} = ∑_{k=0}^{⌊ \frac{n}{2} ⌋} \binom{n}{2k}C_{k},

with generating function

\frac{1 − x − \sqrt{1 − 2x − 3x^{2}}}{2x^{2}} .

We let

a_{n} = M_{n}, b_{n} = M_{n} + M_{n+1}.

We find that s_{n} has the generating function

\frac{1 + 3x + \sqrt{1 − 2x − 3x^{2}}}{6x + 4} ,

and begins

\frac{1}{2}, −\frac{1}{4}, −\frac{1}{8}, −\frac{5}{16}, −\frac{17}{32}, −\frac{77}{64}, ….

We find that 2^{2n+1}h_{n} is the periodic sequence that begins

1, −1, 0, 1, −1, 0, 1, −1, 0, …,

while 2^{2n+2}(−1)^{n+1}h_{n}^{∗} is the all 1’s sequence. Thus we find that ℍ_{n}(M_{n}, M_{n} + M_{n+1}) is the periodic sequence

1, 1, −1, 1, 0, 1, 1, 1, −1, 1, 0, 1, 1, 1, −1, 1, 0, 1, 1, 1, −1, …,

with generating function

\frac{1 + x − x^{2} + x^{3} + x^{5}}{1 − x^{6}} .

Example 6. We define the Hurwitz transform of a single sequence a_{n} to be the Hurwitz transform of the pair (a_{n}, 0^{n}). In this example, we take a_{n} to be the sequence \underline{A025262}(n+1), which begins

1, 1, 3, 8, 23, 68, 207, 644, 2040, 6558, 21343, ….

This sequence has generating function

f(x) = \frac{1 − 2x − \sqrt{1 − 4x + 4x^{3}}}{2x^{2}} .

Its Hankel transform h_{n} is an example of a Somos-4 [8, 12, 33] sequence. This means that it satisfies the recurrence

h_{n−1}h_{n−3} + h_{n−2}^{2} = h_{n}h_{n−4}, n ≥ 3.

In this case, h_{n} begins

1, 2, 3, 7, 23, 59, 314, 1529, 8209, 83313, 620297, ….

This is \underline{A006720}(n + 3).

More generally, we say that a sequence e_{n} is a (α, β) Somos-4 sequence if we have

αh_{n−1}h_{n−3} + βh_{n−2}^{2} = h_{n}h_{n−4}, n ≥ 4.

Now h_{n}^{∗} begins

1, −1, −5, −4, 29, 129, −65, −3689, −16264, 113689, 2382785, …,

and hence ℍ_{n} begins

1, −1, 2, −1, 3, 5, 7, −4, 23, −29, 59, 129, 314, ….

Numerical evidence suggests that ℍ_{n} is then a (−1, 1) Somos-4 sequence.

Example 7. We let a_{n} be the sequence \underline{A160702}(n + 1). This sequence begins

1, 1, 5, 19, 79, 333, 1441, 6351, 28451, 129185, …,

and its Hankel transform h_{n} is a (4, 24) Somos-4 sequence, as is the Hankel transform h_{n}^{∗} of a_{n+1}. We can then conjecture that the Hurwitz transform of a_{n} is a (−2, 2) Somos-4 sequence. ℍ_{n} begins

1, −1, 4, −6, 20, 88, 464, 512, 17024, −173568, 1632256, …,

and our claim is that

(−2)ℍ_{n−1}ℍ_{n−3} + 2ℍ_{n−2}^{2} = ℍ_{n}ℍ_{n−4}, n ≥ 4.

We are not at present able to prove this assertion.

Example 8. We finish this section with an example which recalls the use of the Hurwitz matrix to determine if a polynomial is stable. We let e_{n} = \binom{n}{\frac{n}{2}}, and we set

a_{n} = e_{2n+1} = \binom{2n + 1}{n + 1}, b_{n} = e_{2n} = \binom{2n}{n}.

We find that the Hurwitz transform ℍ_{n}(e_{2n+1}, e_{2n}) in this case is given by

1, −1, 1, 1, 1, −1, 1, 1, 1, −1, 1, ….

3 Hurwitz associated polynomials

One important application of Hankel determinants is in the construction of orthogonal polynomials [10, 31], where the Hankel determinants in question have elements that are the moments of the density associated with the orthogonal polynomials. We now use the Hurwitz matrix to construct families of polynomials, which we then relate to the polynomials defined by s_{n} and s_{n}^{∗} by the Hankel construction.

We let

P_{n}^{(s)}(x) = Δ_{n}^{(s)}(1, x, x^{2}, ⋯, x^{n}) = | \begin{matrix}s_{0} & s_{1} & s_{2} & ⋯ & s_{n} \\ s_{1} & s_{2} & s_{3} & ⋯ & s_{n+1} \\ ⋮ & ⋮ & ⋮ & ⋯ & ⋮ \\ s_{n−1} & s_{n−2} & s_{n−3} & ⋯ & s_{2n−1} \\ 1 & x & x^{2} & ⋯ & x^{n} \end{matrix} | ,

respectively

P_{n}^{(s^{∗})}(x) = Δ_{n}^{(s^{∗})}(1, x, x^{2}, ⋯, x^{n}) = | \begin{matrix}s_{1} & s_{2} & s_{3} & ⋯ & s_{n+1} \\ s_{2} & s_{3} & s_{4} & ⋯ & s_{n+2} \\ ⋮ & ⋮ & ⋮ & ⋯ & ⋮ \\ s_{n} & s_{n−1} & s_{n−2} & ⋯ & s_{2n} \\ 1 & x & x^{2} & ⋯ & x^{n} \end{matrix} | ,

and let L^{(s)} (respectively L^{(s^{∗})}) be the coefficient array of the family of orthogonal polynomials P_{n}^{(s)}(x) (respectively P_{n}^{(s^{∗})}(x)).

If n is even, n = 2m, we set

D_{n}(1, x, …, x^{m}) = | \begin{matrix}a_{0} & a_{1} & a_{2} & ⋯ & a_{m} & ⋯ & a_{2m} \\ b_{0} & b_{1} & b_{2} & ⋯ & b_{m} & ⋯ & b_{2m} \\ 0 & a_{0} & a_{1} & ⋯ & a_{m−1} & ⋯ & a_{2m−1} \\ 0 & b_{0} & b_{1} & ⋯ & b_{m−1} & ⋯ & b_{2m−1} \\ ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ⋮ \\ 0 & 0 & 0 & ⋯ & 1 & ⋯ & x^{m} \end{matrix} | .

If n is odd, n = 2m + 1, then we let

D_{n}(1, x, …, x^{m+1}) = | \begin{matrix}a_{0} & a_{1} & a_{2} & ⋯ & a_{m} & ⋯ & a_{2m+1} \\ b_{0} & b_{1} & b_{2} & ⋯ & b_{m} & ⋯ & b_{2m+1} \\ 0 & a_{0} & a_{1} & ⋯ & a_{m−1} & ⋯ & a_{2m} \\ 0 & b_{0} & b_{1} & ⋯ & b_{m−1} & ⋯ & b_{2m} \\ ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ⋮ \\ 0 & 0 & 0 & ⋯ & a_{0} & ⋯ & a_{m+1} \\ 0 & 0 & 0 & ⋯ & 1 & ⋯ & x^{m+1} \end{matrix} | .

We can gain insight into this construction again by looking at the transpose of the underlying matrix. Using an obvious notation [23], we have

H_{j,i}(x) = \begin{cases}[t^{i}]t^{\frac{j}{2}} f(t), & if 2|j and j < n; \\ [t^{i}]t^{\frac{j−1}{2}} g(t), & if 2 ∤ j and j < n; \\ [t^{i}]\frac{t^{⌊ \frac{j}{2} ⌋}}{1−xt}, & if j = n. \end{cases}  (3)

Finally we let M = (b_{i−j}[j ≤ i]) be the sequence (or renewal) array of the sequence b_{n}, and M_{n} represent the matrix composed of the first n + 1 rows and columns of M (where we use a similar subscript notation to denote the first n + 1 rows and columns of other matrices). We have M = (g(x), x) as a Riordan array.

Proposition 9. We have

D_{2n}(1, x, …, x^{n}) = (−1)^{n}b_{0}^{2n+1}Δ_{n}^{(s^{∗})}(1, ϕ_{1}(x), ϕ_{2}(x), …, ϕ_{n}(x))

where

(1, ϕ_{1}(x), ϕ_{2}(x), …, ϕ_{n}(x))^{t} = M_{n}^{−1}(1, x, x^{2}, …, x^{n})^{t},

and we have

D_{2n+1}(1, x, …, x^{n+1}) = b_{0}^{2n+2}Δ_{n+1}^{(s)}(1, ϕ_{1}(x), ϕ_{2}(x), …, ϕ_{n}(x), ϕ_{n+1}(x))

where

(1, ϕ_{1}(x), ϕ_{2}(x), …, ϕ_{n}(x), ϕ_{n+1}(x))^{t} = M_{n+1}^{−1}(1, x, x^{2}, …, x^{n})^{t}.

Equivalently, if L̃ is the coefficient array of the family of polynomials Q_{n}(x) = D_{2n}(1, x, …, x^{n}) (respectively L̃^{∗} is the coefficient array of the polynomials R_{n+1}(x) = D_{2n+1}(1, x, …, x^{n+1}), R_{0}(x) = 1) then we have

L̃ = S · L^{(s)} · M^{−1}

(respectively

L̃^{∗} = L^{(s^{∗})} · M^{−1}),

where S = diag(1, −1, 1, −1, …).

Proof. Carrying out the eliminations on D_{2m} that we have used in the first proposition, we get, for n = 2m,

( \begin{matrix}s_{0} & s_{1} & s_{2} & ⋯ & s_{m−1} & s_{m} & ⋯ & s_{2m} \\ 1 & 0 & 0 & ⋯ & 0 & 0 & ⋯ & 0 \\ 0 & s_{0} & s_{1} & ⋯ & s_{m−2} & s_{m−1} & ⋯ & s_{2m−1} \\ 0 & 1 & 0 & ⋯ & 0 & 0 & ⋯ & 0 \\ 0 & 0 & s_{0} & ⋯ & s_{m−3} & s_{m−2} & ⋯ & s_{2m−2} \\ 0 & 0 & 1 & ⋯ & 0 & 0 & ⋯ & 0 \\ ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ⋮ \\ 0 & 0 & 0 & ⋯ & s_{0} & s_{1} & ⋯ & s_{m+1} \\ 0 & 0 & 0 & ⋯ & 1 & 0 & ⋯ & 0 \\ 0 & 0 & 0 & ⋯ & 0 & 1 & ⋯ & ϕ_{m}(x) \end{matrix} ) .

Expanding iteratively along the rows with a single 1 we get an “upside-down” augmented Hankel determinant

| \begin{matrix}s_{m+1} & ⋯ & s_{2m} \\ ⋮ & ⋮ & ⋮ \\ s_{1} & ⋯ & s_{m+1} \\ 1 & ⋯ & ϕ_{m}(x) \end{matrix} | .

Similarly for n = 2m + 1, we obtain in D_{2m+1} upon elimination the following matrix.

( \begin{matrix}s_{0} & s_{1} & s_{2} & ⋯ & s_{m−1} & s_{m} & ⋯ & s_{2m+1} \\ 1 & 0 & 0 & ⋯ & 0 & 0 & ⋯ & 0 \\ 0 & s_{0} & s_{1} & ⋯ & s_{m−2} & s_{m−1} & ⋯ & s_{2m} \\ 0 & 1 & 0 & ⋯ & 0 & 0 & ⋯ & 0 \\ 0 & 0 & s_{0} & ⋯ & s_{m−3} & s_{m−2} & ⋯ & s_{2m−1} \\ 0 & 0 & 1 & ⋯ & 0 & 0 & ⋯ & 0 \\ ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ⋮ \\ 0 & 0 & 0 & ⋯ & 1 & 0 & ⋯ & 0 \\ 0 & 0 & 0 & ⋯ & 0 & s_{0} & ⋯ & s_{m+1} \\ 0 & 0 & 0 & ⋯ & 0 & 1 & ⋯ & ϕ_{m+1}(x) \end{matrix} ) .

Expanding iteratively along the rows with a single 1 we get an “upside-down” augmented Hankel determinant

| \begin{matrix}s_{m} & ⋯ & s_{2m+1} \\ ⋮ & ⋮ & ⋮ \\ s_{0} & ⋯ & s_{m+1} \\ 1 & ⋯ & ϕ_{m+1}(x) \end{matrix} | .

The result follows from this. Note that in terms of the matrix elements H_{i,j}(x), we can interpret the above as

M_{n}^{−1} · (H_{j,i}(x))_{n} = (\frac{1}{g(t)}, t)_{n} · (H_{j,i}(x))_{n}

= (\begin{cases}[t^{i}]t^{\frac{j}{2}} f(t)/g(t), & if 2|j and j < n; \\ [t^{i}]t^{\frac{j−1}{2}} g(t)/g(t), & if 2 ∤ j and j < n; \\ [t^{i}]t^{⌊ \frac{j}{2} ⌋} \frac{1}{g(t)} \frac{1}{1−xt}, & if j = n. \end{cases})

= (\begin{cases}[t^{i}]t^{\frac{j}{2}} s(t), & if 2|j and j < n; \\ [t^{i}]t^{\frac{j−1}{2}} , & if 2 ∤ j and j < n; \\ [t^{i}]t^{⌊ \frac{j}{2} ⌋} \frac{1}{g(t)} \frac{1}{1−xt}, & if j = n. \end{cases}) ,

where

ϕ_{n}(x) = [t^{n}]\frac{1}{g(t)} \frac{1}{1 − xt}.

Note that we have

( \begin{matrix}b_{0} \\ b_{1} & b_{0} \\ ⋮ & ⋮ & ⋮ \\ b_{m} & b_{m−1} & b_{m−2} & ⋮ \\ b_{m+1} & b_{m} & b_{m−1} & ⋮ \\ ⋮ & ⋮ & ⋮ & ⋮ & ⋮ \\ b_{2m} & b_{2m−1} & b_{2m−2} & b_{2m−3} & ⋯ & b_{0} \end{matrix} )^{−1} · ( \begin{matrix}a_{0} & b_{0} & 0 & 0 & ⋯ & 0 \\ a_{1} & b_{1} & a_{0} & b_{0} & ⋯ & 0 \\ ⋮ & ⋮ & ⋮ & ⋮ & ⋯ & ⋮ \\ a_{m} & b_{m} & a_{m−1} & b_{m−1} & ⋯ & 1 \\ a_{m+1} & b_{m+1} & a_{m} & b_{m} & ⋯ & x \\ ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ⋮ \\ a_{2m} & b_{2m} & a_{2m−1} & b_{2m−1} & ⋯ & x^{m} \end{matrix} )

= ( \begin{matrix}s_{0} & 1 & 0 & 0 & ⋯ & 0 \\ s_{1} & 0 & s_{0} & 1 & ⋯ & 0 \\ ⋮ & ⋮ & ⋮ & ⋮ & ⋯ & ⋮ \\ s_{m} & 0 & s_{m−1} & 0 & ⋯ & 1 \\ s_{m+1} & 0 & s_{m} & 0 & ⋯ & ϕ_{1}(x) \\ ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ⋮ \\ s_{2m} & 0 & s_{2m−1} & 0 & ⋯ & ϕ_{m}(x) \end{matrix} )

with a corresponding matrix equation for the case n = 2m + 1.

4 The Riordan array case

We recall elements of the theory of Riordan arrays before giving examples of Hurwitz associated polynomials, where the relevant coefficient matrices happen to be Riordan arrays. For a power series f(x) = ∑_{n=0}^{∞} a_{n}x^{n} with f(0) = 0 we define the reversion or compositional inverse of f to be the power series f̄(x) such that f(f̄(x)) = x.

For a lower triangular matrix (a_{n,k})_{n,k≥0} the row sums give the sequence with general term ∑_{k=0}^{n} a_{n,k}. More generally, a lower triangular matrix (a_{n,k})_{n,k≥0} is the coefficient array of the polynomials

P_{n}(x) = ∑_{k=0}^{n} a_{n,k}x^{k}.

The Riordan group [25, 28], is a set of infinite lower-triangular integer matrices, where each matrix is defined by a pair of generating functions g(x) = 1 + g_{1}x + g_{2}x^{2} + ⋯ and f(x) = f_{1}x + f_{2}x^{2} + ⋯ where f_{1} ≠ 0 [28]. We often require in addition that f_{1} = 1, but this is not the case in this note. The associated matrix is the matrix whose i-th column is generated by g(x)f(x)^{i} (the first column being indexed by 0). The matrix corresponding to the pair g, f is denoted by (g, f) or R(g, f). The group law is then given by

(g, f) · (h, l) = (g, f)(h, l) = (g(h ∘ f), l ∘ f).

The identity for this law is I = (1, x) and the inverse of (g, f) is (g, f)^{−1} = (1/(g ∘ f̄), f̄) where f̄ is the compositional inverse of f.

Elements of the form (g(x), x) form a subgroup called the Appell subgroup.

If M is the matrix (g, f), and a = (a_{0}, a_{1}, …)^{t} is an integer sequence (expressed as an infinite column vector) with ordinary generating function A (x), then the sequence Ma has ordinary generating function g(x)A(f(x)). The (infinite) matrix (g, f) can thus be considered to act on the ring of integer sequences ℤ^{ℕ} by multiplication, where a sequence is regarded as a (infinite) column vector. We can extend this action to the ring of power series ℤ[[x]] by

(g, f) : A(x) ↦ (g, f) · A(x) = g(x)A(f(x)).

This action is often referred to as the fundamental theorem of Riordan arrays.

Example 10. The so-called binomial matrix B is the element (\frac{1}{1−x}, \frac{x}{1−x}) of the Riordan group. It has general element \binom{n}{k}, and hence as an array coincides with Pascal’s triangle. More generally, B^{m} is the element (\frac{1}{1−mx}, \frac{x}{1−mx}) of the Riordan group, with general term \binom{n}{k}m^{n−k}. It is easy to show that the inverse B^{−m} of B^{m} is given by (\frac{1}{1+mx}, \frac{x}{1+mx}).

Example 11. The Riordan array (\frac{1}{1+x}, \frac{x}{(1+x)^{2}} ) has inverse (c(x), xc(x)^{2}). It is the coefficient array of the unique family of orthogonal polynomials

P_{n}(x) = (x − 2)P_{n−1}(x) − P_{n−2}(x)

for which the Catalan numbers C_{n} are the moments.

The row sums of the matrix (g, f) have generating function

(g, f) · \frac{1}{1 − x} = \frac{g(x)}{1 − f(x)},

while the polynomial sequence P_{n}(t) for which (g, f) is the coefficient array will have g.f.

\frac{g(x)}{1 − tf(x)}.

For an invertible matrix M, its production matrix (also called its Stieltjes matrix) [14, 15] is the matrix

P_{M} = M^{−1}M̂,

where M̂ is the matrix M with its first row removed. A Riordan array M is the inverse of the coefficient array of a family of orthogonal polynomials [10, 31] if and only if P_{M} is tri-diagonal [2, 3]. Necessarily, the Jacobi coefficients (i.e., the coefficients of the three-term recurrence [10] that defines the polynomials) of these orthogonal polynomials are then constant.

Example 12. The production matrix of (c(x), xc(x)^{2}) is given by

( \begin{matrix}1 & 1 & 0 & 0 & 0 & 0 & ⋯ \\ 1 & 2 & 1 & 0 & 0 & 0 & ⋯ \\ 0 & 1 & 2 & 1 & 0 & 0 & ⋯ \\ 0 & 0 & 1 & 2 & 1 & 0 & ⋯ \\ 0 & 0 & 0 & 1 & 2 & 1 & ⋯ \\ 0 & 0 & 0 & 0 & 1 & 2 & ⋯ \\ ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ... \end{matrix} ) .

An important feature of Riordan arrays is that they have a number of sequence characterizations [9, 16]. The simplest of these is as follows.

Proposition 13. [16, Theorem 2.1, Theorem 2.2]. Let D = [d_{n,k}] be an infinite triangular matrix. Then D is a Riordan array if and only if there exist two sequences A = [α_{0}, α_{1}, α_{2}, …] and Z = [z_{0}, z_{1}, z_{2}, …] with α_{0} ≠ 0, z_{0} ≠ 0 such that

• d_{n+1,k+1} = ∑_{j=0}^{∞} α_{j}d_{n,k+j}, (k, n = 0, 1, …)

• d_{n+1,0} = ∑_{j=0}^{∞} z_{j}d_{n,j}, (n = 0, 1, …).

The coefficients α_{0}, α_{1}, α_{2}, … and z_{0}, z_{1}, z_{2}, … are called the A-sequence and the Zsequence of the Riordan array M = (g(x), f(x)), respectively. Letting A(x) be the generating function of the A-sequence and Z(x) be the generating function of the Z-sequence, we have

A(x) = \frac{x}{f̄(x)}, Z(x) = \frac{1}{f̄(x)} (1 − \frac{d_{0,0}}{g(f̄(x))}) .  (4)

The first column of P_{M} is then generated by Z(x), while the k-th column is generated by x^{k−1}A(x) (taking the first column to be indexed by 0). There is a close link between orthogonal polynomials whose defining three term recurrences have constant coefficients and Riordan arrays whose inverses have tri-diagonal production matrices [2, 3]. We devote this section to examples where the coefficient array L^{(s)} is a Riordan array

L^{(s)} = (u(x), v(x)).

We shall also assume that a_{0} = b_{0} = 1 for the rest of this section. Note that we have, in this case,

L^{(s)}^{−1} = (u(x), v(x))^{−1} = (\frac{1}{u(v̄(x))}, v̄(x)) = (s(x), v̄(x)).

In particular,

s(x) = \frac{1}{u(v̄(x))} ⇒ u(x) = \frac{1}{s(v(x))}.

We have

L^{(s)} · M^{−1} = L^{(s)} · (g(x), x)^{−1} = L^{(s)} · (\frac{1}{g(x)}, x) = (\frac{u(x)}{g(x)}, v(x)) .

Looking at inverses, we get

(L^{(s)} · M^{−1})^{−1} = M · (L^{(s)})^{−1} = (\frac{g(x)}{u(v̄(x))}, v̄(x)) .

We wish to compare the production array of the matrix (L^{(s)})^{−1} with that of the matrix (L^{(s)} · M^{−1})^{−1}. For the matrix (L^{(s)})^{−1} = (u, v)^{−1} = (\frac{1}{u(v̄(x))}, v̄(x)), we have

A(x) = \frac{x}{v(x)}, Z(x) = \frac{1}{v}(1 − u(x)),  (5)

since by assumption d_{0,0} = 1. For (L^{(s)} · M^{−1})^{−1} = (\frac{g(x)}{u(v̄(x))}, v̄(x)) we find that

Ã(x) = \frac{x}{v(x)}, Z̃(x) = \frac{1}{v(x)} (1 − \frac{u(x)}{g(v(x))}) .  (6)

In our case (that of L^{(s)} being the coefficient array of a family of orthogonal polynomials), we have

L^{(s)} = (\frac{1 + α′x + β′x^{2}}{1 + αx + βx^{2}} , \frac{x}{1 + αx + βx^{2}} ) ,

for suitable values of α, β, α′, β′. Then

A(x) = Ã(x) = 1 + αx + βx^{2},

and

Z(x) = \frac{1 + αx + βx^{2}}{x} (1 − \frac{1 + α′x + β′x^{2}}{1 + αx + βx^{2}} ) = (α − α′) + (β − β′)x,

along with

Z̃(x) = \frac{1}{x} (1 + αx + βx^{2} − (1 + α′x + β′x^{2}) · \frac{1}{g (\frac{x}{1+αx+βx^{2}} )}) .

Thus as expected, (L^{(s)})^{−1} has a tri-diagonal production matrix, which begins

( \begin{matrix}α − α′ & 1 & 0 & 0 & 0 & 0 & ⋯ \\ β − β′ & α & 1 & 0 & 0 & 0 & ⋯ \\ 0 & β & α & 1 & 0 & 0 & ⋯ \\ 0 & 0 & β & α & 1 & 0 & ⋯ \\ 0 & 0 & 0 & β & α & 1 & ⋯ \\ 0 & 0 & 0 & 0 & β & α & ⋯ \\ ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ... \end{matrix} ) .

However, given the form of Z̃(x), only in the exceptional case when

Z̃(x) = \frac{1}{x} (1 + αx + βx^{2} − \frac{1 + α′x + β′x^{2}}{g (\frac{x}{1+αx+βx^{2}} )} )

is of the form γ + δx will the production matrix of (L^{(s)} · M^{−1})^{−1} be tri-diagonal. Only in this case are the polynomials Q_{n}(x) orthogonal.

In the case when

L^{(s^{∗})} = (u^{∗}(x), v^{∗}(x)) = (s^{∗}(x), v̄^{∗}(x))^{−1}

is a Riordan array, a similar analysis is valid.

Example 14. We look at the case where a_{n} = ∑_{k=0}^{n} \binom{2k}{k}C_{n−k} = \binom{2n+1}{n+1} and b_{n} = \binom{2n}{n}. In this case, we have

f(x) = \frac{c(x)}{\sqrt{1 − 4x}}, g(x) = \frac{1}{\sqrt{1 − 4x}}, s(x) = \frac{f(x)}{g(x)} = c(x),

and hence s_{n} = C_{n}. We find that the coefficient array L̃ of the polynomials Q_{n}(x) is the array

(\frac{1 − x}{(1 + x)^{2}} , \frac{x}{(1 + x)^{2}} ) ,

which begins

( \begin{matrix}1 & 0 & 0 & 0 & 0 & 0 & ⋯ \\ −3 & 1 & 0 & 0 & 0 & 0 & ⋯ \\ 5 & −5 & 1 & 0 & 0 & 0 & ⋯ \\ −7 & 14 & −7 & 1 & 0 & 0 & ⋯ \\ 9 & −30 & 27 & −9 & 1 & 0 & ⋯ \\ −11 & 55 & −77 & 44 & −11 & 1 & ⋯ \\ ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ... \end{matrix} ) .

We have

Q_{n}(x) = ∑_{k=0}^{n} \frac{2n + 1}{2k + 1}\binom{n + k}{2k}(−1)^{n−k}x^{k}.

The inverse array L̃^{−1} begins

( \begin{matrix}1 & 0 & 0 & 0 & 0 & 0 & ⋯ \\ 3 & 1 & 0 & 0 & 0 & 0 & ⋯ \\ 10 & 5 & 1 & 0 & 0 & 0 & ⋯ \\ 35 & 21 & 7 & 1 & 0 & 0 & ⋯ \\ 126 & 84 & 36 & 9 & 1 & 0 & ⋯ \\ 462 & 330 & 165 & 55 & 11 & 1 & ⋯ \\ ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ... \end{matrix} ) (\underline{A111418}).

By its form, we see that (\frac{1−x}{(1+x)^{2}} , \frac{x}{(1+x)^{2}} ) is in this case the coefficient array of a family of orthogonal polynomials. This is verified by noting that

Z̃(x) = \frac{(1 + x)^{2}}{x} (1 − _{\frac{\frac{1}{1+x}}{\frac{1}{\sqrt{1− \frac{4x}{(1+x)^{2}}}}}} ) = 3 + x.

In fact, the production matrix of (\frac{1−x}{(1+x)^{2}} , \frac{x}{(1+x)^{2}} )^{−1} is given by

( \begin{matrix}3 & 1 & 0 & 0 & 0 & 0 & ⋯ \\ 1 & 2 & 1 & 0 & 0 & 0 & ⋯ \\ 0 & 1 & 2 & 1 & 0 & 0 & ⋯ \\ 0 & 0 & 1 & 2 & 1 & 0 & ⋯ \\ 0 & 0 & 0 & 1 & 2 & 1 & ⋯ \\ 0 & 0 & 0 & 0 & 1 & 2 & ⋯ \\ ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ... \end{matrix} ) ,

and so we have

Q_{n}(x) = (x − 2)Q_{n−1}(x) − Q_{n−2}(x), Q_{0}(x) = 1, Q_{1}(x) = x − 3.

Looking at M^{−1}L̃^{−1}, we have

( \begin{matrix}1 & 0 & 0 & 0 & 0 & 0 & ⋯ \\ 2 & 1 & 0 & 0 & 0 & 0 & ⋯ \\ 6 & 2 & 1 & 0 & 0 & 0 & ⋯ \\ 20 & 6 & 2 & 1 & 0 & 0 & ⋯ \\ 70 & 20 & 6 & 2 & 1 & 0 & ⋯ \\ 252 & 70 & 20 & 6 & 2 & 1 & ⋯ \\ ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ... \end{matrix} )^{−1} · ( \begin{matrix}1 & 0 & 0 & 0 & 0 & 0 & ⋯ \\ 3 & 1 & 0 & 0 & 0 & 0 & ⋯ \\ 10 & 5 & 1 & 0 & 0 & 0 & ⋯ \\ 35 & 21 & 7 & 1 & 0 & 0 & ⋯ \\ 126 & 84 & 36 & 9 & 1 & 0 & ⋯ \\ 462 & 330 & 165 & 55 & 11 & 1 & ⋯ \\ ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ... \end{matrix} )

= ( \begin{matrix}1 & 0 & 0 & 0 & 0 & 0 & ⋯ \\ 1 & 1 & 0 & 0 & 0 & 0 & ⋯ \\ 2 & 3 & 1 & 0 & 0 & 0 & ⋯ \\ 5 & 9 & 5 & 1 & 0 & 0 & ⋯ \\ 14 & 28 & 20 & 7 & 1 & 0 & ⋯ \\ 42 & 90 & 75 & 35 & 9 & 1 & ⋯ \\ ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ... \end{matrix} ) (\underline{A039599}).

This latter array is the inverse of (\frac{1}{1+x}, \frac{x}{(1+x)^{2}} )^{−1}. The array (\frac{1}{1+x}, \frac{x}{(1+x)^{2}} ) is the coefficient array of the orthogonal polynomials whose moments are the Catalan numbers C_{n}.

Turning now to s_{n}^{∗}, we have s_{n}^{∗} = C_{n+1}. In this case, we find that

L̃^{∗} = L^{(s^{∗})} · M^{−1} = (u^{∗}(x), v^{∗}(x)) = (\frac{1 − x}{(1 + x)^{3}} , \frac{x}{(1 + x)^{2}} ) .

This array represents the coefficients of a family of polynomials R_{n}(x) that are “almost orthogonal”, in the sense that the production matrix of the inverse of this matrix is of the form

( \begin{matrix}4 & 1 & 0 & 0 & 0 & 0 & ⋯ \\ −1 & 2 & 1 & 0 & 0 & 0 & ⋯ \\ 2 & 1 & 2 & 1 & 0 & 0 & ⋯ \\ −2 & 0 & 1 & 2 & 1 & 0 & ⋯ \\ 2 & 0 & 0 & 1 & 2 & 1 & ⋯ \\ −2 & 0 & 0 & 0 & 1 & 2 & ⋯ \\ ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ... \end{matrix} ) .

Thus we have

R_{n}(x) = (x − 2)R_{n−1}(x) − R_{n−2}(x) − z̃_{n−1}, R_{0}(x) = 1, R_{1}(x) = x − 4,

where z̃_{n} is the sequence 0, 0, 2, −2, 2, −2, 2, . . ..

The inverse matrix (u^{∗}(x), v^{∗}(x))^{−1}, which begins

( \begin{matrix}1 & 0 & 0 & 0 & 0 & 0 & ⋯ \\ 4 & 1 & 0 & 0 & 0 & 0 & ⋯ \\ 15 & 6 & 1 & 0 & 0 & 0 & ⋯ \\ 56 & 28 & 8 & 1 & 0 & 0 & ⋯ \\ 210 & 120 & 45 & 10 & 1 & 0 & ⋯ \\ 792 & 495 & 220 & 66 & 12 & 1 & ⋯ \\ ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ... \end{matrix} ) ,

has general term \binom{2n+2}{n+k+2}, and satisfies

( \begin{matrix}1 & 0 & 0 & 0 & 0 & 0 & ⋯ \\ 2 & 1 & 0 & 0 & 0 & 0 & ⋯ \\ 6 & 2 & 1 & 0 & 0 & 0 & ⋯ \\ 20 & 6 & 2 & 1 & 0 & 0 & ⋯ \\ 70 & 20 & 6 & 2 & 1 & 0 & ⋯ \\ 252 & 70 & 20 & 6 & 2 & 1 & ⋯ \\ ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ... \end{matrix} )^{−1} · ( \begin{matrix}1 & 0 & 0 & 0 & 0 & 0 & ⋯ \\ 4 & 1 & 0 & 0 & 0 & 0 & ⋯ \\ 15 & 6 & 1 & 0 & 0 & 0 & ⋯ \\ 56 & 28 & 8 & 1 & 0 & 0 & ⋯ \\ 210 & 120 & 45 & 10 & 1 & 0 & ⋯ \\ 792 & 495 & 220 & 66 & 12 & 1 & ⋯ \\ ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ... \end{matrix} )

= ( \begin{matrix}1 & 0 & 0 & 0 & 0 & 0 & ⋯ \\ 2 & 1 & 0 & 0 & 0 & 0 & ⋯ \\ 5 & 4 & 1 & 0 & 0 & 0 & ⋯ \\ 14 & 14 & 6 & 1 & 0 & 0 & ⋯ \\ 42 & 48 & 27 & 8 & 1 & 0 & ⋯ \\ 132 & 165 & 110 & 44 & 10 & 1 & ⋯ \\ ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ... \end{matrix} ) = (c(x)^{2}, xc(x)^{2}) ,

where the first column of this last matrix (which is \underline{A039598}) is given by s_{n}^{∗} = C_{n+1}. Note that the first column elements of (u^{∗}(x), v^{∗}(x))^{−1} are given by

∑_{k=0}^{n} \binom{2k}{k}C_{n−k+1} = ∑_{k=0}^{n} \binom{2n − 2k}{n − k}C_{k+1} = \binom{2n + 2}{n + 2}, (\underline{A001791}).

The inverse of this last matrix is the coefficient array

L^{(s^{∗})} = (\frac{1}{(1 + x)^{2}} , \frac{x}{(1 + x)^{2}} ) = (c(x)^{2}, xc(x)^{2})^{−1}

for the family of orthogonal polynomials

R̃_{n}(x) = (x − 2)R̃_{n−1}(x) − R̃_{n−2}(x), R̃_{0}(x) = 1, R̃_{1}(x) = x − 2.

These polynomials have moments given by C_{n+1}. We note that we have

Z̃^{∗}(x) = \frac{(1 + x)^{2}}{x} (1 − \frac{\frac{1}{(1+x)^{2}}}{\frac{1}{\sqrt{1− \frac{4x}{(1+x)^{2}}}}} ) = \frac{4 + 3x + x^{2}}{1 + x} ,

where \frac{4+3x+x^{2}}{1+x} expands to give 4, −1, 2, −2, 2, −2, 2, . . ..

Example 15. In the last example, it happened that the family of polynomials Q_{n}(x) constituted a family of orthogonal polynomials. This is not true in general. In this example, we let

a_{n} = ∑_{k=0}^{n} F_{k+1}C_{n−k}, b_{n} = F_{k+1},

where F_{n} \underline{A000045} denotes the n-th Fibonacci number. Then we have

f(x) = \frac{c(x)}{1 − x − x^{2}} , g(x) = \frac{1}{1 − x − x^{2}} , s(x) = \frac{f(x)}{g(x)}

and s_{n} = C_{n}. Thus again, L^{(s)} = (\frac{1}{1+x}, \frac{x}{(1+x)^{2}} ) and hence

L̃ = (\frac{1}{1 + x}, \frac{x}{(1 + x)^{2}} ) · (\frac{1}{1 − x − x^{2}} , x)^{−1} = (\frac{1}{1 + x}, \frac{x}{(1 + x)^{2}} ) · (1 − x − x^{2}, x).

Thus

L̃ = (\frac{1 + 3x + 3x^{2} + 3x^{3} + x^{4}}{(1 + x)^{5}} , \frac{x}{(1 + x)^{2}} ) ,

whose inverse has production matrix

( \begin{matrix}2 & 1 & 0 & 0 & 0 & 0 & ⋯ \\ 1 & 2 & 1 & 0 & 0 & 0 & ⋯ \\ −2 & 1 & 2 & 1 & 0 & 0 & ⋯ \\ 5 & 0 & 1 & 2 & 1 & 0 & ⋯ \\ −9 & 0 & 0 & 1 & 2 & 1 & ⋯ \\ 14 & 0 & 0 & 0 & 1 & 2 & ⋯ \\ ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ... \end{matrix} ) .

This follows since

Z̃(x) = \frac{1}{x} ((1 + x)^{2} − \frac{1 + x}{g (\frac{x}{(1+x)^{2}} )}) = \frac{2 + 7x + 7x^{2} + 4x^{3} + x^{4}}{(1 + x)^{3}} ,

which expands to

2, 1, −2, 5, −9, 14, −20, 27, −35, ….

This means that L̃ is the coefficient array of the “almost-orthogonal” polynomials Q_{n}(x) that satisfy

Q_{n}(x) = (x − 2)Q_{n−1} − Q_{n−2}(x) − z̃_{n−1},

where z̃_{n} is the sequence 0, 0, −2, 5, −9, 14, −20, 27, −35, . . .. Looking now at s^{∗}, we have

L̃^{∗} = (\frac{1}{(1 + x)^{2}} , \frac{x}{(1 + x)^{2}} ) · (1 − x − x^{2}, x) = (\frac{1 + 3x + 3x^{2} + 3x^{3} + x^{4}}{(1 + x)^{6}} , \frac{x}{(1 + x)^{2}} ) .

The inverse of L̃^{∗} then has production array

( \begin{matrix}3 & 1 & 0 & 0 & 0 & 0 & ⋯ \\ 0 & 2 & 1 & 0 & 0 & 0 & ⋯ \\ −1 & 1 & 2 & 1 & 0 & 0 & ⋯ \\ 6 & 0 & 1 & 2 & 1 & 0 & ⋯ \\ −15 & 0 & 0 & 1 & 2 & 1 & ⋯ \\ 29 & 0 & 0 & 0 & 1 & 2 & ⋯ \\ ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ... \end{matrix} ) .

We have

Z̃^{∗}(x) = \frac{1}{x} ((1 + x)^{2} − \frac{1}{g (\frac{x}{(1+x)^{2}} )}) = \frac{3 + 12x + 17x^{2} + 14x^{3} + 6x^{4} + x^{5}}{(1 + x)^{3}} ,

which expands to 3, 0, −1, 6, −15, 29, . . .. Thus in this case we have

R_{n}(x) = (x − 2)R_{n−1}(x) − R_{n−2}(x) − z̃_{n−1}^{∗}, R_{0}(x) = 1, R_{1}(x) = x − 3.

Example 16. For any element T = (u(x), x) of the Appell subgroup of Riordan arrays [25], it is clear that

ℍ_{n}(T a, T b) = ℍ_{n}(a, b).

This is so because for the pair T a, T b, we have

s(x) = \frac{u(x)f(x)}{u(x)g(x)} = \frac{f(x)}{g(x)},

by the fundamental theorem of Riordan arrays. Thus for instance we have

ℍ_{n}(a_{n}, b_{n}) = ℍ_{n}(∑_{k=0}^{n} a_{k}, ∑_{k=0}^{n} b_{k}),

since the partial sum operator is equal to the Riordan array (\frac{1}{1−x}, x).

Similarly we have

ℍ_{n}(a_{n}, b_{n}) = ℍ_{n}(∑_{k=0}^{⌊ \frac{n}{2} ⌋} a_{n−2k}, ∑_{k=0}^{⌊ \frac{n}{2} ⌋} b_{n−2k}),

where in this case the Riordan array is (\frac{1}{1−x^{2}} , x).

5 Further examples

We list below a table showing a small sample of Hurwitz transforms for the pairs of sequences shown.

a_{n}  b_{n}  s(x)  Hurwitz transform
(−1)^{n}C_{n+1}  (−1)^{n}C_{n}  c(−x)  1, 1, 1, 1, 1, 1, …
C_{n}  C_{n+1}  \frac{1}{c(x)}  1, 1, −2, 1, 3, 1, −4, 1, 5, 1, …
C_{n+1}  C_{n}  c(x)  1, −1, 1, 1, 1, −1, 1, 1, 1, −1, 1, …
(−1)^{n}\binom{1}{n}  (−1)^{n}(C_{n} + C_{n−1})  \frac{1}{c(−x)}  1, −1, −2, 1, 3, −1, −4, 1, 5, …
C_{n}  0^{n}  c(x)  1, −1, 1, 1, 1, −1, 1, 1, 1, −1, 1, …
C_{n}  (−1)^{n}\binom{1}{n}  \frac{c(x)}{1−x}  1, −2, 0, 2, −1, 1, −1, −5, 0, 5, 1, …
C_{n}  1  (1 − x)c(x) 1, 0, 1, −1, −1, 1, −4, 0, −4, −1, 1, …
C_{n}  \frac{1}{1−2n} \binom{2n}{n}  \frac{c(x)}{\sqrt{1−4x}}  1, −3, 1, 5, 1, −7, 1, 9, 1, −11, 1, …
C_{n} + C_{n+1}  C_{n}  1 + c(x)  2, −1, 3, 1, 4, −1, 5, 1, 6, −1, 7, …
C\frac{n}{2} \frac{1+(−1)^{n}}{2}  2^{n}  (1 − 2x)c(x^{2})  1, 2, −3, 3, −3, 4, 5, 5, 5, 6, −7, …
T_{n} = ∑_{k=0}^{⌊ \frac{n}{2} ⌋} \binom{n}{2k}\binom{2k}{k}  T_{n+1}  \frac{\sqrt{1−2x−3x^{2}}+3x−1}{x(1−3x)} 1, 2, −2, 4, 0, 8, 8, 16, −16, 32, 0, …

6 Conclusion

Since the notion of Hurwitz transform proposed here has been linked to the Hankel transform in an easily understood way, it may be said that this notion does not add much to what is already known. What it does add, however, is a fresh perspective, both on the Hankel transform, and on the applications of the Hurwitz matrix. Some natural questions arise in this context. What known sequences are the Hurwitz transforms of pairs of sequences? Are there sequences which cannot be the Hurwitz transform of a sequence? Given that many pairs of sequences may have the same Hurwitz transform, what notion of inverse transform can we formulate?

With regard to new perspectives, the Hurwitz transform makes us look at the pair (h_{n}, h_{n}^{∗}) whenever we wish to study h_{n}. An interesting example of this is the case of the Narayana polynomials,

s_{n} = ∑_{k=0}^{n} \frac{1}{k + 1}\binom{n + 1}{k}\binom{n}{k}x^{k}.

It is well known that in this case, we have

h_{n} = x^{\binom{n+1}{2}}.

In looking at the pair (h_{n}, h_{n}^{∗}), we discover that

h_{n}^{∗} = x^{\binom{n+1}{2}} \frac{1 − x^{n+2}}{1 − x} .

Other examples of the pairing (h_{n}, h_{n}^{∗}) have been studied in different contexts [1, 5, 6, 20].

7 Acknowledgement

The author is indebted to an anonymous reviewer whose careful reading and perceptive remarks have hopefully contributed to this version being more complete and more readable. The author is particularly grateful for the reviewer’s insight into the proof of the propositions in the paper.

References

[1] P. Barry, Some conjectures on the ratio of Hankel transforms for sequences and series reversion, preprint, 2012. Available electronically at

    http://arxiv.org/abs/math/0701483.

[2] P. Barry and A. Hennessy, Meixner-type results for Riordan arrays and associated integer sequences, J. Integer Seq., 13 (2010), Article 10.9.4.

[3] P. Barry, Riordan arrays, orthogonal polynomials as moments, and Hankel transforms, J. Integer Seq. 14 (2011), Article 11.2.2.

[4] A. T. Benjamin, N. T. Cameron, J. J. Quinn, and C. R. Yerger, Catalan determinants – a combinatorial approach, preprint, 2012. Available electronically at

    http://www.math.hmc.edu/~benjamin/papers/CatDet.pdf.

[5] R. Bojičić, M. D. Petković, and P. Barry, The Hankel transform of a sequence obtained by series reversion, Integral Transforms Spec. Funct., to appear.

[6] R. Bojičić, M. D. Petković, and P. Barry, Hankel transform of a sequence obtained by series reversion II - aerating transforms, preprint, 2012. Available electronically at

    http://arxiv.org/abs/1112.1656.

[7] W. Chammam, F. Marcellan, and R. Sfaxi, Orthogonal polynomials, Catalan numbers, and a general Hankel determinant evaluation, Lin. Alg. Appl. 436 (2012), 2105–2116.

[8] X-K. Chang and X-B. Hu, A conjecture based on Somos-4 sequence and its extension, Lin. Alg. Appl. 436 (2012), 4285–4295.

[9] G.-S. Cheon, H. Kim, and L. W. Shapiro, Riordan group involutions, Linear Algebra Appl., 428 (2008), 941–952.

[10] T. S. Chihara, An Introduction to Orthogonal Polynomials, Gordon and Breach, 1978.

[11] J. Cigler, Some nice Hankel determinants, preprint, 2012. Available electronically at

http://homepage.univie.ac.at/johann.cigler/preprints/hankel-conjectures.pdf.

[12] D. Gale, The strange and surprising saga of the Somos sequence, Math. Intelligencer, 13 (1991), 40–42.

[13] I. Graham, D. E. Knuth, and O. Patashnik, Concrete Mathematics, Addison–Wesley, 1994.

[14] E. Deutsch, L. Ferrari, and S. Rinaldi, Production matrices, Adv. in Appl. Math., 34 (2005), 101–122.

[15] E. Deutsch, L. Ferrari, and S. Rinaldi, Production matrices and Riordan arrays, Ann. Comb., 13 (2009), 65–85.

[16] Tian-Xiao He and R. Sprugnoli, Sequence characterization of Riordan arrays, Discrete Math. 309 (2009), 3962–3974.

[17] O. Holtz and M. Tyaglov, Structured matrices, continued fractions, and root localization of polynomials, preprint, 2012. Available electronically at

http://arxiv.org/abs/0912.4703.

[18] M. E. H. Ismail, Determinants with orthogonal polynomial entries, J. Comput. Appl. Math. 178 (2005), 255–266.

[19] C. Krattenthaler, Advanced determinant calculus, Séminaire Lotharingien

Combin. 42 (1999),  Article B42q.,  available electronically at

http://arxiv.org/abs/math/9902004.

[20] C. Krattenthaler, Advanced determinant calculus: a complement, Lin. Alg. Appl. 411 (2005), 68-166.

[21] J. W. Layman, The Hankel transform and some of its properties, J. Integer Seq. 4 (2001), Article 01.1.5.

[22] M. E. Mays and J. Wojciechowski, A determinant property of Catalan numbers, Discrete Math. 211 (2000), 125–133.

[23] D. Merlini, R. Sprugnoli and M. C. Verri, The method of coefficients, Amer. Math. Monthly, 114 (2007), 40–57.

[24] Ch. Radoux, Calcul effectif de certains déterminants de Hankel, Bull. Soc. Math. Belg., 31 (1979), 49–55.

[25] L. W. Shapiro, S. Getu, W.-J. Woan, and L. C. Woodson, The Riordan group, Discr. Appl. Math. 34 (1991), 229–239.

[26] N. J. A. Sloane, The On-Line Encyclopedia of Integer Sequences. Published electroni-

    cally at http://oeis.org, 2012.

[27] N. J. A. Sloane, The On-Line Encyclopedia of Integer Sequences, Notices Amer. Math. Soc., 50 (2003), 912–915.

[28] R. Sprugnoli, Riordan arrays and combinatorial sums, Discrete Math. 132 (1994), 267– 290.

[29] R. P. Stanley, Enumerative Combinatorics, Vol. I, Cambridge University Press, 2006.

[30] R. P. Stanley, Enumerative Combinatorics, Vol. II, Cambridge University Press, 2001.

[31] G. Szegö, Orthogonal Polynomials, 4th ed., Amer. Math. Soc., 1975.

[32] R. Vein and P. Dale, Determinants and Their Applications in Mathematical Physics, Springer, 1998.

[33] G. Xin, Proof of the Somos-4 Hankel determinants conjecture, Adv. in Appl. Math. 42 (2009), 152–156.

2010 Mathematics Subject Classification: Primary 11C20; Secondary 11B83, 15A15, 15B05, 15B36. Keywords: Hurwitz matrix, Hankel matrix, Hankel transform, integer sequence, Riordan array.

(Concerned with sequences \underline{A000007}, \underline{A000045}, \underline{A000108}, \underline{A001006}, \underline{A001791}, \underline{A006720}, \underline{A025262}, \underline{A039598}, \underline{A039599}, \underline{A111418}, and \underline{A160702}.)

Received July 26 2012; revised version received October 9 2012. Published in Journal of Integer Sequences, October 10 2012.

Return to Journal of Integer Sequences home page.