Kronecker product decomposition of Boolean matrix with application to topological structure analysis of Boolean networks

1.   Introduction

Matrix decomposition is an important tool in data analysis and processing. As a typical matrix decomposition technique, the concept of nonnegative matrix factorization was first proposed in ^[1] for the purpose of dimensionality reduction. Since then, nonnegative matrix factorization has found many applications such as data storage ^[2], signal processing ^[3], information retrieval ^[4] and neural network ^[5]. Specifically, when the considered nonnegative matrices are Boolean matrices, the goal of Boolean matrix decomposition is to decompose a Boolean matrix into two Boolean matrices based on Boolean algebra ^[6,7]. There exist several feasible algorithms for the implementation of Boolean matrix decomposition ^[8,9], which are used in data engineering ^[7] and gene expression ^[10]. Logical matrix factorization ^[11] was developed to explore the topological structure of BNs.

Besides the nonnegative matrix factorization, there is another matrix decomposition method called KP decomposition. KP is an important matrix operation that generates a large block matrix by the KP of two or more smaller factor matrices. KP decomposition method has been applied to graph theory ^[12,13,14] and finite field ^[15,16]. Furthermore, it can be used to model the complex systems in biology and social networks via large KP networks ^[17]. Here, KP networks are composite networks of small factor networks by using the KP operation, and one can get insights about the properties of KP networks from factor ones ^[18]. Hence, it is important to obtain the factor networks based on the KP decomposition or KP approximation ^[19,20]. To the best of our knowledge, there are fewer results on the KP decomposition of the Boolean matrix. As a special kind of Boolean matrices, the KP decomposition of logical matrix was analyzed in ^[21].

Inspired by ^[11,21], this paper investigates the KP decomposition of the Boolean matrix. Compared with ^[21], this paper presents a more general result on the KP decomposition of the Boolean matrix, which can be used to decompose a graph represented by the Boolean matrix. It is noted that the KP decomposition of logical matrix considered in ^[21] is a special case. Since the adjacency matrix of the network graph is a kind of Boolean matrix, the KP decomposition of Boolean matrix can be used to decompose graphs. Based on this, this paper analyzes the topological structure of KPBNs, which are composite networks obtained by applying the KP operation to some smaller BNs called factor BNs. Since the introduction of the semi-tensor product of matrices ^[22], a BN can be converted into an algebraic form conveniently by calculating its unique state transition matrix ^[23,24]. Some recent development of BNs can be found in ^{[25,26,27,28,29]}. In addition, there are excellent works focusing on large-scale BNs ^[30,31] and finite-field networks ^[32,33]. With the help of algebraic representation, the state transition matrix of KPBN is the KP of state transition matrices for factor BNs. Thus, a large BN can be decomposed into KP of several smaller BNs if its state transition matrix can be decomposed into KP of several state transition matrices. This process is based on the KP decomposition of the Boolean matrix, since the state transition matrix is a special BN. As a result, the dimension of the large BN can be reduced.

In this paper, we first define the support matrix set of the Boolean matrix, which contains the full information of the Boolean matrix, then, we present a verifiable condition for the KP decomposition of the Boolean matrix. As an application, we use the results on the KP decomposition of the Boolean matrix to analyze the topological structure of KPBNs. The notations we used are shown in Table 1.

The rest of this paper is organized as follows: Section 2 gives some useful preliminaries. Section 3 presents the formulation of problem. Section 4 investigates the KP decomposition of the Boolean matrix, which is applied to analyze the topological structure of KPBNs in Section 5. Section 6 is a brief conclusion.

2.   Preliminaries

The basic operations used in this paper are Boolean addition and KP of Boolean matrices ^[34,35], denoted by $\oplus$ and $\otimes$, respectively.

Definition 2.1. ^[34] The Boolean addition of two Boolean matrices

and

is

Definition 2.2. ^[35] The KP of two Boolean matrices

and

is

The following is the distribution law of Boolean matrix in terms of Boolean addition and KP.

Lemma 2.1. Let

and

then

For a Boolean matrix $A = (a_{i, j})\in \mathcal{B}_{m\times n}$, we are interested in its nonzero elements. The support set of $A$ is defined as

