Testing the irreducibility of nonsquare Perron–Frobenius systems

• We provide a polynomial time algorithm for testing the irreducibility of nonsquare matrices.
• This algorithm is useful in order to apply the generalized Perron–Frobenius theorem.
• The algorithm shows that irreducible nonsquare systems have a special graph structure that can be tested efficiently.

The Perron–Frobenius (PF) theorem provides a simple characterization of the eigenvectors and eigenvalues of irreducible nonnegative square matrices. A generalization of the PF theorem to nonsquare matrices, which can be interpreted as representing systems with additional degrees of freedom, was recently presented in [1]. This generalized theorem requires a notion of irreducibility for nonsquare systems. A suitable definition, based on the property that every maximal square (legal) subsystem is irreducible, is provided in [1], and is shown to be necessary and sufficient for the generalized theorem to hold. This note shows that irreducibility of a nonsquare system can be tested in polynomial time. The analysis uses a graphic representation of the nonsquare system, termed the constraint graph, representing the flow of influence between the constraints of the system.