Note on Total Positivity for a Class of Recursive Matrices

Liang Zhao and Fengyao Yan School of Mathematical Sciences Dalian University of Technology Dalian 116024 P. R. China

                  light0617@mail.dlut.edu.cn
                  yanfengyao@mail.dlut.edu.cn

Abstract In this note, we study the total positivity of a class of infinite recursive matrices that depend on three infinite sets of independent variables and on an integer parameter. We give a simple algebraic proof and provide a few examples.

1 Introduction

A (finite or infinite) matrix M is said to be totally positive (T P) if its minors of all orders are nonnegative. Total positivity is a powerful concept that arises frequently in various branches of mathematics, statistics, probability, mechanics, economics, and computer science [4, 10]. The totally positive matrices play an important role in the theory of total positivity [1, 5, 8, 9, 10]. Recently, Chen et al. [6, 7] presented some sufficient conditions for the total positivity of Riordan arrays and recursive matrices. Brenti [4] introduced a class of recursive matrices that depend on three infinite sets of independent variables and on an integer parameter. More precisely, let the infinite matrix M = [M_{n,k}]_{n,k≥0} be defined by

M_{0,0} = 1,  M_{n,k} = z_{n}M_{n−t,k−1} + y_{n}M_{n−1−t,k−1} + x_{n}M_{n−1,k}  (1)

for n + k ≥ 1, where t ∈ ℕ, M_{n,k} = 0 if either n < 0 or k < 0, and (x_{n})_{n≥0}, (y_{n})_{n≥0}, and (z_{n})_{n≥0} are nonnegative sequences. Brenti [4] associated a planar network with the matrix and used its planarity to prove the total positivity of M.

Theorem 1 ([4, Theorem 4.3]). Let M = [M_{n,k}]_{n,k≥0} be defined by (1). Then M is T P.

In this note we give a simple algebraic proof of Theorem 1. With the method of our proof, the total positivity of many recursive matrices can be easily proved, and a few examples are provided in Section 3.

2 Proof of Theorem 1

We first review some basic facts about T P matrices.

Lemma 2 ([11, Proposition 1.6]). Assume A is a nonsingular totally positive matrix. Then so is JA^{−1}J, where J is the diagonal matrix with diagonal entries alternately 1 and −1.

An operation that preserves total positivity is the following form of iteration. Let A = [a_{ij}]_{i,j=1}^{n} be an n × n matrix. Define the matrix B = [b_{ij}]_{i,j=1}^{n} by b_{1j} = a_{1j}, j = 1, …, n, and for i ≥ 2, b_{ij} = ∑_{k=1}^{n} b_{i−1,k}a_{kj}, j = 1, …, n. Pinkus [11] showed that if A is T P, then B is also T P. Actually, this result can be generalized to infinite matrices when A = [a_{i,j}]_{i,j≥0} is an upper triangular matrix. It is clear that B = [b_{i,j}]_{i,j≥0} is T P if and only if its leading principal submatrices [b_{i,j}]_{0≤i,j≤n} are all T P [6, Lemma 2.1], and [b_{i,j}]_{0≤i,j≤n} is obtained directly from [a_{i,j}]_{0≤i,j≤n}. Then we have the following.

Lemma 3. Let A^{T} = [α_{1}, α_{2}, …] be an infinite upper triangular matrix, where for j ≥ 1, α_{j} denotes the infinite column vector. Define the matrix B^{T} = [β_{1}, β_{2}, …] by β_{1} = α_{1}, and for i ≥ 2, β_{i}^{T} = β_{i−1}^{T} A. If A is T P, then so is B.

To prove Theorem 1, we construct two matrices

A = [a_{ij}]_{i≥0,j≥0} = [ \begin{matrix}0 & 1 & x_{1} & x_{1}x_{2} & x_{1}x_{2}x_{3} & ⋯ \\ & z_{0} & y_{1} + x_{1}z_{0} & x_{2}(y_{1} + x_{1}z_{0}) & x_{2}x_{3}(y_{1} + x_{1}z_{0}) \\ & & z_{1} & y_{2} + x_{2}z_{1} & x_{3}(y_{2} + x_{2}z_{1}) \\ & & & z_{2} & y_{3} + x_{3}z_{2} \\ & & & & z_{3} \\ . & . & . \end{matrix} ]

and

I_{t} = [ \begin{matrix}1 & O \\ O & U \end{matrix} ] ,

where U = [δ_{i+t,j}]_{i,j≥0} and δ_{i,j} is the Kronecker delta, i.e.,

δ_{i,j} = \begin{cases}1, & if i = j; \\ 0, & if i ≠ j. \end{cases}