which contains the indices of nonzero elements in $A$. For any $(i, j)\in Supp(A)$, we construct a matrix $E_{m\times n}^{(i, j)}\in \mathcal{B}_{m\times n}$ by fixing the $(i, j)$-th element as one and the remaining elements as zero. $E_{m\times n}^{(i, j)}$ is said to be a support matrix of $A$. Let

be the set of support matrices for $A$, which is called the support matrix set of $A$.

Remark 2.1. Based on the support matrix set, it is obvious that

which reveals the relation between Boolean matrix $A$ and its support matrix set $S_A$.

Lemma 2.2. Given $A\in \mathcal{B}_{m\times n}$ and $B\in \mathcal{B}_{p\times q}$, then the KP of support matrices $E_{m\times n}^{(i, j)}\in S_A$ and $E_{p\times q}^{(k, l)}\in S_B$ is

With the help of Lemma 2.2, the KP of two support matrix sets is defined below.

Definition 2.3. Let the support matrix sets of $A\in \mathcal{B}_{m\times n}$ and $B\in \mathcal{B}_{p\times q}$ be

and

respectively, then the KP of $S_A$ and $S_B$ is

3.   Problem formulation

In this paper, we aim to investigate the KP decomposition of the Boolean matrix, which is defined as follows.

Definition 3.1. Boolean matrix $C\in\mathcal{B}_{mp\times nq}$ is said to be KP decomposable with respect to $(m, n)$ if there exist two Boolean matrices $A\in\mathcal{B}_{m\times n}$ and $B\in \mathcal{B}_{p\times q}$ such that $C = A\otimes B$.

Remark 3.1. As a special Boolean matrix $E_{mp\times nq}^{(\alpha, \beta)}\in S_C$, if it is KP decomposable with respect to $(m, n)$, then

where $\alpha = (i-1)p+k$, and $\beta = (j-1)q+l$.

The basic idea of analyzing KP decomposition for Boolean matrix $C$ is to convert it into the KP decomposition of support matrices in $S_C$. To this end, we define the KP decomposition of the support matrix set.

Remark 3.2. Let $C\in \mathcal{B}_{mp\times nq}$ be given. $S_C$ is said to be KP decomposable with respect to $(m, n)$, if there exist $A\in \mathcal{B}_{m\times n}$ and $B\in\mathcal{B}_{p\times q}$ such that $S_C = S_A\otimes S_B$.

Note that $C\in \mathcal{B}_{mp\times nq}$ can be expressed in the form of (2.4), then, with respect to $(m, n)$, $C$ is KP decomposable, if all support matrices in $S_C$ are KP decomposable. By analyzing the KP decomposition of support matrices in $S_C$, we aim to obtain a verifiable condition for the KP decomposition of $C\in\mathcal{B}_{mp\times nq}$. In addition, with respect to $(m, n)$, it is obvious that $S_C$ is KP decomposable when each $E_{mp\times nq}^{(\alpha, \beta)}\in S_C$ is KP decomposable. Hence, the KP decomposition of $C$ and KP decomposition of $S_C$ are equivalent.

As an application of KP decomposition for the Boolean matrix, we investigate the KP decomposition of large-scale BNs. To this end, we need to recall BNs and semi-tensor product of matrices.

Consider the following BN:

where $x_i\in \mathcal{D}$ is a logical state variable and $f_i$: $\mathcal{D}^n\rightarrow \mathcal{D}$ is a logical function, $i = 1, \cdots, n$.

Cheng and Qi ^[24] introduced the semi-tensor product of matrices and converted system (3.1) into an algebraic form as

where

and

is called the state transition matrix of system (3.1).

It is a basic issue to study the topological structure of BNs, including fixed points and cycles. A state $x_e\in \Delta_{2^n}$ is said to be a fixed point of system (3.1) if $Lx_e = x_e$. A set of different points $\{x_1, \cdots, x_l\}\in \Delta_{2^n}$ is said to be a cycle of system (3.1) with length $l$, if $x_{k+1} = Lx_{k}$ holds for any $k = 1, \cdots, l-1$ and $x_{l+1} = x_1$.

