Will $m \leq n$ if you change the constraints in canonical form from equality constraints to inequality constraints?

Question

The linear programming problem in canonical form has a series of constraints of the form $Ax=b$ where $A$ is an $m\times n$ matrix with $m\leq n$ and $x\geq 0$. Does this condition $m \leq n$ still hold when there are inequality constraints instead of equality constraints? Is there an example to either prove or disprove this?

Answer 1

Broadly speaking, no. And technically that restriction doesn't need to exist for the canonical form either except to note that when $m > n$, unless $A$ has redundancy in its rows then there will not be a solution.

I'd also note that some sources (or at least Wikipedia) claim a different canonical form for LPs that does use inequalities for its constraints:

$\begin{eqnarray}\mbox{maximise } & \mathbf{c}^T \mathbf{x} \\ \mbox{subject to } & A\mathbf{x} & \leq & \mathbf{b} \\ \mbox{and } & \mathbf{x} & \geq & \mathbf{0}\end{eqnarray}$

You can transform the problem to your canonical form by introducing slack variables, e.g. by making the constraint $A \mathbf{x} + \mathbf{y} = \mathbf{b}$, with $\mathbf{y} \geq \mathbf{0}$. The two forms have the same number of constraints (if you don't count the restrictions $\mathbf{x}, \mathbf{y} \geq \mathbf{0}$), but the latter has more variables.

You can also perform a reverse transformation - if you start with the constraint $A \mathbf{x} = \mathbf{b}$, then you can write that as $\begin{bmatrix}A \\ -A\end{bmatrix}\mathbf{x} \leq \begin{bmatrix} \mathbf{b} \\ -\mathbf{b} \end{bmatrix}$ (i.e. every equality constraint is now a pair of inequalities). And with this transformation, you can see that it is possible to have more constraints than variables, although you are still restricted by $m \leq 2n$.