Hessenberg Matrices and Integer Sequences

Milan Janjić Department of Mathematics and Informatics University of Banja Luka Republic of Srpska Bosnia and Herzegovina

                        agnus@blic.net

Dedicated to the memory of Professor Veselin Perić

Abstract

We consider a particular case of upper Hessenberg matrices, in which all subdiagonal elements are −1. We investigate three type of matrices related to polynomials, generalized Fibonacci numbers, and special compositions of natural numbers. We give the combinatorial meaning of the coefficients of the characteristic polynomials of these matrices.

1 Introduction

We investigate a particular case of upper Hessenberg matrices, in which all subdiagonal elements are −1. Several mathematical objects may be represented as determinants of such matrices. We consider three type of matrices related to polynomials, generalized Fibonacci numbers, and a special kind of composition of natural numbers. Our objective is to find the combinatorial meaning of the coefficients of the characteristic polynomials.

The coefficients of the characteristic polynomials of matrices of the first type, that is, the sums of principal minors, are related to some binomial identities.

The characteristic polynomials of matrices of the second kind give, as a particular case, the so-called convolved Fibonacci numbers defined by Riordan [4].

Coefficients of the characteristic polynomial of matrices of the third kind are connected with a special kind of composition of natural numbers, in which there are two different types of ones. These were introduced by Deutsch [2], and studied by Grimaldi [3].

We prove several formulas which generate a number of sequences in Slonae’s Encyclopedia [5].

The following result about upper Hessenberg matrices, which may be easily proved by induction, will be used in this paper.

Theorem 1. Let the matrix P_{n} be defined by

P_{n} = [ \begin{matrix}p_{1,1} & p_{1,2} & p_{1,3} & ⋯ & p_{1,n−1} & p_{1,n} \\ −1 & p_{2,2} & p_{2,3} & ⋯ & p_{2,n−1} & p_{2,n} \\ 0 & −1 & p_{3,3} & ⋯ & p_{3,n−1} & p_{3,n} \\ ⋮ & ⋮ & ⋮ & ... & ⋮ & ⋮ \\ 0 & 0 & 0 & ⋯ & p_{n−1,n−1} & p_{n−1,n} \\ 0 & 0 & 0 & ⋯ & −1 & p_{n,n} \end{matrix} ] ,  (1)

and let the sequence a_{1}, a_{2}, … be defined by

a_{n+1} = ∑_{i=1}^{n} p_{i,n}a_{i}, (n = 1, 2, …).  (2)

Then

a_{n+1} = a_{1} det P_{n}, (n = 1, 2, …).

The Fibonacci numbers are defined by F_{0} = 0, F_{1} = 1, and F_{n} = F_{n−1} + F_{n−2} for n ≥ 2 Also, we use the well-known fact that the coefficients of the characteristic polynomial of a matrix are, up to the sign, sums of principal minors of the matrix.

2 Polynomials

We start our investigations with Hessenbeg matrices whose determinants are polynomials. According to Theorem 1 we have

Proposition 2. Let the matrix P_{n+1} be defined by:

P_{n+1} = [ \begin{matrix}1 & p_{1} & p_{2} & ⋯ & p_{n−1} & p_{n} \\ −1 & x & 0 & ⋯ & 0 & 0 \\ 0 & −1 & x & ⋯ & 0 & 0 \\ ⋮ & ⋮ & ⋮ & ... & ⋮ & ⋮ \\ 0 & 0 & 0 & ⋯ & x & 0 \\ 0 & 0 & 0 & ⋯ & −1 & x \end{matrix} ] .

Then

det P_{n+1} = x^{n} + p_{1}x^{n−1} + ⋯ + p_{n}.

We let S_{n+1−k}(x) denote the sum of all principal minors of order n + 1 − k of P_{n+1}, where k = 0, …, n, and S_{0} = 1.

Proposition 3. The following formulas are valid

S_{n+1−k}(x) = \binom{n}{k − 1}x^{n−k+1} + x^{n−k} ∑_{i=0}^{n−k} p_{i}\binom{n − i}{k}x^{−i}, (k = 0, 1, 2, …, n).  (3)

