Bipartite graphs and an optimal bordered triangular form of a matrix

The problem of determining row and column permutations to transform a nonsingular (not necessarily symmetric) matrix to a minimum -bordered lower triangular form is shown to be an -complete (Intrinsically difficult) problem by treating an equivalent bipartite graph problem-determine a minimum essential dumbbell set. A (sequential, rather than backtrack oriented) algorithm is described by which to obtain a minimal (local minimum, rather than minimum) essential dumbbell set, hence, also a minimal -bordered lower triangular form of a matrix. The performance of an APL realization of the algorithm is illustrated and data to justify an embedded heuristic is provided.