It is worth noting that Cheng and Qi ^[24] proposed a method to figure out the number of fixed points and cycles on the basis of state transition matrix $L$. However, $L$ is a logical matrix with dimension $2^n\times 2^n$, which grows exponentially. To ease the computation burden, a potential idea is to decompose $L$ into the KP of two state transition matrices with smaller dimensions. Keeping this procedure going, we finally obtain the KP of several transition matrices with the smallest dimensions. Hence, we develop a kind of new BNs, called KPBNs, generated by KP of two state transition matrices for two smaller BNs.

Let

and

be the algebraic forms of two small BNs, where $x(t)\in \Delta_{2^{n_x}}$, $y(t)\in \Delta_{2^{n_y}}$, $L_1\in \mathcal{L}_{2^{n_x}\times 2^{n_x}}$ and $L_2\in \mathcal{L}_{2^{n_y}\times 2^{n_y}}$ are state transition matrices of systems (3.3) and (3.4), respectively. Setting

then the KPBN generated by systems (3.3) and (3.4), can be described as

where

Systems (3.3) and (3.4) are called factor BNs of KPBN (3.5).

Based on the method of KP decomposition for the Boolean matrix, we aim to analyze the topological structure of KPBNs by studying factors of the BNs.

4.   KP decomposition of Boolean matrix

In this section, we investigate the KP decomposition of the Boolean matrix. First, we analyze the KP decomposition of support matrix and give a necessary and sufficient condition. Based on this, we present a verifiable condition for the KP decomposition of Boolean matrix. Second, we reveal the relation between KP of Boolean matrices and their support matrix sets, and propose an equivalent condition for KP decomposition of the Boolean matrix, which is useful to obtain the decomposed Boolean matrices.

From Remark 2.1, the KP decomposition of $C\in \mathcal{B}_{mp\times nq}$ can be converted into KP decomposition of $E_{mp\times nq}^{(\alpha, \beta)}\in S_C$. Hence, we establish a theorem to verify whether a support matrix $E_{mp\times nq}^{(\alpha, \beta)}\in S_C$ is KP decomposable with respect to $(m, n)$.

Theorem 4.1. Given a support matrix $E_{mp\times nq}^{(\alpha, \beta)}\in S_C$, $E_{mp\times nq}^{(\alpha, \beta)}$ is KP decomposable with respect to $(m, n)$ if, and only if, there exists a set of integers $i\in \{1, \cdots, m\}$, $j\in \{1, \cdots, n\}$, $k\in \{1, \cdots, p\}$ and $l\in \{1, \cdots, q\}$ such that

Proof. (Necessity) Suppose that $E_{mp\times nq}^{(\alpha, \beta)}$ can be decomposed as the following form:

By Lemma 2.2, we have

and

In addition, $i\in \{1, \cdots, m\}$, $j\in\{1, \cdots, n\}$, $k\in\{1, \cdots, p\}$ and $l\in\{1, \cdots, q\}$.

(Sufficiency) Suppose that there exists a set of integers $i\in \{1, \cdots, m\}$, $j\in \{1, \cdots, n\}$, $k\in \{1, \cdots, p\}$ and $l\in \{1, \cdots, q\}$ satisfying (4.1). According to Lemma 2.2, $E_{mp\times nq}^{(\alpha, \beta)}$ can be decomposed as

□

Remark 4.1. With respect to $(m, n)$, the KP decomposition of $E_{mp\times nq}^{(\alpha, \beta)}$ is unique when $E_{mp\times nq}^{(\alpha, \beta)}\in S_C$ is KP decomposable.

Now, we present a verifiable condition for the KP decomposition of the Boolean matrix based on Theorem 4.1.

Theorem 4.2. Let $C\in \mathcal{B}_{mp\times nq}$ be given, then, with respect to $(m, n)$, $C$ is KP decomposable if, and only if, any $E_{mp\times nq}^{(\alpha, \beta)}\in S_C$ is KP decomposable.

When $C\in \mathcal{B}_{mp\times nq}$ is KP decomposable with respect to $(m, n)$, the decomposition is unique, then, we need to determine $A\in\mathcal{B}_{m\times n}$ and $B\in \mathcal{B}_{p\times q}$ satisfying $C = A\otimes B$. For this purpose, we uncover the relation between KP of Boolean matrices and their support matrix sets.

Proposition 4.1. Let the support matrix sets of $A\in \mathcal{B}_{m\times n}$ and $B\in \mathcal{B}_{p\times q}$ be

and

respectively, then the support matrix set of $A\otimes B$ is

