# Permanents of Hexagonal and Armchair Chains

Authors: O. Nekooei; H. Barzegar; A. R. Ashrafi
Journal: International Journal of Mathematics and Mathematical Sciences
 (2022)

---

## Abstract

The permanent is important invariants of a graph with some applications in physics. IfG is a graph with adjacency matrix A=aij, then the permanent of A is defined as permA=∑σ∈Sn∏i=1naiσi, where Sn denotes the symmetric group on n symbols. In this paper, the general form of the adjacency matrices of hexagonal and armchair chains will be computed. As a consequence of our work, it is proved that if Gk and Hk denote the hexagonal and armchair chains, respectively, then permAG1=4, permAGk=k+12, k≥2, and permAHk=4k with k≥1. One question about the permanent of a hexagonal zig-zag chain is also presented.


---

## Body

## 1. Introduction

Throughout this paper, all graphs are simple and finite. SupposeX is such a graph and VX=u1,u2,…,un is the set of all vertices of X. Two vertices of X are assumed to be adjacent, if there is an edge connecting them. Define a zero-one matrix A=AG=aij in such a way that aij=1 if and only if there is an edge connecting vi and vj. The adjacency matrix is a very important tool for introducing a graph to a computer. It records all information regarding the graph under consideration. We refer to the famous book of Biggs [1] for important properties of this matrix.A perfect matching of a simple graphX is a subset L⊆EX such that end vertices of all edges in L are different, and they coincide with the vertex set of X [2].SupposeG is a graph with an adjacency matrix A=aij. The permanent of A is defined as permA=∑σ∈Sn∏i=1naiσi, where Sn denotes the symmetric group on n symbols. In a recent interesting paper, Bohra and Reddy [3] computed the number of matrices M for which permM≡xmodn, where x is a given integer. By permanent of a graph, we consider the permanent of its adjacency matrix.A 2-connected graph is a connected graph with this property that at least two vertices must be removed to make it disconnected. Following Xu and Zhang [4], a hexagonal chain is a connected plane graph with no cut vertices in which every interior region is bounded by a regular hexagon such that two hexagons are either disjoint or have exactly one common edge, no three hexagons share a common vertex, and each hexagon is adjacent to two other hexagons, with the exception of exactly two terminal hexagons to which a single hexagon is an adjacent. For more information about hexagonal systems and its applications in chemistry, we refer interested readers to consult the famous book of Cyvin and Gutman [5].In this paper, we consider the hexagonal chainGk, Figure 1, the armchair chain Hk, Figure 2, and a zig-zag hexagonal chain I2k+1, Figure 3, where Gk and Hk have exactly k hexagons and the zig-zag hexagonal chain I2k+1 has exactly 2k+1 hexagons. The adjacency matrices and permanents of Gk and Hk are computed, but we obtained a recurrence relation of order 2 for the zig-zag hexagonal chain I2k+1 which is not solvable. We refer our interested readers to consult the paper [6] for more information about hexagonal chains.Figure 1
The hexagonal chainGk.Figure 2
The armchair chainHk.Figure 3
The zig-zag hexagonal chainI2k+1.Our notations here are standard, and the readers can consult the famous book of Biggs [1] for more information on this topic. We refer the interested readers to study [7, 8] for counting perfect matchings of hexagonal systems.


## 2. Adjacency Matrix and Permanent ofGk