Clearly, I_{0} = I and I_{t}A is the matrix obtained from A by removing rows of A from the second row to the (t + 1)th row. Applying Lemma 3 to the matrix I_{t}A, we get B = [O, B̃], where B̃ = [b_{i,j}]_{i≥0,j≥0}.

Proof of Theorem 1. We first show that M = B̃^{T}. For n = 0, it is readily verified that b_{0,k} = M_{k,0}. For n ≥ 1, we have

b_{n,k} = ∏_{i=t+2}^{k} x_{i}(y_{t+1} + x_{t+1}z_{t})b_{n−1,0} + ∏_{i=t+3}^{k} x_{i}(y_{t+2} + x_{t+2}z_{t+1})b_{n−1,1}
+ ⋯ + (y_{k} + x_{k}z_{k−1})b_{n−1,k−t−1} + z_{k}b_{n−1,k−t}
=x_{k}b_{n,k−1} + y_{k}b_{n−1,k−t−1} + z_{k}b_{n−1,k−t}.

Thus M = B̃^{T}.

By the definition of T P and the fact that I_{t}A is a submatrix of A, it suffices to show that A is T P. Let

X = [ \begin{matrix}1 & 0 \\ & 1 & x_{1} \\ & & 1 & x_{2} \\ & & & 1 & x_{3} \\ & & & & 1 & ... \\ . & . & . \end{matrix} ] , Y = [ \begin{matrix}0 & 1 \\ & z_{0} & y_{1} \\ & & z_{1} & y_{2} \\ & & & z_{2} & y_{3} \\ & & & & z_{3} & ... \\ . & . & . \end{matrix} ] .

It is obvious that X and Y are T P. Note that by column operations, we can turn A into Y. Thus A has a factorization of the form

A = Y JX^{−1}J,

where J is defined in Lemma 2, which implies that JX^{−1}J is T P. It is known that the product of two T P matrices is still T P by the classic Cauchy-Binet formula. Thus A is T P. This completes the proof.

3 Applications

In this section we consider some examples for different t. A basic example for case t = 0 and t = 1 is the Delannoy square and the Delannoy triangle [12, \underline{A008288}]. Many properties and applications of Delannoy numbers have been discussed [2, 3, 13, 15]. The Delannoy numbers d_{n,k} are defined as the numbers of lattice paths from (0, 0) to (n, k) with steps (1, 0), (0, 1), and (1, 1). It is well known that the Delannoy numbers satisfy the recursion

d_{n,k} = d_{n,k−1} + d_{n−1,k−1} + d_{n−1,k}.

Brenti [4] showed that the Delannoy square

D = [d_{n,k}]_{n,k≥0} = [ \begin{matrix}1 & 1 & 1 & 1 & … \\ 1 & 3 & 5 & 7 \\ 1 & 5 & 13 & 25 \\ 1 & 7 & 25 & 63 \\ ⋮ & & & & ... \end{matrix} ]

is T P. Let d(n, k) = d_{n−k,k} denote the corresponding Delannoy triangle D̄ = [d(n, k)]_{n,k≥0}, i.e.,

D̄ = [ \begin{matrix}1 \\ 1 & 1 \\ 1 & 3 & 1 \\ 1 & 5 & 5 & 1 \\ ⋮ & & & & ... \end{matrix} ] .

Then the entries in D̄ satisfy the recurrence relation

d(n + 1, k + 1) = d(n, k) + d(n − 1, k) + d(n, k + 1).

Wang and Yang [14] showed that D̄ is T P.

With the method of our proof, applying Lemma 3 to the matrices

[ \begin{matrix}0 & 1 & 1 & 1 & 1 & … \\ & 1 & 2 & 2 & 2 \\ & & 1 & 2 & 2 \\ & & & 1 & 2 \\ & & & & 1 \\ . & . & . \end{matrix} ] and [ \begin{matrix}0 & 1 & 1 & 1 & 1 & … \\ & 0 & 1 & 2 & 2 \\ & & 0 & 1 & 2 \\ & & & 0 & 1 \\ & & & & 0 \\ . & . & . \end{matrix} ] ,

we get

[ \begin{matrix}0 & 1 & 1 & 1 & 1 & ⋯ \\ 0 & 1 & 3 & 5 & 7 \\ 0 & 1 & 5 & 13 & 25 \\ 0 & 1 & 7 & 25 & 63 \\ 0 & 1 & 9 & 41 & 129 \\ ⋮ & & & & & ... \end{matrix} ] and [ \begin{matrix}0 & 1 & 1 & 1 & 1 & ⋯ \\ & 0 & 1 & 3 & 5 \\ & & 0 & 1 & 5 \\ & & & 0 & 1 \\ & & & & 0 \\ . & . & . \end{matrix} ] .

