Recognizing Cartesian products of matrices and polytopes

DOI10.1007/978-3-030-63072-0_28MaRDI QIDQ2056923zbMATH OpenOpenAlexFDO

Authors Manuel Aprile, Michele Conforti, Yuri Faenza, Samuel Fiorini, Tony Huynh, Marco Macchia

Publication date 8 December 2021

Full work available at URL https://arxiv.org/abs/2002.02264

zbMATH Keywords

mutual informationCartesian productslack matrixsubmodular optimization2-level polytopes

Mathematics Subject Classification ID

Combinatorial optimization (90C27) Basic linear algebra (15A99) Combinatorial properties of polytopes and polyhedra (number of faces, shortest paths, etc.) (52B05) Matroids in convex geometry (realizations in the context of convex polytopes, convexity in combinatorial structures, etc.) (52B40) Polyhedra and polytopes; regular figures, division of spaces (51M20)

Abstract: The 1-product of matrices $S_{1}inmathbb{R}^{m_{1}imes{n}_1}$ and $S_{2}inmathbb{R}^{m_{2}imes{n}_2}$ is the matrix in $mathbb{R}^{(m_1+m_2)imes(n_1{n}_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.

Recommendations

• Which nonnegative matrices are slack matrices?
• The geometry of products of minors
• Slack ideals in Macaulay2
• Polytopality and Cartesian products of graphs
• A polynomial time algorithm for finding the prime factors of Cartesian- product graphs

Cites work

• scientific article; zbMATH DE number 1961535 (Why is no real title available?)
• scientific article; zbMATH DE number 764212 (Why is no real title available?)
• scientific article; zbMATH DE number 5047784 (Why is no real title available?)
• Elements of Information Theory
• Expressing combinatorial optimization problems by linear programs
• Extended formulations in combinatorial optimization
• Minimizing symmetric submodular functions
• Recognizing Cartesian products of matrices and polytopes
• The projected faces property and polyhedral relations
• Theta rank, levelness, and matroid minors
• Which nonnegative matrices are slack matrices?

Cited in

(8)

• Recognizing Cartesian products of matrices and polytopes
• Recognizing Cartesian products in linear time
• Slack matrices, \(k\)-products, and 2-level polytopes
• Extended formulations for matroid polytopes through randomized protocols
• Which nonnegative matrices are slack matrices?
• Recognition of \(d\)-dimensional Monge arrays
• Recognizing triangulated Cartesian graph products
• scientific article; zbMATH DE number 7540153 (Why is no real title available?)

This page was built for publication: Recognizing Cartesian products of matrices and polytopes

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2056923)