Home

This Polymake extension enables the user to carry out the mapping of a polytope Q via a linear map pi, resulting in a polytope P = pi(Q). In such a scenario, Q (along with pi) is called an extension (extended formulation) of P.

The slack matrix of a polytope P (given by facets a_i^tx + b_i >= 0 for i=1,2,...,m and vertices v in V) is an m x |V| matrix with entries S_{i,v} = a_i^tv + b_i.

A nonnegative matrix factorization of S is a factorization S = T * U such that T and U are nonnegative matrices. The nonnegative rank of the matrix S is the minimal width of T (which equals the height of U) in a factorization.

For every extended formulation P = pi(Q) there exists a nonnegative factorization of S such that the rank is equal to #facets(Q). On the other hand, every nonnegative factorization of S implies the existance of an extension Q with the same property.

This Polymake extension provides functionality to compute the slack matrix of a polytope, carry out such a projection yielding the two factors and constructing an extension from a given factorization.

To install the extension, simply download the current version, extract it and carry out the following command from within Polymake:

import_extension ("/unpacked/directory/");