The Decomposition of Matrices

Abstract

<p>This thesis deals with algorithms which, for a given square matrix A of order n, construct permutation matrices P and Q (if they exist) such that PAQ is a canonical form of A. The pertinent theory of fully indecomposable matrices is discussed and detailed description is given of the algorithm by Dulmage and Mendelsohn. The connection between irreducible and fully indecomposable matrices is also examined, and it is observed that Harary's algorithm for bringing a matrix to a normal form is interchangeable with the second part of the Dulmage and Mendelsohn algorithm. Efficient computer programs for the Dulmage and Mendelsohn algorithm are presented which are directly applicable to various numerical problems.</p>