Intersection of two sets

Question

Let $E\subset{\mathbb R}^n$ be a set of the type $I_1\times \dots \times I_n$, where $I_k$ are real intervals, and $X$ be and $n\times p$ real matrix. Suppose also that $rank(X)=p$ and $n>p$. Is there a quick way for checking whether the intersection between $E$ and the space generated by the columns of $X$ is empty or not?

Answer 1

First of all we have to complete the set of $p$ vectors defined by the columns of $X$ in order to obtain $n$ columns. This can easily be accomplished by taking a standard basis vector $e_1$ and add it as a new column of $X$, if this doesn't augment the rank of $X$ then throw it away and try $e_2$. Continue this until you get a matrix $M$ of rank $n$ that can serve as a basis. Now consider the vectors that define the vertices of your set (there are $2^n$ of them) and convert the coefficients of these to the new base formed by the columns of $M$. Each vector (column) of $M$ defines a hyperplane (a linear space of dimension $n-1$). The $k$-th vector defines the hyperplane with equation $x_k=0$, so the hyperplane slices the set in two parts iff one vertex has another sign than any other vertex. Continue this for the first $p$ hyperplanes and for all the sets of two distinct vertices until you either find that they all lie on the same of the hyperplanes in wich case the intersection is empty, or you find a first case when two vertices are on different sides of the hyperplane and the intersection is nonempty. In fact you dont even have to check all couples of vertices but only those that are adjacent.