Proof. For k = 0 equation (3) means that S_{n+1} = det P_{n+1}, which is clear.

If we delete the first row and the first column of P_{n+1} we obtain a lower triangular matrix of order n with x’s on the main diagonal. Hence, all principal minors of order n−k obtained by deleting the first row and the first column of P_{n+1} and another k − 1 rows and columns with the same indices are equal to x^{n−k+1}. There are \binom{n}{k−1} such minors. This gives the first term in equation (3).

We shall next calculate the minor M_{n+1−k} obtained by deleting the rows and columns with indices 2 ≤ m_{1} < ⋯ < m_{k} ≤ n + 1. By deleting the mth row and the mth column of P_{n+1}, for m > 1, we obtain an upper triangular block matrix where the upper block is P_{m−1} and thus its determinant is equal ∑_{i=0}^{m−2} p_{i}x^{m−2−i}. The lower block is a lower triangular matrix of order n + 1 − m with x’s on the main diagonal. It follows that M_{n+1−k}(x) = ∑_{i=0}^{m−2} p_{i}x^{m−2−i}x^{n−k−m+2}. For a fixed m > 1 there are \binom{n+1−m}{k−1} such minors.

We thus obtain

S_{n+1−k}(x) = \binom{n}{k − 1}x^{n−k+1} + ∑_{m=2}^{n−k+2} ∑_{i=0}^{m−2} p_{i}\binom{n − m + 1}{k − 1}x^{n−k−i}, (k = 1, 2, …, n).

Changing the order of summation yields

S_{n+1−k}(x) = \binom{n}{k − 1}x^{n−k+1} + ∑_{i=0}^{n−k} p_{i}x^{n−k−i} ∑_{m=i+2}^{n−k+2} \binom{n − m + 1}{k − 1}, (k = 1, 2, …, n).

The corollary now holds by the following recurrence relation for binomial coefficients:

∑_{i=0}^{n−k} \binom{n − i}{k} = \binom{n + 1}{k + 1}.

Corollary 4. If x = 1, p_{i} = 1, (i = 0, 1, …, n) then

S_{n+1} = n + 1, S_{n+1−k} = \binom{n}{k − 1} + \binom{n + 1}{k + 1}, (k = 1, 2, …, n).

Several sequences from Sloane’s OIES [5] are generated by the preceding formulas. We state some of them: \underline{A000124}, \underline{A000217}, \underline{A001105}, \underline{A001845}, \underline{A004006}, \underline{A005744}, \underline{A005893}, \underline{A006522}, \underline{A017281}, \underline{A027927}, \underline{A056220}, \underline{A057979}, \underline{A080855}, \underline{A080856}, \underline{A080857}, \underline{A105163}, \underline{A121555}, \underline{A168050}.

Corollary 5. If x ≠ 1, p_{i} = 1, (i = 1, …, n) in (3) then

S_{n+1}(x) = \frac{x^{n+1} − 1}{x − 1}, S_{n+1−k}(x) = \binom{n}{k − 1}x^{n−k+1} + ∑_{j=0}^{n−k} \binom{k + j}{k}x^{j}, (k = 0, 1, …, n).

According to the well-known binomial identity

\binom{k + j}{j} = (−1)^{j}\binom{−k − 1}{j},

we see that the second term

∑_{j=0}^{n−k} \binom{k + j}{k}x^{j},

in the preceding equation is the partial sum of the expansion of the function \frac{1}{(1−x)^{k+1}} into powers of x.

The characteristic matrix Q_{n+1}(t) of P_{n+1} has the form

Q_{n+1}(t) = − [ \begin{matrix}1 − t & p_{1} & p_{2} & ⋯ & p_{n−1} & p_{n} \\ −1 & x − t & 0 & ⋯ & 0 & 0 \\ 0 & −1 & x − t & ⋯ & 0 & 0 \\ ⋮ & ⋮ & ⋮ & ... & ⋮ & ⋮ \\ 0 & 0 & 0 & ⋯ & x − t & 0 \\ 0 & 0 & 0 & ⋯ & −1 & x − t \end{matrix} ] .

