A graph theoretic approach to matrix inversion by partitioning

Abstract

Let M be a square matrix whose entries are in some field. Our object is to find a permutation matrix P such that PM P −1 is completely reduced, i.e., is partitioned in block triangular form, so that all submatrices below its diagonal are 0 and all diagonal submatrices are square and irreducible. Let A be the binary (0, 1) matrix obtained from M by preserving the 0's of M and replacing the nonzero entries of M by 1's. Then A may be regarded as the adjacency matrix of a directed graph D . Call D strongly connected or strong if any two points of D are mutually reachable by directed paths. A strong component of D is a maximal strong subgraph. The condensation D * of D is that digraph whose points are the strong components of D and whose lines are induced by those of D . By known methods, we construct D * from the digraph, D whose adjacency matrix A was obtained from the original matrix M . Let A * be the adjacency matrix of D * . It is easy to show that there exists a permutation matrix Q such that QA * Q −1 is an upper triangular matrix. The determination of an appropriate permutation matrix P from this matrix Q is straightforward.