# The Adjacency Matrix of One Type of Directed Graph and the Jacobsthal Numbers and Their Determinantal Representation

Authors: Fatih Yılmaz; Durmuş Bozkurt
Journal: Journal of Applied Mathematics
 (2012)

---

## Abstract

Recently there is huge interest in graph theory and intensive study on computing integer powers of matrices. In this paper, we consider one type of directed graph. Then we obtain a general form of the adjacency matrices of the graph. By using the well-known property which states the(i,j)
entry of Am (A is adjacency matrix) is equal to the number of walks of length m from vertex i to vertex j, we show that elements of mth positive integer power of the adjacency matrix correspond to well-known Jacobsthal numbers. As a consequence, we give a Cassini-like formula for Jacobsthal numbers. We also give a matrix whose permanents are Jacobsthal numbers.


---

## Body

## 1. Introduction

The (n+k)th term of the linear homogeneous recurrence relation with constant coefficients is an equation of the form (1.1)an+k=c0an+c1an+1+⋯+ck-1an+k-1,
where (c0,c1,…,ck-1) are constants [1]. Some well-known number sequences are in fact a special form of this difference equation. In this paper, we consider the Jacobsthal sequence which is defined by the following recurrence relation: (1.2)Jn+2=Jn+1+2Jn,whereJ0=0,J1=1
for n≥0. The first few values of the sequence are(1.3)n123456789Jn113511214385171.Consider a graphG=(V,E), with set of vertices V(G)={1,2,…,n} and set of edges E(G)={e1,e2,…,em}. A digraph is a graph whose edges are directed. In the case of a digraph, you can think of the connections as one-way streets along which traffic can flow only in the direction indicated by the arrow. The adjacency matrix for a digraph has a definition similar to the definition of an adjacency matrix for a graph [2]. In other words,(1.4)aij={1,ifthereisadirectededgeconnectingaitoaj,0,otherwise.As it is known, graphs are visual objects. Analysis of large graphs often requires computer assistance. So it is necessary to express graphs via matrices. The difference equations of the form (1.1) can be expressed in a matrix form.In the literature, there are many special types of matrices which have great importance in many scientific work, for example, matrices of tridiagonal, pentadiagonal, and others. These types of matrices frequently appear in interpolation, numerical analysis, solution of boundary value problems, high-order harmonic spectral filtering theory, and so on. In [3–5], the authors investigate arbitrary integer powers of some type of these matrices.The permanent of a matrix is similar to the determinant but all of the signs used in the Laplace expansion of minors are positive. The permanent of ann-square matrix is defined by(1.5)perA=∑σ∈Sn∏i=1naiσ(i),where the summation extends over all permutationsσ of the symmetric group Sn [6].LetA=[aij] be an m×n matrix with row vectors r1,r2,…,rm. We call Acontractible on column (resp., row) k, if column (resp., row) k contains exactly two nonzero elements. Suppose that A is contractible on column k with aik≠0,ajk≠0, and i≠j. Then the (m-1)×(n-1) matrix Aij:k obtained from A replacing row i with ajkri+aikrj and deleting row j and column k is called the contraction ofAon columnk relative to rows i and j. If A is contractible on row k with aki≠0,akj≠0, and i≠j, then the matrix Ak:ij=[Aij:kT]T is called the contraction ofAon rowk relative to columns i and j. Every contraction used in this paper will be according to first column. We know that Acan be contracted to a matrix B if either B=A or if there exist matrices A0,A1,…,At (t≥1) such that A0=A,At=B and Ar is a contraction of Ar-1 for r=1,2,…,t-1. One can see that, if A is a nonnegative integer matrix of order n>1 and B is a contraction of A [7], then (1.6)perA=perB.In [7], the authors consider relationships between the sums of the Fibonacci and Lucas numbers and 1-factors of bipartite graphs.In [8], the authors investigate the relationships between Hessenberg matrices and the well-known number sequences Pell and Perrin.In [9], the authors investigate Jacobsthal numbers and obtain some properties for the Jacobsthal numbers. They also give Cassini-like formulas for Jacobsthal numbers as (1.7)Jn+1Jn-1-Jn2=(-1)n2n-1.In [10], the authors investigate incomplete Jacobsthal and Jacobsthal-Lucas numbers.In [11], the authors consider the number of independent sets in graphs with two elementary cycles. They described the extremal values of the number of independent sets using Fibonacci and Lucas numbers.In [1], the authors give a generalization for known sequences and then they give the graph representations of the sequences. They generalize Fibonacci, Lucas, Pell, and Tribonacci numbers and they show that the sequences are equal to the total number of k-independent sets of special graphs.In [12], the author present a combinatorial proof that the wheel Wn has L2n-2 spanning trees, and Ln is the nth Lucas number and that the number of spanning trees of a related graph is a Fibonacci number.In [13], the authors consider certain generalizations of the well-known Fibonacci and Lucas numbers, the generalized Fibonacci, and Lucas p-numbers. Then they give relationships between the generalized Fibonacci p-numbers Fp(n), and their sums, ∑i=1nFp(i), and the 1-factors of a class of bipartite graphs. Further they determine certain matrices whose permanents generate the Lucas p-numbers and their sums.In this paper, we consider the adjacency matrices of one type of disconnected directed graph family given with Figure1.Figure 1Then we investigate relationships between the adjacency matrices and the Jacobsthal numbers. We also give one type of tridiagonal matrix whose permanents are Jacobsthal numbers. Then we give a Maple 13 procedure to verify the result easily.


## 2. The Adjacency Matrix of a Graph and the Jacobsthal Numbers

In this section, we investigate relationships between the adjacency matrixA of the graph given by the Figure 1 and the Jacobsthal numbers. Then we give a Cassini-like formula for Jacobsthal numbers.The(i,j)th entry of Ar is just the number of walks of length r from vertex i to vertex j. In other words, the number of walks of length r from vertex i to vertex j corresponds to Jacobsthal numbers [14]. One can observe that all integer powers of A are specified to the famous Jacobsthal numbers with positive signs.Theorem 2.1.
LetA=[aij] be the adjacency matrix of the graph given in Figure 1 with  n vertices. That is,
(2.1)A=[aij]={2,am,m+1,1,as+1,s,1,a2+p,3+p,0,otherwise,
where m=1,3,5,…,n-1, p=0,4,8,…,n-4, s={1,2,3,…,n}-{4,8,…,4k}, and k=1,2,…,n/4. Then,
(2.2)Ar={a1+p,1+pr=a4+p,4+pr=112(2(-2)r+2r+1+22(-1)r+4),a2+p,1+pr=a4+p,3+pr=112[-2(-2)r+2r+1+2(-1)r+1+2],a3+p,1+pr=a4+p,2+pr=112[2(-2)r+2r+1+2(-1)r+1-2],a4+p,1+pr=112[-(-2)r+2r+2(-1)r-2],a1+p,2+pr=a3+p,4+pr=112[-4(-2)r+2r+2-4(-1)r+4],a2+p,2+pr=a3+p,3+pr=112[4(-2)r+2r+2-2(-1)r+1+2],a2+p,3+pr=a3+p,2+pr=112[-4(-2)r+2r+2-2(-1)r+1-2],a1+p,3+pr=a2+p,4+pr=112[4(-2)r+2r+2-4(-1)r-4],a1+p,4+pr=112[-4(-2)r+2r+2+8(-1)r-8],0,otherwise.Proof.
It is known that therth (r∈ℕ) power of a matrix A is computed by using the known expression Ar=TJrT-1 [15], where J is the Jordan form of the matrix and T is the transforming matrix. The matrices J and T are obtained using eigenvalues and eigenvectors of the matrix A.
The eigenvalues ofA are the roots of the characteristic equation defined by |A-λI|=0, where I is the identity matrix of nth order.
LetPn(x) be the characteristic polynomial of the matrix A which is defined in (2.1). Then we can write
(2.3)P4(x)=x4-5x2+4P8(x)=x8-10x6+33x4-40x2+16P12(x)=x12-15x10+87x8-245x6+348x4-240x2+64⋮
Taking (2.3) into account, we obtain
(2.4)Pn(λ)=(λ4-5λ2+4)k=[(λ-1)(λ+1)(λ-2)(λ+2)]k,
where n=4k,k=1,2,…. Using mathematical induction method, it can be seen easily. The eigenvalues of the matrix are multiple according to the order of the matrix. Then Jordan's form of the matrix A is
(2.5)J=Jk=diag⁡[-2,…,-2,︸ktimes2,…,2,︸ktimes-1,…,-1,︸ktimes1,…,1︸ktimes].
Let us consider the relationJ=T-1AT (AT=TJ); here A is nth-order matrix (2.1), J is the Jordan form of the matrix A and T is the transforming matrix. We will find the transforming matrix T. Let us denote the jth column of T by Tj. Then T=(T1,T2,…,Tn) and
(2.6)(AT1,…,ATn)=(T1λ1,…,Tkλ1,Tk+1λ2,…,T2kλ2,…,T3k+1λ4,…,T4kλ4).
In other words,
(2.7)AT1=T1λ1AT2=T2λ1⋮ATk=Tkλ1ATk+1=Tk+1λ2ATk+2=Tk+2λ2⋮AT2k=T2kλ2AT2k+1=T2k+1λ3AT2k+2=T2k+2λ3⋮AT3k=T3kλ3AT3k+1=T3k+1λ3AT3k+2=T3k+2λ3⋮AT4k=T4kλ4.
Solving the set of equations system, we obtain eigenvectors of the matrix A:
(2.8)T=(-20⋯00⋯020⋯0220⋯020⋯00⋯020⋯0-1-10⋯0-20⋯00⋯020⋯0-110⋯010⋯00⋯010⋯0110⋯00-2⋯00⋯200⋯2002⋯002⋯00⋯200⋯-100-1⋯00-2⋯00⋯200⋯-1001⋯001⋯00⋯100⋯1001⋯0⋮⋮⋱⋮⋮⋰⋮⋮⋮⋰⋮⋮⋮⋮⋱⋮00⋯-22⋯002⋯0000⋯200⋯22⋯00-1⋯0000⋯-100⋯-22⋯00-1⋯0000⋯100⋯11⋯001⋯0000⋯1)n×n.︸ktimes︸ktimes︸ktimes︸ktimes
We will find inverse matrix T-1 denoting the ith row of the inverse matrix T-1 by T-1=(t1,t2,…,tn) and implementing the necessary transformations, we obtain
(2.9)T-1=112(-12-220000⋯000000000000-12-22⋯00000000⋮⋮⋮⋮⋮⋮⋮⋮⋱⋮⋮⋮⋮⋮⋮⋮⋮00000000⋯-12-22000000000000⋯0000-12-2200000000⋯0000122200000000⋯12220000⋮⋮⋮⋮⋮⋮⋮⋮⋰⋮⋮⋮⋮⋮⋮⋮⋮00001222⋯0000000012220000⋯0000000000000000⋯00002-2-2400000000⋯2-2-240000⋮⋮⋮⋮⋮⋮⋮⋰⋮⋮⋮⋮⋮⋮⋮00002-2-24⋯000000002-2-240000⋯00000000-2-2240000⋯000000000000-2-224⋯00000000⋮⋮⋮⋮⋮⋮⋮⋱⋮⋮⋮⋮⋮⋮⋮⋮00000000⋯-2-224000000000000⋯0000-2-224).
Using the derived equalities and matrix multiplication,
(2.10)A=TJT-1⟹Ar=TJrT-1=[ai,jr].
We obtain the expression for the rth power of the matrix A as in (2.2), that is,
(2.11)Ar={ai+1,ir=Jrai,i+1r=2Jra1+p,4+pr=4Jr-1a2+p,3+pr=a3+p,2+pr=Jr+1a4+p,1+pr=Jr-10,otherwiseifrisoddAr={a1+4(k-1),1+4(k-1)r=a4k,4kr=2Jr-1a2+p,2+pr=a3+p,3+pr=Jr+1a1+p,3+pr=a2+p,4+pr=2Jra3+p,1+pr=a4+p,2+pr=Jr0,otherwiseifriseven,
where i=1,3,5,…,n-1,p=0,4,8,…,4(k-1),and k=1,2,…,n/4.See AppendixB.Let us consider the matrixA for n=4 as below: (2.12)A=[0200101001020010].
One can see that(2.13)Al=[02Jl04Jl-1Jl0Jl+100Jl+102JlJl-10Jl0],At=[2Jt-102Jt00Jt+102JtJt0Jt+100Jt02Jt-1],wherel is positive odd integer and t is a positive even integer. Then we will give the following corollary without proof.Corollary 2.2.
LetA be a matrix as in (2.12). Then,
(2.14)det⁡Ar=(det⁡A)r=(Jr2-Jr-1Jr+1)2=4r-1.
We call this property as Cassini-like formula for Jacobsthal numbers. This formula also is equal to square of the formula given by (1.7).


## 3. Determinantal Representations of the Jacobsthal Numbers

LetHn=[hij]n×n be n-square matrix, in which the main diagonal entries are 1s, except the second and last one which are −1 and 3, respectively. The superdiagonal entries are 2s, the subdiagonal entries are 1s and otherwise 0. In other words,(3.1)Hn=[121-120112⋱⋱⋱112011213].Theorem 3.1.
LetHn be an  n-square matrix  (n>2) as in (3.1), then
(3.2)perHn=perHn(n-2)=Jn+1,
where Jn is the nth Jacobsthal number.Proof.
By definition of the matrixHn, it can be contracted on column 1. Let Hn(r) be the rth contraction of Hn. If r=1, then
(3.3)Hn(1)=[120112112⋱⋱⋱112013].
Since Hn(1) also can be contracted according to the first column,
(3.4)Hn(2)=[320112112⋱⋱⋱112013].
Going with this process, we have
(3.5)Hn(3)=[560112112⋱⋱⋱112013].
Continuing this method, we obtain the rth contraction
(3.6)Hn(r)=[Jr+12Jr0112112⋱⋱⋱112013],
where 2≤r≤n-4. Hence
(3.7)Hn(n-3)=[Jn-22Jn-30112013]
which, by contraction of Hn(n-3) on column 1, becomesHn(n-2)=[Jn-12Jn-213].By (1.6), we have perHn=perHn(n-2)=Jn+1.See AppendixA.


## 4. Examples

We can find the arbitrary positive integer powers of the matrixA, taking into account derived expressions.Fork=2, the arbitrary positive integer power of A is(4.1)Ar={a11r=a44r=a55r=a88r=112(2(-2)r+2r+1+22(-1)r+4),a21r=a43r=a65r=a87r=112[-2(-2)r+2r+1+2(-1)r+1+2],a31r=a42r=a75r=a86r=112[2(-2)r+2r+1+2(-1)r+1-2],a41r=a85r=112[-(-2)r+2r+2(-1)r-2],a12r=a34r=a56r=a78r=112[-4(-2)r+2r+2-4(-1)r+4],a22r=a33r=a66r=a77r=112[4(-2)r+2r+2-2(-1)r+1+2],a23r=a32r=a67r=a76r=112[-4(-2)r+2r+2-2(-1)r+1-2],a13r=a24r=a57r=a68r=112[4(-2)r+2r+2-4(-1)r-4],a14r=a58r=112[-4(-2)r+2r+2+8(-1)r-8],0,otherwise.
For r=4,(4.2)A4={a114=a444=a554=a884=112(2(-2)4+25+22(-1)4+4)=6,a214=a434=a654=a874=112[-2(-2)4+25+2(-1)5+2]=0,a314=a424=a754=a864=112[2(-2)4+25+2(-1)5-2]=5,a414=a854=112[-(-2)4+24+2(-1)4-2]=0,a124=a344=a564=a784=112[-4(-2)4+26-4(-1)4+4]=0,a224=a334=a664=a774=112[4(-2)4+26-2(-1)5+2]=11,a234=a324=a674=a764=112[-4(-2)4+26-2(-1)5-2]=0,a134=a244=a574=a684=112[4(-2)4+26-4(-1)4-4]=10,a144=a584=112[-4(-2)4+26+8(-1)4-8]=0,0,otherwise.
In other words,(4.3)A4=[601000000011010000050110000005060000000060100000001101000005011000000506].
For r=5,(4.4)A5={a115=a445=a555=a885=112(2(-2)5+26+22(-1)5+4)=0,a215=a435=a655=a875=112[-2(-2)5+26+2(-1)6+2]=11,a315=a425=a755=a865=112[2(-2)5+26+2(-1)6-2]=0,a415=a855=112[-(-2)5+25+2(-1)5-2]=5,a125=a345=a565=a785=112[-4(-2)5+27-4(-1)5+4]=22,a225=a335=a665=a775=112[4(-2)5+27-2(-1)6+2]=0,a235=a325=a675=a765=112[-4(-2)5+27-2(-1)6-2]=21,a135=a245=a575=a685=112[4(-2)5+27-4(-1)5-4]=0,a145=a585=112[-4(-2)5+27+8(-1)5-8]=20,0,otherwise.
That is,(4.5)A5=[022020000011021000000210220000501100000000002202000001102100000021022000050110].


## 5. Conclusion

The basic idea of the present paper is to draw attention to find out relationships between graph theory, number theory, and linear algebra. In this content, we consider the adjacency matrices of one type of graph. Then we compute arbitrary positive integer powers of the matrix which are specified to the Jacobsthal numbers.



---

*Source: 423163-2012-06-26.xml*