The fully indecomposable matrix and its associated bipartite graph - an investigation of combinatorial and structural properties

For any nxn (0,1) matrix A , a correspondence is established between A and a certain bigraph G . Equivalences between various concepts pertaining to A and G , respectively, are demonstrated. It is shown that if A is fully indecomposable, then G is 2-connected. A method is developed for reducing a bigraph G of a nearly decomposable matrix to a strictly smaller biqraph G' , which is also associated with a nearly decomposable matrix A' . This result is used to completely characterize the fully indecomposable matrices in terms of their bigraphs and leads to a lower-bound estimate for the permanent function on this class of matrices. Finally, the characterization theorem is shown to be relevant to the problems of (1) finding an upper-bound estimate for the permanent and (2) of determining the structure of the class of nearly decomposable matrices. Some partial results along these lines are given.