Inferring dimension of a polyhedron from a point

Question

If we have a polyhedron $P = \{x\in\mathbb{R}^n \mid Ax \leq b \}$, and we find a point $x\in P$ such that $x$ satisfies at least $n$ of the $Ax\leq b$ (linearly independent) inequalities strictly, then does that mean that the dimension of $P$ is $n$?

More generally, if we can find a point $x\in P$ such that $x$ satisfies at least $k$ of the $Ax\leq b$ (linearly independent) inequalities strictly, then does that mean that the dimension of $P$ is at least $k$?

Answer 1

The answer is no, as the following examples show.

Example 1. Consider the polytope $P = \{x \in \mathbb{R}^n \, \mid \, Ax \leq b\}$, where $A \in \mathbb{R}^{4n \times n}$ and $b \in \mathbb{R}^{4n}$ are given by the block matrices $$ A = \begin{pmatrix} I_n \\ -I_n \\ I_n \\ -I_n \end{pmatrix}, \qquad b = \begin{pmatrix} 0 \\ 0 \\ \pmb{1} \\ \pmb{1} \end{pmatrix}, $$ where $I_n$ is the $n \times n$ identity matrix and $\pmb{1}$ is the $n$-dimensional all-ones vector. In other words:

• The first $n$ inequalities read $x_i \leq 0$ for all $i \in [n]$;
• The next $n$ inequalities read $-x_i \leq 0$ for all $i \in [n]$;
• The next $n$ inequalities read $x_i \leq 1$ for all $i \in [n]$;
• The last $n$ inequalities read $-x_i \leq 1$ for all $i \in [n]$.

It is easy to see that $P = \{0\}$. Note that $0 \in P$ satisfies the last $2n$ inequalities strictly, and $n$ of these are linearly independent. Yet $P$ is $0$-dimensional, so your statement fails dramatically.

The preceding example is somewhat contrived, because the last $2n$ inequalities are redundant and can be removed. The following example shows that your statement might still fail if no single inequality can be removed.

Example 2. Consider the polytope $P = \{x \in \mathbb{R}^2 \, \mid \, Ax \leq b\}$, where $A \in \mathbb{R}^{4 \times 2}$ and $b \in \mathbb{R}^4$ are given by $$ A = \begin{pmatrix} -1 & 0 \\ 0 & 1 \\ 1 & -1 \\ -1 & 1 \end{pmatrix}, \qquad b = \begin{pmatrix} 0 \\ 1 \\ 0 \\ 0 \end{pmatrix}. $$ The first inequality reads $x_1 \geq 0$, the second inequality reads $x_2 \leq 1$, and the last two inequalities read $x_1 = x_2$. So $P = \{(t,t) \, \mid \, t \in [0,1]\}$ is $1$-dimensional. Nevertheless, the first two inequalities are linearly independent, and they are strict for the point $(\frac{1}{2},\frac{1}{2}) \in P$.

In the second example, I don't think there is another half-space representation of the same polytope such that every point of $P$ satisfies at most one inequality strictly. However, you can replace the inequality $x_2 \leq 1$ by the inequality $x_1 \leq 1$, and then the two inequalities that are strict for the point $(\frac{1}{2},\frac{1}{2})$ are linearly dependent. I think you can do something similar for a general polyhedron. In any case, my examples show that the answer depends on the halfspace-representation of $P$.