Recognizing cartesian products of matrices and polytopes

The 1-product of matrices S1∈ℝm1×n1 and S2∈ℝm2×n2 is the matrix in ℝ(m1+m2)×(n1n2) whose columns are the concatenation of each column of S1 with each column of S2. Our main result is a polynomial time algorithm for the following problem: given a matrix S, is S a 1-product, up to permutation of rows and columns? Our main motivation is a close link between the 1-product of matrices and the Cartesian product of polytopes, which relies on the concept of slack matrix. Determining whether a given matrix is a slack matrix is an intriguing problem whose complexity is unknown, and our algorithm reduces the problem to irreducible instances. Our algorithm is based on minimizing a symmetric submodular function that expresses mutual information in information theory. We also give a polynomial time algorithm to recognize a more complicated matrix product, called the 2-product. Finally, as a corollary of our 1-product and 2-product recognition algorithms, we obtain a polynomial time algorithm to recognize slack matrices of 2-level matroid base polytopes.