The polytope of even doubly stochastic matrices

DOI10.1016/0097-3165(91)90048-LMaRDI QIDQ1175954zbMATH OpenFDO

Authors Richard A. Brualdi, Bolian Liu

Publication date 25 June 1992

Published in Journal of Combinatorial Theory. Series A (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0097-3165(91)90048-L

zbMATH Keywords

algorithmcounterexampleeven doubly stochastic matrixeven permutationspermanentpolyhedral combinatorics

Mathematics Subject Classification ID

Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Stochastic matrices (15B51) Special polytopes (linear programming, centrally symmetric, etc.) (52B12)

Review text

An even doubly stochastic matrix is even if it is the convex combination of even permutation matrices. This paper studies the combinatorial structure of the polytope of these matrices of a fixed order \(n\). For \(n\geq 4\) the dimension is \((n-1)^ 2\). Five families of valid independent inequalities (necessary conditions) and one sufficient condition are derived. A characterization of the pairs of even permutations defining an edge of the polytope is obtained, from which it follows that for \(n\geq 4\) any two vertices may be joined by an edge path of length 2. A counterexample shows that a well-known algorithm for expressing a doubly stochastic matrix as a convex combination of permutation matrices fails for the even case. Finally it is conjectured that the number of faces is exponential and that a certain lower bound holds for the permanent of any even doubly stochastic matrix.

Recommendations

• scientific article; zbMATH DE number 599459
• Even and odd diagonals in doubly stochastic matrices
• A characterization of even doubly-stochastic matrices
• Some facets of the polytope of even permutation matrices.
• Minimizing the permanent over some faces of the polytope of doubly stochastic matrices

Cites work

• Convex polyhedra of doubly stochastic matrices. I: Applications of the permanent function
• Even doubly-stochastic matrices
• Notes on the Birkhoff Algorithm for Doubly Stochastic Matrices
• On a theorem of L. Mirsky on even doubly-stochastic matrices

Cited in

(21)

• A characterization of even doubly-stochastic matrices
• On a theorem of L. Mirsky on even doubly-stochastic matrices
• Some facets of the polytope of even permutation matrices.
• Faces of Birkhoff Polytopes
• Partitions of the polytope of doubly substochastic matrices
• On the even permutation polytope
• Singular values, doubly stochastic matrices, and applications
• Symmetric, Hankel-symmetric, and centrosymmetric doubly stochastic matrices
• Ehrhart series of polytopes related to symmetric doubly-stochastic matrices
• Comments on a Paper of R. A. Brualdi
• scientific article; zbMATH DE number 599459 (Why is no real title available?)
• scientific article; zbMATH DE number 772773 (Why is no real title available?)
• On a Special Class of Generalized Doubly Stochastic Matrices and Its Relation to Bézier Polygons
• On the Volume of the Polytope of Doubly Stochastic Matrices
• scientific article; zbMATH DE number 2237620 (Why is no real title available?)
• A note on certain subpolytopes of the assignment polytope associated with circulant graphs
• 123-avoiding doubly stochastic matrices
• On the permutation polytopes of some cyclic groups
• On permutation polytopes
• Permutation polytopes and indecomposable elements in permutation groups
• Even and odd diagonals in doubly stochastic matrices

This page was built for publication: The polytope of even doubly stochastic matrices

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