[Math] Dimension of polyhedron defined by inequalities and rank of implied equalities

linear algebralinear programmingoptimizationpolyhedra

I'm looking at "Optimization Over Integers" by Bertsimas and Weismantel and I have a question about one of the examples in the book. I'm getting a conflicting answer and I'm not sure what I'm misunderstanding. Also, as far as I know, there is no published errata for the book.

On page 555, Proposition A.4 states that

If $P = \{\mathbf{x} \in \mathbb{R}^n | \mathbf{Ax \geq b}\} \neq \emptyset$ and $ P \subset \mathbb{R}^n$, then $\dim(P) + rank(A^=,b^=) = n$

where $(\mathbf{ A^=x\geq b^=})$ are the subset of inequalities of $\mathbf{Ax \geq b}$ which are satisfied at equality for any feasible $\mathbf{x}$.

First, the error may be that I'm misinterpreting $rank(A,b)$. I can't find a definition in the book, but I'm assuming that the $(A,b)$ notation means the $m \times n + 1$ matrix made by appending $b$ as a column of $A$.

Now, the example from the book works out that the dimension of the following polyhedron is 2:

$x_1 + x_2 + x_3 \geq 2$

$x_1 + x_2 \leq 1$

$x_3 \leq 1$

$x_1 \leq \frac{1}{2}$

$x_1, x_2, x_3 \geq 0$

The reasoning in the book is that adding the second and third constraints gives $x_1 + x_2 + x_3 \leq 2$. Combining with constraint 1 gives $x_1 + x_2 + x_3 = 2$. This is one constraint that is satisfied at equality for all feasible solutions, and $rank(A^=, b^=) = 1$. By Proposition A.4 above, $\dim(P) = 3 – 1 = 2$.

Here's where I'm not getting it.

Negating the second constraint and adding it to the first, we get $x_3 \geq 1$, and so constraint $x_3 \leq 1$ is always satisfied at equality. It's easy to verify that you can get feasible solutions with the other constraints all satisfied at strict inequality (interior points of the polyhedron).

Then $(A^=, b^=)$ is

\begin{bmatrix}
1 & 1 & 1 & 2 \\
0 & 0 & -1 & -1 \\
\end{bmatrix}

which has rank 2, so the dimension of $P = 3-2 = 1$. What am I doing wrong here?

Edit: More information. I used the software polymake to compute the dimension of the polyhedron, the output was dimension one.

If anyone is interested, the code

$inequalities=new Matrix<Rational>([[-2,1,1,1],[1,-1,-1,0],[1,0,0,-1],[1/2,-1,0,0],[0,1,0,0],[0,0,1,0],[0,0,0,1]]); 
    $p=new Polytope<Rational>(INEQUALITIES=>$inequalities);    
    print $p->DIM;

Best Answer

Your logic makes sense. P dimension has to be at least 3-2 since every point in it must satisfy two linear independent equalities in R3. Since P has more than one point, it's dim must be exactly one. You are right and the book wrong. The way to read math books is always with pen and pencil next and don't trust everything until you can replicate. :-)

Related Question