Transformations that leave the linear program unchanged

Question

A typical linear program is written as $$L_0:\min_{x \geq 0; A^\top x \leq b}c^\top x.$$ Here, $x \in \mathbb{R}^n$, $c \in \mathbb{R}^n$, $A \in \mathbb{R}^{m \times n}$, and $b \in \mathbb{R}^m$.

Now consider a matrix $M \in \mathbb{R}^{m \times m}$ which is multiplied on both sides of the inequality constraints such that the problem becomes $$L_1:\min_{x \geq 0; MA^\top x \leq Mb}c^\top x.$$

What should be the constraints on $M$ such that $L_0$ and $L_1$ have the same

1. feasible region;
2. and/or the same solutions?

The answer is somewhat clear in the case of equality - $M$ should be an invertible matrix (I might be wrong here too).

What mathematical concepts should I use to reason about the above problem?

_{Cross-posted on Math.SE.}

Answer 1

I'll try to give a geometrical approach.

You are considering a polyhedron $$ P = \{x \in \mathbb{R}^{n} \ | \ Ax \leq b \}. $$ where $b \in \mathbb{R}^{m}$ and $A \in \mathbb{R}^{n \times m}$. (I'm using $Ax$ and not $A^{T}x$ to match the dimensions in the OP).

The easy case: no degeneracy

Let's assume that

1. there is no primal degeneracy, i.e., no constraints are redundant w.r.t each other, and
2. $P$ is full-dimensional (non-empty interior)

Then, $P$ has exactly $m$ facets, with the $i$-th facet being described by the $i$-th constraint $$ \sum_{j} A_{i, j} x_{j} \leq b_{i}. $$

Now, let $M \in \mathbb{R}^{m \times m}$, and consider $$ Q = \{x \in \mathbb{R}^{n} \ | \ (MA)x \leq Mb \}. $$ Geometrically, 1. asks under which condition on $M$ we have $Q = P$.

If $Q = P$, then each facet of $P$ is a facet of $Q$, and vice-versa. Thus, for every $i$, there exists $\sigma(i)$ such that the hyperplanes $$ \sum_{j} A_{i, j} x_{j} \leq b_{i} $$ and $$ \sum_{j} (MA)_{\sigma(i), j} x_{j} \leq (M b)_{\sigma(i)} $$ are (geometrically) identical.

Since the polyhedra are non-degenerate, the $i \leftrightarrow \sigma(i)$ mapping is one-to-one, i.e., $\sigma$ is permutation, which gives you permutation matrices. Assume for simplicity that $\sigma$ is the identity. From the identity between each pair of hyperplanes, you then get that $M$ is a diagonal matrix with positive coefficients.

To conclude, we get $M = D \times S$ where $D$ is diagonal with positive coefficients and $S$ is a permutation matrix. Note that this result only holds under the above two assumptions.

The hard case: degeneracy

As it's already been pointed out, depending on the data, there may be arbitrarily many valid $M$. Essentially, any redundant constraints can be aggregated in any way you want, without changing anything to the feasible region.

If you can isolate a set of non-redundant constraints, then you might apply the above result, combined with some (positive?) combination of the redundant constraints. Obviously, there may exist multiple sets of non-redundant constraints, and you will likely see a combinatorial explosion there.

Answer 2

Permutation matrices will preserve the feasible region. Since you are not modifying the objective function, the solution will also be the same.