# Prove that every ray is a polyhedron

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.

• Are you sure a polyhedron isn't defined as the solution set of a system of linear inequalities, rather than just one linear inequality? Because all you get from one inequality is half-spaces. Nov 28 '21 at 20:36
• @coffeemath Actually the book uses the vector inequality notation but I will edit my question. Thanks. Nov 28 '21 at 20:39
• @coffeemath By vector notation, I mean $Ax\le b$ where $A$ is $n\times n$ matrix and $x$ and $b$ are both $n$-dimensional vectors. The inequality means that every component of $Ax$ is less than the corresponding component of $b$. So I believe that this is equivalent to a system of linear inequalities. It also is equivalent to the intersection of a finite number of half-spaces. Hence it determines a polyhedron in all three definitions. Nov 28 '21 at 20:52
• I am pretty sure a set of linear inequalities can only give you convex polyhedra. Nov 28 '21 at 20:55
• Ok, then that's fine. I'm just used to polyhedra not necessarily being convex as an implicit assumption. Nov 28 '21 at 21:03

## 1 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\}$$.