Reachability matrix by partitioning and related Boolean results (Q1118616)

The reachability matrix of a partitioned matrix is obtained, in closed form, based on the properties of the structural matrix inverse. A graph theoretic interpretation of the partitioning is given in terms of the reachability relations on the two subgraphs into which the original graph splits, corresponding to the partitioned adjacency matrix. The reachability complement of a partitioned matrix is thus defined. A result analogous to the usual method of modified matrices is also presented, called here as the ``structural Householder formula'' and its special case: a formula for the reachability matrix of a sum of Boolean matrices. The latter is used to prove that the structural matrix inverse \((A^{- 1})_ B\) does not depend on which maximal permutation matrix \(P_ A\) included in A is taken.