Dimension, Polyhedra and Faces
John Mitchell

Definition 1   A set is a subspace of if every linear combination of points in S is also in S.

Definition 2   A point is an affine combination of x and y if for some . (Note that we do not require .)

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

Definition 4   The points are affinely independent if the vectors are linearly independent.

Definition 5   Given a scalar and a vector , the set 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 . Let . If for all 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.

John E Mitchell
2001-02-05