Dimension, Polyhedra and Faces
John Mitchell

Definition 1   A set $S \in I\!\!R^n$ is a subspace of $I\!\!R^n$ if every linear combination of points in S is also in S.

Definition 2   A point $z \in I\!\!R^n$ is an affine combination of x and y if $z=\lambda x + (1-\lambda)y$ for some $\lambda\in I\!\!R$. (Note that we do not require $0 \leq \lambda \leq 1$.)

Definition 3   A set M is affine if every affine combination of points in M is also in M.

Definition 4   The points $a^1,\ldots,a^k$ are affinely independent if the vectors $a^2-a^1,a^3-a^1,\ldots,a^k-a^1$ are linearly independent.

Definition 5   Given a scalar $\alpha$ and a vector $a\in I\!\!R^n$, the set $\{x:a^Tx \geq \alpha\}$ is a halfspace.

Definition 6   A polyhedron is a finite intersection of halfspaces.

Note that the feasible region of a linear programming problem is a polyhedron.

Definition 7   The dimension of a subspace is the maximum number of linearly independent vectors in it.

Proposition 1   Every affine space is a translation of a subspace. Further, the subspace is uniquely defined by the affine space.

Definition 8   The dimension of an affine space is the dimension of the corresponding subspace.

Definition 9   The affine hull of a set is the set of all affine combinations of points in the set. This is equivalent to the intersection of all affine sets containing the set.

Definition 10   The dimension of a polyhedron is the dimension of its affine hull.

Definition 11   Let P be a polyhedron. Let H be the hyperplane $H:=\{x:a^Tx=\alpha\}$. Let $Q=P \cap H$. If $a^Tx \geq \alpha$ for all $x \in P$ then Q is a face of P.

Definition 12   Let P be a polyhedron of dimension d. A face of dimension d-1 is a facet. A face of dimension 1 is an edge. A face of dimension 0 is a vertex.