Jacobsthal Numbers and Associated Hessenberg Matrices

Ahmet Öteleş Department of Mathematics

Faculty of Education

Dicle University Diyarbakır Turkey

  aoteles85@gmail.com

Zekeriya Y. Karatas

Department of Mathematics, Physics and Computer Science

University of Cincinnati Blue Ash College

Blue Ash, OH 45236 USA

zekeriya.karatas@uc.edu

Diyar O. Mustafa Zangana Department of Mathematics

Art and Science Faculty

Siirt University Siirt Turkey

 diyar.math2@gmail.com

Abstract

In this paper, we define two n × n Hessenberg matrices, one of which corresponds to the adjacency matrix of a bipartite graph. We then investigate the relationships between the Hessenberg matrices and the Jacobsthal numbers. Moreover, we give Maple algorithms to verify our results.

1 Introduction

The famous Fibonacci, Pell, and Jacobsthal integer sequences, which appear, respectively, in the On-Line Encyclopedia of Integer Sequences (OEIS) as sequences \underline{A000045}, \underline{A000129}, and \underline{A001045} [1], provide invaluable research opportunities for us. These number sequences contribute significantly to mathematics, especially to the field of number theory, as Koshy observed [2, 3]. In particular, the Jacobsthal sequence is considered as one of the major sequences among the well-known integer sequences. The Jacobsthal sequence attracts many researchers in number theory.

The Jacobsthal sequence (J_{n})_{n≥0} is defined by the recurrence relation as follows:

J_{n} = J_{n−1} + 2J_{n−2},  (1)

with J_{0} = 0 and J_{1} = 1, for n ≥ 2 [4]. The number J_{n} is called the nth Jacobsthal number. The list of the first 11 terms of the sequence is given in Table 1.

\begin{matrix}n & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & ⋯ \\ J_{n} & 0 & 1 & 1 & 3 & 5 & 11 & 21 & 43 & 85 & 171 & 341 & 683 & ⋯ \end{matrix}

Table 1: Terms of J_{n}

We note for further reference that

J_{n} = \frac{2^{n} − (−1)^{n}}{3}  (2)

is the Binet formula of the Jacobsthal sequence (J_{n})_{n≥0} [4].

Microcontrollers and other computers use conditional instructions to change the flow of the execution of a program. In addition to branch instructions, some microcontrollers use skip instructions which conditionally skip to the next instruction. This winds up being useful for one case out of the four possibilities on 2 bits, 3 cases on 3 bits, 5 cases on 4 bits, 11 on 5 bits, 21 on 6 bits, 43 on 7 bits, 85 on 8 bits, …, which are exactly the Jacobsthal numbers.

König studied the properties of the bipartite graphs in [5, 6]. His papers were motivated by an attempt to give a new approach to evaluate the determinants of matrices. In practice, the bipartite graphs form a model of interaction between two different types of objects such as jobs and workers, telephone exchanges and cities [7]. The enumeration or the actual construction of the perfect matchings of the bipartite graphs has many applications, for example, in maximal flow problems, and assignment and scheduling problems arising in operational research [8]. The number of perfect matchings of bipartite graphs also plays a significant role in organic chemistry [9].

A bipartite graph G is a graph whose vertex set V can be partitioned into two subsets V_{1} and V_{2} such that every edge of the bipartite graph G joins a vertex in V_{1} and a vertex in V_{2}. A perfect matching (or 1-factor) of a graph is a matching in which each vertex has exactly one edge incident on it. In other words, every vertex in the graph has degree 1. Let A(G) be the adjacency matrix of the bipartite graph G, and let μ(G) denote the number of perfect matchings of the bipartite graph G. Then the following fact which states the relation between μ(G) and A(G) can be found in [8]: μ(G) = \sqrt{per (A(G))}.

Let G be a bipartite graph whose vertex set V is partitioned into two subsets V_{1} and V_{2} such that |V_{1}| = |V_{2}| = n. Next, we construct the bipartite adjacent matrix B(G) = (b_{ij}) of the bipartite graph G as follows: b_{ij} = 1 if and only if the bipartite graph G contains an edge from v_{i} ∈ V_{1} to v_{j} ∈ V_{2}, and otherwise b_{ij} = 0. Minc stated in [8] that the number of perfect matchings of the bipartite graph G is equal to the permanent of its bipartite adjacency matrix.

The permanent of an n × n matrix A = (a_{ij}) is defined by

per (A) = ∑_{σϵS_{n}} ∏_{i=1}^{n} a_{iσ(i)},

where the summation extends over all permutations σ of the symmetric group S_{n}. The permanent of a matrix is analogous to the determinant in which all of the signs used in the Laplace expansion of minors are positive.

