@inproceedings{1a78dd67d6504983a5b07a66517dff31,
title = "Recognizing cartesian products of matrices and polytopes",
abstract = "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.",
keywords = "2-level polytopes, Cartesian product, Mutual information, Slack matrix, Submodular optimization",
author = "Manuel Aprile and Michele Conforti and Yuri Faenza and Samuel Fiorini and Tony Huynh and Marco Macchia",
note = "Funding Information: This project was supported by ERC Consolidator Grant 615640-ForEFront and by a gift by the SNSF. Publisher Copyright: {\textcopyright} The Author(s), under exclusive license to Springer Nature Switzerland AG 2021. Copyright: Copyright 2021 Elsevier B.V., All rights reserved.",
year = "2021",
doi = "10.1007/978-3-030-63072-0_28",
language = "English",
isbn = "9783030630713",
series = "AIRO Springer Series",
publisher = "Springer",
pages = "361--373",
editor = "Claudio Gentile and Giuseppe Stecca and Paolo Ventura",
booktitle = "Graphs and Combinatorial Optimization: from Theory to Applications",
}