Recognizing Cartesian products of matrices and polytopes

DOI10.1007/978-3-030-63072-0_28zbMATH Open1483.15023arXiv2002.02264OpenAlexW3005352619MaRDI QIDQ2056923FDOQ2056923

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

Publication date: 8 December 2021

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.

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

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

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)

Cites Work

• Elements of Information Theory
• Expressing combinatorial optimization problems by linear programs
• The projected faces property and polyhedral relations
• Title not available (Why is that?)
• Minimizing symmetric submodular functions
• Extended formulations in combinatorial optimization
• Title not available (Why is that?)
• Theta rank, levelness, and matroid minors
• Which nonnegative matrices are slack matrices?
• Title not available (Why is that?)
• Recognizing Cartesian products of matrices and polytopes

Cited In (8)

• Slack matrices, \(k\)-products, and 2-level polytopes
• Recognizing Cartesian products in linear time
• Recognizing Cartesian products of matrices and polytopes
• Which nonnegative matrices are slack matrices?
• Recognition of \(d\)-dimensional Monge arrays
• Title not available (Why is that?)
• Recognizing triangulated Cartesian graph products
• Extended formulations for matroid polytopes through randomized protocols

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)