4
$\begingroup$

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.

1 Answers 1

1

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$.