This is also a Hessenberg matrix. If f_{n+1}(t) is the characteristic polynomial of P_{n+1} then

f_{n+1}(t) = det(Q_{n+1}(t)) = (−1)^{n+1} [∑_{k=1}^{n} p_{k}(x − t)^{n−k} + (1 − t)(x − t)^{n}] .

We thus obtain

Proposition 6. The following equation holds

∑_{k=0}^{n+1}(−1)^{n−k+1}S_{n−k+1}(x)t^{k} = (−1)^{n+1} [∑_{k=1}^{n} p_{k}(x − t)^{n−k} + (1 − t)(x − t)^{n}] .  (4)

As a consequence we shall prove a curious binomial identity.

Proposition 7. Let m, n (0 ≤ m ≤ n) be arbitrary integers. Then

∑_{j=m}^{n} ∑_{k=0}^{n−j}(−1)^{k}\binom{k + j}{j}\binom{j}{m} = 1.

Proof. Take p_{i} = 1, (i = 0, …, n), t = 1, and x+1 instead of x in (4). The left side becomes

L = 1 + ∑_{k=0}^{n}(−1)^{n−k+1} [\binom{n}{k − 1}(x + 1)^{n−k+1} + ∑_{j=0}^{n−k}(−1)^{n−k+1}\binom{k + j}{j}(x + 1)^{j}] .

It is easily seen that

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

Therefore,

L = (−x)^{n} + ∑_{k=0}^{n} ∑_{j=0}^{n−k} ∑_{m=0}^{j}(−1)^{n−k+1}\binom{k + j}{j}\binom{j}{m}x^{m}.

Changing the order of summation we have

L = (−x)^{n} + ∑_{m=0}^{n} [∑_{j=m}^{n} ∑_{k=0}^{n−j}(−1)^{n−k+1}\binom{k + j}{j}\binom{j}{m}] x^{m}.

The right side of (4) has the form R = (−1)^{n+1}(x^{n−1} + x^{n−2} + ⋯ + 1).

In this way we obtain

∑_{m=0}^{n} [∑_{j=m}^{n} ∑_{k=0}^{n−j}(−1)^{n−k+1}\binom{k + j}{j}\binom{j}{m}] x^{m} = (−1)^{n+1}(x^{n} + x^{n−1} + ⋯ + 1).

The proposition follows by comparing coefficients of the same powers of x in this equation.

3 Generalized Fibonacci Numbers

Consider the sequence recursively given by l_{1} = 1, l_{2} = x, l_{n+1} = yl_{n−1} + xl_{n}, (n > 2), and an upper Hessenberg matrix L_{n} of order n defined by:

L_{n} = [ \begin{matrix}x & y & 0 & ⋯ & 0 & 0 \\ −1 & x & y & ⋯ & 0 & 0 \\ 0 & −1 & x & ⋯ & 0 & 0 \\ ⋮ & ⋮ & ⋮ & ... & ⋮ & ⋮ \\ 0 & 0 & 0 & ⋯ & x & y \\ 0 & 0 & 0 & ⋯ & −1 & x \end{matrix} ] .

From Theorem 1 we obtain

det L_{n} = l_{n+1}, (n = 1, 2, …).

For l_{1} = l_{2} = x = y = 1 we have l_{n+1} = f_{n+1}, where f_{n+1} is the n + 1th Fibonacci number. The numbers l_{n} are usually called generalized Fibonacci numbers.

Proposition 8. Let S_{n−k}, (k = 0, 1, …, n − 1) be the sum of all principal minors of L_{n} of order n − k. Then

S_{n−k} = ∑_{j_{1}+j_{2}+···+j_{k+1}=n+1} l_{j_{1}}l_{j_{2}} ⋯ l_{j_{k+1}},  (5)

