text:
\def\scalefactor{.3}
\def\colorAB{blue}
\def\colorBC{magenta}
\def\colorCA{black}
\def\colorA{orange}
\def\colorB{gray}
\def\colorC{yellow}
\def\opazero{0.5}
\def\colordot{red}
\def\colorzero{green}
\def\colorone{blue}
\def\colortwo{black}
\def\colornu{purple}
\def\picfontsize{\small}

A ``polytope'' has two equivalent definitions: a convex hull of finitely many points, or a bounded intersection of finitely many ``half spaces.'' In \cref{basic-convex-section,poly-characterizection} we prove the equivalence of these definitions after introducing the basic terminology. The rest of the chapter is devoted to different properties of polytopes which are implicitly or explicitly used in the forthcoming chapters.

\section{Basic notions} \label{basic-convex-section}
In this chapter we treat the spaces $\rr^n$, $n \geq 0$, as vector spaces over $\rr$ equipped with the Euclidean topology, and deal only with ``affine maps'' between these spaces. Recall that a map $\phi: \rr^n \to \rr^m$ is {\em affine} if there is $\beta \in \rr^m$ such that $\phi(\cdot) = \beta + \phi_0(\cdot)$ for some {\em linear} map $\phi_0: \rr^n \to \rr^m$. Given $S \subset \rr^n$ and $T \subset \rr^m$, and a map $\phi: S \to T$, we say that $\phi$ is {\em affine} if it is the restriction of an affine map from $\rr^n \to \rr^m$; we say that $\phi$ is an {\em affine isomorphism} if $\phi$ is affine and bijective. An {\em affine subspace} $A$ of $\rr^n$ is a subset of $\rr^n$ which is the image of an affine map; in other words it is simply a translation of a linear subspace $L$ of $\rr^n$. The {\em dimension} $\dim(A)$ of $A$ is the dimension of $L$ as a vector space over $\rr$. A {\em hyperplane} in $\rr^n$ is an affine subspace of dimension $n-1$. The {\em affine hull} $\aff(S)$ of a set $S$ of $\rr^n$ is the smallest affine subspace of $\rr^n$ containing $S$; alternatively, if $L$ is the linear subspace of $\rr^n$ spanned by all elements of the form $\alpha - \beta$ such that $\alpha, \beta \in S$, then $\aff(S) = L + \alpha$ for any $\alpha \in S$. In \cref{fig:min-max}, it is straightforward to check that $\aff(S) = \rr^2$, $\aff(\{C\}) = \{C\}$, and since $A, B, E$ are collinear, $\aff(\{A,B, E\})$ is the (unique) line $L$ through these points.

\begin{figure}[h]
\def\xmin{-0.5}
\def\xmax{16.5}
\def\ymin{-4.5}
\def\ymax{5.5}
\def\tx{0}
\def\ty{5}
\def\tw{5cm}

\tikzstyle{dot} = [\colordot, circle, minimum size=4pt, inner sep = 0pt, fill]

\begin{center}

\begin{tikzpicture}[scale=\scalefactor]

\node[dot] (A) at (1,-4) {};
\node[dot] (B) at (16,1) {};
\node[dot] (C) at (10,5) {};
\draw[thick, \colorone, fill=\colorzero, opacity=\opazero ] (A.center) --  (B.center) -- (C.center) -- cycle;
\node[dot] (D) at (11,1) {};
\node[dot] (E) at (7,-2) {};
\coordinate (nu) at (1,-3);
\coordinate (nuperp) at (3,1);

\node[anchor = north] at (A) {\picfontsize $A$};
\node[anchor = north] at (B) {\picfontsize $B$};
\node[anchor = south] at (C) {\picfontsize $C$};
\node[anchor = east] at (D) {\picfontsize $D$};
\node[anchor = north] at (E) {\picfontsize $E$};

\draw[thick, \colortwo] ($(A)-(nuperp)$) --  ($(B)+(nuperp)$);
\coordinate (O) at ($(A)!0.5!(B)$);
\draw [thick, \colornu, ->] (O) -- ($(O) + 0.4*(nu)$);
\node[anchor = north] at ($(O) + 0.4*(nu)$) {\picfontsize $\nu$};
\node[anchor = north] at ($(B)+(nuperp)$) {\picfontsize $L$};

\draw[thick, \colortwo, dashed] ($(A)-(nuperp)-1.8*(nu)$) --  ($(B)+(nuperp)-1.8*(nu)$);
\draw [thick, \colornu, ->] ($(O)-1.8*(nu)$) -- ($(O) - 1.4*(nu)$);
\end{tikzpicture}

\caption{
	$S = \{A, B, C, D, E\}$, $\In_\nu(S) = \{C\}$, $\ld_\nu(S) = \{A, E, B\}$

} \label{fig:min-max}
\end{center}
\end{figure}
It is straightforward to check that an affine map preserves affine subspaces, affine hulls, and if the map is injective, then also the dimension of affine hulls (\cref{exercise:affine-image}). Given $\alpha \in \rr^n$ and $\nu \in \rnstar$, we write $\langle \nu, \alpha \rangle$ for the ``value of $\nu$ at $\alpha$,'' and write $\nu^\perp := \{\alpha \in \rr^n: \langle \nu, \alpha \rangle = 0\}$. Define
\begin{align*}
\min_S(\nu)
	&:= \min\{\langle \nu, \alpha \rangle: \alpha \in S\},\ \text{provided the minimum exists.} \\
\max_S(\nu)
	&:= \max\{\langle \nu, \alpha \rangle: \alpha \in S\},\ \text{provided the maximum exists.}  \\
\In_\nu(S)
	&:= \{\alpha \in S: \langle \nu, \alpha \rangle =  \min_S(\nu)\},\ \text{provided $\min_S(\nu)$ exists.}  \\
\ld_\nu(S)
	&:= \{\alpha \in S: \langle \nu, \alpha \rangle =  \max_S(\nu)\},\ \text{provided $\max_S(\nu)$ exists.}
\end{align*}
See \cref{fig:min-max} for an illustration of these notions for a planar set. Note that in \cref{fig:min-max} we depicted $\nu \in \rnnstar{2}$ on $\rr^2$ by identifying it with an element (modulo ``parallel translations'') in $\rr^2$ via the ``dot product.'' A set is {\em convex} if it contains the line segment joining any two points in it. The {\em convex hull} $\conv(S)$ of $S$ is the smallest convex set containing $S$. In \cref{fig:min-max} the convex hull of the $5$ points is the green triangle. Given $\alpha_1, \ldots, \alpha_k \in \rr^n$, an expression of the form $\sum_{j=1}^k \epsilon_j \alpha_j$, where the $\epsilon_j$ are nonnegative numbers whose sum is $1$, is called a {\em convex combination} of the $\alpha_j$. The set of convex combinations of two elements in $\rr^n$ is precisely the line segment joining them, and from this observation it can be shown that the convex hull of a set consists of the convex combinations of its points (\cref{exercise:conv-rep}), i.e.\
\begin{align}
\conv(S) = \{\sum_{j=1}^k \epsilon_j \alpha_j:
			k \geq 0,\
			\alpha_j \in S,\ \epsilon_j \geq 0\
			\text{for each}\ j,\ 1 \leq j \leq k,\
			\text{and}\ \sum_{j=1}^k \epsilon_j  = 1
		\}
\label{conv-rep}
\end{align}
Given a nonnegative real number $r$ and $S \subset \rr^n$, we define $rS := \{r\alpha : \alpha \in S\}$, i.e.\ $rS$ is the ``dilation of $S$ by a factor of $r$.'' We say that $S$ is a {\em cone} if it is ``dilation invariant,'' i.e.\ if $rS \subseteq S$ for each $r \geq 0$. The {\em convex cone generated by $S$} is defined to be
\begin{align}
\cone(S) := \{\sum_{j=1}^k \epsilon_j \alpha_j:
			k \geq 0,\
			\alpha_j \in S\
			\text{and}\ \epsilon_j  \geq 0\
			\text{for each}\ j,\ 1 \leq j \leq k
		\}
\label{cone-rep}
\end{align}
We say that $\cone(S)$ is {\em finitely generated} if $S$ is finite. A {\em convex polyhedron} $\scrP$ is a subset of $\rr^n$ defined by finitely many linear inequalities, i.e.\ inequalities of the form $a_0 +  a_1x_1 + \cdots + a_nx_n \geq 0$. Geometrically, a polyhedron is a finite intersection of ``half-spaces,'' where a ``half-space'' is the set of all points on one side of a hyperplane - see \cref{fig:two-hedra}. If $\scrP$ is bounded, we call it a convex {\em polytope}, and if it is a cone, we call it a convex {\em polyhedral cone}. A convex polyhedral cone is equivalently a set defined by finitely many linear inequalities with {\em zero} constant term (\cref{exercise:cone-inequalities}). In this book we only consider convex polyhedra, and therefore we will simply write ``polyhedra,'' ``polytopes,'' ``cones,'' ``polyhedral cones'' to mean ``convex polyhedra,'' ``convex polytopes,'' ``convex cones,'' ``convex polyhedral cones'' respectively. The {\em dimension} $\dim(\scrP)$ of a polyhedron $\scrP$ is the dimension of its affine hull. \Cref{fig:two-hedra} depicts a few two dimensional convex polyhedra.

\begin{center}
\begin{figure}[h]

\def\scalefactor{.3}

\def\tinyshift{0.05}
\def\xmin{-2}
\def\xmaxwithoutshift{8}
\pgfmathsetmacro{\xmax}{\xmaxwithoutshift+\tinyshift}
\def\ymin{-5}
\def\ymax{8}

\def\tx{0}
\def\ty{\ymin}

\def\xshift{5}
\xdefinecolor{c1}{HTML}{D4ACEE}
\xdefinecolor{c2}{HTML}{EEc6AC}
\xdefinecolor{c3}{HTML}{EDEEAC}

\tikzstyle{dot} = [\colordot, circle, minimum size=4pt, inner sep = 0pt, fill]

\begin{tikzpicture}[scale=\scalefactor]
\pgfmathsetmacro\shiftone{\xshift + \xmax -\xmin};

\coordinate (A) at (-2, -1);
\coordinate (B) at (3,-3);
\coordinate (C) at (7,1);
\coordinate (D) at (5,6);
\coordinate (E) at (1,4);

\draw[fill=\colorzero, opacity=\opazero ] (A) --  (B) -- (C) -- (D) -- (E) -- cycle;

\draw[thick, \colorone ] (A) --  (B) -- (C) -- (D) -- (E) -- cycle;

\draw (\xmax, 0) -- (\xmin, 0);
\draw (0, \ymax) -- (0, \ymin);

\node[dot] (O) at (0,0){};
\node[anchor = south west] at (O) {\picfontsize $(0,0)$};
\node[anchor = west] at (\xmax, 0) {\picfontsize $x$};
\node[anchor = south] at (0, \ymax) {\picfontsize $y$};

\node [below right, text width= 0.75cm, align=left] at (\tx,\ty) {
	\picfontsize
	Polytope
};