It is easy to see thatGk has exactly n=6+4k−1 vertices. Suppose AGk=aij is the adjacency matrix of the graph Gk. In our labeling of Gk, the vertex i is adjacent with the vertex i+1, 1≤i≤n−1, and the vertex 1 is adjacent to the vertex n. Moreover, the vertices i and j such that i+j=n+1 will be adjacent. In a simple form, the vertices i and j are adjacent if and only if i−j=1 or i+j=n+1. Note that by adding one hexagon to Gk, the number of vertices will be increased by 4. The form of the adjacency matrix of Gk is as follows:(1)AGk=01000.0000110100.0000001010.0010000101.0000000010.10000...........00001.0100000000.1010000100.0101000000.0010110000.00010.To compute the permanent of this matrix, we need to calculate the permanent of two matricesEn×n, n≥3, and Fn×n, n≥5. In both of these matrices, n is assumed to be an odd number. In the matrix En×n, the entries in the positions i,i for 1≤i≤n, i+1,i for 1≤i≤n−1, and i,n+1−i for 1≤i≤n+1/2 are equal to one, and other entries are 0. In the matrix Fn×n, the entries in the positions i,i for 1≤i≤n, i,i+1 for 1≤i≤n−1, and n+1−i,i for n+1/2≤i≤n are equal to one, and other entries are 0. These matrices have the following forms:(2)En×n=100…01110…1001…100⋮00…110000…11,Fn×n=110…00011…0000…100⋮010…011100…01.Lemma 1.
permEn×n=n+1/2, n is odd.Proof.
We proceed by induction onn with step 2. If n=3, then a simple calculation shows that permE3×3=2. By our inductive assumption, permEn−2×n−2=n−1/2, whenn≥5. We now expand the matrix En×n through the first row to obtain two matrices A and B as follows:(3)A=10…1011…100⋮0…11000…11,B=110…101…10⋮00…11000…1.
Sincen is odd, permEn×n=permA+permB. The matrix B is unitriangular, and so its permanent is 1. We now expand the matrix A through the last column to obtain another matrix A′ with the same permanent. Therefore, A′=En−2×n−2, and by inductive assumption, permEn×n=n−1/2+1=n+1/2, proving the lemma.Lemma 2.
permFn×n=n+1/2, n is odd.Proof.
Similar to the proof of Lemma 1, we proceed by induction with step 2. By an easy calculation,permF5×5=3. By our inductive assumption, permFn−2×n−2=n−2+1/2=n−1/2, n≥7. We now expand the matrix Fn×n through the first row to obtain two matrices C and D as follows:(4)C=11…000…100⋮10…01100…01,D=01…00011…00⋮00…01110…01.
If we expand the matrixD through its first column, we will have a triangular matrix with permanent one, and if expand the matrix C through its last row, then we will have another matrix C′ which is equal to Fn−2×n−2. Therefore, permFn×n=permC+permD=n−1/2+1=n+1/2, proving the lemma.Lemma 3.
Supposen≡2mod4 is a positive integer greater than or equal to 10. Then, permAGk=permAGk−1−n/2−4.Proof.
Expand the matrixAGk through the first row to obtain two matrices in which the first matrix is related to the second column, and another one is related to the n-th column. These matrices have the following form:(5)L=1100.000000010.001000101.000000010.10000..........0001.010000000.101000100.010100000.001011000.00010,M=10100.000001010.001000101.000000010.1000..........00001.010000000.101000100.010100000.001010000.0001.
Our main proof will consider the methods for computing the permanent ofL and M.


### 2.1. Computing the Permanent ofL

To computepermL, we expand the matrix L through its first row to construct matrices B and C as follows:(6)B=010.00100101.00000.........000.10100100.01010000.00101000.00010,C=010.00100001.00000010.10000.........000.01010000.00101100.00010.SinceB has a unique nonzero entry in the last row, we expand B through its last row to obtain a new matrix B′. The matrix B′ has a unique nonzero entry in its last column, and by expanding it through this column, the matrix AGk−1 will be obtained. For the matrix C, we first expand it through the first column and next expand the new matrix through its last column to find the matrix C′ as follows:(7)C′=10.001001.000010.1000.......01.010000.101000.0101.Note thatC′ is a matrix of size n−4×n−4, and by our assumption, it can be assumed that n=4k−2. We now prove that permC′=permE2k−1×2k−1,k≥2. To do this, we proceed by induction with step 4. We start by n=10. By our algorithm for constructing the matrix C′, it can be easily seen that(8)C′=100010010000101000010100001010000101.We now expandC′ through its second row, the new matrix through its third row, and the resulting matrix through its fourth row to construct the matrix.(9)C′′=E3×3=101110011.With permanent2=permC′. Suppose that n=4k−2. By our discussion above, C′ has the size 4k−6×4k−6. We do the following operations on C′ to construct E2k−1×2k−1,k≥2.(a)
Expand the matrixC′ through its second row to construct the matrix C2(b)
Expand the matrixC2 through its third row to construct the matrix C3⋮(c)
Expand the matrixC4k−7 through its 4k−8-th row to construct the matrix C4k−6This algorithm constructs the matrixC4k−6=E2k−1×2k−1. We now apply Lemma 1 to deduce that permC=permE2k−1×2k−1=k,k≥2.