where the sum is taken over j_{t} ≥ 1, (t = 1, 2, …, k + 1).

Proof. Principal minors of L_{n} are some convolutions of l_{n}. For example, the minor obtained by deleting the ith row and the ith column of L_{n} is obviously equal to l_{i} · l_{n−i+1}. Therefore, the principal minor M(i_{1}, i_{2}, …, i_{k}) of L_{n} obtained by deleting the rows and columns with indices 1 ≤ i_{1} < i_{2} < ⋯ < i_{k} ≤ n is

M(i_{1}, i_{2}, …, i_{k}) = l_{i_{1}} · l_{i_{2}−i_{1}} ⋯ l_{i_{k}−i_{k−1}} · l_{n−i_{k}+1}.

Denoting i_{1} = j_{1}, i_{2} − i_{1} = j_{2}, …, i_{k} − i_{k−1} = j_{k}, n − i_{k} + 1 = j_{k+1} yields

M(i_{1}, i_{2}, …, i_{k}) = l_{j_{1}} · l_{j_{2}} ⋯ l_{j_{k}} · l_{j_{k+1}},

where j_{t} ≥ 1, (t = 1, 2, …, k + 1), and j_{1} + ⋯ + j_{k+1} = n + 1.

Summing over all 1 ≤ i_{1} < i_{2} < ⋯ < i_{k} ≤ n we obtain (5).

From Proposition 8 we easily derive the following known result for compositions of a natural number.

Proposition 9. The number c(n + 1, k + 1) of compositions of n + 1 into k + 1 parts is

c(n + 1, k + 1) = \binom{n}{k}.

Proof. Take specifically l_{1} = x = 1, y = 0. Then L_{n} is a lower triangular matrix with 1’s on the main diagonal. Therefore, all of its principal minors equal 1, and there are \binom{n}{k} minors of order n − k. It follows that the sum (5) equals \binom{n}{k}, and that all its summands are equal 1. On the other hand, this sum is taken over all compositions of n + 1 into k + 1 parts and the proposition follows.

In Riordan’s book [4] the sum on the right side of (5) for x = y = 1 is called a convolved Fibonacci number and is denoted by f_{n−k+1}^{(k+1)}. Hence,

Corollary 10. The convolved Fibonacci number f_{n−k+1}^{(k+1)} is equal, up to sign, to the coefficient of t^{k} in the characteristic polynomial p_{n}(t) of L_{n}, in the case x = y = 1.

The following result is an explicit formula for convolved Fibonacci numbers.

Corollary 11. Let f_{n−k+1}^{(k+1)} denote the convolved Fibonacci number. Then

f_{n−k+1}^{(k+1)} = ∑_{i=0}^{⌊ \frac{n−k}{2} ⌋} \binom{n − i}{i}\binom{n − 2i}{k}.

Proof. The characteristic matrix of L_{n} has the form:

[ \begin{matrix}t − 1 & 1 & 0 & ⋯ & 0 & 0 \\ −1 & t − 1 & 1 & ⋯ & 0 & 0 \\ 0 & −1 & t − 1 & ⋯ & 0 & 0 \\ ⋮ & ⋮ & ⋮ & ... & ⋮ & ⋮ \\ 0 & 0 & 0 & ⋯ & t − 1 & 1 \\ 0 & 0 & 0 & ⋯ & −1 & t − 1 \end{matrix} ] .

It follows that p_{n}(t) = f_{n+1}(t − 1), where f_{n+1}(t) is a Fibonacci polynomial. The corollary follows from the preceding corollary and the following explicit formula for Fibonacci polynomials:

f_{n+1}(x) = ∑_{i=0}^{⌊ \frac{n}{2} ⌋} \binom{n − i}{i}x^{n−2i}.

Since f_{n+1}(1) = f_{n+1} we also have the following identity for Fibonacci numbers:

Corollary 12. For Fibonacci numbers f_{n}, (n = 0, 1, …) we have