Proof. According to (2.4), we have

and

From Lemmas 2.1 and 2.2, we can obtain

where

is clearly derived by the definition of the support set. Thus, $E_{mp\times nq}^{((i-1)p+k, (j-1)q+l)}$ is the support matrix in $S_{A\otimes B}$ for any $(i, j)\in Supp(A)$ and any $(k, l)\in Supp(B)$. Therefore, we have $S_{A\otimes B} = S_A\otimes S_B$ by Definition 2.3. □

Proposition 4.1 indicates that the support matrix set $S_C$ can be decomposed as KP of two support matrix sets $S_A$ and $S_B$ if, and only if, $C\in \mathcal{B}_{mp\times nq}$ can be decomposed as $C = A\otimes B$. In other words, with respect to KP, the decomposed support matrix sets $S_A$ and $S_B$ can determine the decomposed matrices $A$ and $B$ based on (2.4).

Proposition 4.2. Let the support matrix set of $C\in \mathcal{B}_{mp\times nq}$ be

then, with respect to $(m, n)$, $C = A\otimes B$ is a KP decomposition if, and only if,

is a KP decomposition, where

and

Remark 4.2. Note that a Boolean matrix can be decomposed into more than two Boolean matrices, if the decomposed matrices are still KP decomposable.

We give a simple example to show the process of using the obtained results to decompose a Boolean matrix with respect to KP.

Example 4.1. Given a Boolean matrix

we discuss whether $C\in \mathcal{B}_{6\times 9}$ can be decomposed into the KP of two Boolean matrices with respect to (2, 3).

First, one can obtain

From Theorem 4.1, we conclude that all the support matrices in $S_C$ are KP decomposable with respect to $(2, 3)$ and

then, with respect to $(2, 3)$, $C$ is KP decomposable by Theorem 4.2.

Suppose that $C$ can be decomposed as $C = A\otimes B$, where $A\in \mathcal{B}_{2\times 3}$ and $B\in \mathcal{B}_{3\times 3}$, then we have $S_C = S_A\otimes S_B$, where

and

According to (2.4), we obtain

and

that is,

5.   Topological structure analysis of KPBNs

In this section, we explore the topological structure of KPBNs, including fixed points and cycles, on the basis of results obtained in Section 4.

We first present the process of characterizing the topological structure of KPBNs by using graph theory. A graph $G = (V, E)$ consists of a set of vertices $V = \{v_1, \cdots, v_n\}$ and a set of edges $E\subseteq V\times V.$ An edge $(i, j)\in E$ if there exists a directed path from vertex $v_i$ to vertex $v_j$, denoted by $v_i\rightarrow v_j$. Note that a convenient representation of finite graphs is an adjacency matrix. The adjacency matrix $A(G)$ of graph $G$ is a matrix $A(G) = (a_{i, j})$ such that $a_{i, j} = 1$ if $v_i\rightarrow v_j$ and $a_{i, j} = 0$ otherwise. Apparently, the adjacency matrix $A(G)$ is a Boolean matrix. Additionally, the adjacency matrix $A(G)$ contains the interaction information between vertices in the graph $G$. We consider fixed points as self-loops and cycles with length $l$ as directed cycles on $l$ vertices, which are denoted by graphs $G_1$ and $G_2$, respectively. Based on the construction of KPBNs, it is natural to use the KP of graphs to characterize the topological structure of KPBNs. For this purpose, we recall the KP of graphs. For details, please refer to ^[12].

Definition 5.1. ^[12] Let $A(G_1)$ and $A(G_2)$ be adjacency matrices of graphs $G_1$ and $G_1$, respectively. The KP of graphs $G_1$ and $G_1$, denoted by $G_1\otimes G_2$, is the graph with adjacency matrix $A(G_1)\otimes A(G_2)$.

In order to characterize the KP of graphs, we denote the vertex set of $G_1\otimes G_2$ by

where $G_1$ has vertex set $V_1 = \{i_1, \cdots, i_p\}$ and $G_2$ has vertex set $V_2 = \{j_1, \cdots, j_q\}$.

As was shown in ^[21], the KP of $p$ fixed points and a cycle with length $q$ is composed of $p$ cycles with length $q$. Next, we give a further analysis of topological structure for KPBNs.

