Tropical determinant of integer doubly-stochastic matrices

DOI10.1016/J.LAA.2011.07.033MaRDI QIDQ665944zbMATH OpenOpenAlexFDO

Authors Thomas Dinitz, Matthew Hartman, Evgenia Soprunova

Publication date 7 March 2012

Published in Linear Algebra and its Applications (Search for Journal in Brave)

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

zbMATH Keywords

bi-stochastic matricesBirkhoff polytopeinteger linear programmingtropical determinant

Mathematics Subject Classification ID

Determinants, permanents, traces, other special matrix functions (15A15) Stochastic matrices (15B51) Special polytopes (linear programming, centrally symmetric, etc.) (52B12) Integer programming (90C10)

Abstract: Let D(m,n) be the set of all the integer points in the m-dilate of the Birkhoff polytope of doubly-stochastic n by n matrices. In this paper we find the sharp upper bound on the tropical determinant over the set D(m,n). We define a version of the tropical determinant where the maximum over all the transversals in a matrix is replaced with the minimum and then find the sharp lower bound on thus defined tropical determinant over D(m,n).

Review text

The authors find a sharp upper bound of the set \(D(m,n)\) of all the integer points in the \(m\)-dilate of the Birkhoff polytope of bi-stochastic \(n\times n\)-matrices. They introduce a version of the tropical determinant where the maximum over all the transversals in a matrix is replaced with the minimum and then find a sharp lower bound on thus defined tropical determinant over \(D(m,n)\).

Recommendations

• Tropical determinant on transportation polytopes
• scientific article; zbMATH DE number 5024404
• Minimizing the permanent over some faces of the polytope of doubly stochastic matrices
• Permanents of doubly stochastic matrices with diagonal submatrices of fixed order.
• MINIMUM PERMANENTS OF DOUBLY STOCHASTIC MATRICES WITH k DIAGONAL p×p BLOCK SUBMATRICES

Cites work

• Assignment Problems
• Max algebra and the linear assignment problem
• On Representatives of Subsets
• Proof of the van der Waerden conjecture regarding the permanent of a doubly stochastic matrix
• The solution of van der Waerden's problem for permanents

Cited in

(1)

• Tropical determinant on transportation polytopes

This page was built for publication: Tropical determinant of integer doubly-stochastic matrices

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