f_{n+1} = (−1)^{n} ∑_{k=0}^{n} ∑_{i=0}^{⌊ \frac{n−k}{2} ⌋}(−2)^{k}\binom{n − i}{i}\binom{n − 2i}{k}.

Remark 13. Taking particular values for x and y in the matrix L_{n} we may obtain different kinds of generalized Fibonacci numbers. For example, taking x = y = 1, and taking 3 instead of 1 in the upper left corner of L_{n} we obtain a matrix whose determinant is a Lucas number. In this case Proposition 8 shows that the coefficients of the characteristic polynomial are convolutions between Fibonacci and Lucas numbers.

Many of the sequences in Sloane’s Encyclopedia are generated by the sums from Proposition 8. Here are some of them: \underline{A000045}, \underline{A000129}, \underline{A001076}, \underline{A001628}, \underline{A001629}, \underline{A001872}, \underline{A006190}, \underline{A006503}, \underline{A006504}, \underline{A006645}, \underline{A023607}, \underline{A052918}, \underline{A054457}, \underline{A073380}, \underline{A073381}. \underline{A077985}, \underline{A152881}.

4 Particular Compositions of Natural Numbers

We shall now consider a type of Hessenberg matrices whose determinants are Fibonacci numbers with odd indices. This will lead us to the compositions of a natural number with two different types of ones, introduced by E. Deutsch in [2].

Proposition 14. Let G_{n} be the matrix of order n defined by:

G_{n} = [ \begin{matrix}2 & 1 & 1 & ⋯ & 1 & 1 \\ −1 & 2 & 1 & ⋯ & 1 & 1 \\ 0 & −1 & 2 & ⋯ & 1 & 1 \\ ⋮ & ⋮ & ⋮ & ... & ⋮ & ⋮ \\ 0 & 0 & 0 & ⋯ & 2 & 1 \\ 0 & 0 & 0 & ⋯ & −1 & 2 \end{matrix} ] .

Then

det G_{n} = f_{2n+1}.

Proof. According to Theorem 1 we have

a_{1} = 1, a_{2} = 2, …, a_{n+1} = a_{1} + a_{2} + ⋯ + a_{n−1} + 2a_{n}, (n > 2).

It follows from Identity 2 in [1] that a_{n+1} = f_{2n+1}.

Proposition 15. Let S_{n−k}, (0 ≤ k ≤ n) be the sum of all minors of order n − k of G_{n}. Then

S_{n−k} = ∑_{j_{1}+j_{2}+···+j_{k+1}=n−k} f_{2j_{1}+1}f_{2j_{2}+1} ⋯ f_{2j_{k+1}+1},

where the sum is taken over j_{t} ≥ 0, (t = 1, 2, …, k + 1).

Proof. Let M(i_{1}, i_{2}, …, i_{k}) be the minor of order n − k obtained by deleting the rows and columns with indices 1 ≤ i_{1} < i_{2} < ⋯ < i_{k} ≤ n. Then

M = det(G_{i_{1}−1}) · det(G_{i_{2}−i_{1}−1}) ⋯ det(G_{i_{k}−i_{k−1}−1}) · det(G_{n−i_{k}}).

Applying Proposition 14 we obtain

M = f_{2(i_{1}−1)+1}f_{2(i_{2}−i_{1}−1)+1} ⋯ f_{2(i_{k}−i_{k−1}−1)+1}f_{2(n−i_{k})+1}.

It follows that

S_{n−k} = ∑_{1≤i_{1}<i_{2}<···<i_{k}≤n} f_{2(i_{1}−1)+1}f_{2(i_{2}−i_{1}−1)+1} ⋯ f_{2(i_{k}−i_{k−1}−1)+1}f_{2(n−i_{k})+1}.

If we set

i_{1} − 1 = j_{1}, i_{2} − i_{1} − 1 = j_{2}, …, i_{k} − i_{k−1} − 1 = j_{k}, n − i_{k} = j_{k+1},

we have

S_{n−k} = ∑_{j_{1}+j_{2}+···+j_{k+1}=n−k} f_{2j_{1}+1}f_{2j_{2}+1} ⋯ f_{2j_{k+1}+1},

