English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Tools annual

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Tools monthly

Global: Zendy Plus monthly

Presents the access of premium content as premium feature

Premium Content

Global: Zendy Plus annual

Global: Zendy Free Plan

In this paper, we study algorithmic questions concerning products of matricesand their consequences for recognition algorithms for polyhedra.  The 1-product of matrices $S_1$, $S_2$ is a matrix whose columns are theconcatenation of each column of $S_1$ with each column of $S_2$. The$k$-product generalizes the $1$-product, by taking as input two matrices $S_1,S_2$ together with $k-1$ special rows of each of those matrices, and outputtinga certain composition of $S_1,S_2$.  Our study is motivated by a close link between the 1-product of matrices andthe Cartesian product of polytopes, and more generally between the $k$-productof matrices and the glued product of polytopes. These connections rely on theconcept of slack matrix, which gives an algebraic representation of classes ofaffinely equivalent polytopes. The slack matrix recognition problem is theproblem of determining whether a given matrix is a slack matrix. This is anintriguing problem whose complexity is unknown. Our algorithm reduces theproblem to instances which cannot be expressed as $k$-products of smallermatrices.  In the second part of the paper, we give a combinatorial interpretation of$k$-products for two well-known classes of polytopes: 2-level matroid basepolytopes and stable set polytopes of perfect graphs. We also show that theslack matrix recognition problem is polynomial-time solvable for suchpolytopes. Those two classes are special cases of $2$-level polytopes, forwhich we conjecture that the slack matrix recognition problem ispolynomial-time solvable.

Slack matrices, $k$-products, and $2$-level polytopes