According to "Convex Optimization" by Boyd and Vandenberghe, a polyhedron is defined as the solution set to a finite number of linear equalities and inequalities:
$$P = \{x \: | \: a_j^T \leq b_j, j = 1, \ldots, m, c_j^T x = d_j, j = 1, \ldots, p\}$$
Geometrically, this corresponds with finitely many intersecting hyperplanes and halfspaces.
Exercise 2.8(d) then goes on to ask whether or not the following set is a polyhedron:
$$S = \{ x \in \mathbb{R}^n \: | \: x \succeq 0, x^T y \leq 1 \text{ for all } y \text{ with } \sum_{i=1}^n |y_i| = 1 \}$$
(where $\succeq$ indicates component-wise vector inequality)
I believe that the answer is Yes.
$x \succeq 0$ can easily be written as finitely many equations explicitly checking each component.
I believe the condition $\{ y | \sum |y_i| = 1\}$ means that $y$ has to be an edge on a unit cube centered around 0 and rotated 45 degrees (e.g. in two dimensions, a square with endpoints $\{ (0, 1), (0, -1), (1, 0), (-1, 0)\}$). This can also be expressed with finitely many hyperplanes.
However, I can't figure out how to express the $x^T y \leq 1$ condition as a linear inequality.
Is my answer on the right track, or totally wrong? How can this be done?
Sometimes it helps to look at the question in more specificity. In this case, the easiest way to do that is probably to take $n=2$.
You say 'this corresponds with finitely many intersecting hyperplanes and halfspaces'. How many $\vec{y}=\langle y_1,y_2\rangle $ are there with $\left|y_1\right|+\left|y_2\right|=1$? Pick some particular subset of those (for instance, you could just take the set of vectors $\vec{y}=\langle t,1-t\rangle$ for $0\leq t\leq 1$) and for each one of these, look at the set $\mathbb{X}_t$ of all $\vec{x}$ that satisfy the constraint. What does the intersection (over $t$) of these sets $\mathbb{X}_t$ look like?