Faces of the signed Birkhoff polytopes
A \textit{signed permutation matrix} is a \(n\mathord{\times}n\) matrix with coefficients in \(\{-1,0,1\}\) that admits exactly one non-zero entry in each row and in each column. One recovers permutation matrices by replacing every \(-1\) by a \(1\) in a signed permutation matrix. Reorganising the entries of (signed) permutation matrices into vectors from \(\{-1,0,1\}^{n^2}\), one can define the Birkhoff polytope \(\Omega_n\) as the convex hull of all the permutation matrices and the signed Birkhoff polytope \(\Omega_n^\pm\) as the convex hull of all the signed permutation matrices. Note that \(\Omega_n\) has dimension \((n-1)^2\) because the rows and columns of a permutation matrix sum to \(1\) but no such relation exists for a signed permutation matrix and therefore \(\Omega_n^\pm\) has dimension \(n^2\).\N\N\textit{G. Birkhoff} [Univ. Nac. Tucuman. Revista A. 5, 147--151 (1946; Zbl 0060.07906)] has shown that the vertices of \(\Omega_n\) are precisely the permutation matrices and \textit{L. Mirsky} [Arch. Math. 10, 88--92 (1959; Zbl 0088.25105)] has given a similar statement for the intersection of \(\Omega_n^\pm\) with the non-negative orthant.\N\NIn this paper, the authors provide a description of all the faces of the signed Birkhoff polytope by encoding them bijectively as \textit{facial matrices}, matrices with coefficients in \(\{0,1,-1,\pm1\}\) that satisfy certain additional properties. Given a face \(F\) of \(\Omega_n^\pm\) and the corresponding facial matrix \(A\), one can recover the signed permutation matrices contained in \(F\) by replacing a subset of the entries of \(A\) equal to \(1\) or \(-1\) by \(0\) and by replacing the entries equal to \(\pm1\) by \(-1\), \(0\), or \(1\). Moreover, the number of vertices of \(F\) is the permanent of the matrix obtained from \(A\) by replacing the entries equal to \(-1\) and \(\pm1\) by \(1\) and \(2\), respectively. The face lattice of \(\Omega_n^\pm\) can also be recovered from a corresponding lattice on the facial matrices.\N\NThe article also study the facial matrices that correspond to the edges, the \(2\)-dimensional faces, and the facets of \(\Omega_n^\pm\). This allows to show that the \(2\)-dimensional faces of \(\Omega_n^\pm\) are either triangles or rectanges and that the edge-graph of \(\Omega_n^\pm\) is a diameter \(2\) Hamiltonian graph. Finally, the authors recover a result by \textit{F. Kohl} et al., [Discrete Comput. Geom. 64, No. 2, 427--452 (2020; Zbl 1454.52012)] whereby \(\Omega_n^\pm\) admits regular unimodular triangulation.
- Binomial ideals
- Birkhoff's theorem and convex hulls of Coxeter groups
- Combinatorial matrix classes
- Concerning nonnegative matrices and doubly stochastic matrices
- Convex polyhedra of doubly stochastic matrices III. Affine and combinatorial properties of
- Convex polyhedra of doubly stochastic matrices. I: Applications of the permanent function
- Convex polyhedra of doubly stochastic matrices. II: Graph of Omega sub(n)
- Convex polyhedra of doubly stochastic matrices. IV
- Faces of Birkhoff Polytopes
- Faces of the polytope of doubly substochastic matrices
- scientific article; zbMATH DE number 3804333 (Why is no real title available?)
- scientific article; zbMATH DE number 1857822 (Why is no real title available?)
- scientific article; zbMATH DE number 835749 (Why is no real title available?)
- scientific article; zbMATH DE number 848091 (Why is no real title available?)
- scientific article; zbMATH DE number 2237620 (Why is no real title available?)
- scientific article; zbMATH DE number 3095897 (Why is no real title available?)
- Lectures on Polytopes
- On a convex set of matrices
- On the Assignment Polytope
- Quadratic Gröbner bases for smooth \(3\times 3\) transportation polytopes
- The Distribution of Positive Elements in Doubly-Stochastic Matrices
- Triangulations. Structures for algorithms and applications
- Unconditional reflexive polytopes
This page was built for publication: Faces of the signed Birkhoff polytopes
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6908603)
