Mixed Matrices: Irreducibility and Decomposition

This paper surveys mathematical properties of (layered-) mixed matrices with emphasis on irreducibility and block-triangular decomposition. A matrix A is a mixed matrix if A = Q + T, where Q is a “constant” matrix and T is a “generic” matrix (or formal incidence matrix) in the sense that the nonzero entries of T are algebraically independent parameters. A layered mixed (or LM-) matrix is a mixed matrix such that Q and T have disjoint nonzero rows, i.e., no row of A = Q + T has both a nonzero entry from Q and a nonzero entry from T. The irreducibility for an LM-matrix is defined with respect to a natural admissible transformation as an extension of the well-known concept of full indecomposability for a generic matrix. Major results for fully indecomposable generic matrices such as Frobenius’ characterization in terms of the irreducibility of determinant are generalized. As for block-triangularization, the Dulmage-Mendelsohn decomposition is generalized to the combinatorial canonical form (CCF) of an LM-matrix along with the uniqueness and the algorithm. Matroid-theoretic methods are useful for investigating a mixed matrix.