\begin{scope}[shift = {(\shiftone,0)}]
	\coordinate (A) at (-2, -1);

	\pgfmathsetmacro\Cy{-1 -0.4*(\xmax+2)};
	\coordinate (C') at (\xmax, \Cy);
	\coordinate (C') at (8,-5);

	\pgfmathsetmacro\Dy{4 + 0.5*(\xmax - 1)};
	\coordinate (D') at (\xmax, \Dy);
	\coordinate (E) at (1,4);

	\fill[\colorzero, opacity=\opazero ] (A) -- (C') -- (D') -- (E) -- cycle;

	\draw[thick, \colorone ] (A) -- (C');
	\draw[thick, \colorone ] (A) -- (E) -- (D');

	\draw (\xmax, 0) -- (\xmin, 0);
	\draw (0, \ymax) -- (0, \ymin);

	\node[dot] (O) at (0,0){};
	\node[anchor = south west] at (O) {\picfontsize $(0,0)$};
	\node[anchor = west] at (\xmax, 0) {\picfontsize $x$};
	\node[anchor = south] at (0, \ymax) {\picfontsize $y$};

	\node [below right, text width= 1.8cm, align=left] at (\tx,\ty) {
		\picfontsize
		Unbounded polyhedron
	};
\end{scope}

\begin{scope}[shift = {(2*\shiftone,0)}]

	\pgfmathsetmacro\Cy{-0.4*\xmax};
	\coordinate (C') at (\xmax,\Cy);

	\pgfmathsetmacro\Dy{0.5*\xmax};
	\coordinate (D') at (\xmax, \Dy);
	\coordinate (O) at (0,0);

	\pgfmathsetmacro\xmindiffed{\xmin + 2*\tinyshift};

	\foreach \x in {\xmin,\xmindiffed,...,\xmaxwithoutshift} {

		\draw[color=c2, ultra thin] (\x, \ymax) -- (\x,{-0.4*\x});
		\draw[color=c1, ultra thin] ({\x + \tinyshift}, \ymin) -- ({\x + \tinyshift}, {0.5*(\x + \tinyshift)});
	}
	\draw[color=c2] (\xmin, {-0.4*\xmin}) -- (\xmax, {-0.4*\xmax});
	\draw[color=c1] (\xmin, {0.5*\xmin}) -- (\xmax, {0.5*\xmax});

	\draw[thick, \colorone ] (O) -- (C');
	\draw[thick, \colorone ] (O) -- (D');

	\draw (\xmax, 0) -- (\xmin, 0);
	\draw (0, \ymax) -- (0, \ymin);

	\node[dot] (extra) at (O) {};
	\node[anchor = north] at (O) {\picfontsize $(0,0)$};
	\node[anchor = west] at (\xmax, 0) {\picfontsize $x$};
	\node[anchor = south] at (0, \ymax) {\picfontsize $y$};

	\node [below right, text width= 2.7cm, align=left] at (\tx,\ty) {
		\picfontsize
		Polyhedral cone
	};
\end{scope}

\end{tikzpicture}

\caption{
	Some planar convex polyhedra; ``half-planes'' defining the cone are also depicted.

} \label{fig:two-hedra}

\end{figure}
\end{center}

A {\em strongly convex cone} $\scrC$ is a convex cone which does not contain any line through the origin, equivalently, for all $\alpha \in \scrC\setminus \{0\}$, $-\alpha \not\in \scrC$. The {\em Minkowski sum} of two subsets $\scrP, \scrQ$ of $\rr^n$ is $\scrP + \scrQ := \{\alpha + \beta : \alpha \in \scrP,\ \beta \in \scrQ\}$. It is straightforward to check that the Minkowski sum of convex sets is also convex (\cref{exercise:minkonvex}); see \cref{fig:minkowski-sum} for some examples in $\rr^2$.  We now show that every convex polyhedral cone or finitely generated cone\footnote{We will see in \cref{poly-characterizection} that convex polyhedral cones and finitely generated cones are the same. However, we will use \cref{strongly-convex-prop} in the proof of this equivalence.} can be represented as the Minkowski sum of a linear subspace and a strongly convex cone.

\begin{figure}[h]
\begin{center}
\begin{tikzpicture}[scale=0.4]
\def\shifttwo{5}
\def\minx{-1.5}
\def\maxx{1.5}
\def\maxxx{1.5}
\def\miny{-1.5}
\def\maxy{1.5}
\def\tx{\minx}
\def\ty{\miny}
\def\bigshiftdhor{3}
\def\bigshiftdver{3}

\draw [gray,  line width=0pt] (\minx,\miny) grid (\maxx,\maxy);
\draw[ultra thick, \colorone] (0,0) -- (-1,1);

\node[anchor = west] at (\maxx, 0) {\picfontsize $x$};
\node[anchor = south] at (0, \maxy) {\picfontsize $y$};
\draw (\tx,\ty) node [below right] {\picfontsize $\scrP$};

\begin{scope}[shift={(\shifttwo,0)}]
	\def\tx{0}
	\draw [gray,  line width=0pt] (\minx,\miny) grid (\maxx,\maxy);
	\draw[ultra thick, \colorone] (0,0) -- (1,-1);

	\node[anchor = west] at (\maxx, 0) {\picfontsize $x$};
	\node[anchor = south] at (0, \maxy) {\picfontsize $y$};
	\draw (\tx,\ty) node [below right] {\picfontsize $\scrQ$};
\end{scope}

\begin{scope}[shift={(2*\shifttwo,0)}]
	\draw [gray,  line width=0pt] (\minx,\miny) grid (\maxx,\maxy);
	\draw[ultra thick, \colorone] (-1,1) -- (1,-1);

	\node[anchor = west] at (\maxx, 0) {\picfontsize $x$};
	\node[anchor = south] at (0, \maxy) {\picfontsize $y$};
	\draw (\tx,\ty) node [below right] {\picfontsize $\scrP+ \scrQ$};
\end{scope}

\begin{scope}[shift={(2*\shifttwo+\maxxx - \minx +\bigshiftdhor,0)}]
	\def\minx{-0.5}
	\def\maxx{2.5}
	\def\maxxx{4.5}

	\draw [gray,  line width=0pt] (\minx,\miny) grid (\maxx,\maxy);
	\draw[ultra thick, \colorone] (0,1) -- (1,0);

	\node[anchor = west] at (\maxx, 0) {\picfontsize $x$};
	\node[anchor = south] at (0, \maxy) {\picfontsize $y$};
	\draw (\tx,\ty) node [below right] {\picfontsize $\scrP$};

	\begin{scope}[shift={(\shifttwo,0)}]
		\def\tx{1}
		\draw [gray,  line width=0pt] (\minx,\miny) grid (\maxx,\maxy);

		\draw[ultra thick, \colorone] (1,0) -- (2,0);

		\node[anchor = west] at (\maxx, 0) {\picfontsize $x$};
		\node[anchor = south] at (0, \maxy) {\picfontsize $y$};
		\draw (\tx,\ty) node [below right] {\picfontsize $\scrQ$};
	\end{scope}

	\begin{scope}[shift={(2*\shifttwo,0)}]
		\def\tx{1}
		\draw [gray,  line width=0pt] (\minx,\miny) grid (\maxxx,\maxy);

		\node[anchor = west] at (\maxxx, 0) {\picfontsize $x$};
		\node[anchor = south] at (0, \maxy) {\picfontsize $y$};
		\draw[fill=\colorzero, opacity=\opazero] (1,1) --  (2,1) -- (3,0) -- (2,0) -- cycle;
		\draw[thick, \colorone ] (1,1) --  (2,1) -- (3,0) -- (2,0) -- cycle;
		\draw (\tx,\ty) node [below right] {\picfontsize $\scrP+ \scrQ$};
	\end{scope}
\end{scope}

\begin{scope}[shift={(0,-\maxy +\miny -\bigshiftdver)}]

	\draw [gray,  line width=0pt] (\minx,\miny) grid (\maxx,\maxy);

	\node[anchor = west] at (\maxx, 0) {\picfontsize $x$};
	\node[anchor = south] at (0, \maxy) {\picfontsize $y$};
	\draw (\tx,\ty) node [below right] {\picfontsize $\scrP$};
	\draw[fill=\colorzero, opacity=\opazero] (-1,0) --  (-1,1) -- (0,0) -- cycle;
	\draw[thick, \colorone ] (-1,0) --  (-1,1) -- (0,0) -- cycle;

	\begin{scope}[shift={(\shifttwo,0)}]
		\def\tx{0}
		\draw [gray,  line width=0pt] (\minx,\miny) grid (\maxx,\maxy);

		\node[anchor = west] at (\maxx, 0) {\picfontsize $x$};
		\node[anchor = south] at (0, \maxy) {\picfontsize $y$};
		\draw[fill=\colorzero, opacity=\opazero] (1,0) --  (1,-1) -- (0,0) -- cycle;
		\draw[thick, \colorone ] (1,0) --  (1,-1) -- (0,0) -- cycle;
		\draw (\tx,\ty) node [below right] {\picfontsize $\scrQ$};
	\end{scope}

	\begin{scope}[shift={(2*\shifttwo,0)}]
		\draw [gray,  line width=0pt] (\minx,\miny) grid (\maxx,\maxy);

		\node[anchor = west] at (\maxx, 0) {\picfontsize $x$};
		\node[anchor = south] at (0, \maxy) {\picfontsize $y$};
		\draw[fill=\colorzero, opacity=\opazero] (-1,0) --  (-1,1) -- (0,1) -- (1,0) -- (1,-1) -- (0, -1) -- cycle;
		\draw[thick, \colorone ] (-1,0) --  (-1,1) -- (0,1) -- (1,0) -- (1,-1) -- (0, -1) -- cycle;
		\draw (\tx,\ty) node [below right] {\picfontsize $\scrP+ \scrQ$};
	\end{scope}

	\begin{scope}[shift={(2*\shifttwo+\maxxx - \minx +\bigshiftdhor,0)}]

		\def\minx{-0.5}
		\def\maxx{2.5}
		\def\maxxx{4.5}

		\draw [gray,  line width=0pt] (\minx,\miny) grid (\maxx,\maxy);

		\node[anchor = west] at (\maxx, 0) {\picfontsize $x$};
		\node[anchor = south] at (0, \maxy) {\picfontsize $y$};
		\draw[fill=\colorzero, opacity=\opazero] (0,-1) --  (1,2) -- (2,-1) -- (1,0) -- cycle;
		\draw[thick, \colorone ] (0,-1) --  (1,2) -- (2,-1) -- (1,0) -- cycle;
		\draw (\tx,\ty) node [below right] {\picfontsize $\scrP$};

		\begin{scope}[shift={(\shifttwo,0)}]
			\def\tx{1}
			\draw [gray,  line width=0pt] (\minx,\miny) grid (\maxx,\maxy);

			\draw[ultra thick, \colorone] (1,0) -- (2,0);

			\node[anchor = west] at (\maxx, 0) {\picfontsize $x$};
			\node[anchor = south] at (0, \maxy) {\picfontsize $y$};
			\draw (\tx,\ty) node [below right] {\picfontsize $\scrQ$};
		\end{scope}

		\begin{scope}[shift={(2*\shifttwo,0)}]
			\def\tx{1}
			\draw [gray,  line width=0pt] (\minx,\miny) grid (\maxxx,\maxy);

			\node[anchor = west] at (\maxxx, 0) {\picfontsize $x$};
			\node[anchor = south] at (0, \maxy) {\picfontsize $y$};
			\draw[fill=\colorzero, opacity=\opazero] (1,-1) --  (2,2) -- (3,2) -- (4,-1) -- (3,-1) -- (2.5, -0.5) -- (2,-1) -- cycle;
			\draw[thick, \colorone ] (1,-1) --  (2,2) -- (3,2) -- (4,-1) -- (3,-1) -- (2.5, -0.5) -- (2,-1) -- cycle;
			\draw (\tx,\ty) node [below right] {\picfontsize $\scrP+ \scrQ$};
		\end{scope}
	\end{scope}
\end{scope}
\end{tikzpicture}
\caption{Minkowski sums of planar sets}  \label{fig:minkowski-sum}
\end{center}
\end{figure}

\begin{prop} \label{strongly-convex-prop}
Let $\scrC$ be a convex cone in $\rr^n$.
\begin{enumerate}
\item \label{strongly-convex:polyhedral} If $\scrC$ is a polyhedral cone, then there is a strongly convex polyhedral cone $\scrC'$ and a linear subspace $L$ of $\rr^n$ such that $\scrC = \scrC' + L$ and $\aff(\scrC') \cap L = \{0\}$.
\item  \label{strongly-convex:finite} If $\scrC$ is a finitely generated cone, then there is a strongly convex finitely generated cone $\scrC'$ and a linear subspace $L$ of $\rr^n$ such that $\scrC = \scrC' + L$ and $\aff(\scrC') \cap L = \{0\}$.
\item \label{dsum-linear} Let $L'$ be a linear subspace of $\rr^n$ such that $L' \cap \aff(C) = \{0\}$. Then $\scrC$ is a polyhedral cone (respectively, finitely generated cone) if and only if $\scrC + L'$ is a polyhedral cone (respectively, finitely generated cone).
\end{enumerate}

\end{prop}

\begin{proof}
Let $L$ be the (unique) maximal linear subspace of $\rr^n$ contained in $\scrC$ (see \cref{exercise:maxlinconvex}). After a linear change of coordinates if necessary, we may assume that $L$ is the coordinate subspace spanned by the first $k$ coordinates. At first assume $\scrC$ is a polyhedral cone. \Cref{exercise:cone-inequalities} implies that it is defined by finitely many inequalities of the form $a_{i,1}x_1 + \cdots + a_{i,n}x_n \geq 0$, $1 \leq i \leq m$. For each $j = 1, \ldots, n$, write $e_j$ for the $j$-th standard unit vector in $\rr^n$. Since $re_j \in L \subseteq \scrC$ for each $j = 1, \ldots, k$, and each $r \in \rr$, it follows that $a_{i,1} = \cdots = a_{i,k} = 0$ for each $i$. Let $\scrC'$ be the polyhedral cone on the $(n-k)$-dimensional coordinate subspace of $\rr^n$ spanned by $e_{k+1}, \ldots, e_n$ defined by the inequalities $a_{i,k+1}x_{k+1} + \cdots + a_{i,n}x_n = 0$. Then assertion \eqref{strongly-convex:polyhedral} holds with $\scrC'$ and $L$. Now assume $\scrC$ is the cone generated by finitely many elements $\alpha_1, \ldots, \alpha_m \in \rr^n$. Let $\alpha_i := (\alpha_{i,1}, \ldots, \alpha_{i,n})$. Since $\tilde \alpha_i := (-\alpha_{i,1}, \ldots, -\alpha_{i,k}, 0, \ldots, 0) \in L \subseteq \scrC$, it follows that $\alpha'_i := \alpha_i + \tilde \alpha_i = (0, \ldots, 0, \alpha_{i, k+1}, \ldots, \alpha_{i,n}) \in \scrC$ for each $i$. Then assertion \eqref{strongly-convex:finite} holds with $L$ and $\scrC' := \cone(\alpha'_1, \ldots, \alpha'_m)$. The proof of assertion \eqref{dsum-linear} follows via the same arguments as in the proof of the preceding assertions by choosing a system of coordinates on $\rr^n$ such that $L'$ is the coordinate subspace spanned by the first $k'$ coordinates, where $k' := \dim(L')$.
\end{proof}

\begin{rem} \label{equivalent-multiplication}
If $\scrA \subset \rr^n$ and $d$ is a positive integer, then $d\scrA$ has two natural interpretations: one is the dilation (which is how we defined it), and the other is the Minkowski sum of $d$ copies of $\scrA$. If $\scrA$ is convex, then these are equivalent (\cref{exercise:integer-multiplication}).
\end{rem}

\subsection{Exercises}

\begin{exercise}\label{exercise:affine-image}
Let $\phi: \rr^n \to \rr^m$ be an affine map and let $S \subseteq \rr^n$. Show that
\begin{enumerate}
\item \label{affine-image-affine} If $A$ is an affine subspace of $\rr^n$, then $\phi(A)$ is an affine subspace of $\rr^m$, and $\dim(\phi(A)) \leq \dim(A)$.
\item \label{affine-image-hulls} $\phi(\aff(S)) = \aff(\phi(S))$ and $\phi(\conv(S)) = \conv(\phi(S))$.
\item \label{affine-image-cone} Assume $\phi$ is in addition a {\em linear map}, i.e.\ $\phi(0) = 0$. Then $\phi(\cone(S)) = \cone(\phi(S))$.
\end{enumerate}
Now assume $\phi$ is in addition injective. Then show that
\begin{enumerate} [resume]
\item The inequality in assertion \eqref{affine-image-affine} holds with equality.
\item The converses of assertions \eqref{affine-image-affine}, \eqref{affine-image-hulls} and \eqref{affine-image-cone} are also true, i.e.\
\begin{enumerate}
\item if $A \subseteq \rr^n$ is such that $\phi(A)$ is an affine subspace of $\rr^m$, then $A$ is also an affine subspace of $\rr^n$,
\item $\phi^{-1}(\aff(S)) = \aff(S)$ and $\phi^{-1}(\conv(\phi(S)) = \conv(S)$,
\item if $\phi$ is a linear map, then $\phi^{-1}(\cone(\phi(S)) = \cone(S)$.
\end{enumerate}
\end{enumerate}
\end{exercise}

\begin{exercise}\label{exercise:conv-rep}
Show that the line segment joining $\alpha, \beta \in \rr^n$ is precisely the set of their convex combinations. Use it to prove identity \eqref{conv-rep}. If $\nu \in \rnstar$ and $S \subset \rr^n$ are such that $\min_S (\nu)$ exists, then use identity \eqref{conv-rep} to show that $\min_{\conv(S)}(\nu) = \min_S(\nu)$.
\end{exercise}

\begin{exercise}\label{exercise:pol-is-convex}
Check that a convex polyhedron as defined in \cref{basic-convex-section} is actually convex.
\end{exercise}

\begin{exercise}\label{exercise:zerone-dim-pol}
Let $S \subseteq \rr^n$.
\begin{enumerate}
\item Show that $\aff(S)$ is zero dimensional if and only if $S$ is a ``singleton'' (i.e.\ it consists of a single point). Deduce that zero dimensional polyhedra are precisely singletons.
\item Assume $S$ is convex and closed in $\rr^n$, and $\aff(S)$ is one dimensional. Show that there is an affine isomorphism $\phi: \rr \to \aff(S)$ such that $\phi^{-1}(S)$ is a (possibly unbounded) closed interval of $\rr$.
\end{enumerate}
\end{exercise}

\begin{exercise}\label{exercise:2-cone}
Show that every finitely generated two dimensional cone in $\rr^2$ can be generated as a cone by two nonzero elements of $\rr^2$ (these correspond to ``edges'' of $S$). If $S$ is in addition strongly convex, show that the generators of $S$ are linearly independent.
\end{exercise}

\begin{exercise} \label{exercise:cone-inequalities}
Let $\scrP \subseteq \rr^n$.
\begin{enumerate}
\item Assume $\scrP$ is ``dilation invariant,'' i.e.\ for every $\alpha \in \scrP$ and every $r \geq 0$, $r\alpha \in \scrP$. Show that for every $\nu \in \rnstar$, $\inf\{ \langle \nu, \alpha \rangle: \alpha \in \scrP\}$ is either $0$ or $-\infty$.
\item Deduce that $\scrP$ is a convex polyhedral cone if and only if it can be defined by finitely many inequalities with zero constant term, i.e.\ inequalities of the form $a_1x_1 + \cdots + a_nx_n \geq 0$.
\end{enumerate}
\end{exercise}

\begin{exercise} \label{exercise:linear-sum-invariance}
If $S, T \subseteq \rr^m$ and $\phi: \rr^m \to \rr^n$ is a linear map, show that $\phi(S+T) = \phi(S) + \phi(T)$.
\end{exercise}

\begin{exercise}\label{exercise:minkonvex}
Let $\scrP, \scrQ$ be subsets of $\rr^n$.
\begin{enumerate}
\item If $\scrP = \conv(S)$ and $\scrQ = \conv(T)$, then show that $\scrP+ \scrQ= \conv(S + T)$. [Hint: if $\sum_i \delta_i = \sum_j \epsilon_j = 1$, then $\sum_i \delta_i a_i + \sum_j \epsilon_j b_j = \sum_{i,j}\delta_i\epsilon_j (a_i + b_j)$.]
\item Deduce that if $\scrP$ and $\scrQ$ are convex (respectively, convex hulls of finitely many points, finitely generated cones) then so is $\scrP + \scrQ$.
\end{enumerate}
\end{exercise}

\begin{exercise} \label{exercise:maxlinconvex}
Let $\scrC$ be a convex subset of $\rr^n$ containing the origin. Show that $\scrC$ contains a unique maximal linear subspace of $\rr^n$, i.e.\ there is a linear subspace $L$ of $\rr^n$ such that $L \subseteq \scrC$, and if $L'$ is any linear subspace of $\rr^n$ contained in $\scrC$, then $L' \subseteq L$. [Hint: if $L_1, L_2$ are two linear subspaces of $\rr^n$ contained in $\scrC$, then $L_1 + L_2 \subseteq \scrC$.]
\end{exercise}

\begin{exercise} \label{exercise:integer-multiplication}
Let $\scrA \subset \rr^n$ and $d$ be a positive integer.
\begin{enumerate}
\item If $\scrA$ is convex, then show that $\{d\alpha: \alpha \in \scrA\} = \{\alpha_1 + \cdots + \alpha_d: \alpha_j \in \scrA$ for each $j\}$.
\item Give an example to show that the above equality may not hold if $\scrA$ is not convex.
\end{enumerate}
\end{exercise}

\begin{exercise} \label{exercise:eq-dim-embedding}
Let $S \subset \rr^m$ and $n: = \dim(\aff(S))$.
\begin{enumerate}
\item \label{eq-dim-embedding:affine} Show that there is $T \subseteq \rr^n$ and an injective affine map $\phi:\rr^n \to \rr^n$ such that $\aff(T)$ is $\rr^n$, and $\phi(T) = S$.  [Hint: $\aff(S)$ is a translation of an $n$-dimensional linear subspace of $\rr^m$.]
\item If $S$ contains the origin (this is the case when e.g.\ $S$ is a cone) then show that it is possible to ensure in assertion \eqref{eq-dim-embedding:affine} that $\phi$ is in addition a {\em linear} map.
\end{enumerate}
\end{exercise}

\begin{exercise} \label{exercise:affine-invariance}
Show that each of the following properties is invariant under injective affine maps, i.e.\ if $\phi: \rr^{n_1} \to \rr^{n_2}$ is an injective affine map then each of the following properties holds with $S = S_1$ and $n = n_1$ if and only if it holds with $S = \phi(S_1)$ and $n = n_2$.
\begin{enumerate}
\item $S$ is an affine subspace of $\rr^n$,
\item $S$ is a convex subset of $\rr^n$,
\item $S$ is the convex hull of finitely many points in $\rr^n$,
\item $S$ is convex polyhedron in $\rr^n$,
\item $S$ is convex polytope in $\rr^n$.
\end{enumerate}
\end{exercise}

\begin{exercise}\label{exercise:linear-invariance}
Show that each of the following properties is invariant under injective linear maps, i.e.\ if $\phi: \rr^{n_1} \to \rr^{n_2}$ is an injective linear map then each of the following properties holds with $S = S_1$ and $n = n_1$ if and only if it holds with $S = \phi(S_1)$ and $n = n_2$.
\begin{enumerate}
\item $S$ is a linear subspace of $\rr^n$,
\item $S$ is a convex cone in $\rr^n$,
\item $S$ is a strongly convex cone in $\rr^n$,
\item $S$ is a finitely generated convex cone in $\rr^n$,
\item $S$ is a convex polyhedral cone in $\rr^n$.
\end{enumerate}
\end{exercise}

\begin{exercise} \label{exercise:dual-extension}
Let $H$ be a linear subspace of $\rr^n$.
\begin{enumerate}
\item \label{dual-extension-0} Show that every linear map $\nu:H \to \rr$ can be extended to a map $\rr^n \to \rr$.

\item \label{dual-extension-positive} Assume $H \subseteq \eta^\perp$ for some $\eta \in \rnstar$. Let $S \subset \rr^n$ be a finite set such that $\langle \eta, \alpha \rangle >0$ for each $\alpha \in S$, and let $c$ be an arbitrary real number. Show that in assertion \eqref{dual-extension-0} it can be ensured that $\langle \nu', \alpha \rangle > c$ for each $\alpha \in S$. [Hint: after a linear change of coordinates on $\rr^n$ we may assume that $H$ is spanned by the first $k$-coordinates and $\eta$ is the projection onto the $(k+1)$-th coordinate.]
\end{enumerate}
\end{exercise}

\begin{exercise}  \label{exercise:injectively-positive-dual}
Given $S \subset \rr^n$, consider the following property:
\begin{align}
\parbox{0.6\textwidth}{
there is $\nu \in \rnstar$ such that $\langle \nu, \alpha \rangle > 0$ for each $\alpha \in S\setminus \{0\}$.
}
\label{positive-dual-property}
\end{align}
Let $\phi: \rr^{n_1} \to \rr^{n_2}$ be an injective linear map and $S_1 \subseteq \rr^{n_1}$. Show that property \eqref{positive-dual-property} holds with $S = S_1$ and $n = n_1$ if and only if it holds with $S = \phi(S_1)$ and $n = n_2$. [Hint: use assertion \eqref{dual-extension-0} of \cref{exercise:dual-extension}.]
\end{exercise}

\begin{exercise} \label{exercise:0-line}
Let $S \subseteq \rr^n\setminus\{0\}$. Show that the origin is in the convex hull of $S$ if and only if $\cone(S)$ contains a line through the origin. [Hint: $0$ can be written as a convex combination of elements from $S$ if and only if there is $\alpha \in \cone(S)$, $\alpha \neq 0$, such that $-\alpha$ is also in $\cone(S)$.]
\end{exercise}

\begin{exercise} \label{exercise:strongly-convex-projection}
Let $\scrC$ be a convex cone in $\rr^n$ and $\pi:\rr^n \to \rr^m$ be a linear map such that $\ker(\pi) \cap \scrC = \{0\}$. Show that $\scrC$ is a strongly convex cone in $\rr^n$ if and only if $\pi(\scrC)$ is a strongly convex cone in $\rr^m$. [Hint: use \cref{exercise:0-line}.]
\end{exercise}

\section{Characterization of convex polyhedra} \label{poly-characterizection}
In this section we describe a characterization of convex polytopes and polyhedral cones, and use it to show that every polyhedron is the Minkowski sum of a polytope and a polyhedral cone. The proofs we give are elementary and geometric, but not the most ``efficient''; see e.g.\ \cite[Section 7.2]{schrijver} for a quicker proof (which is somewhat less intuitive in the beginning), and \cite[Section 1.3]{ziegtopes} for a more algorithmic proof.

\begin{thm}[Farkas (1898, 1902), Minkowski (1896), Weyl (1935)]  \label{poly-basic-thm}
Let $\scrP$ be a convex subset of $\rr^n$.
\begin{enumerate}
\item \label{characterize-polytope} $\scrP$ is a polytope if and only if it is the convex hull of finitely many points.
\item \label{characterize-cone} $\scrP$ is a polyhedral cone if and only if it is a finitely generated cone.
\item \label{characterize-strongly-convex} Assume $\scrP$ is a polyhedral cone. Then it is strongly convex if and only if there is $\nu \in \rnstar$ such that $\langle \nu, \alpha \rangle > 0$ for each $\alpha \in \scrP \setminus \{0\}$.
\end{enumerate}
\end{thm}

\begin{proof}
We are going to prove assertions \eqref{characterize-cone}, \eqref{characterize-strongly-convex} and $(\Leftarrow)$ implication of assertion \eqref{characterize-polytope}. The $(\im)$ direction of assertion \eqref{characterize-polytope} follows from these assertions; it is left as an exercise (\cref{exercise:pol-to-hull}). We start with the proof of assertion \eqref{characterize-strongly-convex}. For the $(\Leftarrow)$ direction note that if $\scrP$ contains both $\alpha$ and $-\alpha$ for some nonzero $\alpha \in \rr^n$, then for all $\nu \in \rnstar$, either $\langle \nu, \alpha \rangle \leq 0$ or $\langle \nu, -\alpha \rangle < 0$. For the $(\im)$ direction we proceed by induction on $\dim(\scrP)$. Due to \cref{exercise:eq-dim-embedding,exercise:linear-invariance,exercise:injectively-positive-dual} we may assume \woutlog\ that $\dim(\scrP) = n$. Since the only strongly positive cones in $\rr$ are $\rr_{\geq 0}$ and $\rr_{\leq 0}$, it holds for $n = 1$. In the general case $\scrP$ is defined by finitely many inequalities of the form $\langle \nu, x \rangle \geq 0$ for nonzero $\nu \in \rnstar$ (\cref{exercise:cone-inequalities}). Take one such $\nu$. Since $\nu\perp \cap \scrP$ is a smaller dimensional strongly convex polyhedral cone, it follows by induction that there is $\eta \in \rnstar$ which is positive on $(\nu^\perp \cap \scrP) \setminus \{0\}$.

\begin{proclaim} \label{claim:positive-dual-by-induction}
For sufficiently small $\epsilon > 0$, $\nu + \epsilon \eta$ is positive on $\scrP\setminus \{0\}$.
\end{proclaim}

\begin{proof}
If the claim is false, then we can find a sequence of positive numbers $\epsilon_k \to 0$ and $\alpha_k \in S^{n-1} \cap \scrP$, where $S^{n-1}$ is the unit sphere centered at the origin in $\rr^n$, such that $\langle \nu + \epsilon_k \eta, \alpha_k \rangle < 0$. Since $\scrP$ is closed and $S^{n-1}$ is compact, we may assume that the $\alpha_k$ converge to $\alpha \in \scrP \cap S^{n-1}$. Then $\langle \nu, \alpha \rangle = \lim_{k \to \infty} \langle \nu + \epsilon_k \eta, \alpha_k \rangle \leq  0$, so that $\langle \nu, \alpha \rangle = 0$. It follows that $\alpha \in  S^{n-1} \cap \nu^\perp \cap \scrP$, so that $\langle \eta, \alpha \rangle > 0$. By continuity $\eta$ is positive on an open neighborhood $U$ of $\alpha$, which means that $\langle \nu + \epsilon_k \eta, \alpha_k \rangle > 0$ for sufficiently large $k$. This contradiction proves the claim.
\end{proof}

\Cref{claim:positive-dual-by-induction} finishes the proof of assertion \eqref{characterize-strongly-convex}. We now prove the $(\im)$ direction of assertion \eqref{characterize-cone} by induction on $\dim(\scrP)$. Due to  \cref{strongly-convex-prop,exercise:eq-dim-embedding,exercise:linear-invariance} we may assume \woutlog\ that $\scrP$ is an $n$-dimensional strongly convex polyhedral cone in $\rr^n$. As in the proof of assertion \eqref{characterize-strongly-convex}, the $n = 1$ case follows directly from the observation that the only strongly convex polyhedral cones in $\rr$ are $\rr_{\geq 0}$ and $\rr_{\leq 0}$. Now consider the case $n \geq 2$. Assertion \eqref{characterize-strongly-convex} implies that there is $\nu \in \rnstar$ such that $\langle \nu, \alpha \rangle > 0$ for each $\alpha \in \scrP \setminus \{0\}$.

\begin{proclaim} \label{bounded-nu=1}
$\scrP' := \{\alpha \in \scrP : \langle \nu, \alpha \rangle = 1\}$ is bounded.
\end{proclaim}

\begin{proof}
Indeed, otherwise take a sequence $\alpha_k \in \scrP'$ such that $\norm{\alpha_k}$ is unbounded, where $\norm{\cdot}$ is the Euclidean norm on $\rr^n$. Note that each $\alpha_k/\norm{\alpha_k}$ is in the intersection of $\scrP$ and the $(n-1)$-dimensional unit sphere $S^{n-1}$. Since $S^{n-1}$ is compact and $\scrP$ is closed, we may assume \woutlog\ that $\alpha_k/\norm{\alpha_k}$ converge to $\alpha \in \scrP \cap S^{n-1}$. But then $\langle \nu, \alpha \rangle = \lim_{k \to \infty} \langle \nu, \alpha_k/\norm{\alpha_k} \rangle = 0$, which contradicts the choice of $\nu$.
\end{proof}

\Cref{exercise:cone-inequalities} implies that $\scrP$ is defined by inequalities of the form $\langle \nu_j, x \rangle \geq 0$, $j = 1, \ldots, N$, for some $\nu_1, \ldots, \nu_N \in \rnstar$. For each $j$, let $\scrP_j := \scrP \cap \nu_j^\perp$. By the inductive hypothesis, each $\scrP_j$ is generated by finite sets $S_j \subset \rr^n$. We claim that $\scrP$ is generated by $\bigcup_j S_j$. Indeed, take $\alpha \in \scrP \setminus \{0\}$. There is $r > 0$ such that $r\alpha \in \scrP'$. Take any straight line through $r\alpha$ on the hyperplane $\{\alpha: \langle \nu, \alpha \rangle = 1\}$. \Cref{bounded-nu=1} implies that either $r\alpha \in \scrP_j$ for some $j$, or each end of the line intersects one of the $\scrP_j$. In any event, the inductive hypothesis implies that $\alpha$ is a nonnegative linear combination of elements from $\bigcup_j S_j$, as required to complete the proof of $(\im)$ implication of assertion \eqref{characterize-cone}. Now we prove $(\Leftarrow)$ implications of assertions \eqref{characterize-polytope} and \eqref{characterize-cone} by induction on $\dim(\aff(\scrP))$. We will first show that it suffices to prove only the implication from assertion \eqref{characterize-cone}.

\begin{figure}[h]
\begin{center}

\xdefinecolor{c1}{HTML}{D4ACEE}
\xdefinecolor{c2}{HTML}{EEc6AC}
\xdefinecolor{c3}{HTML}{EDEEAC}
\def\tinyshifth{0.09}
\def\tinyshiftv{0.09}

\def\xmin{-2}
\def\xmax{8}
\def\ymin{-3}

\tikzstyle{dot} = [red, circle, minimum size=4pt, inner sep = 0pt, fill]

\begin{tikzpicture}[scale=\scalefactor]

\coordinate (A) at (0,0);
\coordinate (B) at (4,2);
\coordinate (C) at (3,3);

\foreach \x in {0,\tinyshifth,...,\xmax} {
	\draw[color=c1, ultra thin] (\x, {0.5*\x}) -- (\x,\x);
}
\pgfmathsetmacro\xlim{4-\xmin}
\foreach \x in {0,\tinyshifth,...,\xlim} {

	\draw[color=c2, ultra thin] ({4-\x}, {2-0.5*\x}) -- ({4-\x},{2+\x});
}
\pgfmathsetmacro\ylim{3-\ymin}
\foreach \y in {0,\tinyshiftv,...,\ylim} {
	\draw[color=c3, ultra thin] ({3-\y}, {3-\y}) -- ({3+\y}, {3-\y});
}

\node[dot] at (A) {};
\node[dot] at (B) {};
\node[dot] at (C) {};

\draw[thick, \colorAB] (A) -- (B);
\draw[thick, \colorBC] (B) -- (C);
\draw[thick, \colorCA] (C) -- (A);
\node[anchor = north] at (A) {$\alpha_1$};
\node[anchor = west] at (B) {$\alpha_2$};
\node[anchor = south] at (C) {$\alpha_3$};

\def\xmin{-5.5}
\def\xshift{9}
\def\yshift{2.5}
\pgfmathsetmacro\shiftone{\xshift + \xmax -\xmin};
\def\xmax{5.5}
\def\ymin{-5.5}
\def\ymax{5.5}

\begin{scope}[shift={(\shiftone,\yshift)}]

\coordinate (O) at (0,0);
\coordinate (BA) at (\xmin, \xmin/2);
\coordinate (AB) at (\xmax, \xmax/2);
\coordinate (CA) at (\ymin, \ymin);
\coordinate (AC) at (\ymax, \ymax);
\coordinate (BC) at (-\ymax, \ymax);
\coordinate (CB) at (-\ymin, \ymin);

\foreach \x in {0,\tinyshifth,...,\xmax} {

	\draw[color=c1, ultra thin] (\x, {0.5*\x}) -- (\x,\x);
	\draw[color=c2, ultra thin] (-\x, -{0.5*\x}) -- (-\x,\x);
}

\foreach \y in {0,-\tinyshiftv,...,\ymin} {

	\draw[color=c3, ultra thin] (\y, \y) -- (-\y,\y);
}

\draw [thick, \colorAB] (AB) -- (BA);
\draw [thick, \colorBC] (CB) -- (BC);
\draw [thick, \colorCA] (AC) -- (CA);

\node at (-3.5,0.5) {\picfontsize $\scrC_2$};
\node at (4.5,3.5) {\picfontsize $\scrC_1$};
===\node at (0.5,-3.5) {\picfontsize $\scrC_3$};
\end{scope}
\end{tikzpicture}
\caption{Convex hull of finitely many points is a finite intersection of translations of cones}  \label{fig:polytope=polyhedral-intersection}
\end{center}
\end{figure}

\begin{proclaim} \label{fin2cone-to-hull2pol}
Let $k \geq 1$. Assume the $(\Leftarrow)$ implication of assertion \eqref{characterize-cone} holds whenever $\dim(\aff(\scrP)) \leq k$. Then the $(\Leftarrow)$ implication of assertion \eqref{characterize-polytope} holds whenever $\dim(\aff(\scrP)) \leq k$.
\end{proclaim}

\begin{proof}
Let $\scrP$ be the convex hull of a finite set $S$, and $m := \dim(\aff(\scrP)) \leq k$. \Woutlog\ we may assume that $\scrP\subset \rr^m$ (\cref{exercise:eq-dim-embedding,exercise:affine-invariance}). Let $\alpha_1, \ldots, \alpha_s$ be the elements of $S$. For each $j$, let $\scrC_j$ be the cone generated by $S - \alpha_j = \{\alpha_i - \alpha_j: 1 \leq i \leq s\}$. The hypothesis of the claim implies that each $\scrC_j$ is a polyhedral cone, which implies in turn that $\scrC_j + \alpha_j$ is a polyhedron (\cref{exercise:affine-invariance}). It follows that $\scrP' := \bigcap_j (\scrC_j + \alpha_j)$ is also a polyhedron. Therefore it suffices to show that $\scrP' = \scrP$ (\cref{fig:polytope=polyhedral-intersection}). By \eqref{conv-rep} every element $\alpha \in \scrP$ can be expressed as $\sum_i \epsilon_i\alpha_i$ where $\epsilon_i$ are nonnegative real numbers with $\sum_i \epsilon_i = 1$. But then $\alpha = \alpha_j + \sum_i \epsilon_i(\alpha_i - \alpha_j) \in \scrC_j + \alpha_j$ for each $j$. Therefore $\scrP\subseteq \scrP'$. Now take $\alpha \not\in \scrP$. To complete the proof of the claim it suffices to show that $\alpha \not \in \scrP'$. Since $\alpha \not\in \scrP$, it follows that $\cone(\scrP - \alpha)$ is strongly convex (\cref{exercise:0-line}). By the hypothesis of the claim $\cone(\scrP - \alpha)$ is polyhedral, so that due to assertion \eqref{characterize-strongly-convex} there is $\nu \in \rnstar$ which is positive on $ \scrP - \alpha$. Pick $j$ such that $\langle \nu, \alpha_j\rangle = \min \{\langle \nu, \alpha_i\rangle: 1 \leq i \leq s\}$. Then $\nu$ is nonnegative on $\scrC_j$, whereas $\langle \nu, \alpha - \alpha_j \rangle $ is negative. Therefore $\alpha \not\in \scrC_j + \alpha_j$, and consequently $\alpha \not\in \scrP'$, as required.
\end{proof}

Now we start the proof of $(\Leftarrow)$ direction of assertion \eqref{characterize-cone} by induction on $\dim(\aff(\scrP))$. Due to \cref{strongly-convex-prop,exercise:eq-dim-embedding,exercise:linear-invariance} we may assume \woutlog\ that $\scrP$ is a strongly convex cone generated by a finite set $S \subset \rr^n$ and $n = \dim(\aff(\scrP))$. For $n = 1$ the possibilities for $\scrP$ are $\rr_{\geq 0}$ and $\rr_{\leq 0}$, both of which are polyhedral. For general $n$ we proceed by induction on $|S|$. The case $|S| = 1$ is also covered by the case $n = 1$. So assume $|S| \geq 2$.

\begin{proclaim}
There is $\nu \in \rnstar$ which is positive on $S \setminus \{0\}$.
\end{proclaim}

\begin{proof}
 Pick $\alpha \in S \setminus \{0\}$. By the inductive hypothesis $\scrP_1 := \cone(S \setminus \{\alpha\})$ is polyhedral, so that $\scrP_1$ is defined by finitely many inequalities of the form $\langle \nu_j, x \rangle \geq 0$, $j = 1, \ldots, N$ (\cref{exercise:cone-inequalities}). We claim that $\langle \nu_j, \alpha \rangle > 0$ for some $j$. Indeed, otherwise $\langle \nu_j, -\alpha \rangle \geq 0$ for each $j$, so that $-\alpha \in \scrP_1$. But then $\scrP$ contains the line through the origin and $\alpha$, contradicting the strong convexity of $\scrP$. So we can pick $j$ such that $\langle \nu_j, \alpha \rangle > 0$. Now let $\scrP_2 := \scrP \cap \nu_j^\perp$. Then $\dim(\aff(\scrP_2)) < n$, so that $\scrP_2$ is polyhedral by the inductive hypothesis. Assertion \eqref{characterize-strongly-convex} then implies that there is $\nu \in \rnstar$ which is positive on $\scrP_2 \setminus \{0\}$. We claim that if $\epsilon$ is a sufficiently small positive number, then $\nu_j + \epsilon \nu$ is positive on $\scrP \setminus \{0\}$. Indeed, simply take $\epsilon$ such that $\epsilon | \langle  \nu, \beta \rangle | < \langle \nu_j, \beta \rangle$ for all (the finitely many) elements of $S \setminus \scrP_2$.
\end{proof}

Let $\scrP' := \{\alpha \in \scrP: \langle \nu, \alpha \rangle =1\}$. If $\alpha_1, \ldots, \alpha_s$ are elements of $S$, then $\alpha'_j := \alpha_j/\langle \nu, \alpha_j\rangle \in \scrP'$ for each $j$, and it is straightforward to check that $\scrP'$ is the convex hull of $\alpha'_1, \ldots, \alpha'_s$. Since $\dim(\aff(\scrP')) < n$, the inductive hypothesis and \cref{fin2cone-to-hull2pol} imply that $\scrP'$ is a polytope. It is then straightforward to check that $\scrP$ is a polyhedral cone (\cref{exercise:pol-to-cone}), as required.
\end{proof}

\begin{cor}  \label{cor:polyhedral-sum}
The Minkowski sum of two convex polytopes (respectively, polyhedral cones) is a convex polytope (respectively, polyhedral cone).
\end{cor}

\begin{proof}
Follows immediately from \cref{poly-basic-thm,exercise:minkonvex}.
\end{proof}

The next corollary of \cref{poly-basic-thm} shows that each convex polyhedron $\scrQ$ has a representation of the form $\scrQ= \scrP+ \scrC$, where $\scrC$ is a polyhedral cone and $\scrP$ is a polytope. In general the decomposition is {\em not} unique, see \cref{fig:non-unique-sum}. However, $\scrC$ is uniquely determined from $\scrQ$ (\cref{exercise:minkomposition-uniqueness}). It is also possible to find $\scrP$ which is ``minimal'' (modulo translations in the case that $\scrC$ is not strongly convex), but we will not get into that.

\begin{center}
\begin{figure}[h]

\def\scalefactor{.3}

\def\xmin{-2}
\def\xmax{8}
\def\ymin{-5}
\def\ymax{8}

\def\tx{0}
\def\ty{\ymin}

\def\xshiftone{6}
\def\xshifttwo{5}

\def\yminsmall{-2.5}
\def\ymaxsmall{4.5}

\def\ygap{5}
\def\yshiftup{6}
\def\yshiftdown{-5}
\tikzstyle{dot} = [\colordot, circle, minimum size=4pt, inner sep = 0pt, fill]

\begin{tikzpicture}[scale=\scalefactor]
\pgfmathsetmacro\shiftone{\xshiftone + \xmax -\xmin};
\pgfmathsetmacro\shifttwo{\xshifttwo + \xmax -\xmin};

\coordinate (A) at (-2, -1);

\coordinate (C') at (8,-5);

\coordinate (D') at (8,7.5);
\coordinate (E) at (1,4);

\fill[\colorzero, opacity=\opazero ] (A) -- (C') -- (D') -- (E) -- cycle;

\draw[thick, \colorone ] (A) -- (C');
\draw[thick, \colorone ] (A) -- (E) -- (D');

\draw (\xmax, 0) -- (\xmin, 0);
\draw (0, \ymax) -- (0, \ymin);

\node[dot] (O) at (0,0){};
\node[anchor = south west] at (O) {\picfontsize $(0,0)$};
\node[anchor = west] at (\xmax, 0) {\picfontsize $x$};
\node[anchor = south] at (0, \ymax) {\picfontsize $y$};

\node [below right, text width= 1.8cm, align=left] at (\tx,\ty) {
	\picfontsize
	$\scrQ$
};

\def\ymax{\ymaxsmall}
\def\ymin{\yminsmall}

\begin{scope}[shift = {(\shiftone,\yshiftup)}]

\coordinate (A) at (-2, -1);
\coordinate (B) at (3,-3);
\coordinate (C) at (7,1);
\coordinate (D) at (5,6);
\coordinate (E) at (1,4);

\draw[fill=\colorzero, opacity=\opazero ] (A) --  (B) -- (C) -- (D) -- (E) -- cycle;

\draw[thick, \colorone ] (A) --  (B) -- (C) -- (D) -- (E) -- cycle;

\draw (\xmax, 0) -- (\xmin, 0);
\draw (0, \ymax) -- (0, \ymin);

\node[dot] (O) at (0,0){};
\node[anchor = south west] at (O) {\picfontsize $(0,0)$};
\node[anchor = west] at (\xmax, 0) {\picfontsize $x$};
\node[anchor = south] at (0, \ymax) {\picfontsize $y$};

\node [below right, text width= 0.75cm, align=left] at (\tx,\ty) {
	\picfontsize
	$\scrP_1$
};

\end{scope}

\begin{scope}[shift = {(\shiftone + \shifttwo,\yshiftup)}]

	\coordinate (C') at (8,-3.2);

	\coordinate (D') at (8, 4);
	\coordinate (O) at (0,0);

	\fill[\colorzero, opacity=\opazero ] (O) -- (C') -- (D') -- cycle;

	\draw[thick, \colorone ] (O) -- (C');
	\draw[thick, \colorone ] (O) -- (D');

	\draw (\xmax, 0) -- (\xmin, 0);
	\draw (0, \ymax) -- (0, \ymin);

	\node[dot] (extra) at (O) {};
	\node[anchor = north] at (O) {\picfontsize $(0,0)$};
	\node[anchor = west] at (\xmax, 0) {\picfontsize $x$};
	\node[anchor = south] at (0, \ymax) {\picfontsize $y$};

	\node [below right, text width= 2.7cm, align=left] at (\tx,\ty) {
		\picfontsize
		$\scrC$
	};
\end{scope}

\begin{scope}[shift = {(\shiftone,\yshiftdown)}]

\coordinate (A) at (-2, -1);
\coordinate (E) at (1,4);

\draw[thick, \colorone ] (A) -- (E);

\draw (\xmax, 0) -- (\xmin, 0);
\draw (0, \ymax) -- (0, \ymin);

\node[dot] (O) at (0,0){};
\node[anchor = south west] at (O) {\picfontsize $(0,0)$};
\node[anchor = west] at (\xmax, 0) {\picfontsize $x$};
\node[anchor = south] at (0, \ymax) {\picfontsize $y$};

\node [below right, text width= 0.75cm, align=left] at (\tx,\ty) {
	\picfontsize
	$\scrP_2$
};

\end{scope}

\begin{scope}[shift = {(\shiftone + \shifttwo,\yshiftdown)}]

	\coordinate (C') at (8,-3.2);

	\coordinate (D') at (8, 4);
	\coordinate (O) at (0,0);

	\fill[\colorzero, opacity=\opazero ] (O) -- (C') -- (D') -- cycle;

	\draw[thick, \colorone ] (O) -- (C');
	\draw[thick, \colorone ] (O) -- (D');

	\draw (\xmax, 0) -- (\xmin, 0);
	\draw (0, \ymax) -- (0, \ymin);

	\node[dot] (extra) at (O) {};
	\node[anchor = north] at (O) {\picfontsize $(0,0)$};
	\node[anchor = west] at (\xmax, 0) {\picfontsize $x$};
	\node[anchor = south] at (0, \ymax) {\picfontsize $y$};

	\node [below right, text width= 2.7cm, align=left] at (\tx,\ty) {
		\picfontsize
		$\scrC$
	};
\end{scope}

\end{tikzpicture}

\caption{
$\scrQ = \scrP + \scrC$ for $\scrP = \scrP_1$ and $\scrP= \scrP_2$. The ``minimal'' possible choice for $\scrP$ is the line segment $\scrP_2$.
} \label{fig:non-unique-sum}

\end{figure}
\end{center}

\begin{cor}[Motzkin (1936)] \label{poly-basic-cor}
A subset of $\rr^n$ is a convex polyhedron if and only if it is the Minkowski sum of a convex polyhedral cone and a convex polytope.
\end{cor}

\begin{proof}
At first we prove the $(\im)$ implication. Let $\scrQ$ be a polyhedron in $\rr^n$ defined by inequalities $a_{q,0} + a_{q,1}x_1 + \cdots + a_{q,n}x_n \geq 0$, $q = 1, \ldots, N$. We will show that it is the sum of a polyhedral cone and a polytope.

Consider the polyhedral cone $\scrQ'$ in $\rr^{n+1}$ defined by the ``homogenizations'' $a_{q,0}x_0 +  a_{q,1}x_1 + \cdots + a_{q,n}x_n \geq 0$, $q = 1, \ldots, N$, and $x_0 \geq 0$. Note that $\scrQ = \scrQ' \cap (\{1\} \times \rr^n)$. \Cref{poly-basic-thm} implies that $\scrQ'$ is a finitely generated cone. We may choose a set of generators of $\scrQ'$ of the form $(1, \alpha_1), \ldots, (1, \alpha_k), (0, \beta_1), \ldots, (0, \beta_l)$, where $\alpha_1, \ldots, \alpha_k, \beta_1, \ldots, \beta_l \in \rr^n$. Let $\scrP$ be the convex hull of $\alpha_1, \ldots, \alpha_k$, and $\scrC$ be the cone in $\rr^n$ generated by $\beta_1, \ldots, \beta_l$. \Cref{poly-basic-thm} implies that $\scrP$ is a polytope and $\scrC$ is a polyhedral cone.

\begin{proclaim} \label{poly-basic-cor:cla-im}
$\scrQ = \scrP + \scrC$.
\end{proclaim}

\begin{proof}
Let $\gamma \in \scrQ$. Then $(1, \gamma) \in \scrQ'$, and therefore $(1, \gamma) = \sum_i a_i (1, \alpha_i) + \sum_j b_j (0, \beta_j)$ where the $a_i, b_j$ are nonnegative numbers. Then it follows that $\sum_i a_i = 1$ and $\gamma = \alpha + \beta$, where $\alpha = \sum_i a_i \alpha_i$ and $\beta = \sum_j b_j \beta_j$. It is clear that $\beta \in \scrC$. Since $\sum_i a_i = 1$, it follows that $\alpha$ is a convex combination of the $\alpha_i$, so that $\alpha \in \scrP$. Therefore $\scrQ \subset \scrP+ \scrC$. Now we check the opposite inclusion. Let $\alpha \in \scrP$ and $\beta \in \scrC$. Then $\alpha = \sum_i a_i \alpha_i$ where the $a_i$ are nonnegative numbers such that $\sum_i a_i = 1$. Since $(1, \alpha_i) \in \scrQ'$ for each $i$, it follows that $(1, \alpha) = \sum_i a_i (1,\alpha_i) \in \scrQ'$. On the other hand, it follows from the construction of $\scrC$ that $\{0\} \times \scrC = \scrQ' \cap (\{0\} \times \rr^n)$, so that $(0,\beta) \in \scrQ'$. Since the sum of two elements of a convex cone is also in that cone, it follows that $(1, \alpha + \beta) = (1, \alpha) + (0, \beta) \in \scrQ'$. Therefore, $\alpha + \beta \in \scrQ$, as required.
\end{proof}
\Cref{poly-basic-cor:cla-im} finishes the proof of $(\im)$ implication of the corollary. Now we prove the $(\Leftarrow)$ implication. Let $\scrP$ be a convex polytope and $\scrC$ be a convex polyhedral cone in $\rr^n$. We will show that $\scrP+ \scrC$ is a convex polyhedron. By \cref{exercise:affine-invariance} we may assume \woutlog\ that $\scrP$ contains the origin. Identify $\rr^{n+1}$ with $\rr \times \rr^n$. Let $\scrP'$ be the cone in $\rr^{n+1}$ generated by $\{1\} \times \scrP$, and $\scrC'$ be the closure of the cone in $\rr^{n+1}$ generated by $\{1\} \times \scrC$. Either \cref{poly-basic-thm} or \cref{exercise:pol-to-cone} implies that $\scrP'$ is a polyhedral cone, and \cref{exercise:cone-to-cone} implies that $\scrC'$ is a polyhedral cone. \Cref{cor:polyhedral-sum} then implies that $\scrP' + \scrC'$ is a polyhedral cone, so that $\scrQ := (\scrP' + \scrC') \cap (\{1\} \times \rr^n)$ is a polyhedron.

\begin{proclaim} \label{claim:cone-hedral-crossectoin}
$\scrQ = \{1\} \times (\scrP + \scrC)$.
\end{proclaim}

\begin{proof}
Let the inequalities defining $\scrP$ be $a_{i,0} + a_{i,1}x_1 + \cdots + a_{i,n}x_n \geq 0$, $i = 1, \ldots, k$, and the inequalities defining $\scrC$ be $b_{j,1}x_1 + \cdots + b_{j,n}x_n \geq 0$, $j = 1, \ldots, l$. \Cref{exercise:pol-to-cone} shows that $\scrP'$ is defined by the inequalities $a_{i,0}x_0 + a_{i,1}x_1 + \cdots + a_{i,n}x_n \geq 0$, $i = 1, \ldots, k$, and $x_0 \geq 0$. On the other hand \cref{exercise:cone-to-cone} implies that $\scrC'$ is defined by the same inequalities as $\scrC$ together with the inequality $x_0 \geq 0$. If $\alpha \in \scrP$ and $\beta \in \scrC$, then it follows that $(1, \alpha) \in \scrP'$ and $(0, \beta) \in \scrC'$, so that $(1, \alpha + \beta) \in \scrP' + \scrC'$, which proves that $\scrQ \supset \{1\} \times (\scrP + \scrC)$. For the opposite inclusion, pick $(1, \gamma) \in \scrQ$. We will show that $\gamma \in \scrP+ \scrC$. Write $(1, \gamma) = (a, \alpha) + (b, \beta)$, where $(a, \alpha) \in \scrP'$ and $(b, \beta) \in \scrC'$, and $a, b$ are nonnegative numbers such that $a + b = 1$. An examination of the inequalities defining $C'$ shows that $\beta \in \scrC$ for each $r \geq 0$. If $a = 0$, then assertion \eqref{pol-to-cone-0} of \cref{exercise:pol-to-cone} implies that $\alpha = 0$. Since the origin is in $\scrP$, it follows that $\gamma = 0 + \beta \in \scrP + \scrC$. On the other hand, if $a \neq 0$, then $(1/a)\alpha \in \scrP$. Since $0 < a \leq 1$, and since $0 \in \scrP$, it follows by convexity of $\scrP$ that $\alpha \in \scrP$. Therefore $\gamma = \alpha + \beta \in \scrP+ \scrQ$, as required.
\end{proof}

\Cref{claim:cone-hedral-crossectoin} finishes the proof of $(\Leftarrow)$ implication, and therefore the proof of \cref{poly-basic-cor}.
\end{proof}

\begin{cor} \label{polyhedron-minkomposition}
Let $\scrP$ be a polyhedron in $\rr^n$.
\begin{enumerate}
\item $\scrP$ has a decomposition of the form $\scrP = \scrP_0 + \scrC + L$, where $\scrP_0$ is a polytope, $\scrC$ is strongly convex polyhedral cone, and $L$ is a linear subspace of $\rr^n$ such that $\scrC \cap L = \{0\}$. Moreover, $L$ and $\scrC + L$ are uniquely determined by $\scrP$.
\item If $\scrP$ is defined by inequalities $a_{i,0} + a_{i,1}x_1 + \cdots + a_{i,n}x_n \geq 0$, $i = 1, \ldots, N$, then
\begin{enumerate}
\item $L = \{x:a_{i,1}x_1 + \cdots + a_{i,n}x_n = 0,\ i = 1, \ldots, N\}$.
\item $\scrC + L = \{x:a_{i,1}x_1 + \cdots + a_{i,n}x_n \geq 0,\ i = 1, \ldots, N\}$.
\item For each $r \gg 1$, the set $\scrP_r := \{x:a_{i,1}x_1 + \cdots + a_{i,n}x_n = 0,\ i = 1, \ldots, N,$ and $-r \leq x_j \leq r$, $j = 1, \ldots, n\}$ is a polytope, and we can take $\scrP_0 = \scrP_r$ for any such $r$.
\end{enumerate}
\end{enumerate}
\end{cor}

\begin{proof}
Combine \cref{strongly-convex-prop,poly-basic-cor}.
\end{proof}

\begin{cor} \label{cor:polyhedral-sum-general}
The Minkowski sum of finitely many convex polyhedra is a convex polyhedron.
\end{cor}

\begin{proof}
Follows directly from \cref{cor:polyhedral-sum} and the arguments of the proof of \cref{poly-basic-cor}.
\end{proof}

\begin{cor}
The image of a polyhedron under an affine map is also a polyhedron.
\end{cor}

\begin{proof}
By \cref{exercise:affine-invariance} it suffices to consider the case of linear maps. Let $\scrP$ be a polyhedron in $\rr^n$, and $\phi:\rr^n \to \rr^m$ be a linear map. Write $\scrP = \scrP_0 + \scrC + L$ as in \cref{polyhedron-minkomposition}. Then $\phi(\scrP) = \phi(\scrP_0) + \phi(\scrC) + \phi(L)$ (\cref{exercise:linear-sum-invariance}). \Cref{poly-basic-thm,exercise:affine-image} imply that $\phi(\scrP)$ is a polytope, and $\phi(\scrC)$ is a polyhedral cone. Since $\phi(L)$ is a linear subspace of $\rr^m$ (due to linearity of $\phi$), \cref{cor:polyhedral-sum-general} implies that $\phi(\scrP)$ is a polyhedron.
\end{proof}

\subsection{Exercises}

\begin{exercise} \label{exercise:pol-to-cone}
Let $\scrP$ be a nonempty polytope in $\rr^n$ defined by inequalities $a_{i,0} + a_{i,1}x_1 + \cdots + a_{i,n}x_n \geq 0$, $i = 1, \ldots, N$. Let $\scrC_0 := \{x \in \rr^n: a_{i,1}x_1 + \cdots + a_{i,n}x_n \geq 0,\ 1 \leq i \leq N\}$, and $\scrC$ be the cone generated by $\{1\} \times \scrP$ in $\rr^{n+1} = \rr \times \rr^n$.
\begin{enumerate}
\item \label{pol-to-cone-0} Show that $\scrC_0 = \{0\}$. [Hint: $\scrC_0$ is a cone, $\scrC_0 + \scrP\subset\scrP$, and $\scrP$ is bounded.]
\item Deduce that $\scrC$ is a polyhedral cone in $\rr^{n+1}$ defined by the inequalities $x_0 \geq 0$ and $a_{i,0}x_0 + a_{i,1}x_1 + \cdots + a_{i,n}x_n \geq 0$, $i = 1, \ldots, N$.
\item Show that the assumption ``$\scrP$ is nonempty'' is necessary in the preceding statements. In particular, show by an example that $\scrC_0$ may be a nontrivial cone if $\scrP = \emptyset$.
\end{enumerate}
\end{exercise}

\begin{exercise} \label{exercise:pol-to-hull}
Show that if the $(\im)$ implication of assertion \eqref{characterize-cone} of \cref{poly-basic-thm} holds for all $n$, then the $(\im)$ direction of assertion \eqref{characterize-polytope} of \cref{poly-basic-thm} also holds for all $n$. [Hint: use \cref{exercise:pol-to-cone}.]
\end{exercise}

\begin{exercise} \label{exercise:cone-to-cone}
Let $\scrC$ be a polyhedral cone in $\rr^n$. \Cref{exercise:cone-inequalities} implies that $\scrC$ is defined by finitely many inequalities of the form $a_1x_1 + \cdots + a_nx_n \geq 0$. Show that the closure in $\rr^{n+1}$ of the cone generated by $\{1\} \times \scrC$ is a polyhedral cone defined by the same inequalities as the ones defining $\scrC$ coupled with $x_0 \geq 0$.
\end{exercise}

\begin{exercise} \label{exercise:minkomposition-uniqueness}
Let $\scrP \subset \rr^n$.
\begin{enumerate}
\item Assume $\scrP = \scrP_1 + \scrC_1 = \scrP_2 + \scrC_2$, where $\scrP_j$ are bounded and $\scrC_j$ are closed cones. Prove that $\scrC_1 = \scrC_2$. Show by examples that it is possible to have $\scrP_1 \neq \scrP_2$.
\item Assume $\scrP = \scrC_1 + L_1 =  \scrC_2 + L_2$ where $\scrC_j$ are strongly convex polyhedral cones and $L_j$ are linear subspaces of $\rr^n$ such that $\scrC_j \cap L_j = \{0\}$. Prove that $L_1 = L_2$. Show by examples that it is possible to have $\scrC_1 \neq \scrC_2$.
\item Assume $\scrP = \scrP_1 + \scrC_1 + L_1 = \scrP_2 + \scrC_2 + L_2$ where $\scrP_j$ are polytopes, $\scrC_j$ are strongly convex polyhedral cones and $L_j$ are linear subspaces of $\rr^n$ such that $\scrC_j \cap L_j = \{0\}$. Prove that $L_1 = L_2$ and $\scrC_1 + L_1 = \scrC_2 + L_2$.
\end{enumerate}
[Hint: we may assume \woutlog\ that $\scrP$ contains origin. Then for the first assertion pick $\alpha \in \scrP$ such that $r\alpha \in \scrP$ for each $r \geq 0$. Express $\alpha$ as a sum of elements of $\frac{1}{r}\scrP_j$ and $\scrC_j$, and then take the limit as $r \to \infty$ to show that each $\scrC_j$ must be the largest cone contained in $\scrP$. For the second assertion prove that each $L_j$ is the largest linear subspace of $\rr^n$ contained in $\scrP$ as follows: pick $\alpha \in \rr^n$ such that both $\alpha$ and $-\alpha$ are in $\scrP$. Express both $\alpha$ and $-\alpha$ as elements of $\scrC_j + L_j$, add them up, and use the condition that $\scrC_j \cap L_j = \{0\}$ to show that $\alpha \in L_j$.]
\end{exercise}

\section{Basic properties of convex polyhedra} \label{poly-basic-section}
In this section we establish a few basic properties of convex polyhedra. Throughout this section $\scrP$ will denote a {\em nonempty} convex polyhedron in $\rr^n$. The first property we state follows directly from the definition of a polyhedron:

\begin{prop} \label{poly-separation}
For each $\alpha \in \rr^n \setminus \scrP$, there is $\nu \in \rnstar$ such that $\min_\scrP(\nu)$ exists and $\langle \nu, \alpha \rangle < \min_\scrP(\nu)$. \qed
\end{prop}

Geometrically, \cref{poly-separation} states that every point in the complement of $\scrP$ is separated from $\scrP$ by a hyperplane - see \cref{fig:pols-0}. A {\em face} of $\scrP$ is a subset of the form $\In_\nu(\scrP)$ for some $\nu \in \rnstar$.

\begin{figure}[h]
\def\xmin{-0.5}
\def\xmax{16.5}
\def\ymin{-4.5}
\def\ymax{5.5}
\def\tx{0}
\def\ty{5}
\def\tw{5cm}

\tikzstyle{dot} = [\colordot, circle, minimum size=4pt, inner sep = 0pt, fill]

\begin{center}

\begin{tikzpicture}[scale=\scalefactor]

\coordinate (A) at (1,-4);
\coordinate (B) at (16,1);
\coordinate (C) at (10,5);
\fill[\colorzero, opacity=\opazero ] (A) --  (B) -- (C) -- cycle;
\draw[thick, \colorone] (A) --  (B) -- (C) -- cycle;

\node[dot] at (A) {};
\node[dot] at (B) {};
\node[dot] at (C) {};

\coordinate (nu) at (0,-1);

\coordinate (eta) at (-2,-3);
\coordinate (etaperp) at (-3,2);

\node[anchor = north] at (A) {\picfontsize $A$};
\node[anchor = north] at (B) {\picfontsize $B$};
\node[anchor = south] at (C) {\picfontsize $C$};

\coordinate (A1) at (1,5);
\coordinate (B1) at (16,5);
\coordinate (O) at (6.5,5);
\draw[thick, \colortwo, dashed] (A1) -- (B1);
\draw [thick, \colornu, ->] (O) -- ($(O) + (nu)$);
\node[anchor = north] at ($(O) + (nu)$) {\picfontsize $\nu$};
\node[anchor = south] at ($(B1)$) {\picfontsize $L$};

\coordinate (out) at (3, 6);
\node[dot] at (out) {};
\node[anchor = west] at (out) {\picfontsize $\alpha$};

\coordinate (O) at ($(B)!0.5!(C)$);
\draw[thick, \colortwo, dashed] ($(B)-(etaperp)$) --  ($(C)+(etaperp)$);
\draw [thick, \colornu, ->] (O) -- ($(O) + 0.3*(eta)$);
\node[anchor = east] at ($(O) + 0.3*(eta)$) {\picfontsize $\eta$};
\node at (9,{2/3}) {\picfontsize $\scrP$};
\end{tikzpicture}

\caption{
	$\In_\nu(\scrP) = \{C\}$, $\In_\eta(\scrP) = BC$. The line $L$ separates $\scrP$ from $\alpha$.

} \label{fig:pols-0}
\end{center}
\end{figure}

\begin{prop} \label{facedron}
Every face of $\scrP$ is a convex polyhedron. If $\scrP$ is a polytope (respectively polyhedral cone), then every face of $\scrP$ is also a polytope (respectively, polyhedral cone).
\end{prop}

\begin{proof}
The case of a convex polyhedron and that of a polytope are direct consequences of the definitions of polyhedra, polytopes and faces. The case of a polyhedral cone follows from combining \cref{exercise:cone-inequalities,exercise:minconelinear}.
\end{proof}

We also note the following property whose proof is left as an exercise:

\begin{prop} \label{prop:face-invariance}
Let $\phi: \scrP\to \scrQ$ be an affine isomorphism of convex polyhedra. Then $\phi$ induces a bijection of faces, i.e.\ $\scrR \subseteq \scrP$ is a face of $\scrP$ if and only if $\phi(\scrR)$ is a face of $\scrQ$.
\end{prop}

\begin{proof}
This is \cref{exercise:face-invariance}.
\end{proof}

\Cref{facedron} implies that every face of $\scrP$ is a polyhedron, and therefore has a well-defined dimension. A {\em vertex} (respectively, {\em edge, facet}) is a face of dimension zero (respectively one, $\dim(\scrP) - 1$). In \cref{fig:pols-0} the vertices of $\scrP$ are $A,B,C$, and the edges are the three sides. \Cref{prop:finite-vertedges} below gives a more precise description of vertices and edges. The part of the proposition about finiteness of numbers of vertices and edges is a special case of the more general result (\cref{prop:finite-faces}) that a polyhedron can have only finitely many faces. We will also see later that every polytope is the convex hull of its vertices (as it is evident for $\scrP$ from \cref{fig:pols-0}).

\begin{prop} \label{prop:finite-vertedges}
Every vertex of a polyhedron is a singleton, and up to an affine isomorphism, every edge is a (possibly unbounded) closed interval of $\rr$. Every polytope has finitely many vertices. Every strongly convex polyhedral cone has only one vertex (namely, the origin) and finitely many edges.
\end{prop}

\begin{proof}
The first statement follows directly from \cref{exercise:zerone-dim-pol}. By \cref{poly-basic-thm} every polytope $\scrP$ is the convex hull of a finite set. The first statement together with \cref{exercise:conv-rep} then implies that $\scrP$ has only finitely many vertices. Now let $\scrC$ be a strongly convex polyhedral cone. \Cref{poly-basic-thm} implies that the origin is a vertex of $\scrC$. Since every face of $\scrC$ is also a cone (\cref{facedron}), and since the only zero-dimensional cone is the origin, it follows that the origin is the only vertex of $\scrC$. The finiteness of the numbers of edges of $\scrC$ follows from \cref{exercise:cone-to-pol} and finiteness of the numbers of vertices of polytopes.
\end{proof}

Note in \cref{fig:pols-0} every pair of edges of $\scrP$ intersects in a vertex. The following result shows that this corresponds to a general phenomenon:

\begin{prop} \label{prop:facection}
The intersection of finitely many faces of $\scrP$ is also a face of $\scrP$, provided the intersection is nonempty.
\end{prop}

\begin{proof}
Let $\scrQ := \In_\nu(\scrP)$ and $\scrR := \In_\eta(\scrP)$ be faces of $\scrP$ with $\scrQ \cap \scrR \neq \emptyset$. It is then straightforward to check that $\scrQ \cap \scrR = \In_{\nu + \eta}(\scrP)$. [Where is it used that $\scrQ \cap \scrR \neq \emptyset$? See \cref{exercise:facection-counter-example}.]
\end{proof}

Every polyhedron $\scrP$ is a face of itself, since $\scrP = \In_0 (\scrP)$. A {\em proper face} of $\scrP$ is a face which is properly contained in $\scrP$, and the {\em relative interior} $\relint(\scrP)$ of $\scrP$ is the complement in $\scrP$ of the union of its proper faces. In \cref{fig:pols-0} the relative interior is the complement in $\scrP$ of the union of the three edges.

\begin{prop} \label{prop:relative-containment}
Let $\scrQ, \scrR$ be faces of $\scrP$.
\begin{enumerate}
\item \label{relatively-smaller-dim} If $\scrQ$ is a proper face of $\scrP$, then $\dim(\scrQ) < \dim(\scrP)$.
\item If $\scrQ \cap \relint(\scrR) \neq \emptyset$, then $\scrQ \supset \scrR$.
\end{enumerate}
\end{prop}

\begin{proof}
The first assertion is an immediate consequence of the observation that if $\nu \in \rnstar$ is non-constant on an affine subspace $H$ of $\rr^n$, then for every $r \in \rr$, $\{ \alpha \in H: \langle \nu, \alpha \rangle = r\}$ is an affine subspace of $\rr^n$ whose dimension is one less than that of $H$. For the second assertion, note that if $\scrQ \cap \scrR \neq \emptyset$, then by \cref{prop:facection} $\scrQ \cap \scrR$ is a face of $\scrR$, and it can not be a proper face of $\scrR$ if it contains a point from $\relint(\scrR)$.
\end{proof}

Note that in \cref{fig:pols-0} the relative interior of $\scrP$ is also its {\em topological interior}\footnote{A point $x \in S \subseteq \rr^n$ is in the topological interior of $S$ if and only if $S$ contains an open neighborhood of $x$ in $\rr^n$.} in $\rr^2$. We will now see that this is a manifestation of a general property of polyhedra.

\begin{prop} \label{prop:relint-inequalities}
$\scrP$ is the closure of its relative interior. In particular, $\relint(\scrP)$ is nonempty, and it is precisely the topological interior of $\scrP$ in $\aff(\scrP)$ (where $\aff(\scrP)$ is equipped with the relative topology from $\rr^n$). In particular, $\relint(\scrP)$ is a nonempty relatively open subset of $\aff(\scrP)$. In the case that $\scrP \subset \rr^n$ is ``full dimensional'' (i.e.\ $\dim(\scrP) = n$), and $a_{i,0} +  a_{i,1}x_1 + \cdots + a_{i,n}x_n \geq 0$, $i = 1, \ldots, N$, are a set of ``nontrivial inequalities''\footnote{``Nontrivial inequalities'' means that we do not allows inequalities with $a_{i,0} = \cdots = a_{i,n} = 0$.} defining $\scrP$, then $\relint(\scrP)$ is the nonempty open set of $\rr^n$ defined by the strict inequalities $a_{i,0} +  a_{i,1}x_1 + \cdots + a_{i,n}x_n > 0$, $i = 1, \ldots, N$.
\end{prop}

\begin{proof}
Due to \cref{exercise:eq-dim-embedding,exercise:affine-invariance,exercise:face-invariance} it suffices to consider the case that $\scrP$ is full dimensional. For each $i$, let $H_i$ be the hyperplane $a_{i,0} +  a_{i,1}x_1 + \cdots + a_{i,n}x_n = 0$. Let $\scrP^0 := \{x \in \rr^n:a_{i,0} +  a_{i,1}x_1 + \cdots + a_{i,n}x_n > 0,\ i = 1, \ldots, N\} = \scrP \setminus \bigcup_i H_i$. \Cref{exercise:top-bdry} implies that $\scrP^0$ is the topological interior of $\scrP$. We claim that $\scrP^0 \neq \emptyset$. Indeed, for each $i = 1, \ldots, N$, there is $\alpha_i \in \scrP$ such that $a_{i,0} +  a_{i,1}x_1 + \cdots + a_{i,n}x_n > 0$, since otherwise $\scrP$ would be contained in $H_i$, and $\dim(\scrP)$ would be less than $n$. Since $\scrP$ is convex, $\alpha := (1/N)\sum_{i=1}^N \alpha_i \in \scrP$. It is straightforward then to check that $\alpha \in \scrP^0$, as required. We now show that $\scrP^0 = \relint(\scrP)$. The full-dimensionality of $\scrP$ also implies that $H_i \cap \scrP$ is a proper face of $\scrP$ for each $i$, so that $\scrP^0 \supset \relint(\scrP)$. On the other hand, if $\alpha \in \scrP^0$, then by openness of $\scrP^0$, for every $\nu \in \rnstar \setminus \{0\}$, there is $\alpha' \in \scrP^0$ such that $\langle \nu, \alpha' \rangle < \langle \nu, \alpha \rangle$, so that $\alpha \not\in \In_\nu(\scrP)$. This shows that $\scrP^0 \subset \relint(\scrP)$, and therefore $\scrP^0 = \relint(\scrP)$. Finally, to see that $\scrP$ is the closure of its relative interior, let $\beta := (\beta_1, \ldots, \beta_n) \in \relint(\scrP)$. Given $\gamma = (\gamma_1, \ldots, \gamma_n) \in \scrP$, let $L := \{(1-\epsilon)\beta + \epsilon\gamma: 0 \leq \epsilon \leq \beta \}$ be the line segment from $\beta$ to $\gamma$. We claim that $L \setminus \{\gamma\} \subseteq \relint(\scrP)$. Indeed, for each $i = 1, \ldots,N$, let
\begin{align*}
\epsilon_i
	&:= \sup\{\epsilon: 0 \leq \epsilon \leq 1,\
		a_{i,0} +  a_{i,1}((1-\epsilon) \beta_1 + \epsilon\gamma_1) +  \cdots +  a_{i,n}((1-\epsilon) \beta_n + \epsilon\gamma_n)
		> 0 \}
\end{align*}
Note that each of the functions $a_{i,0} +  a_{i,1}((1-\epsilon) \beta_1 + \epsilon\gamma_1) +  \cdots +  a_{i,n}((1-\epsilon) \beta_n + \epsilon\gamma_n)$ is linear in $\epsilon$, and it is strictly positive at $\epsilon = 0$. Therefore if $\epsilon_i < 1$, then it must be zero at $\epsilon_i$ and negative on the interval $(\epsilon_i, 1]$, contradicting the fact that $L \subset \scrP$. Therefore $\epsilon_i = 1$ for each $i$, and consequently, $L\setminus \{\gamma\} \subset \scrP^0 = \relint(\scrP)$. This implies that $\scrP$ is the closure of $\relint(\scrP)$, as required.
\end{proof}

\begin{prop} \label{prop:sum-faces}
Let $\scrP_1, \ldots, \scrP_s$ be polyhedra in $\rr^n$, and $\nu \in \rnstar$. Then
\begin{enumerate}
\item \label{sum-faces:existence} $\min_{\sum_j \scrP_j}(\nu)$ exists if and only if $\min_{\scrP_j}(\nu)$ exists for each $j$.
\end{enumerate}
Now assume $\min_{\sum_j \scrP_j}(\nu)$ exists. Then
\begin{enumerate}[resume]
\item \label{sum-faces:min} $\min_{\sum_j \scrP_j}(\nu) = \sum_j \min_{\scrP_j}(\nu)$.
\item \label{sum-faces:sum} $\In_\nu(\sum_j \scrP_j) = \sum_j \In_\nu(\scrP_j)$.
\item \label{sum-faces:uniqueness} $\In_\nu(\scrP_j)$ are the ``unique maximal'' subsets of $\scrP_j$ whose sum is $\In_\nu(\sum_j \scrP_j)$, i.e.\ if $\alpha_j \in \scrP_j$ are such that $\sum_j \alpha_j \in \In_\nu(\sum_j \scrP_j)$, then $\alpha_j \in \In_\nu(\scrP_j)$ for each $j$.
\item \label{sum-faces:polytope-uniqueness} If each $\scrP_j$ is a polytope, then $\In_\nu(\scrP_j)$ are in fact unique faces of $\scrP_j$ whose sum is $\In_\nu(\sum_j \scrP_j)$, i.e.\ if $\scrQ_j$ are faces of $\scrP_j$ such that $\sum_j \scrQ_j = \In_\nu(\sum_j \scrP_j)$, then $\scrQ_j = \In_\nu(\scrP_j)$ for each $j$.
\item \label{sum-faces:conelinear} Assume there is $j$ such that
\begin{enumerate}
\item \label{conelinear:cone} either $\scrP_j$ is a cone, or
\item \label{conelinear:linear} $\scrP_j$ is a linear subspace of $\rr^n$.
\end{enumerate}
Then $\In_\nu(\scrP_j)$ contains the origin and $\min_{\scrP_j}(\nu) = 0$. In addition in case \eqref{conelinear:linear}, $\scrP_j \subset \nu^\perp$, and $\In_\nu(\scrP_j) = \scrP_j$.
\end{enumerate}
\end{prop}

\begin{proof}
It suffices to treat the case $s = 2$. Assume at first $\min_{\scrP_1}(\nu)$ does not exist. Then there are $\alpha_k \in \scrP_1$ such that $\langle \nu, \alpha_k \rangle \to -\infty$. If $\beta$ is an arbitrary element in $\scrP_2$, then $\langle \nu, \alpha_k + \beta \rangle \to -\infty$ as well, so that $\min_{\sum_j \scrP_j}(\nu)$ does not exist. On the other hand, if $\min_{\scrP_j}(\nu)$ exists for each $j$, then pick $\alpha_j \in \In_\nu(\scrP_j)$ for each $j$, and note that for all $\beta_j \in \scrP_j$, $\langle \nu, \sum_j \beta_j \rangle \geq \sum_j \langle \nu, \alpha_j \rangle =  \langle \nu, \sum_j \alpha_j\rangle$. This simultaneously proves assertions \eqref{sum-faces:existence} to \eqref{sum-faces:sum}. For assertion \eqref{sum-faces:uniqueness} note that if $\alpha_1 \not\in \In_\nu(\scrP_1)$, then $\langle \nu, \alpha_1 \rangle > \min_{\scrP_1}(\nu)$. It follows that for each $\alpha_2 \in \scrP_2$, $\langle \nu, \alpha_1 + \alpha_2 \rangle > \min_{\scrP_1}(\nu) + \min_{\scrP_2}(\nu)$, so that $\alpha_1 + \alpha_2 \not\in \In_\nu(\scrP_1 + \scrP_2)$. For assertion \eqref{sum-faces:polytope-uniqueness} assume $\scrQ_1 \subsetneq \In_\nu(\scrP_1)$. Since $\scrQ_j$ is a polytope, there is $\eta \in \rnstar$ such that $\min_{\scrQ_1}(\eta) > \min_{\In_\nu(\scrP_1)} (\eta)$. On the other hand, $\In_\nu(\scrP_j)$ is a polytope for each $j$, and therefore by assertion \eqref{sum-faces:existence},
\begin{align*}
\min_{\scrQ_1 + \In_\nu(\scrP_2)}(\eta)
	&= \min_{\scrQ_1}(\eta)  + \min_{\In_\nu(\scrP_2)}(\eta)
	> \min_{\In_\nu(\scrP_1)}(\eta)  + \min_{\In_\nu(\scrP_2)}(\eta)
	= \min_{\In_\nu(\scrP_1) + \In_\nu(\scrP_2)}(\eta)
\end{align*}
It follows that $\scrQ_1 + \In_\nu(\scrP_2) \neq \In_\nu(\scrP_1)(\eta)  + \In_\nu(\scrP_2)$, as required. Finally, assertion \eqref{sum-faces:conelinear} follows directly from \cref{exercise:minconelinear}.
\end{proof}

The example from \cref{fig:non-unique-sum} shows that assertion \eqref{sum-faces:polytope-uniqueness} of \cref{prop:sum-faces} may not be true if some of the $\scrP_j$ are not bounded [what goes wrong with the proof?]. On the other hand, if $\scrP_j$ are polytopes, then it is not too hard to show that it remains true even if $\scrQ_j$ are allowed to be arbitrary convex subsets of $\scrP_j$, i.e.\ $\In_\nu(\scrP_j)$ are unique {\em convex} subsets of $\scrP_j$ whose sum is $\In_\nu(\sum_j \scrP_j)$. \Cref{exercise:non-unique-sum-faces} asks you to show that convexity is necessary for uniqueness.

\begin{cor} \label{prop:finite-faces}
Every polyhedron has finitely many distinct faces.
\end{cor}

\begin{proof}
Let $\nu \in \rnstar$. If $\scrP_0 = \conv(S)$ for some finite set $S \subset \rr^n$, \cref{exercise:positively-convex} implies that $\In_\nu(\scrP_0) = \conv(\In_\nu(S))$; in particular, every face of the polytope $\scrP_0$ is the convex hull of a subset of $S$, and therefore $\scrP_0$ has finitely many distinct faces. Now consider the case that $\scrC = \cone(T)$ for a finite subset $T$ of $\rr^n$. If $\min_\scrC(\nu)$ exists, then \cref{prop:sum-faces} implies that $\min_\scrC(\nu) = 0$ and $\In_\nu(\scrC) = \nu^\perp \cap \scrC = \cone(\nu^\perp \cap T)$. Therefore, the number of distinct faces of $\scrC$ is bounded by the number of subsets of $T$. By \cref{polyhedron-minkomposition} every polyhedron $\scrP$ be can be expressed as $\scrP_0 + \scrC + L$, where $\scrP_0$ is a polytope, $\scrC$ is a strongly convex polyhedral cone, and $L$ is a linear subspace of $\rr^n$. \Cref{prop:sum-faces} then implies that every face of $\scrP$ is of the form $\scrP'_0 + \scrC' + L$, where $\scrP'_0$ (respectively, $\scrC'$) is a face of $\scrP_0$ (respectively, $\scrC$). The result then follows from the cases of polytopes and polyhedral cones.
\end{proof}

\begin{center}
\begin{figure}[h]
\def\viewx{60}
\def\viewy{30}
\begin{tikzpicture}[scale=0.75]

\pgfplotsset{view={\viewx}{\viewy}}

\begin{axis}[axis lines = none]
	\addplot3 [draw, thick, fill=\colorzero,opacity=\opazero] coordinates{(0,0,1) (0,1,0) (1,0,0) (0,0,1)};
	\addplot3 [draw, thick, fill=\colorone,opacity=\opazero] coordinates{(0,0,0) (1,0,0) (0,0,1) (0,0,0)};
	\addplot3 [dashed, \colortwo, thick] coordinates{(0,0,0) (0,1,0)};
	\addplot3 [\colortwo, thick] coordinates{(0.3,0,0.7) (0,0.8,0.2)};
\end{axis}

\draw (0,1.5) node {\picfontsize $O$};
\draw (0,4.75) node {\picfontsize $C$};
\draw (2.5,-0.1) node {\picfontsize $A$};
\draw (4.6,2.75) node {\picfontsize $B$};

\end{tikzpicture}

\caption{$ABC$ is the minimal face containing edges $AC$ and $BC$. The relative interior of the line segment from a point in $\relint(AC)$ to a point in $\relint(BC)$ is contained in $\relint(ABC)$.} \label{fig:positively-relative}
\end{figure}
\end{center}

As a corollary of the finiteness of the number of faces, we now prove a more technical result that we use in \cref{normal-section}. It shows that given two faces $\scrQ_1, \scrQ_2$ of a polyhedron $\scrP$, there is a ``smallest'' face $\scrQ$ of $\scrP$ that contains both $\scrQ_j$, and given two points in the relative interiors of the $\scrQ_j$, the relative interior of the line segment joining these points is contained in the relative interior of $\scrQ$, see \cref{fig:positively-relative}.

\begin{cor} \label{prop:positively-relative}
Let $\scrQ_1, \scrQ_2$ be faces of a convex polyhedron $\scrP$.
\begin{enumerate}
\item There is a (unique) face $\scrQ$ of $\scrP$ such that $\scrQ_1 \cup \scrQ_2 \subset \scrQ$, and $\scrQ \subset \scrQ'$ for every face $\scrQ'$ of $\scrP$ such that $\scrQ_1 \cup \scrQ_2 \subset \scrQ'$.
\item Pick $\alpha_i \in \relint(\scrQ_i)$, $i = 1,2$. Then for every $\epsilon \in (0,1)$, the positive convex combination $\epsilon \alpha_1 + (1- \epsilon)\alpha_2$ of $\alpha_1$ and $\alpha_2$ is in the relative interior of $\scrQ$.
\end{enumerate}
\end{cor}

\begin{proof}
Let $\scrQ$ be the intersection of all faces of $\scrP$ containing both $\scrQ_j$. \Cref{prop:facection,prop:finite-faces} imply that $\scrQ$ is a face of $\scrP$, and it is clearly as in the first assertion. The second assertion follows from \cref{exercise:positively-convex} and the definition of relative interior.
\end{proof}

The following proposition shows that the property of being a face is transitive. Note that this is clear in \cref{fig:pols-0,fig:positively-relative}: every vertex of every edge of $\scrP$ is also a vertex of $\scrP$.

\begin{prop} \label{prop:face-of-face}
Every face of a face of $\scrP$ is also a face of $\scrP$.
\end{prop}

\begin{proof}
Let $\scrQ := \In_\nu(\scrP)$ and $\scrR := \In_\eta(\scrQ)$, $\nu, \eta \in \rnstar$. Let $\scrP = \scrP_0 + \scrC + L$ be a decomposition as in \cref{polyhedron-minkomposition}. \Cref{prop:sum-faces} then implies that
\begin{prooflist}
\item \label{face-of-face:Q} $\scrQ = \In_\nu(\scrP_0) + \In_\nu(\scrC) + L$, where $\nu|_L \equiv 0$ and $\min_\scrC(\nu) = 0$;
\item \label{face-of-face:R} $\scrR = \In_\eta(\In_\nu(\scrP_0)) + \In_\eta(\In_\nu(\scrC)) + L$, where $\eta|_L \equiv 0$, and $\min_{\In_\nu(\scrC)}(\eta) = 0$.
\end{prooflist}
Due to \cref{prop:face-invariance} after a translation of $\scrP$ if necessary we may further assume that $\In_\nu(\scrP_0)$ contains the origin, which implies that
\begin{prooflist}[resume]
\item \label{face-of-face:min-P0-nu} $\min_{\scrP_0}(\nu) = 0$, and
\item \label{face-of-face:Q-containment} $\scrQ \supset \In_\nu(\scrP_0) \cup \In_\nu(\scrC) \cup L$.
\end{prooflist}
By \cref{poly-basic-thm} there are finite sets $S,T \subset \rr^n$ such that $\scrP_0 = \conv(S)$ and $\scrC = \cone(T)$. By observations \ref{face-of-face:Q} and \ref{face-of-face:min-P0-nu}, $\nu$ is nonnegative on $S \cup T$, and therefore we may choose $r \geq 0$ such that $\langle r\nu + \eta, \alpha \rangle > 0$ for each $\alpha \in (S \cup T) \setminus \nu^\perp$.

\begin{proclaim} \label{face-of-face:claim:r}
$\scrR = \In_{\nu+ r\eta}(\scrP)$.
\end{proclaim}

\begin{proof}
This is left as \cref{exercise:claim:r}.

\end{proof}
The proposition follows immediately from \cref{face-of-face:claim:r}.
\end{proof}

\begin{prop} \label{prop:vertex-hull}
Let $\scrP$ be a polytope and $\scrV$ be the set of vertices of $\scrP$.
\begin{enumerate}
\item $\scrP = \conv(\scrV)$.
\item $\scrV$ is the unique minimal set whose convex hull is $\scrP$.
\item \label{vertex-hull:relatively-positive} $\relint(\scrP)$ is the set of {\em positive} convex combinations of its vertices, i.e.\ $\alpha \in \relint(\scrP)$ if and only if $\alpha = \sum_{\beta \in \scrV} \epsilon_\beta \beta$, where $\epsilon_\beta$ are positive real numbers such that $\sum_{\beta \in \scrV} \epsilon_\beta = 1$.
\end{enumerate}
\end{prop}

\begin{proof}
For the first assertion proceed by induction on $\dim(\scrP)$. It is evident when $\dim(\scrP) = 0$. Now consider the case that $\dim(\scrP) \geq 1$. Take $\alpha \in \scrP$. If $\alpha \not\in \relint(\scrP)$, then it is on a proper face $\scrQ$ of $\scrP$. Since $\dim(\scrQ) < \dim(\scrP)$, by induction $\alpha$ is in the convex hull of vertices of $\scrQ$. \Cref{prop:face-of-face} implies that every vertex of $\scrQ$ is also a vertex of $\scrP$, so that $\alpha \in \conv(\scrV)$, as required. If $\alpha \in \relint(\scrP)$, then take a line $L$ through $\alpha$ on $\aff(\scrP)$. Since $\scrP$ is bounded, \cref{prop:relint-inequalities} implies that each end of $L$ intersects a proper face of $\scrP$. Since we already showed that every proper face of $\scrP$ is in $\conv(\scrP)$, it follows that $\alpha \in \conv(\scrV)$ and completes the proof of the first assertion. The second assertion and the $(\Leftarrow)$ implication of the third assertion follow from the first assertion and \cref{exercise:positively-convex}. Now pick $\alpha \in \relint(\scrP)$. It remains to show that $\alpha$ is a positive convex combination of the vertices of $\scrP$. By \cref{prop:finite-vertedges} we may assume $\dim(\scrP) \geq 1$. Since $\relint(\scrP)$ is relatively open in $\aff(\scrP)$ (\cref{prop:relint-inequalities}), $\alpha - \epsilon \sum_{\beta \in \scrV} \beta \in \relint(\scrP)$ for sufficiently small positive $\epsilon$. By the first assertion then $\alpha - \epsilon \sum_{\beta \in \scrV} \beta \in \conv(\scrV)$. It then follows that $\alpha$ is a positive convex combination of elements from $\scrV$, as required.
\end{proof}

\begin{cor} \label{prop:edge-hull}
If $\scrC$ is a strongly convex polyhedral cone, then
\begin{enumerate}[resume]
\item $\scrC$ is the cone generated by its edges.
\item $\relint(\scrC)$ is the set of {\em positive} linear combinations of nonzero elements of its edges, i.e.\ if $\scrE$ is the set consisting of one nonzero element from each of the edges of $\scrC$, then $\alpha \in \relint(\scrC)$ if and only if $\alpha = \sum_{\beta \in \scrE} r_\beta \beta$, where $r_\beta$ are positive real numbers.
\end{enumerate}
\end{cor}

\begin{proof}
Combine \cref{prop:vertex-hull,exercise:cone-to-pol}.
\end{proof}

\begin{center}
\begin{figure}[h]

\def\scalefactor{.3}
\def\xmin{-2}
\def\xmax{9}
\def\ymin{-6}
\def\ymax{3}
\def\nux{6}

\tikzstyle{dot} = [\colordot, circle, minimum size=4pt, inner sep = 0pt, fill]

\begin{tikzpicture}[scale=\scalefactor]

\coordinate (O) at (0,0);
\coordinate (A) at (3,-2);
\coordinate (B) at (4,-1);
\coordinate (C) at (4,4/3);
\coordinate (A') at (9,-6);
\coordinate (C') at (9,3);

\fill [\colorzero, opacity=\opazero ] (O) --  (A') -- (C') -- cycle;

\draw[thick, \colorone ] (O) --  (A');
\draw[thick, \colorone ] (O) --  (C');

\draw (\xmax, 0) -- (\xmin, 0);
\draw (0, \ymax) -- (0, \ymin);

\node[dot] at (O){};
\node[dot] at (A){};
\node[dot] at (B){};
\node[dot] at (C){};
\node[anchor = west] at (\xmax, 0) {\picfontsize $x_{k+1}$};
\node[anchor = south] at (0, \ymax) {\picfontsize $x_{k+2}$};

\coordinate (nu1) at (2,3);
\coordinate (nu2) at (1,-3);
\pgfmathsetmacro\nuratio{sqrt(1.3)};
\def\nuonescale{0.4}

\pgfmathsetmacro\nutwoscale{\nuonescale*\nuratio};
\coordinate (nu1base) at (\nux, {-2*\nux/3});
\coordinate (nu1head) at ($(nu1base) + \nuonescale*(nu1)$);
\draw [thick, \colornu, ->] (nu1base) -- (nu1head);
\node[anchor = west] at (nu1head) {\picfontsize $\eta_1$};

\coordinate (nu2base) at (\nux, {\nux/3});
\coordinate (nu2head) at ($(nu2base) + \nuonescale*\nuratio*(nu2)$);
\draw [thick, \colornu, ->] (nu2base) -- (nu2head);
\node[anchor = west] at (nu2head) {\picfontsize $\eta_2$};

\end{tikzpicture}

\caption{
$\cone(\pi(S \cup T))$ is a two dimensional cone contained in the half-plane $x_{k+1} \geq 0$, and intersects $x_{k+2}$-axis only at the origin.

} \label{fig:pos-2jection}

\end{figure}
\end{center}

\begin{prop} \label{prop:facet-containment}
Every proper face $\scrQ$ of a polyhedron $\scrP$ is the intersection of facets of $\scrP$ containing $\scrQ$. In particular, every proper face is contained in a facet.
\end{prop}

\begin{proof}
Let $\scrP = \scrP_0 + \scrC+L$ be a decomposition of $\scrP$ as in \cref{polyhedron-minkomposition}. Let $\scrQ = \In_\nu(\scrP)$, $\nu \in \rnstar$, be a proper face of $\scrP$. \Cref{prop:sum-faces} implies that $\scrQ = \In_\nu(\scrP_0) + \In_\nu(\scrC) + L$, where $\nu|_L \equiv 0$ and $\min_\scrC(\nu) = 0$. Due to \cref{prop:face-invariance} after an affine isomorphism of $\scrP$ if necessary we may further assume that $\dim(\scrP) = n$, and $\aff(\scrQ)$ is the coordinate subspace of $\rr^n$ spanned by the first $k$-coordinates, where $k := \dim(\scrQ) < n$, and $\nu$ is the projection on to the $(k+1)$-th coordinate. If $n=k+1$, then $\scrQ$ is a facet, and we are done. So assume $n - k \geq 2$. Choose finite sets $S, T$ such that $\scrP_0 = \conv(S)$ and $\scrC = \cone(T)$. Let $\pi$ be the projection map from $\rr^n$ onto the $2$-dimensional coordinate subspace spanned by the $(k+1)$-th and $(k+2)$-th coordinate. By construction every nonzero element of $\pi(S \cup T)$ has {\em positive} $x_{k+1}$-coordinate. We claim that the cone generated by $\pi(S \cup T)$ is two dimensional, i.e.\ it is as in \cref{fig:pos-2jection}. Indeed, by construction $\pi(L) = 0$, so that \cref{exercise:affine-image,exercise:linear-sum-invariance} imply that $\pi(\scrP) = \pi(\scrP_0) + \pi(\scrC) = \conv(\pi(S)) + \cone(\pi(T)) \subseteq \cone(\pi(S \cup T))$. Therefore, if $\cone(\pi(S \cup T))$ is contained in a line $L$, and $\scrP$ would be contained in $\pi^{-1}(L)$, contradicting the full-dimensionality of $\scrP$. It follows that $\dim(\cone(\pi(S\cup T))) = 2$, and $\cone(\pi(S \cup T))$ has two edges (\cref{exercise:2-cone}). As in \cref{fig:pos-2jection}, let $\eta_1, \eta_2$ be the elements in $\rnnstar{2}$ which attains their minima on the two edges of $\cone(\pi(S \cup T))$. It is straightforward to check that
\begin{itemize}
\item for each $j$, $\scrR_j := \In_{\pi^*(\eta_j)}(\scrP)$ is a face of $\scrP$ such that $\scrR_j \supset \scrQ$ and $\dim(\scrR_j) > \dim(\scrQ)$,
\item If $n = k+2$, then each $\scrR_j$ is a facet of $\scrP$, and $\scrQ = \scrR_1 \cap \scrR_2$.
\end{itemize}
The proposition follows from these observations by a straightforward induction on $\dim(\scrP) - \dim(\scrQ)$.
\end{proof}

\begin{cor} \label{prop:minimal-polynequalities}
Let $\scrP$ be an $n$-dimensional polyhedron in $\rr^n$. Assume $\scrP \neq \rr^n$. Then $\scrP$ is determined by the affine hyperplanes corresponding to facets of $\scrP$. More precisely,
\begin{enumerate}
\item up to multiplications by nonzero real numbers, there is a unique minimal set of inequalities determining $\scrP$.
\end{enumerate}
Let $a_{i,0} +  a_{i,1}x_1 + \cdots + a_{i,n}x_n \geq 0$, $i = 1, \ldots, N$, be the minimal set of inequalities defining $\scrP$. Then
\begin{enumerate}[resume]
\item $\scrP \cap \{x : a_{i,0} +  a_{i,1}x_1 + \cdots + a_{i,n}x_n = 0\}$ is a facet of $\scrP$ for each $i$;
\item for every face $\scrQ$ of $\scrP$, there is $I \subseteq \{1, \ldots, N\}$ such that $\scrQ = \scrP \cap \{x: a_{i,0} +  a_{i,1}x_1 + \cdots + a_{i,n}x_n = 0$ for each $i \in I\}$.
\end{enumerate}
\end{cor}

\begin{proof}
Let $a_{i,0} +  a_{i,1}x_1 + \cdots + a_{i,n}x_n \geq 0$, $i = 1, \ldots, N$, be a minimal set of inequalities defining $\scrP$. It suffices to show that $\scrQ_i := \scrP \cap \{x : a_{i,0} +  a_{i,1}x_1 + \cdots + a_{i,n}x_n = 0\}$, $i = 1, \ldots, N$, are the facets of $\scrP$. Indeed, if $\scrQ$ is a facet of $\scrP$, then \cref{prop:relint-inequalities} implies that $\scrQ \subset \bigcup_i \scrQ_i$. \Cref{exercise:face-union} and assertion \eqref{relatively-smaller-dim} of \cref{prop:relative-containment} then imply that $\scrQ = \scrQ_i$ for some $i$. It remains to show that every $\scrQ_i$ is a facet. Indeed, reorder the inequalities so that $\scrQ_i$ are facets for $i = 1, \ldots, M$. Let $\scrP'$ be the polytope determined by  $a_{i,0} +  a_{i,1}x_1 + \cdots + a_{i,n}x_n \geq 0$, $i = 1, \ldots, M$. If $M < N$, then $\scrP \subsetneq \scrP'$ and \cref{prop:relint-inequalities} implies that there is $\alpha \in \relint(\scrP') \setminus \scrP$. Pick $\beta \in \relint(\scrP)$ and let $L$ be the line segment from $\alpha$ to $\beta$. Then \cref{prop:relative-containment,prop:relint-inequalities} imply that
\begin{itemize}
\item for each $i = 1, \ldots, M$, and each $x \in L$, $a_{i,0} +  a_{i,1}x_1 + \cdots + a_{i,n}x_n > 0$.
\item $L$ contains a point $\gamma$ on the {\em topological boundary}\footnote{Topological boundary of $S \subset \rr^n$ is the complement in $S$ of the topological interior of $S$.} of $\scrP$.
\end{itemize}
But then \cref{prop:relative-containment} implies that $\gamma$ is a point of a face of
 $\scrP$ which is not on any facet of $\scrP$, contradicting \cref{prop:facet-containment}.
\end{proof}

The theory of toric varieties (to be discussed in \cref{toric-intro}) exploits many similarities between polytopes and algebraic varieties. Here we note some of the more obvious analogues between a polyhedron $\scrP$ and an irreducible variety $X$.

\begin{align*}
\begin{array}{lcl}
\parbox{0.36\textwidth}{
	The dimension of every proper irreducible subvariety of $X$ is less than $\dim(X)$ (\cref{thm:dim-smaller}).
}
&
\leftrightarrow
&
\parbox{0.3\textwidth}{
	The dimension of every proper face of $\scrP$ is less than $\dim(\scrP)$ (\cref{prop:relative-containment}).
}\\
&
&\\
\parbox{0.36\textwidth}{
	If an irreducible subvariety of $X$ is contained in the union of finitely many subvarieties of $X$, then it is contained in one of them (\cref{exercise:irreducible-union}).
}
&
\leftrightarrow
&
\parbox{0.3\textwidth}{
	If a face of $\scrP$ is contained in the union of finitely many faces of $\scrP$, then it is contained in one of them (\cref{exercise:face-union}).
}
\end{array}
\end{align*}

\subsection{Exercises}
\begin{exercise} \label{exercise:afface-hull}
Let $\scrQ$ be a face of $\scrP$. Show that $\scrQ = \scrP \cap \aff(\scrQ)$. [Hint: if $\scrQ = \In_\nu(\scrP)$, then $\langle \nu, \cdot \rangle$ is constant on $\aff(\scrQ)$.]
\end{exercise}

\begin{exercise} \label{exercise:minconelinear}
Let $\scrP$ be a convex polyhedron and $\nu \in \rnstar$. Assume $\inf\{\langle \nu, \alpha \rangle: \alpha \in \scrP \} > -\infty$, and
\begin{enumerate}
\item \label{minconelinear:cone} either $\scrP$ is a cone, or
\item \label{minconelinear:linear} $\scrP$ is a linear subspace of $\rr^n$.
\end{enumerate}
Then $\In_\nu(\scrP)$ contains the origin and $\min_{\scrP}(\nu) = 0$. In addition, in case \eqref{minconelinear:linear} $\scrP \subset \nu^\perp$, and $\In_\nu(\scrP) = \scrP$. [Hint: in either case $\scrP$ contains the origin, so that $\min_{\scrP}(\nu) \leq 0$. If there is $\alpha \in \scrP$ such that $\langle \nu, \alpha \rangle < 0$, then $\langle \nu, r\alpha \rangle$ approaches $-\infty$ as $r \to \infty$.]
\end{exercise}

\begin{exercise} \label{exercise:face-invariance}
Prove \cref{prop:face-invariance}. [Hint: use assertion \eqref{dual-extension-0} of \cref{exercise:dual-extension}.]
\end{exercise}

\begin{exercise} \label{exercise:top-bdry}
Let $S \subset \rr^n$ and $\nu$ be a nonzero element in $\rnstar$ such that $m := \inf\{\langle \nu, \alpha \rangle : \alpha \in S\} > -\infty$. Show that no point of the hyperplane $\{x \in \rr^n: \langle \nu, \alpha \rangle = m\}$ is in the topological interior of $S$ in $\rr^n$.
\end{exercise}

\begin{exercise}\label{exercise:cone-to-pol}
Let $\scrC$ be a positive dimensional strongly convex polyhedral cone. By \cref{poly-basic-thm} there is $\nu \in \rnstar$ such that $\nu$ is positive on $\scrC \setminus \{0\}$. Let $\scrP :=  \{\alpha \in \scrP: \langle \nu, \alpha \rangle = 1\}$. \Cref{bounded-nu=1} implies that $\scrP$ is a polytope.
\begin{enumerate}
\item If $\scrQ$ is a face of $\scrP$, show that $\cone(\scrQ)$ is a face of $\scrC$ of dimension $\dim(\scrQ) + 1$.
\item Show that the correspondence $\scrQ \mapsto \cone(\scrQ)$ induces a bijection between faces of $\scrP$ and positive dimensional faces of $\scrC$,
\item \label{cone-to-pol:relint} Show that the above correspondence also preserves the relative interiors of the faces, i.e.\ If $\scrQ$ is a face of $\scrP$, then $\relint(\cone(\scrQ)) = \cone(\relint(\scrQ))$.
\end{enumerate}
[Hint: change coordinates on such that $\eta$ is the projection onto the last coordinate.]
\end{exercise}

\begin{exercise} \label{exercise:facection-counter-example}
Let $\scrP$ be a polyhedron, and $\scrQ = \In_\nu(\scrP)$ and $\scrR = \In_\eta(\scrP)$ be faces of $\scrP$. If $\scrQ \cap \scrR = \emptyset$, show by an example that it may not be true that $\In_{\nu + \eta}(\scrP) = \scrQ \cap \scrR$.
\end{exercise}

\begin{exercise} \label{exercise:non-unique-sum-faces}
Find examples of polytopes $\scrP_1, \scrP_2$ in $\rr^n$ and faces  $\scrQ_j$ of $\scrP_j$ such that $\scrQ_1 + \scrQ_2$ is a face of $\scrP_1 + \scrP_2$, and there are $\scrQ'_j \subsetneq \scrQ_j$ such that $\scrQ'_1 + \scrQ'_j = \scrQ_1 + \scrQ_2$. [Hint: there are examples with $n = 1$ with $\scrQ_j = \scrP_j$ for each $j$.]
\end{exercise}

\begin{exercise} \label{exercise:positively-convex}
Let $\alpha = \sum_{j=1}^k \epsilon_j \alpha_j$ be a convex combination of $\alpha_1, \ldots, \alpha_k \in \rr^n$. Assume each $\epsilon_j$ is positive.
\begin{enumerate}
\item If $\nu \in \rnstar$, then show that $\langle \nu, \alpha \rangle \geq \min_j \langle \nu, \alpha_j \rangle$, with equality if and only if $\langle \nu, \alpha_1 \rangle = \cdots = \langle \nu, \alpha_k \rangle$.
\item Conclude that if the $\alpha_j$ are points of a polyhedron $\scrP$, and $\scrQ$ is a face of $\scrP$, then $\scrQ$ contains $\alpha$ if and only if $\scrQ$ contains each $\alpha_j$.
\end{enumerate}
\end{exercise}

\begin{exercise} \label{exercise:relatively-positive-interior}
Let $S$ be a finite subset of $\rr^n$. Let $\scrP := \conv(S)$ and $\scrC$ be the cone generated by $S$. Show that
\begin{enumerate}
\item $\alpha \in \relint(\scrP)$ if and only if $\alpha = \sum_{\beta \in S} \epsilon_\beta \beta$, where $\epsilon_\beta$ are positive real numbers such that $\sum_{\beta \in S} \epsilon_\beta = 1$.
\item $\alpha \in \relint(\scrC)$ if and only if $\alpha = \sum_{\beta \in S} r_\beta \beta$, where $r_\beta$ are positive real numbers.
\end{enumerate}
[Hint: follow the arguments from the proof of assertion \eqref{vertex-hull:relatively-positive} of \cref{prop:vertex-hull}.]
\end{exercise}

\begin{exercise} \label{exercise:face-union}
Let $\scrQ_1, \ldots, \scrQ_k$ be faces of a polyhedron $\scrP$. If $\scrQ$ is a convex subset (e.g.\ a face) of $\scrP$ such that $\scrQ \subseteq \bigcup_j \scrQ_j$, then show that $\scrQ \subseteq \scrQ_j$ for some $j$. [Hint: otherwise for each $j$, there is $\alpha_j \in \scrQ \setminus \scrQ_j$. Apply \cref{exercise:positively-convex} to a positive convex combination of the $\alpha_j$.]
\end{exercise}

\begin{exercise} \label{exercise:edge-graph}
Given distinct vertices $\alpha, \alpha'$ of a polytope $\scrP$, show that there are vertices $\beta_0 = \alpha, \beta_2, \ldots, \beta_k = \alpha'$ of $\scrP$ such that there is an edge of $\scrP$ connecting $\beta_{j-1}$ to $\beta_j$ for each $j = 1, \ldots, k$; in other words, the ``edge-graph'' of $\scrP$ is connected. [Hint: reduce to the case that $\scrP$ is full dimensional. Pick $\nu, \nu' \in \rnstar$ such that $\In_\nu(\scrP) = \{\alpha\}$ and $\In_{\nu'}(\scrP) = \{\alpha'\}$. Consider $\scrP_\epsilon := \In_{\nu + \epsilon \nu'}(\scrP)$ for $\epsilon \geq 0$. As $\epsilon$ goes from $0$ to $\infty$, $\scrP_\epsilon$ transitions from $\{\alpha\}$ to $\{\alpha'\}$ in finitely many steps. Apply induction on dimension to each $\scrP_\epsilon$.]
\end{exercise}

\section{Normal fan of a convex polytope} \label{normal-section}
A {\em fan}\footnote{Our definition of a fan differs from the definition in standard texts on toric varieties (e.g.\cite{fultoric,littlehalcox}) in that we do not require the cones in a fan to be strongly convex.} in $\rr^n$ is a collection $\Sigma$ of convex polyhedral cones in $\rr^n$ such that
\begin{enumerate}
\item \label{cone-face} Each face of a cone in $\Sigma$ is also a cone in $\Sigma$.
\item \label{cone-intersection} The intersection of any two cones in $\Sigma$ is a face of each of them.
\end{enumerate}
Any (finite dimensional) vector space $V$ over real numbers can be identified with $\rr^n$ after choosing a basis $\scrB$, and thus the notions of convex polyhedra, cones, polytopes, fans, etc., can be extended to subsets of $V$. In this section we take $V = \rnstar$ and $\scrB$ to be the basis dual to the standard basis of $\rr^n$. \Cref{exercise:affine-image} implies that convex polyhedra (and therefore cones, polytopes, fans, etc) in $\rnstar$ which are defined in this way remain so after linear changes of coordinates on $\rr^n$. Let $\scrP$ be a convex polytope in $\rr^n$. For each face $\scrQ$ of $\scrP$, define
\begin{align}
\sigma_\scrQ := \{\nu \in \rnstar: \In_\nu(\scrP) \supseteq \scrQ\} \subset \rnstar
\label{sigma-Q}
\end{align}
It is straightforward to see that $\sigma_\scrQ$ is a convex polyhedral cone in $\rnstar$ (\cref{exercise:dual-cone}). Let $\Sigma_\scrP := \{\sigma_\scrQ: \scrQ$ is a face of $\scrP\}$. We will show in \cref{normal-fan} below that $\Sigma_\scrP$ is a fan in $\rnstar$; this is called the {\em normal fan} of $\scrP$. Given a face $\scrQ$ of $\scrP$, let $\sigma^0_\scrQ := \{\nu \in \rnstar: \In_\nu(\scrP) = \scrQ\} \subset \sigma_\scrQ$. We show in \cref{normal-faces} below that $\sigma^0_\scrQ$ is the relative interior of $\sigma_\scrQ$.

\begin{figure}[h]
\begin{center}
\def\xmin{-0.5}
\def\xmax{16.5}
\def\ymin{-5.5}
\def\ymax{5.5}

\tikzstyle{dotbig} = [circle, minimum size=5pt, inner sep = 0pt, fill]

\begin{tikzpicture}[scale=\scalefactor]
\coordinate (A) at (1, -4);
\coordinate (B) at (16, 1);
\coordinate (C) at (10, 5);

\fill[\colorzero, opacity=\opazero ] (A) --  (B) -- (C);
\draw[ultra thick, \colorAB] (A) -- (B);
\draw[ultra thick, \colorBC] (B) -- (C);
\draw[ultra thick, \colorCA] (C) -- (A);

\node[dotbig, \colorA] at (A) {};
\node[dotbig, \colorB] at (B) {};
\node[dotbig, \colorC] at (C) {};
\node[anchor = north] at (A) {\picfontsize $A$};
\node[anchor = west] at (B) {\picfontsize $B$};
\node[anchor = south] at (C) {\picfontsize $C$};

\node at (9.5,0.5) {\picfontsize $\scrP$};

\def\xmin{-8.5}
\def\xshift{5}
\pgfmathsetmacro\shiftone{\xshift + \xmax -\xmin};
\def\xmax{8.5}

\begin{scope}[shift={(\shiftone,0)}]

\coordinate (O) at (0,0);

\coordinate (ABperp) at (-\ymax/3, \ymax);
\coordinate (BCperp) at (\ymin*2/3, \ymin);
\coordinate (CAperp) at (-\ymin, \ymin);

\fill[\colorB, opacity=\opazero ] (O) --  (ABperp) -- (\xmin,\ymax) -- (\xmin,\ymin) -- (BCperp);
\fill[\colorC, opacity=\opazero ] (O) --  (BCperp) -- (CAperp);
\fill[\colorA, opacity=\opazero ] (O) --  (CAperp) -- (\xmax, \ymin) -- (\xmax,\ymax) -- (ABperp);

\draw [ultra thick, \colorAB] (O) -- (ABperp);
\draw [ultra thick, \colorBC] (O) -- (BCperp);
\draw [ultra thick, \colorCA] (O) -- (CAperp);

\node[dotbig, \colorzero] at (O) {};

\node at (-4.5,0.5) {\picfontsize $\sigma^0_B$};
\node at (4.5,1.5) {\picfontsize $\sigma^0_A$};
\node at (.5,-3.5) {\picfontsize $\sigma^0_C$};

\node [anchor= north] at (BCperp) {\picfontsize $\sigma^0_{BC}$};
\node [anchor=north] at (CAperp) {\picfontsize $\sigma^0_{CA}$};
\node [anchor=south] at (ABperp) {\picfontsize $\sigma^0_{AB}$};

\end{scope}
\end{tikzpicture}
\caption{Normal fan of a triangle $\scrP$ in $\rr^2$. $\sigma_\scrP = \sigma^0_\scrP$ is the origin.}  \label{fig:normal-fan}
\end{center}
\end{figure}

\begin{prop} \label{prop:dual-interior}
Let $\scrR_1, \ldots,\scrR_k$ be the faces of $\scrP$ containing $\scrQ$. Then $\sigma^0_\scrQ = \sigma_\scrQ \setminus \bigcup_j \sigma_{\scrR_j}$.
\end{prop}

\begin{proof}
This follows directly from the definition of a face and the definition of $\sigma_\scrQ$.
\end{proof}

Let $L_\scrQ$ be the linear subspace of $\rr^n$ spanned by all vectors of the form $\alpha - \beta$ with $\alpha, \beta \in \scrQ$ and $L_\scrQ^\perp$ be the linear subspace of $\rnstar$ consisting of all $\nu \in \rnstar$ such that $\nu|_{L_\scrQ} \equiv 0$.

\begin{prop} \label{affine-dimension}
$L_\scrQ^\perp = \aff(\sigma_\scrQ) = \aff(\sigma^0_\scrQ)$. In particular, $\dim(\sigma_\scrQ) = n - \dim(\scrQ)$.
\end{prop}

\begin{proof}
Since $\scrQ$ is a face of $\scrP$, there is $\nu' \in \rnstar$ such that $\scrQ= \min_\scrP(\nu')$. It follows that $\nu' \in \sigma^0_\scrQ$; in particular $\sigma^0_\scrQ$ is nonempty.

\begin{proclaim} \label{interior-claim}
Let $\nu \in \sigma^0_\scrQ$. Then for each $\mu \in L_\scrQ^\perp$, $\nu + \epsilon \mu \in \sigma^0_\scrQ$ for all sufficiently small positive $\epsilon$.
\end{proclaim}

\begin{proof}
Indeed, let $m := \min_\scrP(\nu)$ and pick $\epsilon$ such that for all vertices $\alpha$ of $\scrP$ not on $\scrQ$, $\epsilon \langle -\mu, \alpha \rangle < \langle \nu, \alpha \rangle  - m$.
\end{proof}

 \Cref{interior-claim} implies that $\aff(\sigma^0_\scrQ) \supset L_\scrQ^\perp$. On the other hand, if $\nu \in \sigma^0_\scrQ$, then for each $\alpha, \beta \in \scrQ$, $\langle \nu, \alpha - \beta \rangle = 0$, so that $\nu \in L_\scrQ^\perp$. It follows that $\aff(\sigma^0_\scrQ) = L_\scrQ^\perp$. Since $\sigma_\scrQ$ is the union of the $\sigma^0_\scrR$ over all faces $\scrR$ of $\scrP$ containing $\scrQ$, and since $L_\scrR^\perp \subset L_\scrQ^\perp$ whenever $\scrR$ contains $\scrQ$, it follows that $\aff(\sigma_\scrQ) = L_\scrQ^\perp$ as well, as required.
\end{proof}

\begin{cor} \label{normal-faces}
Let $\scrQ$ be a face of $\scrP$.
\begin{enumerate}
\item \label{face-pol-to-normal} If $\scrR$ is a face of $\scrP$ containing $\scrQ$, then $\sigma_\scrR = L_\scrR^\perp \cap \sigma_\scrQ$. In particular, $\sigma_\scrR$ is a face of $\sigma_\scrQ$.
\item \label{normal-interior} $\sigma^0_\scrQ$ is the relative interior of $\sigma_\scrQ$.
\item \label{face-normal-to-pol}  Every face of $\sigma_\scrQ$ is of the form $\sigma_\scrR$ for some face $\scrR$ of $\scrP$ containing $\scrQ$.
\end{enumerate}
\end{cor}

\begin{proof}
In this proof we will identify $\rr^n$ with $(\rnstar)^*$ in the usual way by treating $\alpha \in \rr^n$ as the linear function on $\rnstar$ given by $\nu \mapsto \langle \nu, \alpha \rangle$. \Cref{affine-dimension} implies that $\sigma_\scrR \subset L_\scrR^\perp \cap \sigma_\scrQ$.
Now pick $\nu \in L_\scrR^\perp \cap \sigma_\scrQ$. Since $\nu \in L_\scrR^\perp$, it follows that $\nu$ is constant on $\scrR$. On the other hand, since $\nu \in \sigma_\scrQ$, it follows that $\min_\scrP(\nu)$ is achieved on $\scrQ$. Since $\scrQ \subset \scrR$, it follows that $\min_\scrP(\nu)$ is achieved on all of $\scrR$, and $\nu \in \sigma_\scrR$. Therefore $\sigma_\scrR = L_\scrR^\perp \cap \sigma_\scrQ$. For assertion \eqref{face-pol-to-normal} it remains to show that $\sigma_\scrR$ is a face of $\sigma_\scrQ$.

\begin{proclaim}\label{min-beta-alpha}
Let $\alpha \in \scrQ$ and $\beta \in \scrR$. Then $\beta - \alpha$ induces a nonnegative linear function on $\sigma_\scrQ$. In particular, $\min_{\sigma_\scrQ}(\beta - \alpha) = 0$.
\end{proclaim}

\begin{proof}
If $\langle \nu, \beta - \alpha \rangle < 0$ for some $\nu \in \sigma_\scrQ$, then $\alpha \not\in \In_\nu(\scrP)$, which contradicts the definition of $\sigma_\scrQ$.
\end{proof}

Choose a basis of $L_\scrR$ of the form $\beta_j - \alpha$, $j = 1, \ldots, \dim(L_\scrR)$, where $\alpha \in \scrQ$, and each $\beta_j \in \scrR$. Then \cref{min-beta-alpha} implies that $\sigma_\scrR = L_\scrR^\perp \cap \sigma_\scrQ = \bigcap_j( \sigma_\scrQ \cap (\beta_j - \alpha)^\perp) = \bigcap_j(\In_{\beta_j - \alpha}(\sigma_\scrQ ))$ is an intersection of finitely many faces of $\sigma_\scrQ$, and therefore is also a face of $\sigma_\scrQ$. This completes the proof of assertion \eqref{face-pol-to-normal}, and due to \cref{prop:dual-interior} also implies that $\sigma^0_\scrQ$, being the complement of a union of faces of $\sigma_\scrQ$, contains $\relint(\sigma_\scrQ)$. On the other hand, \cref{interior-claim} implies that for each $\nu \in \sigma_\scrQ$, one can fit inside $\sigma_\scrQ$ a $\dim (\sigma_\scrQ)$-dimensional ball $B_\nu$ centered at $\nu$. \Cref{prop:relint-inequalities} then implies that $\sigma^0_\scrQ \subset \relint(\sigma_\scrQ)$. Consequently, $\sigma^0_\scrQ = \relint(\sigma_\scrQ)$, which proves assertion \eqref{normal-interior}. By assertions \eqref{face-pol-to-normal} and \eqref{normal-interior}, and \cref{prop:finite-faces,exercise:face-union}, every proper face of $\sigma_\scrQ$ is a face of $\sigma_\scrR$ for some face $\scrR$ of $\scrP$ properly containing $\scrQ$. Assertion \eqref{face-normal-to-pol} therefore follows from a straightforward induction on $\dim(\scrP) - \dim(\scrQ)$.
\end{proof}

\begin{cor} \label{normal-fan}
$\Sigma_\scrP$ is a fan in $\rnstar$.
\end{cor}

\begin{proof}
\Cref{normal-faces} shows that $\Sigma_\scrP$ satisfies property \eqref{cone-face} of a fan. Let $\scrQ_1$ and $\scrQ_2$ be faces of $\scrP$, and let $\scrQ$ from \cref{prop:positively-relative} be the smallest face of $\scrP$ containing both $\scrQ_j$. It is clear that $\sigma_\scrQ \subset \sigma_{\scrQ_1} \cap \sigma_{\scrQ_2}$. On the other hand, since $\scrQ$ is contained in every face of $\scrP$ containing both $\scrQ_j$, it follows that for every $\nu \in \sigma_{\scrQ_1}  \cap \sigma_{\scrQ_2}$, $\In_\nu(\scrP) \supset \scrQ$, so that $\nu \in \sigma_\scrQ$. Therefore $\sigma_{\scrQ_1}  \cap \sigma_{\scrQ_2}= \sigma_\scrQ$, which is a face of each $\sigma_{\scrQ_j}$ (\cref{normal-faces}). This shows $\Sigma_\scrP$ satisfies property \eqref{cone-intersection} of a fan as well.
\end{proof}

Recall that in our definition the cones in a fan do not have to be strictly convex. They do however turn out to be so in an important case.

\begin{prop} \label{stritctly-convex-fan}
If $\scrP$ is an $n$-dimensional convex polytope in $\rr^n$, then each cone of $\Sigma_\scrP$ is strictly convex.
\end{prop}

\begin{proof}
Indeed, if $\dim(\scrP) = n$, then for every $\nu \in \rnstar \setminus \{0\}$, $\scrP \setminus \In_\nu(\scrP)$ is nonempty. If $\nu \in  \sigma_\scrQ$ for some face $\scrQ$ of $\scrP$, it then follows from \eqref{sigma-Q} that $\In_{-\nu}(\scrP) \cap \scrQ = \emptyset$, i.e.\ $-\nu \not\in \sigma_\scrQ$, as required.
\end{proof}

\subsection{Exercises}

\begin{exercise} \label{exercise:claim:r}
Prove \cref{face-of-face:claim:r}. [Hint: every $\alpha \in \scrP$ can be expressed as $\sum_{\alpha \in S} \epsilon_\alpha \alpha + \sum_{\beta \in T} r_\beta \beta + \gamma$, where $\gamma \in L$, $r_\beta$ are nonnegative real numbers, and $\epsilon_\alpha$ are nonnegative real numbers such that $\sum_{\alpha \in S} \epsilon_\alpha = 1$. Define $\alpha' := \sum_{\alpha \in S \cap \nu^\perp} \epsilon_\alpha \alpha$, $\alpha'' := \sum_{\alpha \in S \setminus \nu^\perp} \epsilon_\alpha \alpha$, $\beta' := \sum_{\beta \in T \cap \nu^\perp} r_\beta \beta$ and $\beta'' := \sum_{\beta \in T \setminus \nu^\perp} r_\beta \beta$. Examine the value of $r\nu + \eta$ on each of $\alpha', \alpha'', \beta', \beta''$. Show that $\langle r\nu + \eta, \alpha \rangle \geq \min_{\In_\nu(\scrP_0)}(\eta)$, with equality if and only if $\alpha'' = \beta'' = 0$, $\alpha' \in \In_\eta(\In_\nu(\scrP_0))$ and $\beta' \in \In_\eta(\In_\nu(\scrC))$.]
\end{exercise}

\begin{exercise} \label{exercise:deformation-relint}
Let $\scrP$ be an $n$-dimensional polyhedron in $\rr^n$, $\scrQ$ be a facet of $\scrP$, and $\alpha \in \relint(\scrQ)$. Let $\scrQ = \In_\nu(\scrP)$, $\nu \in \rnstar$. If $\beta$ is an arbitrary element of $\rr^n$ such that $\langle \nu, \beta \rangle \geq 0$, then show that $r\alpha + \beta \in r\scrP$ for all $r \gg 1$. [Hint: use \cref{prop:minimal-polynequalities} to show that $\alpha + \epsilon \beta \in \scrP$ if $\epsilon$ is a sufficiently small positive number.]
\end{exercise}

\begin{exercise} \label{exercise:dual-cone}
Let $\scrQ$ be a face of a polytope $\scrP$. Show that $\sigma_\scrQ$ defined in \cref{normal-section} is a convex polyhedral cone in $\rnstar$. [Hint: express $\scrP$ and $\scrQ$ as convex hulls of finite sets. Show that the condition defining $\sigma_\scrQ$ can be expressed in terms of finitely many linear inequalities as in \cref{exercise:cone-inequalities}.]
\end{exercise}

\section{Rational polyhedra} \label{rational-polysection}
We say that a convex polyhedron $\scrP$ is {\em rational} if it can be defined in $\rr^n$ by a finitely many inequalities of the form $a_0 +  a_1x_1 + \cdots + a_nx_n \geq 0$ where each $a_i$ is a rational number (or equivalently, an integer). In particular, a {\em rational affine hyperplane} is the set of zeroes in $\rr^n$ of an equation $a_0  + a_1x_1 + \cdots + a_nx_n = 0$, where each $a_i \in \qq$, and $(a_1, \ldots, a_n) \neq (0, \ldots, 0)$. \Cref{poly-rational-thm} below gives a characterization of rational polyhedra. In particular, it implies that a polytope is rational if and only if its vertices have rational coordinates, and a polyhedral cone is rational if and only if each of its edges have a nonzero element with rational coordinates. We say that a polytope in $\rr^n$ is {\em integral} if all its vertices are in $\zz^n$.

\begin{prop} \label{poly-rational-thm}
Let $\scrP \subset \rr^n$.
\begin{enumerate}
\item \label{characterize-ratiotope} $\scrP$ is a rational polytope if and only if it is the convex hull of finitely many points with rational coordinates.
\item \label{characterize-ratione} $\scrP$ is a rational polyhedral cone if and only if it is the cone generated by finitely many points with rational coordinates.
\item \label{characterize-ratiohedron} $\scrP$ is a rational polyhedron if and only if it is the Minkowski sum of a rational convex polyhedral cone and a rational convex polytope.
\end{enumerate}
\end{prop}

\begin{proof}
At first assume $\scrP = \conv(S) + \cone(T)$ for $S, T \subset \qq^n$. We claim that $\scrP$ is a rational polyhedron. Due to \cref{exercise:rational-reduction} the claim reduces to the case that $\dim(\aff(\scrP)) = n$. By the results from \cref{poly-basic-section}, $\scrP$ is an $n$-dimensional polyhedron in $\rr^n$, and if $\scrQ$ is a facet of $\scrP$, then $\scrQ = \conv(S') + \cone(T')$ for $S' \subset S$ and $T' \subset T$. It is then straightforward to see that $\aff(\scrQ)$ is a rational affine hyperplane. Since an $n$-dimensional polyhedron in $\rr^n$ is determined by the hyperplanes containing its facets (\cref{prop:minimal-polynequalities}), it follows that $\scrP$ is a rational polyhedron, as required, and proves the $(\Leftarrow)$ implications of all three assertions of \cref{poly-rational-thm}. We now prove the $(\im)$ implications of all three assertions simultaneously by induction on $\dim(\scrP)$. Due to \cref{exercise:rational-reduction} we may assume \woutlog\ that $\dim(\scrP) = n$. The cases of $\dim(\scrP) = 0$ and $\dim(\scrP) = 1$ are then obvious. Now assume $\dim(\scrP) \geq 2$. Since the vertices and edges of $\scrP$ are also rational polyhedra (\cref{prop:minimal-polynequalities}), the inductive hypothesis and \cref{prop:vertex-hull,prop:edge-hull} imply that if $\scrP$ is a polytope, then $\scrP = \conv(S)$ for a finite $S \subset \qq^n$, and if $\scrP$ is a strongly convex polyhedral cone, then $\scrP = \cone(T)$ for a finite $T \subset \qq^n$. In general, \cref{polyhedron-minkomposition} implies that $\scrP = \scrP_0 + \scrC$, where $\scrP_0$ is a rational convex polytope and $\scrC$ is a rational convex polyhedron. Due to what we already proved, it suffices to show that $\scrC = \cone(T)$ with finite $T \subset \qq^n$, even if $\scrC$ is {\em not} strongly convex. Indeed, if $\scrC$ is not strongly convex, then \cref{strongly-convex-prop,polyhedron-minkomposition} imply that $\scrC = \scrC' + L$ where $\scrC'$ is a cone and $L$ is a {\em positive} dimensional rational linear subspace of $\rr^n$. Let $k := \dim(L)$. Then we can choose a surjective linear map $\pi: \rr^n \to \rr^{n-k}$ such that $\ker(\pi) = L$, and $\pi$ maps $\qq^n$ onto $\qq^{n-k}$. \Cref{exercise:cone-rational-projection} implies that $\pi(\scrC)$ is a rational polyhedral cone, and therefore, by the inductive hypothesis $\pi(\scrC) = \cone(T')$ for some finite $T' \subseteq \qq^{n-k}$. Another application of \cref{exercise:cone-rational-projection} then implies that $\scrC = \cone(T)$ for a finite $T \subseteq \qq^n$, as required.
\end{proof}

\begin{cor}
If $\scrP$ is a convex rational polytope, then each cone in the normal fan of $\scrP$ is also rational (with respect to the basis on $\rnstar$ which is dual to the standard basis of $\rr^n$).
\end{cor}

\begin{proof}
Let $\scrQ$ be a face of $\scrP$. We will show that the cone $\sigma_\scrQ$ from \cref{normal-section} is rational. \Cref{prop:minimal-polynequalities} implies that $\scrQ$ is also a convex rational polytope. Therefore by \cref{poly-rational-thm} there are finite subsets $S, T$ of $\qq^n$ such that each $\scrP$ is $\scrP = \conv(S)$ and $\scrQ = \conv(T)$. Since $\sigma_\scrQ = \{\nu \in \rnstar: \langle \nu, \beta - \beta' \rangle = 0$ for all $\beta, \beta' \in T$, and $\langle \nu, \alpha - \beta \rangle \geq 0$ for all $\alpha \in S$, $\beta \in T\}$, it follows that $\sigma_\scrQ$ is a rational polyhedral cone, as required.
\end{proof}

Recall that the {\em Hausdorff distance} of $\scrP, \scrQ \subset \rr^n$ is $\sup_{\alpha \in \scrP}\{\inf_{\beta \in \scrQ} \norm{\alpha - \beta}\}$, where $\norm{\cdot}$ is the Euclidean norm on $\rr^n$.

\begin{cor} \label{poly-rational-appxn}
Every polytope can be approximated arbitrarily closely (with respect to the Hausdorff distance) by rational polytopes.
\end{cor}

\begin{proof}
This follows from \cref{poly-basic-thm,poly-rational-thm}, since to approximate the convex hull of $\alpha_1, \ldots, \alpha_N \in \rr^n$, it suffices to take the convex hull of $\beta_1, \ldots, \beta_N$, where each $\beta_j$ has rational coordinates, and is sufficiently close to $\alpha_j$.
\end{proof}

Many results from the theory of rational polyhedra (including \cref{poly-rational-thm}) are ultimately based on the following basic fact from linear algebra.

\begin{lemma} \label{rational-solutions}
Consider a linear system of equations of the form $a_{i,0} + a_{i,1}x_1 + \cdots + a_{i,n}x_n  = 0$, $i = 1, \ldots, k$. Assume each $a_{i,j}\in \qq$. Let $H_\qq$ and $H_\rr$ be the set of common solutions of this system respectively in $\qq^n$ and $\rr^n$. Then $\dim_\qq(H_\qq) = \dim_\rr(H_\rr)$. In particular, the system has a common solution over $\rr$ if and only if it has a common solution over $\qq$.
\end{lemma}

\begin{proof}
If the system has a solution, then it can be found by Gaussian elimination, which produces a solution in $\qq$ (since each $a_{i,j} \in \qq$). Moreover, in that case the dimension of the space of solutions is precisely the rank of the $k \times n$ matrix $(a_{i,j})$, $1 \leq i \leq k$, $1 \leq j \leq n$. Since the rank over $\qq$ is the same as the rank over $\rr$, this completes the proof.
\end{proof}

\begin{cor}[Cf.\ \cref{prop:vertex-hull}] \label{positive-linear-comb-lemma}
Let $\scrP$ be a convex rational polyhedron and $\alpha$ be a point with rational coordinates in the relative interior of $\scrP$.
\begin{enumerate}
\item  \label{positive-linear-comb:pol} If $\scrP$ is a polytope with vertices $\alpha_1, \ldots, \alpha_k$, then there are positive rational numbers $q_1, \ldots, q_k$ such that $\sum_j q_j = 1$ and $\alpha = \sum_j  q_j\alpha_j$.
\item \label{positive-linear-comb:cone} If $\scrP$ is a cone generated by $\alpha_1, \ldots, \alpha_k \in \zz^n$, then there are positive rational numbers $q_1, \ldots, q_k$ such that $\alpha = \sum_j  q_j\alpha_j$.
\end{enumerate}
\end{cor}

\begin{proof}
Let $\phi: \rr^k \to \rr^n$ be the map which sends $(r_1, \ldots, r_k) \mapsto \sum_{j=1}^k r_j\alpha_j - \alpha$. If $\scrP$ is a cone, then \cref{prop:edge-hull}  implies that $\phi^{-1}(0) \cap \rpluss{k} \neq \emptyset$. \Cref{rational-solutions} then implies that $\phi^{-1}(0) \cap \qpluss{k} \neq \emptyset$, which together with \cref{prop:edge-hull} proves assertion \eqref{positive-linear-comb:cone}. Assertion  \eqref{positive-linear-comb:pol} follows  by the same arguments from \cref{prop:vertex-hull,rational-solutions} by considering the map $\phi': \rr^k \to \rr^{n+1}$ given by $(r_1, \ldots, r_k) \mapsto (\phi(r_1, \ldots, r_k), r_1 + \cdots + r_k - 1)$.
\end{proof}

The following result is one of the foundations of the theory of toric varieties we will encounter in \cref{toric-intro}.

\begin{lemma}[Gordan's lemma] \label{gordan}
If $\sigma$ is a rational convex polyhedral cone in $\rr^n$, then $\sigma \cap \zz^n$ is a finitely generated semigroup.
\end{lemma}

\begin{proof}
It is straightforward to check that $\sigma \cap \zz^n$ is a semigroup. Pick $\alpha_1, \ldots, \alpha_s \in S_\sigma$ which generate $\sigma$ as a cone. Let $K := \{\sum_{i=1}^s t_i\alpha_i: t_i \in \rr, 0 \leq t_i \leq 1\} \subset \rr^n$. Since $K$ is compact, $K \cap \zz^n$ is a finite set. Now pick $\alpha \in \sigma \cap \zz^n$. Then $\alpha = \sum_{i=1}^s r_i \alpha_i$, where each $r_i \geq 0$. Write $\alpha = \sum_{i=1}^s \lfloor r_i \rfloor \alpha_i + \beta$, where $\lfloor r_i \rfloor$ is the greatest integer less than or equal to $r_i$ for each $i$, and $\beta := \sum_i (r_i - \lfloor r_i \rfloor) \alpha_i \in K \cap \zz^n$. It follows that $\sigma \cap \zz^n$ is generated as a semigroup by all the $\alpha_j$ together with $K \cap \zz^m$.
\end{proof}

\subsection{Exercises}
\begin{exercise} \label{exercise:rational-reduction}
Assume either $\scrP$ is a rational polyhedron or $\scrP = \conv(S) + \cone(T)$, where $S, T \subset \qq^n$. If $\dim(\aff(\scrP)) < n$, then show that there is a rational affine hyperplane in $\rr^n$ containing $\scrP$. [Hint: if $\scrP$ is a polyhedron in $\rr^n$ with $\dim(\scrP) < n$, then the set of points for which each of the inequalities defining $\scrP$ is strict must be empty, for otherwise $\dim(\scrP)$ would be $n$. In the other case, $\scrP = \conv(S) + \cone(T)$, with $S, T \subset \qq^n$. Let $L_\scrP$ be the linear subspace of $\rr^n$ generated by all elements of the form $\alpha - \beta$, where $\alpha - \beta \in \scrP$. It is possible to choose a generator of $L_\scrP$ consisting of elements of the form $\alpha_1 - \alpha_2 + \beta_1 - \beta_2$, where $\alpha_1, \alpha_2 \in S$ and $\beta_1, \beta_2$ are scalar multiples of elements from $T$. Since each such element is in $\qq^n$, it follows that $L_\scrP$ is contained in a rational hyperplane. $\scrP$ is contained in a translation of $L_\scrP$ by an element of $\qq^n$.]
\end{exercise}

\begin{exercise} \label{exercise:cone-rational-projection}
Let $\pi:\rr^n \to \rr^m$ be a linear map such that $\pi$ maps $\qq^n$ into $\qq^m$. Given $\scrC \subseteq \rr^m$, show that
\begin{enumerate}
\item $\scrC = \cone(T)$ for some (finite) $T \subset \qq^m$ if and only if $\pi^{-1}(\scrC) = \cone(T')$ for some (finite) $T' \subset \qq^n$.
\item $\scrC$ is a rational polyhedral cone in $\rr^m$ if and only if $\pi^{-1}(\scrC)$ is a rational polyhedral cone in $\rr^n$. [Hint: use \cref{exercise:cone-inequalities}.]
\end{enumerate}
\end{exercise}

\section{$^*$Volume of convex polytopes}
\label{rational-vol-section}
\footnote{The asterisk in the section name is to indicate that the material of this section is not going to be used in \cref{toric-intro}. It is only used in the proof of Bernstein's theorem in \cref{bkk-chapter}.}Given linearly independent elements $\alpha_1, \ldots, \alpha_d \in \rr^n$, the {\em parallelotope generated by the $\alpha_j$} is the set
\begin{align*}
\scrP := \{\lambda_1 \alpha_1 + \cdots + \lambda_d \alpha_d: 0 \leq \lambda_j \leq 1,\ 1 \leq j \leq d\}
\end{align*}
It is straightforward to check that $\scrP$ is a $d$-dimensional polytope in $\rr^n$ (\cref{exercise:parallelotope}). We denote by $\vol_n$ the usual $n$-dimensional volume (i.e.\ the Lebesgue measure) on $\rr^n$. Given an affine subspace $H$ of $\rr^n$, we write $\vol_H$ for the measure induced on $H$ by $\vol_n$. Here is a precise definition of $\vol_H$: let $H_0$ be the (unique) linear subspace of $\rr^n$ which is a translate of $H$ (i.e.\ $H_0 = H - \alpha$ for any $\alpha \in H$), $d := \dim(H)$, and $\beta_1, \ldots, \beta_{n-d}$ be an orthonormal set (with respect to the dot product) of elements in $\rr^n$ such that $H_0$ is precisely the set of elements in $\rr^n$ whose dot product with each $\beta_j$ is zero. Let $\scrQ$ be the parallelotope generated by $\beta_1, \ldots, \beta_d$. If $\scrR$ is any subset of $H$, then $\scrR$ is measurable with respect to $\vol_H$ if and only if $\scrQ +\scrR$ is measurable with respect to $\vol_n$, and $\vol_H(\scrR) = \vol_n(\scrQ + \scrR)$.

\begin{center}
\begin{figure}[h]

\def\scalefactor{.6}
\def\xmin{-2.5}
\def\xmax{7.5}
\def\ax{6}
\def\ay{-1}
\def\nux{-\ay}
\def\nuy{\ax}
\pgfmathsetmacro\nulength{sqrt(\nux*\nux + \nuy*\nuy)}
\def\nubasex{-1.5}

\begin{tikzpicture}[scale=\scalefactor]

\coordinate (leftL) at (\xmin, {\xmin*\ay/\ax});
\coordinate (rightL) at (\xmax, {\xmax*\ay/\ax});

\draw [\colortwo] (leftL) -- (rightL);

\coordinate (O) at (0,0);
\coordinate (A) at (\ax,\ay);
\coordinate (nu) at ({\nux/\nulength}, {\nuy/\nulength});
\coordinate (B) at ($(A) + (nu)$);

\fill [\colorzero, opacity=\opazero ] (O) --  (A) -- (B) -- (nu) -- cycle;
\draw[thick, \colorone] (O) -- (A);

\coordinate (nubase) at (\nubasex, {\nubasex*\ay/\ax});
\coordinate (nutip) at ($(nubase) + (nu)$);
\draw [thick, \colornu, ->] (nubase) -- (nutip);

\coordinate (nu2) at ({\ax/\nulength}, {\ay/\nulength});
\coordinate (nu2tip) at ($(nubase) + (nu2)$);
\draw [thick, \colornu, ->] (nubase) -- (nu2tip);

\coordinate (beta1) at ($(nubase)!0.5!(nutip)$);
\coordinate (beta2) at ($(nubase)!0.5!(nu2tip)$);
\node [anchor = east] at (beta1) {\picfontsize $\beta_1$};
\node [anchor = north] at (beta2) {\picfontsize $\beta_2$};

\coordinate (Q) at ($(O)!0.5!(A)$);
\node [anchor = north] at (Q) {\picfontsize $\scrQ$};

\node [anchor = west] at (rightL) {\picfontsize $H$};

\end{tikzpicture}

\caption{
If $\scrQ$ is a segment of a line $H \subset \rr^2$, then $\vol_H(\scrQ)$ is the length of $\scrQ$, and equals the area of the rectangle with base $\scrQ$ and height one.
} \label{fig:length=area}

\end{figure}
\end{center}
If $\scrP \subset \rr^n$ is such that the $\dim(\aff(\scrP)) \leq d$, then we write $\vol_d(\scrP)$ for $\vol_H(\scrP)$, where  $H$ is any $d$-dimensional affine subspace of $\rr^n$ containing $\scrP$; this is well defined since $\vol_H(\scrP)$ does {\em not} depend on $H$ (\cref{exercise:vol-d}). The following properties of $\vol$ follow from basic analysis; we use these without proof.

\begin{thm} \label{vol-basics}
Let $\scrP$ be a polytope in $\rr^n$.
\begin{enumerate}
\item If $\dim(\scrP) \leq d \leq n$, then the map $\lambda \in \rr_{\geq 0} \mapsto \vol_d(\lambda \scrP)$ is {\em homogeneous of order $d$}, i.e.\ $\vol_d(\lambda\scrP) = \lambda^d \vol_d(\scrP)$ for all $\lambda \geq 0$.
\item As a real valued function from the set of the polytopes in $\rr^n$, $\vol_n$ is continuous with respect to the Hausdorff distance.
\end{enumerate}
\end{thm}

Let $\scrP$ be an $n$-dimensional polytope, and $O$ be an arbitrary point of $\rr^n$. For each facet $\scrQ$ of $\scrP$, let $\scrS_{\scrQ,O}$ be the convex hull of $\scrQ \cup \{O\}$, i.e.\ $\scrS_{\scrQ,O}$ is the ``cone with base $\scrQ$ and apex $O$.'' Then it is intuitively clear that the volume of $\scrP$ can be computed in terms of the volumes of the $\scrS_{\scrQ,O}$, see \cref{fig:volume-facet}. This leads to our next result. To state it we introduce a notation: if $\scrQ$ is a facet of an $n$-dimensional polytope $\scrP \subset \rr^n$, then (up to a positive multiple) there is a unique $\nu \in \rnstar \setminus \{0\}$ such that $\scrQ = \In_\nu(\scrP)$. Define
\begin{align*}
\sign_\scrQ(\scrP, O)
	&=
	\begin{cases}
		1 & \text{if}\ \langle \nu, O \rangle > \min_\scrP(\nu),\\
		-1 & \text{otherwise.}
	\end{cases}
\end{align*}
Geometrically, $\sign_\scrQ(\scrP, O)$ is $1$ if and only if $O$ and $\scrP$ are on the same side of $\aff(\scrQ)$ - see \cref{fig:volume-facet}.

\begin{center}
\begin{figure}[h]
\def\xmin{-0.5}
\def\xmax{16.5}
\def\ymin{-5.5}
\def\ymax{5.5}

\tikzstyle{dot} = [\colordot, circle, minimum size=4pt, inner sep = 0pt, fill]
\begin{subfigure}[b]{0.36\textwidth}
\begin{tikzpicture}[scale=\scalefactor]
\coordinate (A) at (1, -4);
\coordinate (B) at (16, 1);
\coordinate (C) at (10, 5);
\coordinate (O) at (9.5, 0.5);
\coordinate (nu) at (-1,1);
\pgfmathsetmacro\nuscale{1}
\coordinate (acperpbase) at ($(A)!(O)!(C)$);
\coordinate (nutop) at ($(O) + \nuscale*(nu)$);

\draw[thick, \colorAB] (A) -- (B);
\draw[thick, \colorBC] (B) -- (C);
\draw[thick, \colorCA] (C) -- (A);
\fill[\colorAB, opacity=\opazero ] (O) --  (A) -- (B) -- cycle;
\fill[\colorBC, opacity=\opazero ] (O) --  (B) -- (C) -- cycle;
\fill[\colorCA, opacity=\opazero ] (O) --  (C) -- (A) -- cycle;

\draw[dashed, thick, \colorA] (O) -- (acperpbase);
\draw[thick, \colornu, ->] (O) -- (nutop);

\node[dot] at (O) {};
\node[dot] at (acperpbase) {};
\node[anchor = north] at (A) {\picfontsize $A$};
\node[anchor = west] at (B) {\picfontsize $B$};
\node[anchor = south] at (C) {\picfontsize $C$};
\node[anchor = north] at (O) {\picfontsize $O$};
\node[anchor = west] at (nutop) {\picfontsize $\nu_{CA}$};
\node[anchor = east] at (acperpbase) {\picfontsize $\alpha_{CA}$};
\end{tikzpicture}
\caption{$\vol_2(ABC) = \vol_2(OAB) + \vol_2(OBC) + \vol_2(OCA)$}
\end{subfigure}\hspace{0.18\textwidth}
\begin{subfigure}[b]{0.39\textwidth}
\begin{tikzpicture}[scale=\scalefactor]
\coordinate (A) at (1, -4);
\coordinate (B) at (16, 1);
\coordinate (C) at (10, 5);
\coordinate (O) at (3, 4);

\coordinate (nu) at (-1,1);
\pgfmathsetmacro\nuscale{1}
\coordinate (acperpbase) at ($(A)!(O)!(C)$);
\coordinate (nutop) at ($(O) + \nuscale*(nu)$);

\draw[thick, \colorAB] (A) -- (B);
\draw[thick, \colorBC] (B) -- (C);
\draw[thick, \colorCA] (C) -- (A);
\fill[\colorAB, opacity=\opazero ] (O) --  (A) -- (B) -- cycle;
\fill[\colorBC, opacity=\opazero ] (O) --  (B) -- (C) -- cycle;
\fill[\colorCA, opacity=\opazero ] (O) --  (C) -- (A) -- cycle;

\draw[dashed, thick, \colorA] (O) -- (acperpbase);
\draw[thick, \colornu, ->] (O) -- (nutop);

\node[dot] at (O) {};
\node[dot] at (acperpbase) {};
\node[anchor = north] at (A) {\picfontsize $A$};
\node[anchor = west] at (B) {\picfontsize $B$};
\node[anchor = south] at (C) {\picfontsize $C$};
\node[anchor = east] at (O) {\picfontsize $O$};
\node[anchor = east] at (nutop) {\picfontsize $\nu_{CA}$};
\node[anchor = west] at (acperpbase) {\picfontsize $\alpha_{CA}$};
\end{tikzpicture}
\caption{$\vol_2(ABC) = \vol_2(OAB) + \vol_2(OBC) - \vol_2(OCA)$}
\label{fig:volume-facet-2}
\end{subfigure}
\caption{If $\scrP$ is a triangle in $\rr^2$ and $O \in \rr^2$, then for each side $\scrQ$ of $\scrP$, $\scrS_{\scrQ,O}$ is the triangle formed by $\scrQ$ and $O$. In \cref{fig:volume-facet-2} $\sign_{CA}(ABC, O) = -1$ since $O$ and $ABC$ are on different sides of the line containing $CA$.}  \label{fig:volume-facet}
\end{figure}
\end{center}

\begin{thm} \label{volume-facet}
Let $\scrP$ be an $n$-dimensional polytope in $\rr^n$ and $O \in \rr^n$. For each facet $\scrQ$ of $\scrP$, let $d(O,\aff(\scrQ))$ denote the distance between $O$ and the affine hull of $\scrQ$. Then
\begin{align}
\vol_n(\scrP) = \frac{1}{n}\sum_\scrQ \sign_\scrQ(\scrP, O) d(O, \aff(\scrQ)) \vol_{n-1}(\scrQ)
\label{volume-facet-formula}
\end{align}
where the sum is over all facets $\scrQ$ of $\scrP$. In particular,
\begin{align}
\vol_n(\scrP)
	= \frac{1}{n}\sum_{\substack{\nu \in \rnstar\\ \norm{\nu} = 1}}
	 			\max_\scrP(\nu) \vol_{n-1}(\ld_\nu(\scrP))
	= -\frac{1}{n}\sum_{\substack{\nu \in \rnstar\\ \norm{\nu} = 1}}
 			\min_\scrP(\nu) \vol_{n-1}(\In_\nu(\scrP))
 	\label{volume-facet-unit-formula}
\end{align}

\end{thm}

\begin{rem}
The norm $\norm{\cdot}$ on $\rnstar$ in \eqref{volume-facet-unit-formula} is the Euclidean norm induced from $\rr^n$ upon identification of $\rnstar$ and $\rr^n$ via the basis dual to the standard basis of $\rr^n$.
\end{rem}

\begin{proof}
Let $\scrI_+$ (respectively, $\scrI_-$) be the collection of facets $\scrQ$ of $\scrP$ such that $\sign_\scrQ(\scrP,O) = 1$ (respectively, $-1$). The results of \cref{poly-basic-section} imply that
\begin{prooflist}
\item \label{volume-facet:P-in-cones} $\scrP \subset \bigcup_{\scrQ \in \scrI_+} \scrS_\scrQ(\scrP,O)$ (\cref{exercise:volume-facet:P-in-cones});
\item \label{volume-facet:minus-interior} if $\scrQ \in \scrI_-$ then $\scrS_{\scrQ,O} \cap \relint (\scrP) = \emptyset$ and $\scrS_{\scrQ,O} \subset \bigcup_{\scrQ' \in \scrI_+} \scrS_{\scrQ'}(\scrP,O)$ (\cref{exercise:volume-facet:minus-interior});
\item \label{volume-facet:plus-exterior} if $\scrQ \in \scrI_+$ then $\scrS_{\scrQ,O} \setminus \scrP \subset \bigcup_{\scrQ' \in \scrI_-} \scrS_{\scrQ'}(\scrP,O)$ (\cref{exercise:volume-facet:plus-exterior});
\item \label{volume-facet:intersect-cones} if $\scrQ$ and $\scrQ'$ are distinct facets of $\scrP$ such that $\sign_\scrQ(\scrP, O) =  \sign_{\scrQ'}(\scrP, O)$, then $\dim(\scrS_{\scrQ,O} \cap \scrS_{\scrQ',O}) \leq n-1$ (\cref{exercise:volume-facet:intersect-cones}).
\end{prooflist}
These observations immediately imply that
\begin{align*}
\vol_n(\scrP)
	&= \sum_\scrQ  \sign_\scrQ(\scrP, O) \vol_n(\scrS_{\scrQ,O})
\end{align*}
Since every cross section of $\scrS_{\scrQ,O}$ parallel to the hyperplane $\aff(\scrQ)$ is a dilation of $\scrQ$, it follows that
\begin{align*}
\vol_n(\scrS_{\scrQ,O})
	&= \int_{r=0}^{d(O,\aff(\scrQ))} \vol_{n-1}(r\scrQ)dr
	=  \int_{r=0}^{d(O,\aff(\scrQ))}  r^{n-1} dr
	=\frac{1}{n} {d(O,\aff(\scrQ))} \vol_{n-1}(\scrQ),
\end{align*}
where the second equality follows from \cref{vol-basics}. This completes the proof of identity \eqref{volume-facet-formula}. Now for each facet $\scrQ$ of $\scrP$, let $\nu_\scrQ \in \rnstar$ be the {\em outward facing} unit normal to $\scrQ$, i.e.\ $\scrQ = \ld_\nu(\scrP)$ and $\norm{\nu} = 1$. We now apply identity \eqref{volume-facet-formula} with $O$ being the origin of $\rr^n$. If we identify $\rnstar$ with $\rr^n$ via the basis dual to the standard basis of $\rr^n$, then $\alpha_\scrQ := \sign_\scrQ(\scrP, O) d(O, \aff(\scrQ)) \nu_\scrQ $ is a point on $\aff(\scrQ)$ (see e.g.\ \cref{fig:volume-facet}). It follows that $\min_\scrP(\nu_\scrQ)
	= \langle \nu_\scrQ, \alpha_\scrQ  \rangle
	= (-1)^{\epsilon_{O, \scrQ}} d_{O, \scrQ}$. The first equality of identity \eqref{volume-facet-unit-formula} now follows from identity \eqref{volume-facet-formula}. The second equality follows from the first by replacing $\nu$ by $-\nu$.
\end{proof}

\subsection{Exercises}
\begin{exercise} \label{exercise:parallelotope}
Let $\scrP := \{\lambda_1 \alpha_1 + \cdots + \lambda_d \alpha_d: 0 \leq \lambda_j \leq 1$ for each $j = 1, \ldots, d\}$, where $\alpha_1,  \ldots, \alpha_d \in \rr^n$. Show that
\begin{enumerate}
\item $\scrP$ is the convex hull of the set consisting of the origin and all elements of the form $\alpha_{i_1} + \cdots + \alpha_{i_k}$, where $1 \leq i_1 < \cdots < i_k \leq d$.
\item $\aff(\scrP)$ is the linear subspace of $\rr^n$ spanned by $\alpha_1, \ldots, \alpha_d$.
\end{enumerate}
\end{exercise}

\begin{exercise}\label{exercise:vol-d}
Let $\scrP \subset \rr^n$ and $k := \dim(\scrP)$. Fix $d$, $k \leq d \leq n$. If $H_1, H_2$ are $d$-dimensional affine subspaces of $\rr^n$ containing $\scrP$, show that
\begin{enumerate}
\item $\scrP$ is measurable with respect to $\vol_{H_1}$ if and only if it is measurable with respect to $\vol_{H_2}$.
\item If $\scrP$ is measurable with respect to either of them, then $\vol_{H_1}(\scrP) = \vol_{H_2}(\scrP)$.
\end{enumerate}
\end{exercise}

\begin{exercise} \label{exercise:volume-facet:P-in-cones}
Prove observation \ref{volume-facet:P-in-cones} from the proof of \cref{volume-facet}. [Hint: it suffices to prove that $\relint(\scrP) \subset \bigcup_{\scrQ \in \scrI_+} \scrS_\scrQ(\scrP,O)$. If $\alpha \in \relint(\scrP)\setminus \{O\}$, the line through $\alpha$ and $O$ intersects the facets at two points. One of these is contained in facets from $\scrI_+$.]
\end{exercise}

\begin{exercise} \label{exercise:volume-facet:minus-interior}
Prove observation \ref{volume-facet:minus-interior} from the proof of \cref{volume-facet}. [Hint: if $\scrI_- \neq \emptyset$, then either $O \not\in \scrP$ or $O$ is on a facet of $\scrP$. Pick $\alpha \in \scrQ$, where $\scrQ \in \scrI_-$. If $\scrQ = \In_\nu(\scrP)$, for the first part show that $\langle \nu, \beta \rangle \leq \min_\scrP(\nu)$ for each $\beta$ on the line segment from $O$ to $\alpha$. For the second part it suffices to show $\relint(\scrS_{\scrQ,O}) \subset \bigcup_{\scrQ' \in \scrI_+}$. Every point of $\relint(\scrS_{\scrQ,O})$ is on the line segment between $O$ and a point on $\relint(\scrQ)$. Extending this line segment hits another point of the topological boundary of $\scrP$ which belongs to a facet from $\scrI_+$.]
\end{exercise}

\begin{exercise} \label{exercise:volume-facet:plus-exterior}
Prove observation \ref{volume-facet:plus-exterior} from the proof of \cref{volume-facet}. [Hint: it suffices to consider the case that $O \not\in \scrP$. If $\alpha \in \relint(\scrQ)$ and $\scrQ \in \scrI_+$, then the line segment $L$ from $O$ to $\alpha$ intersects the boundary of $\scrP$ at a point $\beta$ ``in between'' $O$ and $\alpha$. Any facet $\scrR$ of $\scrP$ containing $\beta$ is in $\scrI_-$ and $L\setminus \scrP \subset \scrS_\scrR(\scrP,O)$.]
\end{exercise}

\begin{exercise} \label{exercise:volume-facet:intersect-cones}
Prove observation \ref{volume-facet:intersect-cones} from the proof of \cref{volume-facet}. [Hint: pick distinct facets $\scrQ_1, \scrQ_2$ of $\scrP$ such that $\scrS_{\scrQ_j,O}$ are full dimensional and $\relint(\scrS_{\scrQ_1,O}) \cap \relint(\scrS_{\scrQ_2,O}) \neq \emptyset$. It suffices to show that $\sign_{\scrQ_j}(\scrP, O)$ have different signs for $j=1$ and $j = 2$. Indeed, if $\alpha$ is a point in the intersection, then the line through $O$ and $\alpha$ intersects $\scrP$ at $\beta_j \in \relint(\scrQ_j)$, $j = 1, 2$. Show that one of the $\beta_j$ is ``in between'' $O$ and the other $\beta_j$.]
\end{exercise}

\begin{exercise} \label{exercise:omegadm}

Given positive $\omega_1, \ldots, \omega_n$ and nonnegative $d, m_1, \ldots, m_p$, where $0 \leq p \leq n$, let $\scrQ(\vec \omega, d, \vec m)$ be the polytope in $\rr^n$ determined by the following inequalities:
\begin{align*}
&x_i \geq 0\ \text{for each}\ i = 1, \ldots, n,\\
&\sum_{i=1}^n \omega_i x_i \leq d,\\
&x_i \leq m_i,\ i = 1, \ldots, p.
\end{align*}
Let $\scrI(\vec \omega, d, \vec m)$ be the collection of subsets $I$ of $\{1, \ldots, p\}$ such that $\sum_{i \in I} \omega_im_i \leq d$.
\begin{enumerate}
\item Show that the vertices of $\scrQ(\vec \omega, d, \vec m)$ are precisely the elements $\alpha_{I} = (\alpha_{I,1}, \ldots, \alpha_{I,n})$ and $\beta_{I,j} = (\beta_{I,j,1}, \ldots, \beta_{I,j,k}) \in \rr^n$, indexed by $I \in \scrI(\vec \omega, d, \vec m)$ and $j \in \{1, \ldots, n\} \setminus I$, and defined as follows:
\begin{align*}
\alpha_{I,k}
	&:=	\begin{cases}
			m_k & \text{if}\ k \in I,\\
			0	& \text{if}\ k \not\in I,
		\end{cases}\\
\beta_{I,j,k}
	&:=	\begin{cases}
			m_k
				& \text{if}\ k \in I,\\
			\frac{d - \sum_{i \in I}\omega_im_i}{\omega_j}
				& \text{if}\ k = j,\\
			0	& \text{if}\ k \not\in I \cup \{j\}.
		\end{cases}
\end{align*}
\item \label{sumQ} Let $d_i, m_{i,1}, \ldots, m_{i,p}$, $i = 1, 2$, be nonnegative real numbers such that $\scrI(\vec \omega, d_1, \vec m_1) = \scrI(\vec \omega, d_2, \vec m_2) = \scrI(\vec \omega, d_1 + d_2, \vec m_1 + \vec m_2)$. Then show that $\scrQ(\vec \omega, d_1+d_2, \vec m_1 + \vec m_2) = \scrQ(\vec \omega, d_1, \vec m_1) + \scrQ(\vec \omega, d_2, \vec m_2)$.
\item With $\vec \omega = (1,1,1)$, and $p = 2$, show that $\scrQ(\vec \omega, 3, (1, 1)) + \scrQ(\vec \omega, 3, (3, 3)) \subsetneq \scrQ(\vec \omega, 6, (4, 4))$, i.e.\ the conclusion of assertion \eqref{sumQ} may not be true in the absence of its assumption.
\end{enumerate}
\end{exercise}

\begin{exercise} \label{exercise:vol-omegadm}
\begin{enumerate}
\item Given polytopes $\Delta_1, \ldots, \Delta_p \subset \rr^n$, show that
\begin{align*}
\vol\left( \bigcup_{q=1}^p \Delta_q \right)
	&= \sum_{q=1}^p (-1)^{q-1} \sum_{I \subseteq [p],\ |I| = q}
		\vol\left(\bigcap_{i \in I} \Delta_i \right)
\end{align*}
where $[p]$ denotes the set $\{1, \ldots, p\}$ (this is the so called ``inclusion-exclusion principle,'' it holds for all ``measurable'' sets with finite volume, i.e.\ as long as the volume of each intersection on the right hand side is well defined and finite).

\item Given $\vec \omega, d, \vec m$ as in \cref{exercise:omegadm}, define
\begin{align*}
\Delta_0
	&:= \{(x_1, \ldots, x_n): x_i \geq 0,\ i = 1, \ldots, n,\ \sum_{i=1}^n \omega_i x_i \leq d\} \\
\Delta_q
	&:= \{(x_1, \ldots, x_n): x_i \geq 0,\ i = 1, \ldots, n,\ x_q \geq m_q, \sum_{i=1}^n \omega_i x_i \leq d\},\ q = 1, \ldots, p.
\end{align*}
Show that the polytope $\scrQ(\vec \omega, d, \vec m)$ from \cref{exercise:omegadm} equals $\Delta_0 \setminus \bigcup_{q=1}^p \Delta_p$. Conclude that
\begin{align*}
\vol(\scrQ(\vec \omega, d, \vec m))

	&=  \frac{1}{n!\omega_1 \cdots \omega_n}
	   \sum_{q = 0}^p (-1)^q
	   \sum_{\substack{I \subseteq [p],\ |I| = q\\ \sum_{i \in I} \omega_i m_i < d}}
	   (d - \sum_{i \in I}\omega_i m_i)^n
\end{align*}
\end{enumerate}
\end{exercise}

\section{$^*$Volume of special classes of polytopes}
\footnote{The asterisk in the section name is to indicate that the material of this section is not going to be used in \cref{toric-intro}. It is only used in the proof of Bernstein's theorem in \cref{bkk-chapter}.}In \cref{minkowski-section} we study the dependence of the volume of Minkowski sums of polytopes on its summands, and in \cref{rational-volume-section} we give a formula of the volume of rational polytopes in terms of ``lattice volumes'' of its facets.

\subsection{Minkowski sums} \label{minkowski-section}
\Cref{vol-basics} implies that volume interacts well with Minkowski addition, in the sense that given compact convex subsets $\scrP, \scrQ$ of $\rr^n$, the function from $\rzero$ to $\rzero$ given by $\lambda \mapsto \vol_n(\scrP + \lambda \scrQ)$ is continuous. However, it turns out that this function is much more than a continuous function, it is a {\em polynomial}. In this section we are going to prove this result for the case of polytopes. At first we need the following result.

\begin{lemma} \label{sum-lemma-2}
Let $\scrP_1, \ldots, \scrP_s$ be subsets of $\rr^n$ and $\lambda := (\lambda_1, \ldots, \lambda_s) \in \rpluss{s}$. Then for different $\lambda$, the affine hull $A_\lambda$ of $\lambda_1\scrP_1 + \cdots + \lambda_s \scrP_s$ are translations of each other. In particular, $\dim(A_\lambda)$ is independent of $\lambda$.
\end{lemma}

\begin{proof}
Fix an arbitrary element $\alpha_i$ of $\scrP_i$, $i = 1, \ldots, n$. \Woutlog\ we may replace $\scrP_i$ by $\scrP_i - \alpha_i$ and assume that each $\scrP_i$ contains the origin. For each $\lambda \in \rpluss{s}$, it then follows that $A_\lambda$ contains each $\scrP_i$, and therefore it is simply the linear subspace of $\rr^n$ spanned by elements in $\bigcup_i \scrP_i$.
\end{proof}

\begin{thm} \label{volume-thm}
Let $\scrP_1, \ldots, \scrP_s$ be convex polytopes in $\rr^n$. Then there are nonnegative real numbers $v_\alpha(\scrP_1, \ldots, \scrP_s)$ for all $\alpha \in \scrE_s:= \{(\alpha_1, \ldots, \alpha_s) \in \zzeroo{s}: \alpha_1 + \cdots  + \alpha_s = n\}$ such that for all $\lambda = (\lambda_1, \ldots, \lambda_s) \in \rzeroo{s}$,
\begin{align*}
\vol_n(\lambda_1\scrP_1 + \cdots + \lambda_s \scrP_s) = \sum_{\alpha \in \scrE_s} v_\alpha(\scrP_1, \ldots, \scrP_s) \lambda_1^{\alpha_1} \cdots \lambda_s^{\alpha_s}
\end{align*}
where $\vol_n$ is the $n$-dimensional volume.
\end{thm}

\begin{proof}
We proceed by induction on $n$. If $n = 1$ each $\scrP_i$ is of the form $[a_i, b_i]$, so that
\begin{align*}
\vol_1(\lambda_1\scrP_1 + \cdots + \lambda_s \scrP_s)
	&= \vol_1([\lambda_1a_1 + \cdots + \lambda_s a_s, \lambda_1b_1 + \cdots + \lambda_s b_s]) \\
	&= \lambda_1(b_1 - a_1) + \cdots + \lambda_s(b_s - a_s) \\
	&= \sum_i \lambda_i\vol_1(\scrP_i)
\end{align*}
Now assume it is true for convex polytopes in $\rr^{n-1}$. Now pick convex polytopes $\scrP_1, \ldots, \scrP_n$ in $\rr^n$. Since the volume is translation invariant, we may assume that
\begin{align}
\parbox{.6\textwidth}{the origin is in the relative interior of each $\scrP_j$.}
\tag{$*$} \label{origin-interior}
\end{align}
Let $P_\lambda := \lambda_1\scrP_1 + \cdots + \lambda_s \scrP_s$. If $\dim(P_\lambda) \leq n-1$, then the result is true with all $v_\alpha$ being zero. So assume $\dim(P_\lambda) = n$. Due to \cref{vol-basics} it suffices to consider the case that each $\lambda_i$ is {\em positive}. Then \cref{prop:sum-faces,sum-lemma-2} imply that the number of facets of $\scrP_\lambda$ does not depend on $\lambda$, and moreover, if $\scrP_{\lambda, 1}, \ldots, \scrP_{\lambda, N}$ are the facets of $\scrP_\lambda$, then for each $j$, there are faces $\scrP_{i,j}$ of $\scrP_i$, $i = 1, \ldots, s$, such that
\begin{align*}
\scrP_{\lambda, j} = \lambda_1 \scrP_{1, j} + \cdots + \lambda_s \scrP_{s,j}
\end{align*}
For each $i,j$, pick an arbitrary $\alpha_{i, j} \in \scrP_{i,j}$. Let $\nu_j$ be the outward pointing unit normal to $\scrQ_{\lambda, j}$. Identity \eqref{volume-facet-unit-formula} implies that
\begin{align*}
\vol_n(\scrP_\lambda)
	&= \frac{1}{n}\sum_j
 			\max_{\scrP_\lambda}(\nu_j) \vol_{n-1}(\scrP_{\lambda, j})\\
 	&= \frac{1}{n}\sum_j
 	 			\langle \nu_j, \lambda_1 \alpha_{1, j} + \cdots + \lambda_s \alpha_{s,j}\rangle \vol_{n-1}(\lambda_1 \scrP_{1, j} + \cdots + \lambda_s \scrP_{s,j})
\end{align*}
Condition \eqref{origin-interior} implies that  $\langle \nu_j, \alpha_{i,j} \rangle$ is nonnegative for each $i,j$. Since for each $j$, all the $\scrP_{i,j}$ can be identified (via a volume preserving affine map from $\aff(\scrP_{\lambda,j})$ to $\rr^{n-1}$) with polytopes in $\rr^{n-1}$, the result then follows from the inductive hypothesis.
\end{proof}

\subsection{Rational polytopes} \label{rational-volume-section}

Let $H$ be a $d$-dimensional rational affine subspace of $\rr^n$. If $\beta \in H \cap \zz^n$, \cref{rational-solutions} implies that $G_H := (H - \beta) \cap  \zz^n$ is isomorphic (as an abelian group) to $\zz^d$. A {\em fundamental lattice parallelotope} on $H$ is a polytope of the form $\scrP + \beta$, where $\scrP$ is a ($d$-dimensional) parallelotope generated by $d$ elements from $G_H$ which generate $G_H$ as an abelian group. We write $\fund(H) := \vol_H(\scrP)$. \Cref{prop:fund-vol} below shows that $\fund(H)$ is well defined. In this section we identify $\rr^n$ with $\rnstar$ via the dot product, and given $\alpha, \beta \in \rr^n$, write $\langle \alpha, \beta \rangle$ for the dot product of $\alpha$ and $\beta$. Similarly we write $\beta^\perp := \{\gamma \in \rr^n: \langle \beta, \gamma \rangle = 0\}$.

\begin{center}
\begin{figure}[h]
\def\xmin{-3.5}
\def\xmax{5.5}
\def\ymin{-3.5}
\def\ymax{3.5}
\def\scalefactor{0.45}
\tikzstyle{dotsmall} = [\colordot, circle, minimum size=3pt, inner sep = 0pt, fill]

\begin{tikzpicture}[scale=\scalefactor]
\draw [gray,  line width=0pt] (\xmin, \ymin) grid (\xmax,\ymax);
\draw [<->] (0, \ymax) |- (\xmax, 0);

\coordinate (A') at (-3.5, -2.5);
\coordinate (B') at (2.5, 3.5);
\coordinate (A) at (-2, -1);
\coordinate (B) at (1, 2);

\coordinate (C') at (-3.5, -3.25);
\coordinate (D') at (5.5, 1.25);
\coordinate (C) at (-1, -2);
\coordinate (D) at (3, 0);

\draw (A') -- (B');
\draw (C') -- (D');
\draw[thick, \colorAB] (A) -- (B);
\draw[thick, \colorBC] (C) -- (D);

\node[dotsmall] at (A) {};
\node[dotsmall] at (B) {};
\node[dotsmall] at (C) {};
\node[dotsmall] at (D) {};

\node[anchor = east] at (A) {\picfontsize $A$};
\node[anchor = east] at (B) {\picfontsize $B$};
\node[anchor = north] at (C) {\picfontsize $C$};
\node[anchor = north] at (D) {\picfontsize $D$};
\node[anchor = south] at (B') {\picfontsize $L$};
\node[anchor = west] at (D') {\picfontsize $M$};
\end{tikzpicture}

\caption{$\fund(L)= \sqrt{2}$, $\fund(M) = \sqrt{5}$. $\vol'_L(AB) = 3$, $\vol'_M(CD) = 2$.}
\label{fig:fundamentally-normal-vol}
\end{figure}
\end{center}

\begin{prop} \label{prop:fund-vol}
Let $H$ be a rational affine subspace of $\rr^n$. If $\scrP_1, \scrP_2$ are two fundamental lattice parallelotopes of $H$, then $\vol_H(\scrP_1) = \vol_H(\scrP_2)$.
\end{prop}

\begin{proof}
By translating $H$ and the $\scrP_j$ if necessary we may assume $H$ is a linear subspace of $\rr^n$, and each $\scrP_j$ is the parallelotope generated by $\alpha_{j,1}, \ldots, \alpha_{j, d} \in H \cap \zz^n$, where $d := \dim(H)$. Pick an orthonormal set $\beta_1, \ldots, \beta_{n-d} \in \rr^n$ such that $H = \bigcap_i \beta_i^\perp$. For each $j = 1, 2$, let $\scrB_j$ be the basis of $\rr^n$ consisting of $\beta_1, \ldots, \beta_{n-d}, \alpha_{j,1}, \ldots, \alpha_{j,d}$. By definition $\vol_H(\scrP_j) = \vol_n(\scrQ_j)$, where $\scrQ_j$ is the parallelotope generated by the elements of $\scrB_j$. Let $\phi: \rr^n \to \rr^n$ be the linear map which changes coordinates with respect to $\scrB_1$ to that of $\scrB_2$. Since $\alpha_{j,1}, \ldots, \alpha_{j,d}$ generate $H \cap \zz^n$ (as an abelian group), it follows that the matrices of both $\phi$ and $\phi^{-1}$ have only integer entries. This means that the determinant of the matrix of $\phi$ is $\pm 1$, and therefore $\phi$ preserves $\vol_n$. Since $\phi$ maps one of the $\scrQ_j$ to the other, this completes the proof.
\end{proof}

Let $H'$ be a rational affine subspace of $\rr^n$ such that $H' \supset H$ and $\dim(H') = d+1$. We now describe the relation between $\fund(H)$ and $\fund(H')$. Pick $\beta \in H$. Since $(H- \beta) \cap \qq^n \subset (H'- \beta) \cap \qq^n$ is an inclusion of vector spaces over $\qq$, it follows from the elementary theory of vector spaces that there is $\eta' \in (H'- \beta) \cap \qq^n$ such that $H - \beta = \eta'^\perp \cap (H' - \beta)$. Pick $r \in \qq \setminus \{0\}$ such that $\eta := r\eta'$ is ``primitive,'' i.e.\ there is no integer $k > 1$ such that $\eta = k\eta''$ for some $\eta'' \in \zz^n$. Let $\norm{\cdot}$ denote the Euclidean norm on $\rr^n$.

\begin{prop} \label{fundamental-cor'}
\begin{align*}
\fund(H) =  \frac{\norm{\eta}}{\min\{|\langle \eta, \alpha\rangle|: \alpha \in ((H' - \beta) \cap \zz^n) \setminus (H - \beta)\}}\fund(H')
\end{align*}
In particular, if $d = n-1$ and $H' = \rr^n$, then $\fund(H) = \norm{\eta}$.
\end{prop}

\begin{proof}
Replacing $H$ by $H - \beta$ if necessary we may assume that $\beta= 0$. \Cref{basis-lemma} implies that we may pick $\alpha_1, \ldots, \alpha_{d+1}, u_{d+1}, \ldots, u_n \in \rr^n$ such that
\begin{itemize}
\item $\alpha_1, \ldots, \alpha_d$ generate $H \cap \zz^n$,
\item $\alpha_1, \ldots, \alpha_{d+1}$ generate $H' \cap \zz^n$,

\item $u_{d+1} \in H'$, $H = u_{d+1}^\perp \cap H'$, $\norm{u_{d+1}} = 1$,
\item $u_{d+2}, \ldots, u_n$ are orthonormal (with respect to dot product), and $H' = \bigcap_{j = d+2}^n u_j^\perp$.
\end{itemize}
Let $M$ be the matrix with column vectors $\alpha_1, \ldots, \alpha_d, u_{d+1}, \ldots, u_n$ and $M'$ be the matrix with column vectors $\alpha_1, \ldots, \alpha_{d+1}, u_{d+2}, \ldots, u_n$. Write $u_{d+1} = c_{d+1}\alpha_{d+1} + u'$, where $u' \in H$. Then
\begin{align*}
\fund(H) = |\det(M)| = |c_{d+1} \det(M')| =| c_{d+1}|\fund(H')
\end{align*}
Note that $u_{d+1} = \pm \eta/\norm{\eta}$. It follows that $\langle \eta, u_{d+1} \rangle = \pm \norm{\eta}$. On the other hand, $\langle \eta, u_{d+1} \rangle = \langle \eta, c_{d+1}\alpha_{d+1} + u' \rangle = c_{d+1} \langle \eta, \alpha_{d+1} \rangle$. Since for each $\alpha \in H' \cap \zz^n$, $\langle  \eta, \alpha \rangle$ is an integer multiple of $ \langle \eta, \alpha_{d+1} \rangle$, the result follows.
\end{proof}

\begin{defn} \label{vol'}
Let $H$ be a rational affine subspace of $\rr^n$ of dimension $d$. The {\em $H$-normalized volume} is
\begin{align*}
\vol'_{H}(\cdot) := \vol_d(\cdot)/\fund(H)
\end{align*}
see \cref{fig:fundamentally-normal-vol} for some examples with $n =2$. An {\em integral} element of $\rr^n$ is an element with integral coordinates; an integral element of $\rnstar$ is one which has integral coordinates with respect to the basis which is dual to the standard basis of $\rr^n$. An integral element $\eta$ of $\rr^n$ or $\rnstar$ is {\em primitive}, if it is not of the form $k\eta'$, where $k > 1$ and $\eta'$ is also integral. If $\nu$ is an integral element of $\rnstar$, then we write $\vol'_\nu$ for $\vol'_{\nu^\perp}$.
\end{defn}

\begin{cor} \label{volume-facet-rational}
Let $\scrP$ be a convex rational polytope in $\rr^n$. Then
\begin{align}
\vol_n(\scrP)
	&= \frac{1}{n}\sum_\nu \max_\scrP(\nu) \vol'_\nu(\ld_\nu(\scrP))
	= -\frac{1}{n}\sum_\nu \min_\scrP(\nu) \vol'_\nu(\In_\nu(\scrP)) \label{rational-volume}
\end{align}
where the sum is over all primitive integral $\nu  \in \rnstar$.
\end{cor}

\begin{proof}
Since $\scrP$ is rational, every facet of $\scrP$ is determined by integral elements of $\rnstar$. Therefore the result follows from combining \cref{volume-facet-unit-formula,fundamental-cor'}.
\end{proof}

\begin{rem} \label{primitive-remark}
If $\scrQ$ is a facet of an $n$-dimensional rational polytope $\scrP$ in $\rr^n$, then the {\em primitive inner} (respectively {\em outer}) {\em normal} to $\scrF$ is the unique primitive integral $\nu \in \rnstar$ such that $\scrQ = \In_\nu(\scrP)$ (respectively $\scrQ = \ld_\nu(\scrP)$). Note that the sum in \eqref{rational-volume} is practically finite: the only non-zero contributions come from those $\nu$ which are primitive outer normal to $(n-1)$-dimensional faces of $\scrP$.
\end{rem}