I have the following constrained linear system:
$$ Ax = y \\ Cx \ge b $$
where $$ y\in \mathbb{R}^3 \\ x \in \mathbb{R}^n \\ b \in \mathbb{R}^m \\ $$ Also, $n$ and $m$ are typically greater than 3, e.g. say 4 and 10 respectively.
For my specific application, the inequality constraints are always such that they create a convex polygon, in case that is of any use.
Is it possible to find a set of linear constraints on $y$, i.e. $$ Dy \ge g $$ such that the original system has solutions?
Algebraic solutions are preferred, but numerical solutions are also of interest.
So I spent some time on the problem and arrived at the following:
Assuming the 3 rows of $A$ are not linearly dependent, we can first partition the unknowns $x$ into subsets $x_1 \in \mathbb{R}^3$ and $x_2 \in \mathbb{R}^{k}$, where $k=n-3$. This leads to a corresponding partitioning of the matrices:
$$ Ax = \begin{pmatrix} A_1 & A_2 \end{pmatrix} \begin{pmatrix} x_1\\ x_2 \end{pmatrix} = y\\ Cx = \begin{pmatrix} C_1 & C_2 \end{pmatrix} \begin{pmatrix} x_1\\ x_2 \end{pmatrix} \ge b\\ $$ Furthermore, we can introduce the auxiliary variables $\lambda = x_2$, by augmenting the equality system with $k$ additional equalities, yielding $$ \begin{pmatrix} A_1 & A_2\\ 0 & \mathbb{I}_{k \times k} \end{pmatrix} \begin{pmatrix} x_1\\ x_2 \end{pmatrix} = \begin{pmatrix} y\\ \lambda \end{pmatrix} . $$ Now, the block matrix can be inverted yielding $$ \begin{pmatrix} x_1\\ x_2 \end{pmatrix} = \begin{pmatrix} A_1^{-1} & -A_1^{-1}A_2\\ 0 & \mathbb{I}_{k \times k} \end{pmatrix} \begin{pmatrix} y\\ \lambda \end{pmatrix} . $$ This can now be plugged into the system of inequalities, $$ \begin{pmatrix} C_1 & C_2 \end{pmatrix} \begin{pmatrix} x_1\\ x_2 \end{pmatrix} = \begin{pmatrix} C_1 & C_2 \end{pmatrix} \begin{pmatrix} A_1^{-1} & -A_1^{-1}A_2\\ 0 & \mathbb{I}_{k \times k} \end{pmatrix} \begin{pmatrix} y\\ \lambda \end{pmatrix} \ge b. $$ Simplifying, we get $$ \begin{pmatrix} C_1 A_1^{-1} & C_2 -C_1 A_1^{-1}A_2 \end{pmatrix} \begin{pmatrix} y\\ \lambda \end{pmatrix} \ge b\\ C_1 A_1^{-1}y +(C_2 -C_1 A_1^{-1}A_2)\lambda \ge b $$ or $$ C_1 A_1^{-1}y \ge b + (C_1 A_1^{-1}A_2 - C_2)\lambda \, . $$ These are now the sought inequalities for $y$ for which there are solutions to the original problem. However, we now have the parameters $\lambda$ left, which are allowed to take on any value as long as all the inequalities hold simultaneously for a given $y$. In other words, $y$ is a solution if there exists a $\lambda$ for which the inequalities hold.
I'm convinced it should be possible to get rid of the parametrization and just have fixed inequalities, but I haven't gotten anywhere with that yet. Any help with solving that part would be greatly appreciated.