Boolean adjacency matrix

The adjacency matrix of a molecule con.si.sting of n atom.s i.s a square (n / n) matrix. with the entric.s giving all the connectivities of the atoms. The intersection of a row and a column obtains a value of 1 if the corresponding atoms are connected. If there is no bond between the atoms being considered, the position in the matrix obtains the value 0. Thus, this matrix representation is a Boolean matrix with bits (0 or I) (Figure 2-13). 

One method of locating these maximal loops is to compute the reachability matrix, R (H1), which is the element by element Boolean union of all of the powers of the adjacency matrix up to the nth, where n is the number of rows of R. An element of the reachability matrix is defined as... 

Once an output set has been established, the direction of information flow is fixed in the system of equations, and they can be represented either by a linear diagraph or its associated Boolean adjacency matrix. For our purposes it is more convenient to work with the Boolean adjacency matrix, which can be obtained directly from the occurrence matrix and output set as follows. First, assign numbers to the equations that correspond to the rows, and numbers to the variables that correspond to the columns of the occurrence matrix as in Fig. 5. Then pick an output set by the methods described in Section III. For the first equation, and the number of the column containing its output variable. The information flow transmitted by the variable designated by the column number goes to all other equations that have nonzero... 

We have shown thus far how the system of equations representing a process can be related to a linear diagraph and its associated Boolean adjacency matrix. In the Section IV, we show how the location of the maximal loops in this adjacency matrix leads to identification of the subsystems of equations that must be solved simultaneously. 

One method of partitioning the system equations is to compute the maximal loops using powers of the adjacency matrix as discussed in Section II. Certain modifications to the methods of Section II are needed in order to reduce the computation time. The first modification is to obtain the product of the matrices using Boolean unions of rows instead of the multiplication technique previously demonstrated to obtain a power of an adjacency matrix. To show how the Boolean union of rows can replace the standard matrix multiplication, consider the definition of Boolean matrix multiplication, Eq. (2), which can be expanded to... 

In order to obtain in a digital computer all of the powers of the adjacency matrix and then compute the reachability matrix by taking the Boolean sum of all of the powers, each power of the adjacency matrix and the reachability matrix would have to be stored in the computer memory. For large systems of equations an unreasonable amount of storage would be required. A second modification to the methods described in Section II is to drastically reduce... 

A Boolean matrix in general P Adjacency matrix of information... 

Representations of a graph, molecular graph, and their adjacency matrix are shown in Figs. 2(a), (b), and (c), respectively. It is apparent that the elements a, may be treated, again, as Boolean truth values of classical... 

---