where the sum is taken over all j_{t} ≥ 0, (t = 1, 2, …, k + 1).

For compositions of n in which there are two types of ones Grimaldi, in his paper [3], shows that its number is f_{2n+1}.

We let c_{n,k} denote the number of such compositions in which exactly k parts equal 0. We finish the paper by showing that the number S_{n−k}, from the preceding proposition, is in fact equal to c_{n−k,k}.

Proposition 16. Let n be a positive integer, and let k be a nonnegative integer. Then

c_{n,k} = ∑_{j_{1}+j_{2}+···+j_{k+1}=n} f_{2j_{1}+1}f_{2j_{2}+1} ⋯ f_{2j_{k+1}+1},  (6)

where the sum is taken over j_{t} ≥ 0, (t = 1, 2, …, k + 1).

Proof. We use induction with respect of k. The theorem is true for k = 0, according to the preceding proposition.

Assume the theorem is true for k − 1. The greatest value of j_{k+1} is n, and is obtained for j_{1} = j_{2} = ⋯ = j_{k} = 0. We thus may write (6) in the form:

c_{n,k} = ∑_{j=0}^{n} f_{2j+1} ∑_{j_{1}+j_{2}+···+j_{k}=n−j} f_{2j_{1}+1}f_{2j_{2}+1} ⋯ f_{2j_{k}+1}.

By the induction hypothesis we have

c_{n,k} = ∑_{j=0}^{n} f_{2j+1} · c_{n−j,k−1}.  (7)

Let (i_{1}, i_{2}, …) be a composition of n with two different types of ones and exactly k zeroes, and let first index, where 0 is a summand, be i_{p}. Then (i_{1}, i_{2}, …, i_{p−1}) is a composition of j = i_{1} + ⋯ + i_{p−1} with no zeroes, and (i_{p+1}, …) is a composition of n − j with exactly k − 1 zeroes. The number of such compositions is f_{2j+1} · c(n − j, k − 1), which is a summand on the right side of (7). In this way the sum on the right side of (7) counts all of the required compositions.

This part of the paper is concerned with \underline{A030267}.

5 Acknowledgments

I would like to thank the referees for valuable comments.

References

[1] A. T. Benjamin and J. J. Quinn, Proofs that Really Count, MAA, 2003.

[2] E. Deutsch, Advanced exercise H-641, Fibonacci Quart. 44 (2006), 188.

[3] R. P. Grimaldi, Compositions and the alternate Fibonacci numbers, Congr. Numer. 186 (2007), 81–96.

[4] J. Riordan, Combinatorial Identities, Wiley, 1968.

[5] N. J. A. Sloane, Online Encyclopedia of Integer Sequences,

    http://www.research.att.com/~njas/sequences/.

2000 Mathematics Subject Classification: Primary 11B39; Secondary 11C20. Keywords: Hessenberg matrix, generalized Fibonacci number, Fibonacci polynomial, composition of a natural number.

(Concerned with sequences \underline{A000045}, \underline{A000124}, \underline{A000129}, \underline{A000217}, \underline{A001076}, \underline{A001105}, \underline{A001628}, \underline{A001629}, \underline{A001845}, \underline{A001872}, \underline{A004006}, \underline{A005744}, \underline{A005893}, \underline{A006190}, \underline{A006503}, \underline{A006504}, \underline{A006522}, \underline{A006645}, \underline{A017281}, \underline{A023607}, \underline{A027927}, \underline{A030267}, \underline{A052918}, \underline{A054457}, \underline{A056220}, \underline{A057979}, \underline{A073380}, \underline{A073381}, \underline{A077985}, \underline{A080855}, \underline{A080856}, \underline{A080857}, \underline{A105163}, \underline{A121555}, \underline{A152881}, \underline{A168050}.)

Received March 31 2010; revised version received July 14 2010. Published in Journal of Integer Sequences, July 16 2010.

Return to Journal of Integer Sequences home page.