Determinantal properties of Boolean graphs using recursive approach

Abstract

The aim of this paper is to study the determinant and inverse of the adjacency matrices of weighted and directed versions of Boolean graphs. Our approach is recursive. We describe the adjacency matrix of a weighted Boolean graph in terms of the adjacency matrix of a smaller-sized weighted Boolean graph. This allows us to compute the determinant and inverse of the adjacency matrix of a weighted Boolean graph recursively. In particular, we show that the determinant of a directed Boolean graph is 1. Further, using a classical theorem of Cayley which expresses the determinant of any skew-symmetric matrix as a square of its Pfaffian, we show that for any directed Boolean graph, the characteristic polynomial has all its even degree coefficients strictly positive with the odd ones being zero.

Keywords:

• Adjacency matrix
• zero-divisor graph
• Boolean graph
• directed graph
• weighted graph

2020 MATHEMATICS SUBJECT CLASSIFICATION:

• Primary: 05C50
• Secondary: 05B20

1 Introduction

For a commutative ring R with $1\ne 0,$ the zero-divisor graph of R is denoted by $\Gamma (R).$ It is a graph with vertex set the set of all nonzero zero-divisors of R. Two vertices $x$ and y are adjacent in $\Gamma (R)$ if xy = 0 in R. For the field ${\mathbb{Z}}_2=\{0,1\}$ and an integer n > 1, let ${\mathbb{Z}}_2^n$ denote the Boolean ring ${\mathbb{Z}}_2\times {\mathbb{Z}}_2\times \cdots \times {\mathbb{Z}}_2$ (n terms). The zero-divisor graph $\Gamma ({\mathbb{Z}}_2^n)$ of the ring ${\mathbb{Z}}_2^n$ is known as Boolean graph. This graph can also be alternatively defined as the simple graph with vertices as the non-empty proper subsets of a fixed set with n elements where two vertices are adjacent if the corresponding subsets have the empty intersection. The aim of this paper is to study the determinant and inverse of weighted and directed versions of Boolean graphs and to prove the positivity of the even degree coefficients of the characteristic polynomial of the directed Boolean graph.

There has been an extensive study of the zero-divisor graphs associated to commutative rings (see [1, 2]). However, one finds a very few papers devoted to the understanding of the determinantal and spectral properties of the zero-divisor graphs and the rich interplay that this theory has to offer. A systematic study of such properties of the Boolean graph $\Gamma ({\mathbb{Z}}_2^n)$ is carried out by LaGrange in a series of papers [4–7]. For instance, he proved that the Boolean graphs, among the zero-divisor graphs, can be characterized as those having their adjacency matrices with determinant equal to –1 (see [5, Theorem 2.5]). Further, he proved that the characteristic polynomial of a Boolean graph is absolutely palindromic and possesses the reciprocal eigenvalue property. For the case of finite commutative rings and principal ideal rings, we mention [8, 9]. However, the graphs dealt with within these two papers, have loops (non-simple graphs) and this brings about some simplification in the matrix theoretic considerations. From this standpoint, the case of graphs without loops (simple graphs) appears to be more involved and interesting.

One of our approaches to the study the Boolean graph $\Gamma ({\mathbb{Z}}_2^n)$ is to describe its adjacency matrix A_n recursively in terms of $A_{n-1}.$ To do this, we come up with a specific ordering of the vertices of this graph and write down the corresponding adjacency matrix A_n in terms of $A_{n-1}.$ Using this recursive description, we easily find the determinant and inverse of $A_n.$ Further, we introduce the notion of the weight matrix which generalizes the notion of the adjacency matrix of weighted and directed graphs. We show in Theorem 3.4 that the determinant of the weight matrix $A(W_n)$ of the adjacency matrix A_n of the graph $\Gamma ({\mathbb{Z}}_2^n)$ is a signed product of the weights received by the edges corresponding to the complementary pairs of vertices. As a consequence, in the case of a Boolean graph, we show that the determinant is $-1,$ and that in the case of a directed Boolean graph, it is 1. We mention here that the determinant of a directed Boolean graph is independent of the choice of orientatations of edges. We further compute the inverse of the matrix $A(W_n).$ As a consequence, the inverses of the undirected Boolean and directed Boolean graphs can be obtained.

It is easy to see that the characteristic polynomial of the adjacency matrix of a directed Boolean graph is a skew-symmetric matrix. In Theorem 4.2, we show that for any directed Boolean graph the characteristic polynomial has all its even degree coefficients strictly positive with all its odd degree coefficients being zero. This is one of our main results and to prove this result, we use a classical theorem of Cayley which states that the determinant of a skew-symmetric matrix of even order is a square of its Pfaffian. We have observed that for values of n up to 8, the even degree coefficients of the characteristic polynomial form a unimodal sequence. We strongly suspect this to be true for any n and state it as an open question.

2 Boolean graphs

In this section, we give a vertex ordering of the Boolean graph and describe its adjacency matrix recursively. Algorithmic expressions of the adjacency matrix of the Boolean graph and its inverse matrix are obtained.

