Occurrence matrix nonzero elements

Let us construct a binary matrix A whose rows correspond to the equations and whose columns correspond to the variables. Let the element alV be 1 if variable j occurs in equation i, and let it be zero otherwise. Such a matrix is called an occurrence matrix. For the special case of Eq. (39) the occurrence matrix is symmetric. It reflects the structure of the underlying graph, since a0 = 1, if and only if the graph contains an edge i, j. If we now introduce the notation to denote the operation which assigns a value of one to a variable if its numerical value is nonzero, and a value of zero if otherwise, that is to say, for any variable x... 

To form the adjacency matrix in a simpler way, note that the elements of the first column of the adjacency matrix in Fig. 7b correspond exactly to the elements of the first column of the occurrence matrix in Fig. 6 if the output element is deleted. Similarly, the elements of column 2 of the adjacency matrix correspond exactly to the elements of the fourth column of the occurrence matrix if the output element is deleted. Therefore, if the columns of the occurrence were permuted until all of the output elements appeared on the main diagonal, as in Fig. 7a, the nonzero elements of the occurrence matrix... 

Form a new j by n Boolean matrix, M(0) as follows For each zero entry in column k, reproduce the corresponding row as a row in M(0). For example, the second row of the occurrence matrix in Fig. 12a contains a zero in column k = 1 and therefore the element = 0, element — 1, to 3 = 0, and to 4 = 1 comprise the first row of M(0). The second row of M(0) would be exactly like the third row of that occurrence matrix. This process is continued until all of the rows with zero entries in column k have been included as rows of M(0). A final row is added to M(0), whch is the Boolean union of all of the rows in the occurrence matrix which contain nonzero entries in column k. For example, rows 1 amd 4 of the occurrence matrix contain nonzero elements in column 1 so that the elements of the last row of M(0) are m3I = 1, m32 = 0, m33 = 1, m34 = 0. Figure 13a illustrates M(0). 

A new matrix M(1) is formed from M(0) in the same manner that M(0) was formed from the occurrence matrix. The column of M<0) containing the most nonzero elements is identified, and M(1> is made up of rows identical to each row of M(0), which contains a zero in column k and one final row, which is the Boolean union of the remaining rows in M(0). Figure 13b illustrates M(1). A record is kept of which rows of the original occurrence matrix have been combined to form each row of M(0), M(1), and so on. 

If an equation appears in more than one loop, one tear can break all of the loops in which the equation appears if in each of these loops the equation included in both loops has exactly the same equation feeding it in the loop. For example, column 2 of the occurrence matrix in Fig. 16a contains nonzero elements in rows 2 and 4. Upon inspection of the corresponding loops, B and D, in the tree of Fig. 15 it is seen that f2 is fed by f3 in both loops (/3 appears immediately after f2 in paths involved in loops B and D). Therefore, loops B and D can be broken by tearing the output variable of f3 from the equation f2. Now instead of putting l s as entries in row i and column j of the occurrence matrix to indicate that equation j appears in loop i, we insert instead the number of the equation that feeds equation j in loop i as in Fig. 16b. Then if the same nonzero number appears more than once in the same column, all of the loops represented by the rows in which that number appears... 

In the residual occurrence matrix comprised solely of independent columns, if a row contains only one nonzero element, the stream corresponding to the column in which the nonzero element appears is the only stream that can be torn to break the loop corresponding to that row. The next step of the algorithm is (1) to remove the columns in which a lone nonzero element in a row appears and (2) to remove all of the rows that have nonzero elements in that column. Each column removed in this step corresponds to tearing the stream represented by the column, and all of the rows removed represent loops that are broken by the tear. 

C THE NONZERO ELEMENTS OF THE OCCURRENCE MATRIX ARE READ HERE. 

---