Rank Of A Slack Matrix

Recall that the rank of a nonzero $p \times q$ matrix $M$ is the least positive integer $r$ such that $M=AB$ where $A$ is a $p \times r$ matrix and $B$ is a $r \times q$ matrix. Argue that the rank of a slack matrix of a $n$-dimensional polytope in $\mathbb{R}^n$ is $n+1$.


Solution:

Suppose $P$ is an $n$-dimensional polytope in $\mathbb{R}^n$ with defining inequalities $a_j \cdot x \leq b_j$ such that $\{x \in P | a_j \cdot x = b_j\}$ defines a facet of $P$ for each $j=1, \ldots, f$. Let $v_1, \ldots, v_m$ denote the vertices of $P$. Let $M$ be the slack matrix of $P$, that is:

$M_{i,j} = b_j - a_j \cdot v_i$.

First, note that the rank of $M$ is at most $n+1$ because

$M = AB$ where

$A = \begin{pmatrix} -v_1^t & 1\\ \vdots & \vdots \\-v_m^t & 1 \end{pmatrix}$, $B=\begin{pmatrix} a_1& \ldots & a_f\\b_1 & \ldots & b_f \end{pmatrix}$.

In order to show that the rank is no smaller than $n+1$, it suffices to show that $A$ and $B$ (as linear maps) are respectively injective and surjective.

Suppose that $A$ is not injective. Then the vertices of $P$ lie in a proper affine hyperplane and $P$ is not of full dimension $n$.

Suppose that $B$ is not surjective and choose $c \in \mathbb{R}^{n+1}$ nonzero such that $c \cdot \begin{pmatrix} a_j\\ b_j \end{pmatrix} =0, \forall j$. We denote the projection onto the first $n$ coordinates by $\pi_n(c) = (c_1,\ldots,c_n)^t \in \mathbb{R}^n$.

If $c_{n+1} = 0$, then $P$ is unbounded since we can add any multiple of the nonzero vector $\pi(c)$ to $P$ without leaving $P$. On the other hand, if $c_{n+1} \neq 0$, we can normalize and redefine $c_{n+1} = -1$. For this new $c$ we have that the projection $\pi_n(c)$ belongs to every facet of $P$. Again, this implies that $P$ is unbounded since for any point $x_0 \neq c$ of $P$ all combinations $x+t(x_0-c)$ with $t \geq 0$ and $x \in P$ belong to $P$. Since $P$ is a polytope, we've shown that $B$ must be surjective.-MH

Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-ShareAlike 3.0 License