Let n be an integer greater than 1. Recall that ${\mathbb{Z}}_2^n={\mathbb{Z}}_2\times {\mathbb{Z}}_2\times \cdots \times {\mathbb{Z}}_2$ (n terms), where ${\mathbb{Z}}_2=\{0,1\}$ is a field. Thus, ${\mathbb{Z}}_2^n$ is a ring with respect to pointwise addition and multiplication modulo 2. The Boolean graph $\Gamma ({\mathbb{Z}}_2^n)$ has vertex set V_n as the set of non-zero zero-divisors of the ring ${\mathbb{Z}}_2^n.$ Two vertices x and y are adjacent in $\Gamma ({\mathbb{Z}}_2^n)$ if $xy=0.$ Note that $V_n={\mathbb{Z}}_2^n\setminus \{\mathbf{0},\mathbf{1}\},$ where 0 and 1 are zero element and unity in the ring ${\mathbb{Z}}_2^n.$ Hence, $\left|V_n\right|=2^n-2$. For n = 2, the graph $\Gamma ({\mathbb{Z}}_2^n)$ is isomorphic to the complete graph K₂. Every element $x\in {\mathbb{Z}}_2^n$ is of the form, $x=(x_1,x_2,x_3,\dots ,x_{n-1},x_n)$ with $x_i\in {\mathbb{Z}}_2$ $\forall i.$ Denote by $\overline{x}=(1,1,\dots ,1)-x$, the complement of x. Note that, every vertex in V_n has a unique complement in V_n and such complementary pair of vertices are always adjacent in $\Gamma ({\mathbb{Z}}_2^n)$. Denote by ${\mathbf{e}}_{\mathbf{n}},$ the element $(0,0,\dots 0,1)$ of $V_n.$ An element x of ${\mathbb{Z}}_2^n$ can be obtained from an element $x\prime$ of ${\mathbb{Z}}_2^{n-1}$ by adjoining 0 or 1 as the nth coordinate. For $x\prime =(x_1,x_2,x_3,\dots ,x_{n-1})\in {\mathbb{Z}}_2^{n-1}$ and $x_n\in {\mathbb{Z}}_2,$ we get $x=(x_1,x_2,x_3,\dots ,x_{n-1},x_n)\in {\mathbb{Z}}_2^n$ and we write $x=x\prime \diamond x_n.$

Define $$X_0=\{v\prime \diamond 0\in V_n | v\prime \in V_{n-1}\}$$and $$X_1=\{v\prime \diamond 1\in V_n | v\prime \in V_{n-1}\}.$$

Note that the vertex set V_n of the graph $\Gamma ({\mathbb{Z}}_2^n)$ has a partition into four parts as follows. $$V_n=\left\{\overline{{\mathit{e}}_{\mathit{n}}}\right\}\cup \left\{{\mathit{e}}_{\mathit{n}}\right\}\cup X_0\cup X_1.$$

Let ${\mathcal{U}}_n=\{v_1,v_2,\dots ,v_{\left|V_n\right|}\}$ be a vertex ordering of $\Gamma ({\mathbb{Z}}_2^n)$ in which the element $\overline{{\mathbf{e}}_{\mathbf{n}}}$ comes first, then comes the element ${\mathbf{e}}_{\mathbf{n}}$ and then come the elements of the parts X₀ and $X_1,$ respectively. The following lemma gives a recursive description of adjacency relations among vertices of $\Gamma ({\mathbb{Z}}_2^n)$.

Lemma 2.1.

Let $\Gamma ({\mathbb{Z}}_2^n)$ be the Boolean graph with vertex set $V_n=\left\{\overline{{\mathbf{e}}_{\mathbf{n}}}\right\}\cup \left\{{\mathbf{e}}_{\mathbf{n}}\right\}\cup X_0\cup X_1.$ Then the following recursive properties hold.

1. The vertex $\overline{{\mathbf{e}}_{\mathbf{n}}}$ is adjacent to only its complement ${\mathbf{e}}_{\mathbf{n}}$.

2. The vertex ${\mathbf{e}}_{\mathbf{n}}$ is adjacent to all vertices in $\left\{\overline{{\mathbf{e}}_{\mathbf{n}}}\right\}\cup X_0$ and no vertex of $X_1.$

3. The subgraph of $\Gamma ({\mathbb{Z}}_2^n)$ induced by X₀ is isomorphic to $\Gamma ({\mathbb{Z}}_2^{n-1})$.

4. The set of vertices X₁ is independent in $\Gamma ({\mathbb{Z}}_2^n)$.

5. A vertex $x\prime \diamond 0\in X_0$ is adjacent to a vertex $y\prime \diamond 1\in X_1$ in $\Gamma ({\mathbb{Z}}_2^n)$ if and only if $x\prime$ and $y\prime$ are adjacent in $\Gamma ({\mathbb{Z}}_2^{n-1}).$

Proof.

Proofs are easy to see.

We apply Lemma 2.1 to describe the adjacency matrix of the graph $\Gamma ({\mathbb{Z}}_2^n)$. Let A_n be the adjacency matrix of $\Gamma ({\mathbb{Z}}_2^n)$ with respect to the vertex ordering ${\mathcal{U}}_n$. Note that the matrix A_n has four block rows and four block columns obtained by the ordering of vertices given by the four parts $\left\{\overline{{\mathbf{e}}_{\mathbf{n}}}\right\}, \left\{{\mathbf{e}}_{\mathbf{n}}\right\}, X_0, X_1.$ Let $\mathbf{1}={(\begin{array}{cccc}1& 1& \cdots & 1\end{array})}^T$ and $\mathbf{0}={(\begin{array}{cccc}0& 0& \cdots & 0\end{array})}^T$ be $(2^{n-1}-2)\times 1$ matrices, and O denote the zero matrix of order $(2^{n-1}-2)\times (2^{n-1}-2)$. Sizes of the block in A_n can be obtained from the respective sizes of the parts of the partition ${\mathcal{U}}_n$.

Proposition 2.2.

Let A_n be the adjacency matrix of the graph $\Gamma ({\mathbb{Z}}_2^n)$ with respect to the vertex ordering ${\mathcal{U}}_n.$ Then $$A_n=\left(\begin{array}{cccc}0& 1& {\mathbf{0}}^T& {\mathbf{0}}^T\\ 1& 0& {\mathbf{1}}^T& {\mathbf{0}}^T\\ \mathbf{0}& \mathbf{1}& A_{n-1}& A_{n-1}\\ \mathbf{0}& \mathbf{0}& A_{n-1}& O\end{array}\right).$$

Proof.

The proof follows from the vertex ordering ${\mathcal{U}}_n$ and Lemma 2.1.

Remark 2.3.

