Jump to content

Riordan array

From Wikipedia, the free encyclopedia
(Redirected from Riordan arrays)

A Riordan array is an infinite lower triangular matrix, , constructed from two formal power series, of order 0 and of order 1, such that .

A Riordan array is an element of the Riordan group.[1] It was defined by mathematician Louis W. Shapiro and named after John Riordan.[1] The study of Riordan arrays is a field influenced by and contributing to other areas such as combinatorics, group theory, matrix theory, number theory, probability, sequences and series, Lie groups and Lie algebras, orthogonal polynomials, graph theory, networks, unimodal sequences, combinatorial identities, elliptic curves, numerical approximation, asymptotic analysis, and data analysis. Riordan arrays also unify tools such as generating functions, computer algebra systems, formal languages, and path models.[2] Books on the subject, such as The Riordan Array[1] (Shapiro et al., 1991), have been published.

Formal definition

[edit]

A formal power series (where is the ring of formal power series with complex coefficients) is said to have order if . Write for the set of formal power series of order . A power series has a multiplicative inverse (i.e. is a power series) if and only if it has order 0, i.e. if and only if it lies in ; it has a composition inverse that is there exists a power series such that if and only if it has order 1, i.e. if and only if it lies in .

As mentioned previously, a Riordan array is usually defined via a pair of power series . The "array" part in its name stems from the fact that one associates to the array of complex numbers defined by (here "" means "coefficient of in "). Thus column of the array consists of the sequence of coefficients of the power series in particular, column 0 determines and is determined by the power series Because is of order 0, it has a multiplicative inverse, and it follows that from the array's column 1 we can recover as . Since has order 1, is of order and so is It follows that the array is lower triangular and exhibits a geometric progression on its main diagonal. It also follows that the map sending a pair of power series to its triangular array is injective.

Example

[edit]

An example of a Riordan array is given by the pair of power series

.

It is not difficult to show that this pair generates the infinite triangular array of binomial coefficients , also called the Pascal matrix:

.

Proof: If is a power series with associated coefficient sequence , then, by Cauchy multiplication of power series, So the latter series has the coefficient sequence , and hence . Fix any If , so that represents column of the Pascal array, then . This argument allows to see by induction on that has column of the Pascal array as coefficient sequence.

Properties

[edit]

Below are some often-used facts about Riordan arrays. Note that the matrix multiplication rules applied to infinite lower triangular matrices lead to finite sums only and the product of two infinite lower triangular matrices is infinite lower triangular. The next two theorems were first stated and proved by Shapiro et al.[1] who say they modified work they found in papers by Gian-Carlo Rota and the book of Roman.[3]

Theorem: a. Let and be Riordan arrays, viewed as infinite lower triangular matrices. Then the product of these matrices is the array associated to the pair of formal power series, which itself is a Riordan array.

b. This fact justifies the definition of a multiplication '' of Riordan arrays viewed as pairs of power series by

Proof: Since have order 0 it is clear that has order 0. Similarly implies So is a Riordan array. Define a matrix as the Riordan array By definition, its -th column is the sequence of coefficients of the power series . If we multiply this matrix from the right with the sequence we get as a result a linear combination of columns of which we can read as a linear combination of power series, namely Thus, viewing sequence as codified by the power series we showed that Here the is the symbol for indicating correspondence on the power series level with matrix multiplication. We multiplied a Riordan array with a single power series. Now let be another Riordan array viewed as a matrix. One can form the product . The -th column of this product is just multiplied with the -th column of Since the latter corresponds to the power series , it follows by the above that the -th column of corresponds to . As this holds for all column indices occurring in we have shown part a. Part b is now clear.

Theorem: The family of Riordan arrays endowed with the product '' defined above forms a group: the Riordan group.[1]

Proof: The associativity of the multiplication '' follows from associativity of matrix multiplication. Next note . So is a left neutral element. Finally, we claim that is the left inverse to the power series . For this check the computation . As is well known, an associative structure which has a left neutral element and where each element has a left inverse is a group.

Of course, not all invertible infinite lower triangular arrays are Riordan arrays. Here is a useful characterization for the arrays that are Riordan. The following result is apparently due to Rogers. [4]

Theorem: An infinite lower triangular array is a Riordan array if and only if there exist a sequence traditionally called the -sequence, such that

Proof.[5] Let be the Riordan array stemming from Since Since has order 1, it follows that is a Riordan array and by the group property there exists a Riordan array such that Computing the left-hand side yields and so comparison yields Of course is a solution to this equation; it is unique because is composition invertible. So, we can rewrite the equation as

Now from the matrix multiplication law, the -entry of the left-hand side of this latter equation is

At the other hand the -entry of the right-hand side of the equation above is

so that i results. From we also get for all and since we know that the diagonal elements are nonzero, we have Note that using equation one can compute all entries knowing the entries

Now assume we know of a triangular array the equations for some sequence Let be the generating function of that sequence and define from the equation Check that it is possible to solve the resulting equations for the coefficients of and since one gets that has order 1. Let be the generating function of the sequence Then for the pair we find This is precisely the same equations we have found in the first part of the proof and going through its reasoning we find equations like in . Since (or the sequence of its coefficients) determines the other entries, we find that the array we started with is the array we deduced. So, the array in is a Riordan array.

Clearly the -sequence alone does not deliver all the information about a Riordan array. Besides the -sequence the -sequence below has been studied and has been shown to be useful.

Theorem. Let be an infinite lower triangular array whose diagonal sequence does not contain zeroes. Then there exists a unique sequence such that

Proof: By triangularity of the array, the equation claimed is equivalent to For this equation is and, as it allows computing uniquely. In general, if are known, then allows computing uniquely.

References

[edit]
  1. ^ a b c d e Shapiro, Louis W.; Getu, Seyoum; Woan, Wen-Jin; Woodson, Leon C. (November 1991). "The Riordan group". Discrete Applied Mathematics. 34 (1?3): 229?239. doi:10.1016/0166-218X(91)90088-E.
  2. ^ "6th International Conference on Riordan Arrays and Related Topics". 6th International Conference on Riordan Arrays and Related Topics.
  3. ^ Roman, S. (1984). The Umbral Calculus. New York: Academic Press.
  4. ^ Rogers, D. G. (1978). "Pascal triangles, Catalan numbers, and renewal arrays". Discrete Math. 22 (3): 301–310. doi:10.1016/0012-365X(78)90063-8.
  5. ^ He, T.X.; Sprugnoli, R. (2009). "Sequence characterization of Riordan Arrays". Discrete Mathematics. 309 (12): 3962–3974. doi:10.1016/j.disc.2008.11.021.