Proposition 5.1. Suppose that system (3.3) has $p$ fixed points $x_{e_1} = \delta_{2^{n_x}}^{i_1}$, $\cdots$, $x_{e_p} = \delta_{2^{n_x}}^{i_p}$ and system (3.4) has $q$ fixed points $y_{e_1} = \delta_{2^{n_y}}^{j_1}$, $\cdots$, $y_{e_q} = \delta_{2^{n_y}}^{j_q}$, then KPBN (3.5) has $pq$ fixed points as follows:

where

Proof. By the definition of fixed points, we can obtain that $x_{e_k} = L_1x_{e_k}$ and $y_{e_l} = L_2y_{e_l}$ hold for any $k = 1, \cdots, p$ and any $l = 1, \cdots, q$. Thus, we have

which implies that $z_{e_{k, l}} = Lz_{e_{k, l}}$ holds for any $k = 1, \cdots, p$ and any $l = 1, \cdots, q$. Thus, $z_{e_{k, l}} = \delta_{2^{n_x+n_y}}^{\alpha_{k, l}}$ is a fixed point of KPBN (3.5). □

The KP of fixed points can be obtained directly through Proposition 5.1. However, when both systems (3.3) and (3.4) have cycles, the topological structure of KPBN (3.5) is hard to be figured out. For the convenience of analysis, we denote two directed cycles with length $p$ and $q$ by $\vec{C}_p$ and $\vec{C}_q$, respectively.

Proposition 5.2. Given two directed cycles $\vec{C}_{p}$ and $\vec{C}_{q}$ with vertex sets $V_1 = \{i_1, \cdots, i_p\}$ and $V_2 = \{j_1, \cdots, j_q\}$, respectively, then the graph $\vec{C}_{p}\otimes \vec{C}_{q}$ with vertex set

is composed of unconnected directed cycles.

Proof. Let the adjacency matrices of directed cycles $\vec{C}_{p}$ and $\vec{C}_{q}$ be $A(\vec{C}_p)$ and $A(\vec{C}_q)$, respectively, then it is easy to see that $A(\vec{C}_p)$, $A(\vec{C}_q)$ and $A(\vec{C}_p)\otimes A(\vec{C}_q)$ are permutation matrices; that is, for any vertex $(i_k, j_l)\in V$, its out-degree and in-degree are exactly one. Obviously, there is no self-loop in graph $\vec{C}_{p}\otimes \vec{C}_{q}$. Now, we prove that any vertex $(i_k, j_l)\in V$, $(i_k, j_l)$ is exactly on one of the cycles in graph $\vec{C}_{p}\otimes \vec{C}_{q}$ by a reduction to absurdity.

Suppose that there exists a vertex $(i_{k_0}, j_{l_0})\in V$, which is not on any cycle in graph $\vec{C}_{p}\otimes \vec{C}_{q}$. Without loss of generality, we assume that there is only one such vertex. Since both out-degree and in-degree of every vertex in $\vec{C}_{p}\otimes \vec{C}_{q}$ are one, there must exist a vertex $(i_{k_1}, j_{l_1})\in V$ such that $(i_{k_0}, j_{l_0})\rightarrow (i_{k_1}, j_{l_1})$ is a directed path in $\vec{C}_{p}\otimes \vec{C}_{q}$. Noting that the vertex $(i_{k_1}, j_{l_1})$ is on a directed cycle, there exists another vertex $(i_{k_2}, j_{l_2})\in V$ on the cycle such that $(i_{k_2}, j_{l_2})\rightarrow (i_{k_1}, j_{l_1})$ is a directed path. Thus, the in-degree of vertex $(i_{k_1}, j_{l_1})$ is two, which is contradictory to the fact that the in-degree of every vertex in $\vec{C}_{p}\otimes \vec{C}_{q}$ is one.

Suppose that there exists a vertex $(i_{k_0}, j_{l_0})\in V$ on two connected but different cycles in $\vec{C}_{p}\otimes \vec{C}_{q}$. We assume that there is only one such vertex, then we have two vertices $(i_{k_1}, j_{l_1})$ and $(i_{k_2}, j_{l_2})$ on the two cycles, respectively, such that $(i_{k_1}, j_{l_1})\rightarrow (i_{k_0}, j_{l_0})$ and $(i_{k_2}, j_{l_2})\rightarrow (i_{k_0}, j_{l_0})$ are directed paths, where $(i_{k_1}, j_{l_1})\neq (i_{k_2}, j_{l_2})$. Thus, the in-degree of vertex $(i_{k_0}, j_{l_0})$ is two, which is also a contradiction.

