Suppose a finite set of $m$ half-spaces $H_i$ in $\mathbb{R}^n$ are described by equations $$ \mathbf{\ell}_i \cdot \mathbf{x} \leq 1. $$ for $1\leq i \leq m$. If $L$ is the $m\times n$ matrix with rows $\mathbf{\ell}_i$, then the intersection $I = \cap H_i$ of half-spaces can be described as the set $$ I = \{ \mathbf{x} \colon \, \text{entries of }L\mathbf{x}\text{ are }\leq 1\}. $$
Note that this intersection is always non-empty (it contains the origin). For many reasons (e.g. doing linear programming, optimization, and in some geometric problems), it is important to know whether the set I is bounded (a polytope). Incidentally, most references I see about linear programming assume that $I$ is bounded or not and don't discuss how best to determine this.
One can characterize boundedness as follows
$I$ is bounded iff for all $\mathbf{x}\neq 0$ there exists $1\leq i \leq m$ such that $\ell_i\cdot \mathbf{x} >0$.
I am wondering, is there a nice ``linear algebraic'' way to characterize this (e.g. in terms of some linear algebraic properties of the matrix $L$)? E.g. can I test for this by performing some sort of matrix decomposition or normal form of $L$?
Edit: By duality:
$I$ is bounded iff the dual $I^* = \text{convex hull}(\ell_i)$ contains zero.
In other words, $I$ is bounded iff there is a convex combination $$ \mathbf{0} = \sum_1^m a_i \ell_i, \text{ where } \sum_1^m a_i = 1. $$ I guess this is a problem that has a well known solution but it doesn't look like it's a solution of the form I was hoping for. Oh well.
Let's see what it means that the linear form $\ell$ is bounded above by $M$
$$\{x\ | \ \ell_i(x)\le 1\}$$
It means that the inequality $\ell(x)-M\le 0$ is a consequence $\ell_i(x)-1\le 0$, that is (Farkas lemma) there exists $\alpha_i\ge 0$ and $\beta\ge 0$ so that $$\ell(\cdot) - M = \sum_i\alpha_i(\ell(\cdot)-1) - \beta$$ It follows that $\ell = \sum \alpha_i \ell_i$. The converse is also true: any functional that is a positive combination of $\ell_i$ is bounded above on $\{x\ | \ \ell_i(x)\le 1\}$
So the condition for the boundedness is: the positive cone generated by the $\ell_i$'s is the whole (dual) space. It is enough that the $\pm$ coordinate functionals are.
It is not that hard to see that one needs at least $(n+1)$ functionals $\ell_i$.
Now, like you said ( translated) the cone is not the whole space if and only if there exists an $x$ so that $$l_i\cdot x < 0$$ for all $i$.
This can be tested as a linear programming problem:
$$\min t \ ,\ (x,t) \in \mathbb{R}^{n} \times \mathbb{R}, \ \ell_i \cdot x \le t \le 0 \ \text{ for all } i \text{ and } -1 \le t$$ (the last inequality to make the $\min$ larger than $-\infty$. There are two cases:
the $min$ is $-1$, the cone of $\ell_i$ is not the full space, the set determined is unbounded
the $min$ is $0$, the cone of $\ell_i$ is the full space, the set determined is bounded.
Another characterization: $I$ (with your notation) is bounded if and only if $0$ is in the interior of the cone $\ell_i$ . This is equivalent to : there exists $n+1$ of the $\ell_i$ forming a system of rank $n$ and $\alpha_1$, $\ldots$, $\alpha_{n+1}> 0$ so that $$\sum_i \alpha_i \ell_i = 0$$
This might be easy to check in some cases, otherwise, it's still a linear optimization problem, although seems more complicated than the previous one.
Added:
A sufficient condition for $n+1$ vectors $y_i$ such that the cone spanned by them is the full space: $y_i \cdot y_j < 0$ for $i\ne j$. Indeed, assume that there exists $y_{n+2}$ such that $y_i \cdot y_{n+2} < 0$ for all $1\le i \le n+1$. The system $$\sum \alpha_i y_i = 0 \\ \sum \alpha_i = 0$$ has a non-zero solution. Separate the positive and the negative coefficients So we can write $$y =\sum_{i \in I'} \alpha_i y_i= \sum_{i \in I''} \beta_i y_i$$
and taking the dot product $y \cdot y$ where the second $y$ is substituted with the second sum we get $y \cdot y < 0$, contradiction.