### 2.2. Computing the Permanent ofM

In a similar argument as (1), we expand the matrix M and its resulting matrices are as follows:(a)
Expand the matrixM through its second column to construct the matrix D2(b)
Expand the matrixD2 through its third column to construct the matrix D3⋮(c)
Expand the matrixD2k−1 through its 2k−2-th column to construct the matrix D2kIt can be seen thatD2k=F2k+3×2k+3, and by Lemma 2,(10)permM=permF2k+1×2k+1=k+1,k≥2.Therefore,permAGk=permAGk−1+permL+permM=permAGk+n/2+4. This completes the proof.Theorem 1.
permAG1=4 and permAGk=k+12, where k≥2.Proof.
By a simple calculation, one can see thatpermAG1=4. By Lemma 3, permAGk=permAGk−1+2k+1, and by solving this recursive equation, permAGk=k+12, where k≥2.


## 2.1. Computing the Permanent ofL

To computepermL, we expand the matrix L through its first row to construct matrices B and C as follows:(6)B=010.00100101.00000.........000.10100100.01010000.00101000.00010,C=010.00100001.00000010.10000.........000.01010000.00101100.00010.SinceB has a unique nonzero entry in the last row, we expand B through its last row to obtain a new matrix B′. The matrix B′ has a unique nonzero entry in its last column, and by expanding it through this column, the matrix AGk−1 will be obtained. For the matrix C, we first expand it through the first column and next expand the new matrix through its last column to find the matrix C′ as follows:(7)C′=10.001001.000010.1000.......01.010000.101000.0101.Note thatC′ is a matrix of size n−4×n−4, and by our assumption, it can be assumed that n=4k−2. We now prove that permC′=permE2k−1×2k−1,k≥2. To do this, we proceed by induction with step 4. We start by n=10. By our algorithm for constructing the matrix C′, it can be easily seen that(8)C′=100010010000101000010100001010000101.We now expandC′ through its second row, the new matrix through its third row, and the resulting matrix through its fourth row to construct the matrix.(9)C′′=E3×3=101110011.With permanent2=permC′. Suppose that n=4k−2. By our discussion above, C′ has the size 4k−6×4k−6. We do the following operations on C′ to construct E2k−1×2k−1,k≥2.(a)
Expand the matrixC′ through its second row to construct the matrix C2(b)
Expand the matrixC2 through its third row to construct the matrix C3⋮(c)
Expand the matrixC4k−7 through its 4k−8-th row to construct the matrix C4k−6This algorithm constructs the matrixC4k−6=E2k−1×2k−1. We now apply Lemma 1 to deduce that permC=permE2k−1×2k−1=k,k≥2.


## 2.2. Computing the Permanent ofM

In a similar argument as (1), we expand the matrix M and its resulting matrices are as follows:(a)
Expand the matrixM through its second column to construct the matrix D2(b)
Expand the matrixD2 through its third column to construct the matrix D3⋮(c)
Expand the matrixD2k−1 through its 2k−2-th column to construct the matrix D2kIt can be seen thatD2k=F2k+3×2k+3, and by Lemma 2,(10)permM=permF2k+1×2k+1=k+1,k≥2.Therefore,permAGk=permAGk−1+permL+permM=permAGk+n/2+4. This completes the proof.Theorem 1.
permAG1=4 and permAGk=k+12, where k≥2.Proof.
By a simple calculation, one can see thatpermAG1=4. By Lemma 3, permAGk=permAGk−1+2k+1, and by solving this recursive equation, permAGk=k+12, where k≥2.


## 3. Adjacency Matrix and Permanent ofHk

