I have a set defined by linear inequalities of the form: $X = \{x : Ax \le b\}$.

For any $x \in X$, I write $y = Gx$ where $G$ is a matrix (the dimension of $y$ is less than the dimension of $x$).

I would like to characterize the set $Y = \{ y : \text{there exists $x \in X$ such that $y = Gx$ }\}$. Is there a way to get a clean description of $Y$ here in terms of $y$, $b$, $A$, and $G$? I know that linear transformations of the elements in a polyhedron are also a polyhedron. What I want to know are $H(A,G,b)$ and $q(A,G,b)$ in $Y = \{ y : H(A,G,b) y \leq q(A,G,b) \}$.

EDIT: I forgot to mention this: $G$ is not left invertible but it is right invertible.

Additional information: for my particular problem, $G$ and $b$ have both positive and negative elements, but $x$ and $y$ are always positive. $A$ is left invertible, but not square (which I have been able to use to get implications of $Ax \leq b$ in terms of $y$, such as: $y \leq |GA^{-1}_{\mathrm{left}}| A x \le |GA^{-1}_{\mathrm{left}}| b$).


Your Answer

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

Browse other questions tagged or ask your own question.