# Transformations that leave the linear program unchanged

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.

• Welcome to OR.SE. Note that it is usually best to wait a few days before cross-posting to avoid duplicate answers in a short time frame. – TheSimpliFire May 25 at 15:31
• Ahh! Good to know. Also, thanks for the edits :) – pg2455 May 25 at 15:32

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.

• Thank you very much! It makes sense. D with positive coefficients is like multiplying constraints with a positive number on both sides of the equation. it leaves the region unchanged. – pg2455 Jun 4 at 9:25

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

• Ahh! Yes. I forgot to mention those matrices in the question. Are there any other matrices other than permutation matrices? – pg2455 May 26 at 10:27
• If you allow for degeneracy and redundancy, there can be arbitrary many matrices preserving the feasible region. Imagine an empty feasible region because of a single infeasible constraint, e.g. sum(x) <= -1, then all other constraints can change arbitrarily without changing the feasible region. So, I guess, the question only makes sense for a well-defined region with all constraints strictly defining a segment of its border. – mattmilten May 26 at 10:44