Consequently, the graph $\vec{C}_{p}\otimes \vec{C}_{q}$ is composed of unconnected directed cycles. □

Remark 5.1. Note that the number of unconnected components for KP of two cycles is determined by the KP of two adjacency matrices corresponding to the two directed cycles. In addition, there exist results on the cases of two special cycles. For detailed information, please refer to ^[12].

To obtain a deeper understanding for the KP of directed cycles, we need to recall some results on the connectivity for KP of graphs. In ^[12], for undirected connected graphs $G_1$ and $G_2$, $G_1\otimes G_2$ is connected if, and only if, either $G_1$ or $G_2$ contains an odd cycle. Here, a cycle is called odd if it contains an odd number of vertices. Similarly, we call a directed cycle with an odd number of vertices a directed odd cycle. Combining with Proposition 5.2, we present a proposition revealing the topological structure of KPBNs.

Proposition 5.3. Suppose that system (3.3) is stable at cycle $\{\delta_{2^{n_x}}^{i_1}, \cdots, \delta_{2^{n_x}}^{i_p}\}$, and system (3.4) is stable at cycle $\{\delta_{2^{n_y}}^{j_1}, \cdots$, $\delta_{2^{n_y}}^{j_q}\}$. If either $p$ or $q$ is odd, then KPBN (3.5) is stable at a cycle with length $pq$.

Remark 5.2. For a large-scale BN, if the state transition matrix can be decomposed into smaller ones with respect to KP, then the topological structure can be described by the KP of graphs representing the topological structure of smaller BNs. Compared with ^[11], in which the topological structure of size-reduced BNs and original ones are identical, this paper presents a new perspective for analyzing the topological structure of large-scale BNs with lower dimensions.

Denote the two cycles in Proposition 5.3 by $\vec{C}_{p}$ and $\vec{C}_{q}$, respectively, then, the specific structure of cycle $\vec{C}_{p}\otimes \vec{C}_{q}$ for KPBN (3.5) can be determined by the adjacency matrix $A(\vec{C}_{p})\otimes A(\vec{C}_{q})$. We give a simple example to illustrate the procedure.

Example 5.1. Consider systems (3.3) and (3.4), where

and

System (3.3) is stable at cycle $\{\delta_{8}^{1}, \delta_{8}^{3}, \delta_{8}^{8}\}$, while system (3.4) is stable at cycle $\{\delta_{16}^{2}, \delta_{16}^{3}, \delta_{16}^{7}, \delta_{16}^{11}\}$. The two cycles are shown in Figure 1.

Let the cycles of systems (3.3) and (3.4) be represented by directed cycles $\vec{C}_3$ and $\vec{C}_4$ with vertex sets $V_1 = \{1, 3, 8\}$ and $V_2 = \{2, 3, 7, 11\}$, respectively. The adjacency matrices $A(\vec{C}_{3})$ and $A(\vec{C}_{4})$ are given below:

By calculating $A(\vec{C}) = A(\vec{C}_{3})\otimes A(\vec{C}_{4})$, we can obtain the specific structure in the cycle $\vec{C}$

Hence, KPBN (3.5) is stable at the cycle

which is shown in Figure 2.

6.   Conclusions

In this paper, we have investigated the KP decomposition of the Boolean matrix and analyzed the topological structure of KPBNs. By analyzing the KP decomposition of support matrices, we have presented a criterion for the KP decomposition of the Boolean matrix. In addition, we have applied the results on the KP decomposition of the Boolean matrix to the topological structure analysis of KPBNs. Future works can analyze the KP approximation of the Boolean matrix when it cannot be decomposed with respect to KP.

Use of AI tools declaration

The authors declare they have not used Artificial Intelligence (AI) tools in the creation of this article.

Acknowledgments

The research was supported by the National Natural Science Foundation of China under grants 62073202 and 62273216 and the Young Experts of Taishan Scholar Project under grant tsqn 201909076.

Conflict of interest

All authors declare that they have no conflicts of interest in this paper.