For a nonnegative matrix -matrix , its **nonnegative rank** is the smallest integer for which there exist nonnegative matrices and with columns such that . Expanding the product, this is the same as the minimum number of nonnegative rank-1 matrices which sum up to :

The expression is called a **nonnegative factorization of size ** of .

Recall that the extension complexity of a (convex) polyhedron is the minimum number of facets of a polyhedron for which there exists a projective mapping which maps *onto(!)* .

In this post I would like to cover the relationship between the **nonnegative rank** of a nonnegative matrix and **extension complexity** of a polyhedron . As it turns out, the extension complexity of is just the nonnegative rank of the so-called **slack matrix** of (or, more accureately, *any* slack matrix).

This essentially goes back to Yannakakis’ 1991 paper Expressing combinatorial optimization problems by linear programs.

** The slack matrix **

The central object linking extension complexity of polyhedra and nonnegative rank is the **slack matrix**. Let the polyhedron be given by a system of linear inequalities

where each is an affine function , and the are in ; and also by a set of points and vectors , i.e.,

where denotes the convex set generated by and denotes the convex cone generated by . Let , and consider the -matrix defined by

This matrix is called a **slack matrix** of with respect to the systems (2) and (3).

** Nonnegative factorizations of the slack matrix and extensions of the polyhedron **

The following is the central fact of this post.

- Every nonnegative factorization of of size gives rise to an extension of with at most facets.
- Every extension of with facets gives rise to a nonnegative factorization of of size at most .

In particular, .

** Some remarks about the nonnegative factorization **

In the “linear” case, we know that row- or column-operations does not change the rank of a matrix. The same is true for the nonnegative rank — but only “nonnegative” row- and column-operations are allowed. A **nonnegative column operation** is one of the following:

- multiplying a row by a strictly positive scalar,
- adding a nonnegative multiple of one row to another row,
- adding a new row to the matrix, all of whose entries are 0.

Nonnegative column-operations are defined similarly. The following is an easy exercise.

Lemma 2If the matrix results from by a series of nonnegative row- and column-operations, then for every nonnegative factorization of of size , there is a nonnegative factorization of of size , and vice versa.

In particular, .

** A (projective) extension gives a factorization **

We now prove the first part of Theorem 1. We first deal with the basic case when is a polyhedral cone, the are all zero, and the projections are required to be linear. After that, we will reduce the general cases to this one.

Suppose that is a polyhedral cone which is not a point. This implies that must be among the points , and for all . By Lemma 2, we may assume that and . Deleting the corresponding 0-column, we arrive at and we are interested in nonnegative factorizations of the -matrix defined as .

We first prove that an extension with linear projection mapping gives rise to a nonnegative factorization of appropriate size. Suppose that there is a polyhedron and a linear mapping which maps onto . By a translation, we may assume that . Denoting by the adjoint linear mapping, the linear inequalities are valid for . Moreover, since these inequalites are satisfied with equality by the point , for example, by Farkas’ Lemma, is a nonnegative linear combination of linear functions for which the inequality define a facet of :

Choosing for every a with , we conclude

if we let and . Thus we have a nonnegative factorization whose size is no larger than the number of facets of .

Secondly, we need to show that the general case ( a polyhedron and the projection allowed to be projective) is implied by the cone/linear case. This is done easily by homogenization. Saying that is projective with is the same as saying that arises from a linear mapping which maps onto . But then also maps the homogenization of onto the homogenization of . A factorization of a slack matrix of is also a slack matrix of .

** A factorization gives an affine extension **

Here we prove that every nonnegative factorization of the slack matrix of a polyhedron gives rise to an extension. Indeed, if , then define the polyhedron

and the projection . Clearly, if then and so satisfies for all , which implies that (because the system (2) defines ).

To see that maps *onto* , denote the rows of by . Then, for we have

To show that contains , we prove that that for all , and for all and . But for by (8), and follows form the linearity of and by (8) for and (9).

[…] This posts summarizes some my favorite open problems about the nonnegative rank of matrices and related concepts like extension complexity of polytopes. […]

16 August 2011at9am