Which Nonnegative Matrices Are Slack Matrices?

2013/03/22 by João Gouveia, Roland Grappe, Gouveia, João +9
Mathematics · #FOS: Mathematics #Optimization and Control (math.OC) #math.OC

paper · pdf · doi:10.48550/arxiv.1303.5670

14 pages

arxiv created 2013/03/22 · arxiv updated 2013/03/25

Abstract

In this paper we characterize the slack matrices of cones and polytopes among all nonnegative matrices. This leads to an algorithm for deciding whether a given matrix is a slack matrix. The underlying decision problem is equivalent to the polyhedral verification problem whose complexity is unknown.

Related

• Slack matrices, k-products, and 2-level polytopes
• Recognizing Cartesian products of matrices and polytopes
• The cone of quasi-semimetrics and exponent matrices of tiled orders
• NP-hardness of polytope M-matrix testing and related problems
• On ranks of regular polygons