The bordered triangular matrix and minimum essential sets of a digraph

A partitioning strategy of sparse matrices is dealt with. In particular, the problem of transforming a nonsingular matrix by symmetric permutation to an optimal bordered triangular form (BTF) is solved. It is shown that the problem is equivalent to the determination of a minimum essential set of a directed graph. An efficient algorithm is given for finding minimum essential sets of a digraph. The method depends on, as a preliminary step, graph simplication using local information at a vertex. A circuit-generation technique based on vertex elimination is then introduced. The algorithm is illustrated with a complete example. A simple electrical network is used to illustrate the use of the BTF in the sparse tableau approach of network analysis.