How to calculate the dimension of a convex polyhedron?

While there are probably much more efficient approaches, the following method can be used to compute the dimension in polynomial time, and is not too complicated.

Implicit inequalities

The dimension of a polyhedron $P$ is defined as the dimension of its affine hull, i.e. $dim P := dim mathrm{aff}(P)$.

Let $a^i x leq b_i$ for $iin M$ be the linear inequalities that compose the system $A xleq b$ defining $P$. An inequality $a^i x leq b_i$ is called an implicit inequality of this system if $a^i x = b_i$ for all $x$ such that $A xleq b$. Let $A^= xleq b^=$ denote the subsystem of $Axleq b$ that consists only of the implicit inequalities in $Axleq b$. Now, we have the folllowing theorem:

Let $P = {xin mathbb{R}^n mid Axleq b}$ be a nonempty¹ polyhedron. Then, $mathrm{aff}(P) = {x mid A^= x= b^=} = {x mid A^= xleq b^=}$. Additionally, $dim P = n - mathrm{rank} A^=$.

(see Theorem 3.17 from Integer Programming by Conforti, Cornuéjols, and Zambelli. Chapter 3.8 contains additional examples for computing the dimension by hand)

So, to compute the dimension of $P$, we first find all implicit inequalities to obtain $A^=$, and then compute the rank of $A^=$. The latter is easy to do, but the first can be rather complicated to do in general (although it is often doable 'by hand' for well structured cases).

Finding implicit inequalities via linear programming

Note that an inequality $a^i x leq b_i$ is implicit if and only if the hyperplane $a^i x = b_i$ (i.e. the 'border' of the halfspace defined by the inequality) contains $P$. We can determine whether this is the case by solving a pair of linear programs (thanks to @plop for pointing this out). The inequality $a^i x leq b_i$ is implicit if and only if

$$max {a^i x mid Axleq b} = min {a^i x mid Axleq b} = b_i,$$

or in other words when optimizing within $P$ in the directions of $a^i$ and $-a^i$ both yields the value $b_i$.

To see why this is true, first note that if either of the results of these programs give a value other than $b_i$, we have found some $xin P$ with $a^i x neq b^i$, so the inequality is not implicit².

For the other implication, any point $x'in P$ that lies outside the hyperplane $a^i x =b_i$ lies inside the hyperplane $a^i x = b'_i$ for some $b'_ineq b_i$. If $b'_i < b_i$, then $min {a^i x mid Axleq b} leq a^i x' = b'_i < b_i$, and if $b'_i > b_i$, then $max {a^i x mid Axleq b} > b_i$. So at least one of the linear programs gives a value unequal to $b_i$ if $a^i x leq b$ is not implicit.

The algorithm

So, a possible algorithm for finding the dimension of $P$ in $mathbb{R}^n$ when given by a system of $m$ inequalities is

1. Solve $2m$ linear programs to find the implicit inequalities and $A^=$.
2. Compute the rank $r$ of $A^=$, and return $n-r$.

Linear programs can be solved in polynomial time via e.g. the interior point method (although the simplex method is much faster in practice), and the rank of a matrix can be computed in polynomial time via Gaussian elimination. So, the dimension of a polyhedron can be computed in polynomial time.

As I mentioned earlier, there are probably much better approaches than what I suggest here. The suggestions offered by @plop in the comments look promising and I recommend anyone looking for something better than what I'm suggesting here to follow them through, but I will end my answer here, it is already long enough.

---

(The first part of this answer is taken from these slides by Rudi Pendavingh , page 8)

---

_{1: If $P$ is empty, then its dimension is $0$. Additionally, we can test whether $P$ is empty via linear programming. So, we can and I will assume that $P$ is non-empty for the remainder of this answer.
2: It may happen that the minimization and maximization program give the same value, but a different one than $b_i$. (Try to think of an example!) In this case, the inequality must be redundant: it can be removed from the system without changing $P$.}