Real Polyhedra

Definition

A polyhedron (or real polyhedron, or convex polyhedron) is a set $P \subset \R ^n$ for which there exists $A \in \R ^{m \times n}$ and $b \in \R ^{m}$ satisfying

\[ P = \Set{x \in \R ^n}{Ax \leq b}. \]

In other words, a polyhedron is an intersection of finitely many halfspaces. If $A$ and $b$ are rational, then $P$ is called a rational polyhedron.

A polyhedron $P$ is a polytope (a real polytope) if it is bounded. In other words, there exists $x_0 \in P$ and $M > 0$ such that

\[ P \subset B_M(x_0) = \Set{x }{\norm{x - x_0} < M} \]

Here $B_M(x_0)$ denotes the open ball of radius $M$, as usual.

As usual, the dimension of a polyhedron $P$ is the dimension of the affine hull of $P$, which we denote by $\dim P$. $P$ is called full-dimensional if $\dim P = n$. An equivalent condition for $P$ to be full-dimensional is that there exist an interior point of $P$ (as a subset of $\R ^n$)

Terminology

Caution: some authors have a more relaxed notion of polyhedra, which does not require the polyhedra be convex.