An advantage of Proposition 2.2 is that it gives an easy algorithm to obtain the exponential-sized adjacency matrix A_n. The computation of A_n by using Proposition 2.2 has less complexity than the computation of A_n by the direct definition. As an illustration, the matrices A₂, A₃, and A₄ obtained using Proposition 2.2 are described as follows. Note that A_n is the matrix of order $2^n-2$ with vertex ordering ${\mathcal{U}}_n$. $$A_2=\left(\begin{array}{cc}0& 1\\ 1& 0\end{array}\right), A_3=\left(\begin{array}{cc}\begin{array}{cc}0& 1\\ 1& 0\end{array}& \begin{array}{cccc}0& 0& 0& 0\\ 1& 1& 0& 0\end{array}\\ \begin{array}{cc}0& 1\\ 0& 1\\ 0& 0\\ 0& 0\end{array}& \begin{array}{cccc}0& 1& 0& 1\\ 1& 0& 1& 0\\ 0& 1& 0& 0\\ 1& 0& 0& 0\end{array}\end{array}\right),$$ $$A_4=\left(\begin{array}{ccc}\begin{array}{cc}0& 1\\ 1& 0\end{array}& \begin{array}{ccc}0& \dots & 0\\ 1& \dots & 1\end{array}& \begin{array}{ccc}0& \dots & 0\\ 0& \dots & 0\end{array}\\ \begin{array}{cc}0& 1\\ ⋮& ⋮\\ 0& 1\end{array}& A_3& A_3\\ \begin{array}{cc}0& 0\\ ⋮& ⋮\\ 0& 0\end{array}& A_3& O\end{array}\right).$$

In [5], it is proved that A_n is invertible and its inverse is computed by composing certain matrices. We now determine $A_n^{-1}$ recursively in the following theorem. Denote by $A\otimes B$ the tensor product of the matrices A and B. Let $\mathbf{1}={(\begin{array}{cccc}1& 1& \cdots & 1\end{array})}^T$ and $\mathbf{0}={(\begin{array}{cccc}0& 0& \cdots & 0\end{array})}^T$ be $(2^{n-1}-2)\times 1$ matrices.

Theorem 2.4.

For the adjacency matrix A_n of $\Gamma ({\mathbb{Z}}_2^n),$ $$A_n^{-1}=\left(\begin{array}{cccc}0& 1& {\mathbf{0}}^T& -{\mathbf{1}}^T{A}_{n-1}^{-1}\\ 1& 0& {\mathbf{0}}^T& {\mathbf{0}}^T\\ \mathbf{0}& \mathbf{0}& O& A_{n-1}^{-1}\\ -A_{n-1}^{-1}\mathbf{1}& \mathbf{0}& A_{n-1}^{-1}& -A_{n-1}^{-1}\end{array}\right)$$

Proof.

Consider A_n with respect to the vertex ordering ${\mathcal{U}}_n.$ It has order $N=2^n-2.$ By Proposition 2.2, $$\left(\begin{array}{cc}\begin{array}{cc}0& 1\\ 1& 0\end{array}& \begin{array}{cc}{\mathbf{0}}^T& {\mathbf{0}}^T\\ {\mathbf{1}}^T& {\mathbf{0}}^T\end{array}\\ \begin{array}{cc}\mathbf{0}& \mathbf{1}\\ \mathbf{0}& \mathbf{0}\end{array}& \begin{array}{cc}{A}_{n-1}& A_{n-1}\\ A_{n-1}& O\end{array}\end{array}\right)=I_{N\times N}·A_n·I_{N\times N}.$$

By performing Row $(i)-$ Row(1) and then Column $(i)-$ Column(1) for $3\le i\le 2^{n-1}$ we get, $$\begin{array}{c}\left(\begin{array}{cc}\begin{array}{cc}0& 1\\ 1& 0\end{array}& \begin{array}{cc}{\mathbf{0}}^T& {\mathbf{0}}^T\\ {\mathbf{0}}^T& {\mathbf{0}}^T\end{array}\\ \begin{array}{cc}\mathbf{0}& \mathbf{0}\\ \mathbf{0}& \mathbf{0}\end{array}& \begin{array}{cc}{A}_{n-1}& A_{n-1}\\ A_{n-1}& O\end{array}\end{array}\right)=\left(\begin{array}{cc}\begin{array}{cc}1& 0\\ 0& 1\end{array}& \begin{array}{cc}{\mathbf{0}}^T& {\mathbf{0}}^T\\ {\mathbf{0}}^T& {\mathbf{0}}^T\end{array}\\ \begin{array}{cc}-\mathbf{1}& \mathbf{0}\\ \mathbf{0}& \mathbf{0}\end{array}& \begin{array}{cc}I& O\\ O& I\end{array}\end{array}\right)\\ ·A_n·\left(\begin{array}{cc}\begin{array}{cc}1& 0\\ 0& 1\end{array}& \begin{array}{cc}-{\mathbf{1}}^T& {\mathbf{0}}^T\\ {\mathbf{0}}^T& {\mathbf{0}}^T\end{array}\\ \begin{array}{cc}\mathbf{0}& \mathbf{0}\\ \mathbf{0}& \mathbf{0}\end{array}& \begin{array}{cc}I& O\\ O& I\end{array}\end{array}\right).\end{array}$$

That is, $$\left(\begin{array}{cc}{A}_2& O\\ O& F_2\otimes A_{n-1}\end{array}\right)=M_1·A_n·M_1^T,$$where $F_2=(\begin{array}{cc}1& 1\\ 1& 0\end{array}), M_1=(\begin{array}{cc}\begin{array}{cc}1& 0\\ 0& 1\end{array}& \begin{array}{cc}{\mathbf{0}}^T& {\mathbf{0}}^T\\ {\mathbf{0}}^T& {\mathbf{0}}^T\end{array}\\ \begin{array}{cc}-\mathbf{1}& \mathbf{0}\\ \mathbf{0}& \mathbf{0}\end{array}& \begin{array}{cc}I& O\\ O& I\end{array}\end{array}).$

Inverting both sides we get, $$M_1^T{}^{-1}·A_n^{-1}·M_1^{-1}=\left(\begin{array}{cc}{A}_2^{-1}& O\\ O& F_2^{-1}\otimes A_{n-1}^{-1}\end{array}\right).$$

