I have a specific linear system I'm working on (all numbers involved are integers), which is $\mathbf{A}\cdot \vec{x} < 0$, subject to $\vec{x}\geq 0$. Now, the solution space is some convex high-dimensional space. I am considering the process of covering it by semi-infinite boxes of the form $\vec{x} \geq \vec{\mathbf{c}}$ (meaning $x_1 \geq c_1$ and $x_2 \geq c_2$ and so on.)
My question is:
For the system $\mathbf{A}\cdot \vec{x} < 0$, subject to $\vec{x}\geq 0$, is it always possible to find a finite cover of boxes —i.e. a collection of vectors $\vec{\mathbf{c}}_1, \ldots \vec{\mathbf{c}}_k$ such that:
- Each $\vec{\mathbf{c}}_k$ lies in the solution space.
- Every point in the solution space is contained in at least one box $\vec{x}\geq \vec{\mathbf{c}}_k$.
My overall goal is to explicitly construct such a collection for my specific system $\mathbf{A}$, and in fact to construct a minimal collection. But I have had difficulty establishing that it is always finite.
What I have tried so far is working with individual rows of my matrix—for our purposes, its entries are all from $\{-1,0,+1\}$—and noting that you can always cover the solution space for a single row by creating one vector $\mathbf{\vec{c}}_k = [0, \ldots,0, 1,0\ldots 0]$ for each column that has a -1 in it.
The trouble is, I don't have a compositional rule for how to combine a cover for one row with a cover for another row. Such boxes are closed under intersection, so you can apply the distributive property to $\bigcup_i (x \geq \mathbf{c_i}) \;\cap\; \bigcup_j (x \geq \mathbf{d}_j)$ to obtain a new set of boxes that covers the space— but unfortunately these will usually violate condition (1), that the box lies in the shared solution space. And in general patching the boxes to work seems as difficult as solving the linear system itself.
I am unsure if this construction is likely to work, so my current question is whether I can be sure that such a finite cover always exists.
Yes, any subset of $n$-tuples of natural numbers — including, as a special case, the integer solutions to an optimization problem like $\mathbf{A}\cdot \vec{x} < 0$ ($\vec{x}\geq 0)$ — can be covered by finitely many boxes. This is the content of Dickson's lemma.
The condition $\vec{x}\geq 0$ is key here, as it ensures that the tuples are bounded below in each dimension.