Recognizing cartesian products of matrices and polytopes

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

Research output: Chapter in Book/Report/Conference proceedingConference PaperResearch

2 Citations (Scopus)

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.

Original languageEnglish
Title of host publicationGraphs and Combinatorial Optimization: from Theory to Applications
Subtitle of host publicationCTW2020 Proceedings
EditorsClaudio Gentile, Giuseppe Stecca, Paolo Ventura
Place of PublicationCham Switzerland
PublisherSpringer
Pages361-373
Number of pages13
ISBN (Electronic)9783030630720
ISBN (Print)9783030630713
DOIs
Publication statusPublished - 2021

Publication series

NameAIRO Springer Series
Volume5
ISSN (Print)2523-7047
ISSN (Electronic)2523-7055

Keywords

  • 2-level polytopes
  • Cartesian product
  • Mutual information
  • Slack matrix
  • Submodular optimization

Cite this