Pre-multiplying by $M_1^T$ and post-multiplying by M₁ gives, $$\begin{array}{c}{A}_n^{-1}=M_1^T·\left(\begin{array}{cc}{A}_2^{-1}& O\\ O& F_2^{-1}\otimes A_{n-1}^{-1}\end{array}\right)·M_1\\ =\left(\begin{array}{cccc}0& 1& {\mathbf{0}}^T& -{\mathbf{1}}^T{A}_{n-1}^{-1}\\ 1& 0& {\mathbf{0}}^T& {\mathbf{0}}^T\\ \mathbf{0}& \mathbf{0}& O& A_{n-1}^{-1}\\ -A_{n-1}^{-1}\mathbf{1}& \mathbf{0}& A_{n-1}^{-1}& -A_{n-1}^{-1}\end{array}\right).\end{array}$$

Remark 2.5.

In general, determining the inverse of the adjacency matrix A_n requires many computations. The advantage of Theorem 2.4 is that it provides an algorithmic construction of the inverse of A_n and thus reduces the computations significantly. Simplicity of the computation of $A_n^{-1}$ is illustrated below for n = 2, 3, and 4. $$\begin{array}{c}{A}_2^{-1}=\left(\begin{array}{cc}0& 1\\ 1& 0\end{array}\right), A_3^{-1}=\left(\begin{array}{cccccc}0& 1& 0& 0& -1& -1\\ 1& 0& 0& 0& 0& 0\\ 0& 0& 0& 0& 0& 1\\ 0& 0& 0& 0& 1& 0\\ -1& 0& 0& 1& 0& -1\\ -1& 0& 1& 0& -1& 0\end{array}\right),\\ A_4^{-1}=\left(\begin{array}{cccc}0& 1& {\mathbf{0}}^T& -{\mathbf{1}}^T{A}_3^{-1}\\ 1& 0& {\mathbf{0}}^T& {\mathbf{0}}^T\\ \mathbf{0}& \mathbf{0}& O& A_3^{-1}\\ -A_3^{-1}\mathbf{1}& \mathbf{0}& A_3^{-1}& -A_3^{-1}\end{array}\right).\end{array}$$

3 Weighted Boolean graphs

The aim of this section is to study the weighted Boolean graphs using the recursive approach. We associate a weight matrix $W(A_n)$ to the adjacency matrix A_n of the usual Boolean graph. This is with the view of treating the weighted adjacency matrix and the directed adjacency matrix of graphs as special cases of the weight matrix. Using the recursive approach, we obtain the determinant of $W(A_n)$ and as a consequence prove that the determinant of the Boolean graph is –1 which is a known result, see [5]. Also, it follows that the determinant of any directed Boolean graph is 1. This shows, in particular, that the determinant is independent of the choice of orientations on the edges of a directed Boolean graph. Further, we obtain the inverse of the matrix $W(A_n)$ recursively.

Definition 3.1.

