# Linear programming -- checking solution subspace containment

### Linear programming -- checking solution subspace containment

We have a set of linear constraints, represented by (*) $A\overline{x} \le \overline{b}$, for a matrix $A$ and a vector $\overline{b}$. I'm looking for a procedure to decide whether the solution subspace of (*) with respect to a subvector $\overline{x}^1$ is contained in the solution subspace with respect to another subvector $\overline{x}^2$ (of the same dimension as $\overline{x}^1$).
To put it another way: if we project the set of all solutions of (*) to the components of $\overline{x}^1$, is the resulting set contained in the projection to $\overline{x}^2$? The order of components of $\overline{x}^1$ and $\overline{x}^2$ does matter.

I can imagine that there are standard procedures for answering this question. Are there efficient ones? Where do I have to look? I haven't yet found anything related in textbooks on Linear Programming, using keywords "subspace" and "sub(-)solution" -- maybe I'm using the wrong keywords?

My own attempts:

(1) Eliminate the variables outside $\overline{x}^1$ by computing suitable positive linear combinations of the lines of $A\overline{b}$. This yields a set of constraints over $\overline{x}^1$ that are implied by (*). If we do the same for $\overline{x}^2$, it just remains to check whether all latter constraints follow from the former, perhaps using the simplex algorithm, which also reveals redundancies. But this seems inefficient to me because, in the worst case, one would have to compute exponentially many linear combinations.

(2) Perhaps it is possible to formulate the above problem as a new linear program, which then can be solved using simplex? I'm still missing a more precise idea here.

Perhaps someone here can put me on the right track?

Thomas

Guest