6 JOONIL KIM

Definition 2.4. Let B = {q1, · · · , qM } ⊂

Rn.

Then the span of B is the set

Sp(B) =

⎧

⎨

⎩

M

j=1

cjqj : cj ∈ R

⎫

⎬

⎭

.

The convex span of B and its interior are defined by

CoSp(B) =

⎧

⎨

⎩

M

j=1

cjqj : cj ≥ 0

⎫

⎬

⎭

and

CoSp◦(B)

=

⎧

⎨

⎩

M

j=1

cjqj : cj 0

⎫

⎬

⎭

respectively. Finally the convex hull of B is the set

Ch(B) =

⎧

⎨

⎩

M

j=1

cjqj : cj ≥ 0 and

M

j=1

cj = 1

⎫

⎬

⎭

.

If B ⊂ Rn is not a finite set, then the span of B is defined by the collection of all

finite linear combinations of vectors in B.

Definition 2.5 (Ambient Space of Polyhedron). Let P ⊂

Rn

and p, q ∈ P.

Then

Sp(P − p) = Sp(P − q) for all p, q ∈ P.

We denote the vector space Sp(P − p) by V (P). The dimension of P is defined by

dim(P) = dim(V (P)).

From the fact p − q ∈ V (P),

V (P) + p = V (P) + q.

We call V (P) + p the ambient aﬃne space of P in Rn and denote it by Vam(P) :

Vam(P) = V (P) + p, (2.1)

which is the smallest aﬃne space containing P.

Example 2.2. Let P be the polyhedron defined in Example 2.1. Then V (P) =

{y : e1 + e2 + e3, y = 0} and Vam = {y : e1 + e2 + e3, y = 1}.

Definition 2.6. Let B ⊂

Rn.

Then the rank of a set B is the number of

linearly independent vectors in B:

rank(B) = dim(Sp(B)).