Permanents have many applications in physics, chemistry, electrical engineering, and so on. Some of the most important applications of permanents are via graph theory. They essentially involve enumerations of certain subgraphs of a graph or a directed graph. A more difficult problem with many applications is the enumeration of perfect matchings of a graph [8]. Therefore, the counting the number of perfect matchings in bipartite graphs has been a very popular problem.

There are many papers on the relationships between the well-known number sequences and the matrices. [13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27] are some of these papers.

In this paper, we firstly define an n × n Hessenberg matrix that corresponds to the adjacency matrix of a bipartite graph, and we prove that the number of perfect matchings of the bipartite graph is equal to the Jacobsthal number. Secondly, we define another n × n Hessenberg matrix, and we prove that the permanent of the Hessenberg matrix is equal to the Jacobsthal number. Finally, we give the Maple algorithms to verify our results.

2 Main results

Let A = [a_{ij}] be an m × n real matrix with row vectors α_{1}, α_{2}, …, α_{m}. We say that the matrix A is contractible on column (resp. row) k if column (resp. row) k contains exactly two nonzero entries. Suppose that the matrix A is contractible on column k with a_{ik} ≠ 0 ≠ a_{jk} and i ≠ j. Then the (m − 1) × (n − 1) matrix A_{ij:k} obtained from the matrix A by replacing row i with a_{jk}α_{i} + a_{ik}α_{j} and deleting row j and column k is called the contraction of the matrix A on column k relative to rows i and j. If the matrix A is contractible on row k with a_{ki} ≠ 0 ≠ a_{kj} and i ≠ j, then the matrix A_{k:ij} = [A_{ij:k}^{T}]^{T} is called the contraction of the matrix A on row k relative to columns i and j. We say that the matrix A can be contracted to a matrix B, if either B = A or there exist matrices A_{0}, A_{1}, …, A_{t} (t ≥ 1) such that A_{0} = A, A_{t} = B, and A_{r} is a contraction of the matrix A_{r−1} for r = 1, …, t [10].

Brualdi and Gibson [10] proved the following result about the permanent of a matrix.

Lemma 1. Let A be a nonnegative integral matrix of order n for n > 1, and let B be a contraction of the matrix A. Then

perA = perB.  (3)

Let us define the n × n (0, 1)-Hessenberg matrix A_{n} as follows:

A_{n} = ( \begin{matrix}1 & 0 & 1 & 0 & ⋯ & 1 & 0 & ⋯ \\ 1 & 1 & 1 & 1 & ⋯ & ⋯ & 1 & 1 \\ 0 & 1 & 1 & 1 & 1 & ⋯ & ⋯ & 1 \\ ⋮ & 0 & 1 & ... & ... & ... & & ⋮ \\ ⋮ & & ... & ... & ... & ... & ... & ⋮ \\ ⋮ & & & ... & ... & 1 & 1 & 1 \\ ⋮ & & & & 0 & 1 & 1 & 1 \\ 0 & ⋯ & ⋯ & ⋯ & ⋯ & 0 & 1 & 1 \end{matrix} ) ,  (4)

where

a_{ij} = \begin{cases}1, & if i = 1 and j − 1 ≡ 0 (mod 2); \\ 1, & if i > 1 and j − i ≥ −1; \\ 0, & otherwise. \end{cases}

Theorem 2. Let G(A_{n}) be the bipartite graph with bipartite adjacency matrix A_{n} given by (4). Then the number of perfect matchings of the bipartite graph G(A_{n}) is the nth Jacobsthal number J_{n}.

Proof. If n = 3, then we have perA_{3} = per ( \begin{matrix}1 & 0 & 1 \\ 1 & 1 & 1 \\ 0 & 1 & 1 \end{matrix} ) = 3 = J_{3}.

Let A_{n}^{k} be the kth contraction of the matrix A_{n}, 1 ≤ k ≤ n − 2. Then by the definition of a contraction, the matrix A_{n} can be contracted on column 1 so that we get

A_{n}^{1} = ( \begin{matrix}1 & 2 & 1 & 2 & ⋯ & 1 & 2 & ⋯ \\ 1 & 1 & 1 & 1 & ⋯ & ⋯ & 1 & 1 \\ 0 & 1 & 1 & 1 & 1 & ⋯ & ⋯ & 1 \\ ⋮ & 0 & 1 & ... & ... & ... & & ⋮ \\ ⋮ & & ... & ... & ... & ... & ... & ⋮ \\ ⋮ & & & ... & ... & 1 & 1 & 1 \\ ⋮ & & & & 0 & 1 & 1 & 1 \\ 0 & ⋯ & ⋯ & ⋯ & ⋯ & 0 & 1 & 1 \end{matrix} )_{(n−1)×(n−1)} .

