  The 1-product of matrices $S_1 \in \mathbb{R}^{m_1 \times n_1}$ and $S_2 \in
\mathbb{R}^{m_2 \times n_2}$ is the matrix in $\mathbb{R}^{(m_1+m_2) \times
(n_1n_2)}$ whose columns are the concatenation of each column of $S_1$ with
each column of $S_2$. 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 goes through 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.
