Let's say I have a system of inequalities: $Ax \leq g$ for some $A \in \mathbb{R}^{4\times4}$, $x \in \mathbb{R}^4$, $g \in \mathbb{R}^4$, and $A$ is full rank. Here, the $\leq$ denotes element-wise inequality.

Specifically, I know that $x$ lies in a two-dimensional subspace of $\mathbb{R}^4$ (determined by the null space of some matrix $N$). What I'm interested in is the dimension of the solution to the above system of inequalities. More succinctly, I'm interested in the dimension of the set

$$ \left\{ x \in \mathbb{R}^4 \ \vert \ x \in {\rm Null}(N) , \ Ax \leq g\right\} $$

Understanding more about this set would be nice too, but the dimension would suffice. I'm really not sure how to approach this problem... at all. This problem arose while I was trying to analyze the set of solutions to a linear program, if you're curious.


If $A$ is an invertible matrix, $S = \{x: Ax \le g\}$ is the image of $V = \{y: y \le g\}$ under the linear transformation $A^{-1}$, and in particular is a convex cone in ${\mathbb R}^4$ with nonempty interior. If you intersect this with a two-dimensional linear subspace, the intersection will be two-dimensional if the subspace intersects the interior of $S$. However, it is also possible that the subspace only intersects the boundary of $S$, in which case the dimension could be $1$ or $0$, or that the subspace does not intersect the boundary. For example, with $A = I$ and $g = (0,0,0,0)$, your intersection would have dimension $2$ if $\text{Null}(N)$ contains a vector with all entries $>0$, but it would have dimension $1$ if $\text{Null}(N)$ is spanned by $(1,0,0,0)$ and $(0,1,-1,0)$ and dimension $0$ (consisting only of the origin) if $\text{Null}(N)$ is spanned by $(1,-1,0,0)$ and $(0,0,1,-1)$, or be empty if $g_1 < 0$ and $\text{Null}(N)$ contains only vectors $v$ with $v_1 = 0$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.