After contracting the matrix A_{n}^{1} on column 1, we have

A_{n}^{2} = ( \begin{matrix}3 & 2 & 3 & 2 & ⋯ & 3 & 2 & ⋯ \\ 1 & 1 & 1 & 1 & ⋯ & ⋯ & 1 & 1 \\ 0 & 1 & 1 & 1 & 1 & ⋯ & ⋯ & 1 \\ ⋮ & 0 & 1 & ... & ... & ... & & ⋮ \\ ⋮ & & ... & ... & ... & ... & ... & ⋮ \\ ⋮ & & & ... & ... & 1 & 1 & 1 \\ ⋮ & & & & 0 & 1 & 1 & 1 \\ 0 & ⋯ & ⋯ & ⋯ & ⋯ & 0 & 1 & 1 \end{matrix} )_{(n−2)×(n−2)} .

Since the Jacobsthal number J_{2} = 1 and the Jacobsthal number J_{3} = 3, we get

A_{n}^{2} = ( \begin{matrix}J_{3} & 2J_{2} & J_{3} & 2J_{2} & ⋯ & J_{3} & 2J_{2} & ⋯ \\ 1 & 1 & 1 & 1 & ⋯ & ⋯ & 1 & 1 \\ 0 & 1 & 1 & 1 & 1 & ⋯ & ⋯ & 1 \\ ⋮ & 0 & 1 & ... & ... & ... & & ⋮ \\ ⋮ & & ... & ... & ... & ... & ... & ⋮ \\ ⋮ & & & ... & ... & 1 & 1 & 1 \\ ⋮ & & & & 0 & 1 & 1 & 1 \\ 0 & ⋯ & ⋯ & ⋯ & ⋯ & 0 & 1 & 1 \end{matrix} )_{(n−2)×(n−2)} .

Furthermore, the matrix A_{n}^{2} can be contracted on column 1 and the Jacobsthal number J_{4} = 5 so that

A_{n}^{3} = ( \begin{matrix}J_{4} & 2J_{3} & J_{4} & 2J_{3} & ⋯ & J_{4} & 2J_{3} & ⋯ \\ 1 & 1 & 1 & 1 & ⋯ & ⋯ & 1 & 1 \\ 0 & 1 & 1 & 1 & 1 & ⋯ & ⋯ & 1 \\ ⋮ & 0 & 1 & ... & ... & ... & & ⋮ \\ ⋮ & & ... & ... & ... & ... & ... & ⋮ \\ ⋮ & & & ... & ... & 1 & 1 & 1 \\ ⋮ & & & & 0 & 1 & 1 & 1 \\ 0 & ⋯ & ⋯ & ⋯ & ⋯ & 0 & 1 & 1 \end{matrix} )_{(n−3)×(n−3)} .

Continuing this process, we get the kth contraction of the matrix A_{n} as

A_{n}^{k} = ( \begin{matrix}J_{k+1} & 2J_{k} & ⋯ & J_{k+1} & 2J_{k} & ⋯ & ⋯ & ⋯ \\ 1 & 1 & 1 & ⋯ & 1 & 1 & ⋯ & 1 \\ 0 & 1 & 1 & 1 & ⋯ & 1 & 1 & 1 \\ ⋮ & 0 & 1 & ... & ... & ... & & ⋮ \\ ⋮ & & ... & ... & ... & ... & ... & ⋮ \\ ⋮ & & & ... & ... & 1 & 1 & 1 \\ ⋮ & & & & 0 & 1 & 1 & 1 \\ 0 & ⋯ & ⋯ & ⋯ & ⋯ & 0 & 1 & 1 \end{matrix} )_{(n−k)×(n−k)}

for 3 ≤ k ≤ n − 4. Hence, the (n − 3)th contraction of the matrix A_{n} is

A_{n}^{n−3} = ( \begin{matrix}J_{n−2} & 2J_{n−3} & J_{n−2} \\ 1 & 1 & 1 \\ 0 & 1 & 1 \end{matrix} )_{3×3} ,

which gives

A_{n}^{n−2} = ( \begin{matrix}J_{n−1} & 2J_{n−2} \\ 1 & 1 \end{matrix} )_{2×2}

by the contraction of the matrix A_{n}^{n−3} on column 1. From Lemma 1, we get perA_{n} = perA_{n}^{n−2} = J_{n−1} + 2J_{n−2}. Moreover, we have J_{n} = J_{n−1} + 2J_{n−2} from (1). Therefore, perA_{n} = J_{n}, which completes the proof.