For a given m × m matrix A with entries from {0, 1} and for $1\le i,j\le m$, let $w_{i,j}$ be nonzero real numbers. Define weight matrix W(A) of A of order m × m such that, $$W(A)(i,j)=\{\begin{array}{cc}0,\hfill & \text{ if }A(i,j)=0;\hfill \\ w_{i,j},\hfill & \text{ if }A(i,j)=1.\hfill \end{array}$$

The matrix A can be termed as the support matrix of $W(A).$ Note that W(A) need not be symmetric or skew-symmetric.

Definition 3.2.

The adjacency matrix of a weighted graph G_w is the matrix A_w such that $$A_w(i,j)=\{\begin{array}{cc}{w}_{i,j},\hfill & \text{ if }{w}_{ij}\text{ is the weight assigned to the edge}\hfill \\ \hfill & \mathrm{\hspace{1em}}\mathrm{\hspace{1em}}(v_i,v_j)\text{ in }{G}_w;\hfill \\ 0,\hfill & \text{otherwise. }\hfill \end{array}$$

Definition 3.3.

Let $\overrightarrow{G}$ be a directed graph obtained from a simple graph G by orienting its edges. Then the adjacency matrix of $\overrightarrow{G}$ is the matrix $\overrightarrow{A}$ such that $$\overrightarrow{A}(i,j)=\{\begin{array}{cc}1,& \text{ if }\overrightarrow{G}\text{has directed edge from }i\text{th vertex to}\\ & \mathrm{\hspace{1em}}\mathrm{\hspace{1em}}j\text{th vertex};\\ -1,& \text{ if }\overrightarrow{G}\text{ has directed edge from}\\ & \mathrm{\hspace{1em}}\mathrm{\hspace{1em}}j\text{ th vertex to }i\text{th vertex; }\\ 0,& \text{otherwise}.\end{array}$$

For the Boolean graph $\Gamma ({\mathbb{Z}}_2^n),$ the adjacency matrix A_n and its weighted variants ${(A_n)}_w$ and ${\overrightarrow{A}}_n$ are special cases of the weight matrix $W(A_n)$.

Recall that ${\mathcal{U}}_n=\{v_1,v_2,\dots ,v_{\left|V_n\right|}\}$ is a vertex ordering of $\Gamma ({\mathbb{Z}}_2^n)$ wherein the element $\overline{{\mathbf{e}}_{\mathbf{n}}}$ comes first, then comes the element ${\mathbf{e}}_{\mathbf{n}}$ and then the elements of X₀ and X₁, respectively. In the following theorem, we obtain the determinant of $W(A_n)$ and show that it is negative of the product of the entries corresponding to complementary pairs of vertices.

Theorem 3.4.

Let A_n be the adjacency matrix of the graph $\Gamma ({\mathbb{Z}}_2^n)$ and let $W(A_n)$ be any weight matrix of A_n. Then $W(A_n)$ is a nonsingular matrix with determinant $$\det W(A_n)=-\prod _{v_i=\overline{v_j}}{w}_{i,j}.$$

Proof.

Consider the matrix A_n as in Proposition 2.2 with the vertex ordering ${\mathcal{U}}_n$. As ${\mathcal{U}}_n$ has the partition $\left\{\overline{{\mathbf{e}}_{\mathbf{n}}}\right\}\cup \left\{{\mathbf{e}}_{\mathbf{n}}\right\}\cup X_0\cup X_1,$ any weight matrix $W(A_n)$ of A_n has the following form with four block-rows and four block-columns corresponding to this partition. $$W(A_n)=\left(\begin{array}{cccc}0& w_{1,2}& {\mathbf{0}}^T& {\mathbf{0}}^T\\ w_{2,1}& 0& M_1& {\mathbf{0}}^T\\ \mathbf{0}& M_2& W_1(A_{n-1})& W_2(A_{n-1})\\ \mathbf{0}& \mathbf{0}& W_3(A_{n-1})& O\end{array}\right),$$where M₂ and M₁ are submatrices of $W(A_n)$ all of whose entries are nonzero and the block-matrices $W_i(A_{n-1})$ are some weight matrices of $A_{n-1}$. Sizes of the block-matrices in $W(A_n)$ can be obtained from the respective sizes of the parts of the vertex partition ${\mathcal{U}}_n$. As (1, 2)th and (2, 1)th entries of the support matrix A_n are nonzero, the entries $w_{1,2}$ and $w_{2,1}$ are nonzero. Hence $$\det W(A_n)=w_{1,2}·w_{2,1}·\det \mathrm{}\left(\begin{array}{cccc}0& 1& {\mathbf{0}}^T& {\mathbf{0}}^T\\ 1& 0& M_1& {\mathbf{0}}^T\\ \mathbf{0}& M_2& W_1(A_{n-1})& W_2(A_{n-1})\\ \mathbf{0}& \mathbf{0}& W_3(A_{n-1})& O\end{array}\right)\mathrm{}.$$

For $3\le i\le 2^{n-1},$ by performing $\text{Row}(i)-w_{i,2}·\text{Row}(1)$ and then $\text{Column}(i)-w_{2,i}·\text{Column}(1),$ we get $$\det W(A_n)=w_{1,2}·w_{2,1}·\det \left(\begin{array}{cccc}0& 1& {\mathbf{0}}^T& {\mathbf{0}}^T\\ 1& 0& {\mathbf{0}}^T& {\mathbf{0}}^T\\ \mathbf{0}& \mathbf{0}& W_1(A_{n-1})& W_2(A_{n-1})\\ \mathbf{0}& \mathbf{0}& W_3(A_{n-1})& O\end{array}\right).$$

As $W_i(A_{n-1})$’s have an even number of columns, by interchanging columns, it is easy to get the following recurrence relation on determinants of weight matrices, $$\det W(A_n)=-w_{1,2}·w_{2,1}·\det W_2(A_{n-1})·\det W_3(A_{n-1}).$$

Note that, $W_2(A_{n-1})$ is a submatrix of $W(A_n)$ and also, it can be viewed as a weight matrix of the adjacency matrix $A_{n-1}$ of $\Gamma ({\mathbb{Z}}_2^{n-1}).$ Hence, $W_2(A_{n-1})$ has its rows and columns labeled in two different ways. The first labeling of it comes from the vertex ordering ${\mathcal{U}}_n$ while the second labeling is induced by the vertex ordering ${\mathcal{U}}_{n-1}$ of $\Gamma ({\mathbb{Z}}_2^{n-1})$. More specifically, in the first labeling, rows of $W_2(A_{n-1})$ are labeled by X₀ and the columns by X₁ as the parts of vertex partition ${\mathcal{U}}_n$ whereas in the second labeling, rows and columns of $W_2(A_{n-1})$ are labeled by vertices in $V_{n-1}$. We can go back and forth between the two labeling via the process of adjoining elements 0 and 1 to the vertices in $V_{n-1}$. Note further that, this process of adjoining $0,1\in {\mathbb{Z}}_2$ preserves the complementation of vertex labels, that is, for $v_i,v_j\in X_0\cup X_1$ with $v_i=v_i^{\prime }\diamond k_i,v_j=v_j^{\prime }\diamond k_j$ for some $v_i^{\prime },v_j^{\prime }\in V_{n-1}$ and $k_i,k_j\in {\mathbb{Z}}_2,$ we have $v_i={\overline{v}}_j$ holds in the first labeling if and only if $v_i^{\prime }={\overline{v}}_j^{\prime }$ holds in the second labeling. The case of the matrix $W_3(A_{n-1})$ can be treated similarly.

Now, we prove the result by induction on n. For n = 2, $A_2=(\begin{array}{cc}0& 1\\ 1& 0\end{array})$ and weight matrix $W(A_2)=(\begin{array}{cc}0& w_{1,2}\\ w_{2,1}& 0\end{array})$. Therefore, $\det W(A_2)=-w_{1,2}·w_{2,1}$. Note here that, vertices $v_1=(1,0)$ and $v_2=(0,1)$ satisfy $v_1={\overline{v}}_2$. Assume that, the result is true for all integers less than n. From the above paragraph, the matrices $W_2(A_{n-1})$ and $W_3(A_{n-1})$ can be viewed as weight matrices of $A_{n-1}$ with two different vertex ordering discussed in the paragraph above. Then by the induction hypothesis we get, $$\det W_2(A_{n-1})=-\prod _{v_i^{\prime }={\overline{v}}_j^{\prime }, v_i^{\prime },v_j^{\prime }\in V_{n-1}}{W}_2(v_i,v_j),$$where $W_2(v_i,v_j)$ denotes the entry of $W_2(A_{n-1})$ which is also the entry of $W(A_n)$ lying in the row labeled by the vertex $v_i=v_i^{\prime }\diamond 0$ and in the column labeled by the vertex $v_j=v_j^{\prime }\diamond 1$. From the paragraph above, we have, $v_i={\overline{v}}_j$ holds in ${\mathcal{U}}_n$ if and only if $v_i^{\prime }={\overline{v}}_j^{\prime }$ holds in ${\mathcal{U}}_{n-1}$. Therefore, $$\det W_2(A_{n-1})=-\prod _{v_i={\overline{v}}_j,v_i\in X_0\text{ and }{v}_j\in X_1}{w}_{i,j}.$$

Similarly, by the induction hypothesis, we have $$\det W_3(A_{n-1})=-\prod _{v_i^{\prime }={\overline{v}}_j^{\prime }, v_i^{\prime },v_j^{\prime }\in V_{n-1}}{W}_3(v_i,v_j)$$ $$=-\prod _{v_i={\overline{v}}_j,v_i\in X_1\text{ and }{v}_j\in X_0}{w}_{i,j}.$$

Putting these values in the recurrence relation of the determinants of weight matrices obtained above, we get, $$\det W(A_n) = -w_{1,2}·w_{2,1}·{(-1)}^2\mathrm{}\mathrm{}\prod _{v_i\mathrm{ }=\mathrm{ }{\overline{v}}_j,v_i,v_j\in X_0\cup X_1}{w}_{i,j} = -\prod _{v_i\mathrm{ }=\mathrm{ }{\overline{v}}_j}\mathrm{}{w}_{i,j}.$$

Now, if $v_i={\overline{v}}_j$ then v_i is adjacent to v_j in $\Gamma ({\mathbb{Z}}_2^n)$, that is, (i, j)th entry of the support matrix A_n of $W(A_n)$ is nonzero. This implies that the terms $w_{i,j}$ involved in the above expression of $\det W(A_n)$ are nonzero. Therefore, $\det W(A_n)\ne 0.$ Thus $W(A_n)$ is a nonsingular matrix. □

Remark 3.5.

Theorem 3.4 can be proved alternatively by generalizing the proof of the result, $\det A_n=-1$, given in [5]. However, our proof uses the recursive approach and also generalizes the result to the weighted and directed Boolean graphs.

Let w(e) denote the weight of an edge e in a weighted graph of $\Gamma ({\mathbb{Z}}_2^n)$. Let $E_n^{\prime }$ be the set of all edges of $\Gamma ({\mathbb{Z}}_2^n)$ whose end vertices are complements of each other.

Corollary 3.6.

Let ${(A_n)}_w$ be the adjacency matrix of a weighted Boolean graph of $\Gamma ({\mathbb{Z}}_2^n)$. Then $$\det {(A_n)}_w=-\prod _{e\in E_n^{\prime }}(w(e){)}^2.$$

Proof.

As seen earlier, the matrix ${(A_n)}_w$ of a weighted graph of $\Gamma ({\mathbb{Z}}_2^n)$ is a special case of weight matrix $W(A_n).$ Now, the proof follows from Theorem 3.4 since, in this case, $w_{i,j}=w_{j,i}=w(e)$ whenever $e=(v_i,v_j)$ is an edge of $\Gamma ({\mathbb{Z}}_2^n)$. □

Corollary 3.7.

[5] The determinant of the adjacency matrix of the Boolean graph $\Gamma ({\mathbb{Z}}_2^n)$ is –1.

Proof.

Proof follows from Theorem 3.4 since, in this case, $w_{i,j}=1$ whenever (v_i, v_j) is an edge of the graph $\Gamma ({\mathbb{Z}}_2^n)$.

Corollary 3.8.

The determinant of the adjacency matrix of any directed Boolean graph $\overrightarrow{\Gamma }({\mathbb{Z}}_2^n)$ is 1.

Proof.

Let ${\overrightarrow{A}}_n$ be the adjacency matrix of a directed Boolean graph $\overrightarrow{\Gamma }({\mathbb{Z}}_2^n)$. From Definition 3.3, ${\overrightarrow{A}}_n$ is a special case of the weight matrix $W(A_n)$ whose (i, j)th entry $w_{i,j}=1$ if $\overrightarrow{\Gamma }({\mathbb{Z}}_2^n)$ has a directed edge from vertex v_i to vertex $v_j,$ and $w_{i,j}=-1$ if there is a directed edge from vertex v_j to vertex $v_i,$ and $w_{i,j}=0$ when there is no edge. By Theorem 3.4, $\det {\overrightarrow{A}}_n=-\prod _{v_i=\overline{v_j}}{w}_{i,j}.$ Since $\overrightarrow{\Gamma }({\mathbb{Z}}_2^n)$ has $\frac{2^n-2}{2}$ complementary pairs of vertices, $\det {\overrightarrow{A}}_n=-{(-1)}^{2^{n-1}-1}=1.$ □

Remark 3.9.

It follows from Corollary 3.8 that the determinant of the adjacency matrix of any directed Boolean graph is 1 and thus it is independent of the choice of orientation of edges.

Recall the vertex set X₀ defined at the beginning of Section 2. Let H be the subgraph of $\Gamma ({\mathbb{Z}}_2^n)$ induced by the set $X_0.$ By Lemma 2.1, H is isomorphic to $\Gamma ({\mathbb{Z}}_2^{n-1}).$ Let $\widetilde{\Gamma ({\mathbb{Z}}_2^n)}$ be the simple graph obtained from the graph $\Gamma ({\mathbb{Z}}_2^n)$ by deleting any number of edges of H or adding any number of edges between the vertices of H. We observe that the determinant of $\widetilde{\Gamma ({\mathbb{Z}}_2^n)}$ is the same as the determinant of $\Gamma ({\mathbb{Z}}_2^n).$

Proposition 3.10.

Let A_n and $\widetilde{A_n}$ be the adjacency matrices of $\Gamma ({\mathbb{Z}}_2^n)$ and $\widetilde{\Gamma ({\mathbb{Z}}_2^n)},$ respectively. Then $$\det W(A_n)=\det W(\widetilde{A_n}).$$

Consequently, $\det {(A_n)}_w=\det {(\widetilde{A_n})}_w, \det \overrightarrow{A_n}=\det \overrightarrow{\widetilde{A_n}}$ and $\det A_n=\det \widetilde{A_n}.$

Proof.

The proof follows from the proof of Theorem 3.4 as the entries of the block-matrix $W_1(A_{n-1})$ corresponding to the vertices in X₀ do not affect the value of the determinant of $W(A_n)$.

The description of $A_n^{-1}$ obtained in Theorem 2.4 can be extended to more general matrices, namely to the weight matrices $W(A_n)$. We only state the expression of ${[W(A_n)]}^{-1}$ in the following theorem. For $1<n\in \mathbb{Z}$, let $W(A_n)$ be a weight matrix of A_n considered in the proof of Theorem 3.4 with (i, j)th entry $w_{i,j}$. Let ${\mathbf{w}}_1$ and ${\mathbf{w}}_2$ be column vectors in ${\mathbb{R}}^{\left|V_{n-1}\right|}$ such that their $i^{\text{th}}$ coordinates are $w_{2,i}$ and $w_{i,2}$, respectively for all $i=3,4,\dots ,\left|V_{n-1}\right|+2$.

Theorem 3.11.

Let $W(A_n)$ be any weight matrix of the adjacency matrix A_n of the Boolean graph $\Gamma ({\mathbb{Z}}_2^n)$. Then $W(A_n)$ is ivertible and its inverse is given by $$\left(\begin{array}{cccc}0& \frac{1}{w_{2,1}}& {\mathbf{0}}^T& -\frac{1}{w_{2,1}}{\mathit{w}}_1{}^T{[W_3(A_{n-1})]}^{-1}\\ \frac{1}{w_{1,2}}& 0& {\mathbf{0}}^T& {\mathbf{0}}^T\\ \mathbf{0}& \mathbf{0}& O& {[W_3(A_{n-1})]}^{-1}\\ -\frac{1}{w_{1,2}}{[W_2(A_{n-1})]}^{-1}{\mathit{w}}_2& \mathbf{0}& {[W_2(A_{n-1})]}^{-1}& -{[W_2(A_{n-1})]}^{-1}{W}_1(A_{n-1}){[W_3(A_{n-1})]}^{-1}\end{array}\right).$$

Proof.

The proof follows by performing the transformations and steps similar to those used in Theorem 2.4. □

The expressions for ${\overrightarrow{A}}_n^{-1},{(A_n)}_w^{-1}$, and $A_n^{-1}$ can be obtained from Theorem 3.11.

4 Directed Boolean graphs

In this section, we restrict our investigations to the class of directed Boolean graphs. The adjacency matrix of a directed Boolean graph is a skew-symmetric matrix and so its characteristic polynomial has all odd degree coefficients zero. By a classical theorem of Cayley, the determinant of a skew-symmetric matrix is a square of its Pfaffian and so all even degree coefficients of the characteristic polynomial are non-negative. In Section 3, we proved that the determinant of the adjacency matrix of a directed Boolean graph is 1 implying that the constant term (an even degree coefficient) of the characteristic polynomial is positive. We prove that this is also the case with all its even degree coefficients.

Theorem 4.1.

(Cayley) [3, Theorem 6.4] Let S be a skew-symmetric matrix with real entries. Then there is a polynomial in the entries of S, denoted $\text{Pf} (S)$, such that, $$\det S=\text{Pf} {(S)}^2.$$

We now prove our main theorem.

Theorem 4.2.

Let $1<n\in \mathbb{Z}$ and $N=2^n-2$. Then the characteristic polynomial of the adjacency matrix of a directed Boolean graph of $\Gamma ({\mathbb{Z}}_2^n)$ is of the form ${\sum }_{k=0}^{N/2}{c}_{2k}{x}^{2k}$ with $c_{2k}$ positive integers for all k.

Proof.

Let $\overrightarrow{\Gamma }({\mathbb{Z}}_2^n)$ be a directed Boolean graph with adjacency matrix ${\overrightarrow{A}}_n.$ Let $C_{\overrightarrow{A_n}}(x)$ be the characteristic polynomial of ${\overrightarrow{A}}_n.$ Denote the complement ${\mathbf{1}}_{\mathbf{n}}-v$ of a vector v of $\overrightarrow{\Gamma }({\mathbb{Z}}_2^n)$ by $\overline{v}$. To write down the adjacency matrix ${\overrightarrow{A}}_n$, we fix the ordering $I=\{v_1,{\overline{v}}_1,\dots ,v_{N/2},{\overline{v}}_{N/2}\}$ of the vertices of $\overrightarrow{\Gamma }({\mathbb{Z}}_2^n)$ by pairing up the complementary vertices. Let $\overrightarrow{A_n}=(a_{ij})$ be the directed adjacency matrix of the graph $\overrightarrow{\Gamma }({\mathbb{Z}}_2^n)$ with respect to this ordering. Note that $\overrightarrow{A_n}$ is a skew-symmetric matrix of even order $N=2^n-2.$ We know that the coefficient of x^k of the characteristic polynomial is given by the sum of principal minors of size N – k signed by ${(-1)}^{N-k}$. Also, the principal minors are the determinants of skew-symmetric sub-matrices of $\overrightarrow{A_n}$, and hence the minors of odd size are zero. Therefore, all the coefficients of $C_{\overrightarrow{A_n}}(x)$ of odd-degree terms are zero. The coefficient $c_{2k}$ is the sum of principal minors of ${\overrightarrow{A}}_n$ of size $N-2k$ multiplied by ${(-1)}^{N-2k}=1.$ By Theorem 4.1, (also see [3, Theorem 6.4]), the determinant of any skew-symmetric matrix S is given by a square of its Pfaffian, $\text{Pf}(S)$ (a polynomial in the coefficients of the matrix S), that is, $$\det S=\text{Pf}{(S)}^2.$$

All even sized minors of $\overrightarrow{A_n}$ are thus perfect squares and hence $c_{2k}\ge 0.$

We now show that $c_{2k}>0.$ To do this, we use the vertex ordering and the directed adjacency matrix given above. Since the principal minors are a perfect square and hence nonnegative, therefore is enough to prove that for any $1\le r\le N/2,$ there exists at least one principal minor that is nonzero (and hence positive). To do this we claim that the principal minors of ${\overrightarrow{A}}_n$ given by the row and column indices corresponding to the vertices $J=\{v_1,{\overline{v}}_1,v_2,{\overline{v}}_2,\dots ,v_r,{\overline{v}}_r\}$ is always non-zero. So let B be the submatrix of ${\overrightarrow{A}}_n$ formed by rows and columns of J. We know that $\det B=\sum _{\sigma \in S_{2r}}\text{sgn }\sigma a_{1\sigma (1)}{a}_{2\sigma (2)}\dots a_{2r\sigma (2r)}.$ Let $\tau \in S_{2r}$ be defined by $\tau (2i-1)=2i$ and $\tau (2i)=2i-1$ for all $1\le i\le r.$ Observe that $a_{i\tau (i)}=\pm 1$ for all i. Hence, $a_{1\tau (1)}{a}_{2\tau (2)}\dots a_{2r\tau (2r)}=\pm 1\ne 0.$ Let $\sigma \in S_{2r}$ be any permutation such that $a_{1\sigma (1)}{a}_{2\sigma (2)}\dots a_{2r\sigma (2r)}\ne 0.$ Now extend this permutation σ to a permutation $\tilde{\sigma }\in S_N$ by defining $\tilde{\sigma }(2i-1)=2i$ and $\tilde{\sigma }(2i)=2i-1$ for all $r+1\le i\le N.$ Thus, $$a_{1\tilde{\sigma }(1)}{a}_{2\tilde{\sigma }(2)}\dots a_{(2r)\tilde{\sigma }(2r)}\dots a_{(2N-1)\tilde{\sigma }(2N-1)}{a}_{(2N)\tilde{\sigma }(2N)}\ne 0.$$

By Theorem 3.4 and noting the vertex ordering $I=\{v_1,{\overline{v}}_1,\dots ,$ $v_{N/2},{\overline{v}}_{N/2}\}$ given above we obtain, $$\det {\overrightarrow{A}}_n=-\prod _{i=1}^{N/2}{a}_{2i,2i-1}{a}_{2i-1,2i}.$$

Hence, it follows that $\tilde{\sigma }\in S_{2N}$ is of the form $\tilde{\sigma }(2i-1)=2i$ and $\tilde{\sigma }(2i)=2i-1$ for all $1\le r\le N/2.$ Therefore, $\tilde{\sigma }$ agrees with τ on $\{1,2,\dots ,r\}.$ Already, $\tilde{\sigma }{|}_{\{1,2,\dots ,r\}}=\sigma ,$ we obtain $\sigma =\tau .$ Thus, for any $\sigma \in S_{2r}$ with $a_{1\sigma (1)}\dots a_{2r\sigma (2r)}\ne 0$, we have $\sigma =\tau ,$ i.e., $\sigma (2i-1)=2i$ and $\sigma (2i)=2i-1$ for all $1\le i\le r$. Note that this σ is the product of r transpositions and so $\text{sgn }\sigma ={(-1)}^r.$ Hence $$\begin{array}{ccc}\det B\hfill & =\hfill & \sum _{\sigma \in S_{2r}}\text{sgn }\sigma a_{1\sigma (1)}{a}_{2\sigma (2)}\dots a_{2r\sigma (2r)}\hfill \\ \hfill & =\hfill & {(-1)}^r{a}_{12}{a}_{21}\dots a_{i(i+1)}{a}_{(i+1)i}\dots a_{(2r-1)(2r)}{a}_{2r(2r-1)}\hfill \\ \hfill & =\hfill & {(-1)}^r{(-1)}^r=1\ne 0.\hfill \end{array}$$

Thus, for every even $r\in \{2,4,\dots ,N\},$ we get at least one nonzero principal minor. Furthermore, any such minor is a perfect square (being a square of the Pfaffian of the corresponding submatrix) and hence is positive. As noted at the beginning of the proof, the coefficient $c_{2k}$ of the characteristic polynomial $C_{{\overrightarrow{A}}_n}(x)$ is the sum of principal minors and as the positive minors live in every even degree, we obtain that $c_{2k}>0.$ □

Recall that the determinant of a directed Boolean graph is independent of the choice of the orientation of its edges. Note that this determinant is the constant term of the characteristic polynomial of the directed Boolean graph. However, we have verified that the other coefficients of the characteristic polynomial do depend on the choice of orientation.

Unimodal property for directed Boolean graphs:

LaGrange [5, Corollary 2.6] proved that the characteristic polynomial of an undirected Boolean graph $\Gamma ({\mathbb{Z}}_2^n)$ has the absolute palindromic property. A natural question to ask is whether a similar property holds for the class of directed Boolean graphs. We discuss this problem here.

As noted in Theorem 4.2, the even degree coefficients of the characteristic polynomial of the adjacency matrix $\overrightarrow{A_n}$ of a directed Boolean graph are positive. The examples worked out by us suggest that the values of these coefficients depend on the choice of the orientations of the edges and so a different choice of orientations on the edges of a Boolean graph leads to different positive coefficients. However, we observed in several examples of directed Boolean graphs that the even degree coefficients of the characteristic polynomial possess, what is called a unimodal property. A sequence $a_0,a_1,\dots ,a_n$ is called unimodal (or the polynomial $a_k{x}^k+a_{k-1}{x}^{k-1}+\cdots +a_{1}x+a_0$a unimodal polynomial) if there is some integer $0\le l\le k$ such that $$a_0\le a_1\le \cdots \le a_{l-1}\le a_l\ge a_{l+1}\ge \cdots \ge a_{k-1}\ge a_k.$$

The unimodal property can be regarded as an analog of the absolute palindromic property ($\left|a_i\right|=\left|a_{k-i}\right|$) wherein there is a symmetry in the absolute values of the coefficients of the polynomial along the middlemost term of the polynomial. A sequence or a polynomial being unimodal is an interesting combinatorial property and can often be hard to prove. We have worked out several examples of Boolean graphs up to n = 8 (with different choices of orientations) and observed unimodal property for the even degree coefficients. For example, a computer experiment with one of the examples of a directed Boolean graph when n = 4 (matrix in this case has size 14 × 14) yields the characteristic polynomial, $$x^{14}+25x^{12}+192x^{10}+574x^8+678x^6+256x^4+33x^2+1.$$

Note that the even degree coefficients of this polynomial are unimodal. We strongly suspect this to be true in the general case and state this as a question.

Question 4.3.

Do the even degree coefficients of the characteristic polynomial of a directed Boolean graph possess the unimodal property?

From our observation, we believe that all the eigenvalues of a directed Boolean graph are simple.

Question 4.4.

Are the eigenvalues of a directed Boolean graph simple?

Acknowledgments

The authors are thankful to the referees for providing useful suggestions.

Disclosure statement

The authors declare that there are no conflicts of interest.

Additional information

Funding

This work was supported by the SERB under grant CRG/2022/002184.