Then the total positivity of the Delannoy square and the Delannoy triangle immediately follows.

An example for case t = 2 is the Harer-Zagier numbers g(n, k) [12, \underline{A035309}], which count the number of ways to glue all edges of a 2n-gon pairwise, so as to produce a surface of given genus k. The first three columns of G = [g(n, k)]_{n,k≥0} (for k = 0, 1, 2) are respectively the Catalan numbers [12, \underline{A000108}], \underline{A002802}, and \underline{A006298}. The entries of G satisfy the recursion

(n + 2)g(n + 1, k) = (4n + 2)g(n, k) + (4n^{3} − n)g(n − 1, k − 1),  (2)

where g(n, k) = 0 if either n < 0 or k < 0, g(0, 0) = 1, and g(0, k) = 0. So,

G = [ \begin{matrix}1 \\ 1 \\ 2 & 1 \\ 5 & 10 \\ 14 & 70 & 21 \\ 42 & 420 & 483 \\ 132 & 2310 & 6468 & 1485 \\ ⋮ & & & & ... \end{matrix} ] .

Using Lemma 3 with

A = [ \begin{matrix}0 & 1 & 1 & 2 & 5 & 14 & 42 & … \\ & & & 1 & \frac{5}{2} & 7 & 21 \\ & & & & \frac{15}{2} & 21 & 63 \\ & & & & & 21 & 63 \\ & & & & & & 42 \\ . & . & . \end{matrix} ] ,

we get

B = [ \begin{matrix}0 & 1 & 1 & 2 & 5 & 14 & 42 & ⋯ \\ & & & 1 & 10 & 70 & 420 \\ & & & & & 21 & 483 \\ . & . & . \end{matrix} ] .

Then we have the following. Corollary 4. Let G = [g(n, k)]_{n,k≥0} be defined by (2). Then G is T P.

4 Acknowledgments

The authors thank the anonymous referees for their careful reading and valuable suggestions.

References

[1] T. Ando, Total positive matrices, Linear Algebra Appl. 90 (1987), 165–219.

[2] C. Banderier and S. Schwer, Why Delannoy numbers?, J. Statist. Plann. Inference 135 (2005), 40–54.

[3] P. Barry, On integer-sequence-based constructions of generalized Pascal triangles, J. Integer Seq. 9 (2006), Article 06.2.4.

[4] F. Brenti, Combinatorics and total positivity, J. Combin. Theory Ser. A 71 (1995), 175–218.

[5] F. Brenti, The applications of total positivity to combinatorics, and conversely, in Total Positivity and Its Applications, in Math. Appl., Vol. 359, Kluwer, 1996, pp. 451–473.

[6] X. Chen, H. Liang, and Y. Wang, Total positivity of recursive matrices, Linear Algebra Appl. 471 (2015), 383–393.

[7] X. Chen, H. Liang, and Y. Wang, Total positivity of Riordan arrays, European J. Combin. 46 (2015), 68–74.

[8] S. M. Fallat and C. R. Johnson, Totally Nonnegative Matrices, Princeton University Press, 2011.

[9] M. Gasca and J. M. Peña, Total positivity and Neville elimination, Linear Algebra Appl. 165 (1992), 25–44.

[10] S. Karlin, Total Positivity, Vol. 1, Stanford University Press, 1968.

[11] A. Pinkus, Totally Positive Matrices, Cambridge University Press, 2010.

[12] N. J. A. Sloane, The On-Line Encyclopedia of Integer Sequences, http://oeis.org.

[13] R. A. Sulanke, Objects counted by the central Delannoy numbers, J. Integer Seq. 6 (2003), Article 03.1.5.

[14] Y. Wang and A. L. B. Yang, Total positivity of some symmetric triangular and square arrays, in preparation.

[15] S.-L. Yang, S.-N. Zheng, S.-P. Yuan, and T.-X. He, Schröder matrix as inverse of Delannoy matrix, Linear Algebra Appl. 439 (2013), 3605–3614.

2010 Mathematics Subject Classification: Primary 05A20; Secondary 15A45, 15B36. Keywords: totally positive matrix, recursive matrix.

(Concerned with sequences \underline{A000108}, \underline{A002802}, \underline{A006298}, \underline{A008288}, and \underline{A035309}.)

Received August 17 2015; revised versions received April 11 2016; June 4 2016; July 2 2016. Published in Journal of Integer Sequences, July 5 2016.

Return to Journal of Integer Sequences home page.