Let B_{n} be an n × n Hessenberg matrix as follows:

B_{n} = ( \begin{matrix}1 & −1 & 1 & −1 & ⋯ & 1 & −1 & ⋯ \\ 1 & 2 & 0 & 0 & ⋯ & ⋯ & 0 & 0 \\ 0 & 1 & 2 & 0 & 0 & ⋯ & ⋯ & 0 \\ ⋮ & 0 & 1 & ... & ... & ... & & ⋮ \\ ⋮ & & ... & ... & ... & ... & ... & ⋮ \\ ⋮ & & & ... & ... & 2 & 0 & 0 \\ ⋮ & & & & 0 & 1 & 2 & 0 \\ 0 & ⋯ & ⋯ & ⋯ & ⋯ & 0 & 1 & 2 \end{matrix} ) ,  (5)

where

b_{ij} = \begin{cases}1, & if j − i = −1 or i = 1 and j − 1 ≡ 0 (mod 2); \\ −1, & if i = 1 and j ≡ 0 (mod 2); \\ 2, & if i > 1 and j − i = 0; \\ 0, & otherwise. \end{cases}

Now, let us give the following lemma for the Jacobsthal sequence (J_{n})_{n≥0} which will be used later.

Lemma 3. Let J_{n} be the nth Jacobsthal number. Then we have

J_{n} = 2J_{n−1} − (−1)^{n} .  (6)

Proof. By using the Binet formula (2), we obtain

J_{n} = \frac{2 · 2^{n−1} + (−1)^{n−1}}{3} = 2 (\frac{2^{n−1} − (−1)^{n−1}}{3} ) − (−1)^{n} .

The proof follows by substituting J_{n−1} for \frac{2^{n−1}−(−1)^{n−1}}{3} .

Theorem 4. Let B_{n} be the n × n Hessenberg matrix given by (5). Then the permanent of the matrix B_{n} is equal to the nth Jacobsthal number J_{n}.

Proof. Let B_{n}^{k} be the kth contraction of the matrix B_{n} for 1 ≤ k ≤ n − 2. Then by applying successive contractions to the matrices B_{n}^{k} on their first columns for 1 ≤ k ≤ n − 3, we get

B_{n}^{n−2} = \begin{cases}( \begin{matrix}J_{n−1} & 1 \\ 1 & 2 \end{matrix} ) , & if n is odd; \\ ( \begin{matrix}J_{n−1} & −1 \\ 1 & 2 \end{matrix} ) , & if n is even. \end{cases}  (7)

By Lemma 1 and the equation (7), we deduce that perB_{n} = perB_{n}^{n−2} = 2J_{n−1} − (−1)^{n}. Moreover, we have J_{n} = 2J_{n−1} − (−1)^{n} from (6), and the result follows.

Appendix

The following Maple program calculates the number of perfect matchings of the bipartite graph G(A_{n}) given in Theorem 2.

with(LinearAlgebra):
permanent:=proc(n) local i,j,r,f,A;
f:=(i,j)->piecewise(i=1 and j mod 2=1,1,i>1 and j-i>-2,1,0);
A:=Matrix(n,n,f):
for r from 0 to n-2 do
  print(r,A):
  for j from 2 to n-r do
    A[1,j]:=A[2,1]*A[1,j]+A[1,1]*A[2,j]:
    od:
  A:=DeleteRow(DeleteColumn(Matrix(n-r,n-r,A),1),2):
  od:
print(r,eval(A)):
end proc:with(LinearAlgebra):

It can be called, for example, with the syntax

                           permanent(8);

The following Maple algorithm calculates the permanent of the Hessenberg matrix B_{n} given in Theorem 4.

with(LinearAlgebra):
permanent2:=proc(n) local i,j,r,f,A;
f:=(i,j)->piecewise(i=1 and j mod 2=0,-1,j-i=-1,1,i=1 and j-1 mod 2=0,1,
i>1 and j-i=0,2,0);
A:=Matrix(n,n,f):
for r from 0 to n-2 do
  print(r,A):
  for j from 2 to n-r do
    A[1,j]:=A[2,1]*A[1,j]+A[1,1]*A[2,j]:
    od:
  A:=DeleteRow(DeleteColumn(Matrix(n-r,n-r,A),1),2):
  od:
print(r,eval(A)):
end proc:with(LinearAlgebra):

It can be called with the syntax, for example,

                           permanent2(8);

References

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

[2] T. Koshy, Fibonacci and Lucas Numbers with Applications, Wiley-Interscience, New York, 2001.

