Vector subset diagram

Moore's traditional discussion gives no internal structure to the nodes of the subset diagram, but we will find it convenient to regard each node as a vector whose components are indexed by the nodes of the original graph. Then links in the subset graph are represented by projections applied to the topological matrix of the original graph; precisely, projection onto the subset belonging to the label in question. Each row of the graph will have k nonzero submatrices (if that is the number of labels) except that if there is no link corresponding to some particular label, its submatrix will be zero too.

The column containing the submatrix for label k will correspond to the subset of nodes which are destinations for that label. Should the destination subsets coincide for two or more labels, neither common nor impossible, the multiplicity should be entered into the submatrix. Alternatively, one could separate the subset matrices for each link and later sum them as needed.

If there were n nodes in the original graph, the topological matrix of the subset diagram will have dimension . For a g-stage de Bruijn diagram, . As usual, powers of the topological matrix describe chains with multiple links, but the most interesting matrix elements will be the ones in the top row, so to speak. They connect the full set with other subsets, including the empty set. If it is immaterial where a path begins or ends, the submatrix connecting the full set with itself suffices. Restrictions placed upon the choices of initial and terminal nodes will lead to other submatrices.

Were it not for the projections, the vector connection matrix V would be the tensor product of the de Bruijn matrix with the scalar connection matrix. But the projected elements are missing; so introduce row and column indices of the form , where , are subsets whose own linkage is defined by

Then,

---

Harold V. McIntosh
E-mail:mcintosh@servidor.unam.mx