Let \(C \subseteq \mathbb{R}^n\) be a polyhedral cone.
A nonzero \(\mathbf{d} \in C\) is an extreme ray of \(C\)
if there do not exist linearly independent \(\mathbf{u},\mathbf{v}\in C\)
and positive scalars \(\lambda\) and \(\gamma\) such that
\(\mathbf{d} = \lambda \mathbf{u} + \gamma \mathbf{v}\).
Note that if \(\mathbf{d}\) is an extreme ray, then
\(\lambda \mathbf{d}\) is also an extreme ray for all \(\lambda > 0\).
We say that two extreme rays are equivalent if one is a positive
scalar multiple of the other.
Hence, when enumerating extreme rays of a polyhedral cone, we often
enumerate one representative from each equivalent class of extreme rays.
One way to achieve this is to impose a normalization condition such as
restricting to unit vectors with respect to some vector norm.
Proposition 10.2.
Let \(C\subseteq \mathbb{R}^n\) be given by
\(\{\mathbf{x} \in \mathbb{R}^n: \mathbf{A}\mathbf{x} \geq \mathbf{0}\}\)
for some \(\mathbf{A} \in \mathbb{R}^{m \times n}\).
Let \(\mathbf{d} \in C\) be nonzero.
Let \(\mathbf{A}^= \mathbf{x} \geq \mathbf{0}\) denote
the subsystem of \(\mathbf{A}\mathbf{x} \geq \mathbf{0}\) consisting
of all the inequalities active at \(\mathbf{d}\).
Then \(\mathbf{d}\) is an extreme ray of \(C\) if and only if
\(\operatorname{rank}(\mathbf{A}^=) = n-1\).
Proof.
Suppose that \(\mathbf{d} = \lambda \mathbf{u} + \gamma\mathbf{v}\)
for some linearly independent \(\mathbf{u},\mathbf{v}\in C\)
and scalars \(\lambda,\gamma \gt 0\).
Then
\[\mathbf{0} = \mathbf{A}^=\mathbf{d}
= \lambda \mathbf{A}^=\mathbf{u} + \gamma\mathbf{A}^=\mathbf{v}
\geq \mathbf{0}.\]
Hence, equality holds throughout.
Since \(\lambda, \gamma \gt 0\), we must have
\(\mathbf{A}^=\mathbf{u} = \mathbf{A}^=\mathbf{v} = \mathbf{0}\).
Hence, \(\mathbf{u}\) and \(\mathbf{v}\) are linearly independent
vectors in the nullspace of \(\mathbf{A}^=\), implying that
\(\operatorname{rank}(\mathbf{A}^=) \lt n-1\).
Suppose that \(\operatorname{rank}(\mathbf{A}^=) \lt n-1\).
There exists a nonzero vector \(\mathbf{y}\) in the nullspace of
\(\mathbf{A}^=\) such that \(\mathbf{d}\) and \(\mathbf{y}\) are
linearly independent. For a sufficiently small \(\epsilon \gt 0\),
\(\mathbf{d} \pm \epsilon\mathbf{y} \in C\).
Note that \(\mathbf{d} - \epsilon\mathbf{y}\) and
\(\mathbf{d} + \epsilon\mathbf{y}\) are linearly independent and
\(\mathbf{d} = \left(\mathbf{d} - \epsilon\mathbf{y}\right)
+\left(\mathbf{d} + \epsilon\mathbf{y}\right)\), implying that
\(\mathbf{d}\) is not an extreme ray.
Example.
Consider
\(C = \left\{ \mathbf{x} \in \mathbb{R}^3 : \mathbf{A}\mathbf{x} \geq \mathbf{0}
\right\}\) where
\(\mathbf{A} = \begin{bmatrix}
3 & 0 & -1 \\
1 & -2 & 1 \\
-1 & 2 & -1 \\
\end{bmatrix}\).
Then \(\mathbf{d} = \begin{bmatrix} 1 \\ 2 \\ 3 \end{bmatrix}\)
is an extreme ray since \(\mathbf{A}^= = \mathbf{A}\)
and \(\operatorname{rank}(\mathbf{A}^=) = 2\).
Incidentally, we could have also taken the first and third rows of
\(\mathbf{A}\) for \(\mathbf{A}^=\).
Corollary 10.3.
The number of nonequivalent extreme rays of a polyhedral cone is finite.
Proof.
Since there are only finitely many subsystems of a finite system
of linear inequalities, it follows from Proposition 10.2 that there
can only be a finite number of nonequivalent extreme rays.
We say that \(\mathbf{d}^1,\ldots,\mathbf{d}^k\) form a
complete set of extreme rays of \(C\) if
\(\mathbf{d}^i\) is an extreme ray of \(C\) for
\(i = 1,\ldots,k\) and every extreme ray of \(C\) is equivalent to
\(\mathbf{d}^i\) for some \(i \in \{1,\ldots,k\}\).
Worked examples
Let \(C = \left \{ \begin{bmatrix}
x_1 \\ x_2 \end{bmatrix} \in \mathbb{R}^2:
\begin{array}{r}
x_1 + 2x_2 \geq 0 \\
-3x_1 + x_2 \geq 0
\end{array}
\right \}\).
Find all extreme rays of \(C\) of unit length.
Solving this problem graphically is certainly an option.
Since \(C \subseteq \mathbb{R}^2\), we only need to consider
subsystems consisting of a single inequality.
Setting the inequality \(x_1 + 2x_2\geq 0\) to equality, we
obtain the general solution \(\lambda \begin{bmatrix} -2 \\ 1\end{bmatrix}\).
Since \(\begin{bmatrix} -2 \\ 1\end{bmatrix}\) also satisfies the other
inequality, normalizing it to a unit vector gives the extreme ray
\(\begin{bmatrix} -\frac{2}{\sqrt{5}} \\ \frac{1}{\sqrt{5}}\end{bmatrix}\).
Setting the inequality \(-3x_1 + x_2\geq 0\) to equality, we
obtain the general solution \(\lambda \begin{bmatrix} 1\\ 3\end{bmatrix}\).
Since \(\begin{bmatrix} 1 \\ 3\end{bmatrix}\) also satisfies the other
inequality, normalizing it to a unit vector gives the extreme ray
\(\begin{bmatrix} \frac{1}{\sqrt{10}} \\ \frac{3}{\sqrt{10}}\end{bmatrix}\).
Let \(\mathbf{d}^1,\ldots,\mathbf{d}^k \in \mathbb{R}^n\) be such that
\(C = \operatorname{cone}\left(\left\{ \mathbf{d}^1,\ldots,\mathbf{d}^k
\right\}\right)\) is pointed.
Prove that if for some \(\bar{i} \in \{1,\ldots,k\}\),
\(\mathbf{d}^\bar{i}\) is not an extreme ray of \(C\), then
\(C = \operatorname{cone}\left(\left\{
\mathbf{d}^i : i \in \{1,\ldots,k\}\setminus\{\bar{i}\}
\right\}\right)\).
Without loss of generaliy, we may assume that \(\bar{i} = k\).
Since \(\mathbf{d}^k\) is not an extreme ray,
there exist linearly independent \(\mathbf{u},\mathbf{v} \in C\)
and scalars \(\lambda, \gamma \gt 0\) such that
\[\mathbf{d}^k = \lambda\mathbf{u} + \gamma\mathbf{v}.\]
Let \(\alpha_1,\ldots,\alpha_{k} \geq 0\) be scalars
such that \(\mathbf{u} = \sum_{i=1}^k \alpha_i \mathbf{d}^i\)
and let \(\beta_1,\ldots,\beta_{k}\geq 0\) be scalars
such that \(\mathbf{v} = \sum_{i=1}^k \beta_i \mathbf{d}^i\).
Then,
\[(1-\lambda\alpha_k-\gamma\beta_k)\mathbf{d}^k =
\sum_{i=1}^{k-1} (\lambda\alpha_i + \gamma\beta_i)\mathbf{d}^i.\]
If
\(1-\lambda\alpha_k-\gamma\beta_k \gt 0\), then
\[\mathbf{d}^k =
\sum_{i=1}^{k-1} \frac{\lambda\alpha_i + \gamma\beta_i}
{1-\lambda\alpha_k-\gamma\beta_k} \mathbf{d}^i,\]
implying that \(\mathbf{d}^k \in \operatorname{cone}\left(\left\{
\mathbf{d}^1,\ldots,\mathbf{d}^{k-1} \right\}\right)\). It follows
that \(C = \operatorname{cone}\left(\left\{
\mathbf{d}^1,\ldots,\mathbf{d}^{k-1} \right\}\right)\).
Suppose that \(1-\lambda\alpha_k-\gamma\beta_k \leq 0\).
Then
\[\sum_{i=1}^k \zeta_i \mathbf{d}^k = \mathbf{0}\]
where \(\zeta_i = \lambda\alpha_i + \gamma\beta_i\) for \(i = 1,\ldots, k-1\),
and \(\zeta_i = 1-\lambda\alpha_k - \gamma\beta_k\).
The important point is that \(\zeta_i \geq 0\) for \(i = 1,\ldots,k\).
Note that we cannot have \(\zeta_i = 0\) for \(i =1,\ldots,k-1\).
Otherwise, we will have that \(\mathbf{u}\) and \(\mathbf{v}\)
are both scalar multiples of \(\mathbf{d}^k\), contradicting that they are
linearly independent.
Without loss of generality, we may assume that \(\zeta_1 \gt 0\).
Thus
\[ -\zeta_1\mathbf{d}^1 = \sum_{i=2}^k \zeta_i \mathbf{d}^k.\]
Dividing both sides by \(\zeta_1\) gives
\[ -\mathbf{d}^1 = \sum_{i=2}^k \frac{\zeta_i}{\zeta_1} \mathbf{d}^k,\]
implying that \(-\mathbf{d}^1 \in C\).
Since we also have \(\mathbf{d}^1 \in C\), it follows that
\(C\) contains the line \(\{\lambda \mathbf{d}^1 : \lambda \in \mathbb{R}\}\).
By Theorem 8.6.
cannot be pointed, which is a contradiction.