I am reading a book on linear optimization and I am stuck with the following problem:
Prove that every ray in $\mathbb{R}^n$ is a polyhedron.
The book defines a ray as follows:
For a point $x_0\in\mathbb{R}^n$ and a vector $d\in\mathbb{R}^n$, a ray is the set $$\{x_0+\lambda d \mid \forall \lambda \in \mathbb{R} \, \text{such that} \, \lambda \ge 0\}$$
It also defines a polyhedron as a set of solutions to a system of linear inequalities.
My idea is to find a linear transformation $A$, whose kernel is the subspace spanned by $d$. Consequently, the set of solutions to the equation $Ax=Ax_0$ will be a line containing the ray. But there is two problems. First I do not know how to find such a $A$. Second, I do not know what to do next.
Any help is appreciated.
Best Answer
Let the ray be $R= \{x_0+t d \}_{t \ge 0}$. Let $d_2,...,d_n$ be a basis for $\{ d \}^\bot$, then $R = \{ x | d_k^T(x-x_0) = 0, d^T(x-x_0) \ge 0\}$.