The aim of this section is to calculate the adjacency matrix and permanent ofHk, Figure 2. It is easy to see that this graph has exactly n=6k vertices. The adjacency matrix of Hk is denoted by AHk=bij.We first calculate the general term of the adjacency matrix. From Figure2, one can see that bnn+1=1, 1≤i≤n−1, other than all values of i with i≠6t−3 with 1≤t≤k. Furthermore, b6t−36t=1 and b6t−56t−2=1, where 1≤t≤k. Since the adjacency matrix is symmetric, if bij=1, then bji=1. In other cases, bij=0. Therefore, the adjacency matrix of Hk is as follows:(11)AHk=0101000.000001010000.000000100010.000001000100.000000001010.000000010101.00000............0000010.101000000001.010000000000.100010000001.000100000000.001010000000.01010.Lemma 4.
SupposeAHk is the adjacency matrix of Hk with n=6k vertices. Then, permAH1=4 and permAHk=4permAHk−1, where k≥2.Proof.
Our proof is by induction onk. The case of k=1,2 are trivial, and we have permAH1=4 and permAH2=16. So, we proceed by induction and assume that k≥3 is a natural number. Suppose permAHk−1=4permAHk−2. In the first row of the matrix AHk, there are two nonzero entries which are b12 and b14. To calculate the permanent, we expand the matrix through the first row. Then, we will have two new matrices B1 and B2 such that permAHk=permB1+permB2. We first calculate permB1. Note that B1 has a unique nonzero entry on its second row and so by expanding it through this row, it is enough to calculate the permanent of this new matrix. The new matrix has a unique nonzero entry on the third row that to simplify our calculations, we expand again this new matrix through this row. The resulting matrix D is as follows:(12)D=1100.000001010.000000111.00000.........0000.101000001.010000000.100010001.000100000.001010000.01010.
If we expandD through the first row, then we will find two matrices B and C. These matrices can be written as follows:(13)B=010.00000111.00000.........000.10100001.01000000.10001001.00010000.00101000.01010,C=110.00000011.00000........000.10100001.01000000.10001001.00010000.00101000.01010.
By expandingB through its first row and expanding the new matrix through its first column, the resulting matrix will be AHk−1. On the other hand, by expanding the matrix C through its first column and expanding the new matrix through its first column, the resulting matrix will be again AHk−1. Therefore, permD=permB+permC=permAHk−1+permAHk−1.
We are now ready to calculatepermB2. The second column of B2 has a unique nonzero entry, and by expanding it through this column and then expanding this new matrix through its third row, we obtain again the matrix D. This proves that permAHk=4permAHk−1.Theorem 2.
permAHk=4k, where k≥1.Proof.
Induct onk.


## 4. Concluding Remarks

In this paper, the adjacency matrices and permanents of a hexagonal and armchair chain were computed. At the end of this section, a zig-zag hexagonal chainI2k+1, k≥1, with exact 2k+1 hexagons and n=8k+6 vertices, is investigated.To calculate the form of the adjacency matrixAI2k+1=cij, we will determine all unit entries cij such that i≤j, and then, all entries will be calculated based on the condition that cij=cji. Suppose that t=n/8+1. By the labeling of this graph given in Figure 3, one can see that cii+1=1, where 1≤i≤n−1. Furthermore, c1n=1. It is also clear from our figure that c4in−4i−3=1, i=1,2,…,t−1. The final set of our unit entries is corresponding to the pairs 4i−3,n−4i−4, where i=2,3,…,t. Based on these calculations, the form of the adjacency matrix of I2k+1 is as follows:(14)AI2k+1=01000000.0000110100000.0000001010000.0000000101000.0001000010100.1000000001010.0000000000101.0000000000010.00000..............00001000.0100000000000.1010000000000.0101000010000.0010110000000.00010.Our calculations with Mathematica [9] and some arguments as Theorems 1 and 2 suggest the following conjecture:Conjecture 1.permAI2k+1=3permAI2k−1−permAI2k−32, where n≥22.Moreover, by our calculations with Mathematica on adjacency matrices of small dimensions, we calculate thatpermAI3=25, permAI5=169, permAI7=1156, permAI9=7921, permAI11=54289, and permAI13=372100. We could not solve the equation of Conjecture 1, but it is possible to apply some techniques in numerical analysis to obtain approximately the permanent. We end this section with the following question:Question 1. What is the exact value of perm (A(I [2k + 1])).



---

*Source: 7786922-2022-11-25.xml*