**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*