[3] T. Koshy, Fibonacci, Lucas, and Pell numbers, and Pascal’s triangle, Math. Spectrum 43 (2011), 125–132.

[4] A. F. Horadam, Jacobsthal and Pell curves, Fibonacci Quart. 26 (1988), 79–83.

[5] D. König, Vonalrendszerek és determinások, Math. Termész. Ért. 33 (1915), 221–229.

[6] D. König, Über Graphen und ihre Anwendungen, Math. Annalen 77 (1916), 453–465.

[7] A. S. Asratian, T. M. J. Denley, and R. Häggkvist, Bipartite Graphs and their Applications, Cambridge University Press, 1998.

[8] H. Minc, Permanents, Encyclopedia of Mathematics and its Applications, Addison-Wesley, 1978.

[9] G. W. Wheland, The Theory of Resonant and its Application to Organic Chemistry, Wiley, 1953.

[10] R. A. Brualdi and P. M. Gibson, Convex polyhedra of doubly stochastic matrices I: Applications of the permanent function, J. Combin. Theory A 22 (1977), 194–230.

[11] F. Harary, Determinants, permanents and bipartite graphs, Math. Mag. 42 (1969), 146–148.

[12] M. Marcus and H. Minc, Permanents, Amer. Math. Monthly 72 (1965), 577–591.

[13] G. Y. Lee, S. G. Lee, and H. G. Shin, On the k-generalized Fibonacci matrix Q_{k}, Lin. Alg. Appl. 251 (1997), 73–88.

[14] G. Y. Lee, k-Lucas numbers and associated bipartite graphs, Lin. Alg. Appl. 320 (2000), 51–61.

[15] W. C. Shiu and Peter C. B. Lam, More on the generalized Fibonacci numbers and associated bipartite graphs, Int. Math. J. 3 (2003), 5–9.

[16] E. Kılıç and D. Tasçı, On families of bipartite graphs associated with sums of Fibonacci and Lucas numbers, Ars Combin. 89 (2008), 31–40.

[17] G. Y. Lee and S. G. Lee, A note on generalized Fibonacci numbers, Fibonacci Quart. 33 (1995), 273–278.

[18] E. Kılıç and D. Taşçı, On the permanents of some tridiagonal matrices with applications to the Fibonacci and Lucas numbers, Rocky Mt. J. Math. 37 (2007), 1953–1969.

[19] M. Akbulak and A. Öteleş, On the number of 1-factors of bipartite graphs, Math. Sci. Lett. 2 (2013), 1–7.

[20] A. Öteleş, On the number of perfect matchings for some certain types of bipartite graphs, Filomat 31 (2017), 4809–4818.

[21] K. Kaygisiz and A. Sahin, Determinants and permanents of Hessenberg matrices and generalized Lucas polynomials, Bull. Iranian Math. Soc. 39 (2013), 1065–1078.

[22] F. Yılmaz and D. Bozkurt, The adjacency matrix of one type of directed graph and the Jacobsthal numbers and their determinantal representation, J. Appl. Math. 2012 (2012), Article ID 423163.

[23] F. Yılmaz and D. Bozkurt, Some properties of Padovan sequence by matrix methods, Ars Combin. 104 (2012), 149–160.

[24] C. M. da Fonseca, T. Sogabe, and F. Yılmaz, Lower k-Hessenberg matrices and k-Fibonacci, Fibonacci-p and Pell (p, i) number, Gen. Math. Notes 31 (2015), 10–17.

[25] E. Kılıç and D. Tasçı, On families of bipartite graphs associated with sums of generalized order-k Fibonacci and Lucas numbers, Ars Combin. 94 (2008), 13–23.

[26] E. Kılıç and A. P. Stakhov, On the Fibonacci and Lucas p-numbers, their sums, families of bipartite graphs and permanents of certain matrices, Chaos Solitons Fractals 40 (2009), 10–21.

[27] P. Vasco, P. Catarino, H. Campos, A. P. Aires, and A. Borges, k-Pell, k-Pell-Lucas and modified k-Pell numbers: Some identities and norms of Hankel matrices, Int. J. Math. Anal. 9 (2015), 31–37.

2010 Mathematics Subject Classification: Primary 05C50; Secondary 15A15, 11B83. Keywords: Bipartite graph, permanent, Hessenberg matrix, Jacobsthal number.

(Concerned with sequences \underline{A000045}, \underline{A000129}, and \underline{A001045}.)

Received August 1 2017; revised versions received November 6 2017; December 25 2018; February 26 2018; March 5 2018. Published in Journal of Integer Sequences, March 6 2018.

Return to Journal of Integer Sequences home page.