Is it necessary that $A$ be a thick matrix (m < n) for standard form of Linear programming matrix $Ax = b$?

40 Views Asked by At

While looking at the derivation of Linear optimization, I see that it starts by considering standard form; $$min(c^T x)$$ $$Ax = b ; \qquad x \ge 0 \qquad b \ge 0$$ Then, it proceeds saying $Without\ Loss\ of\ generality\ rank(A) = m < n $, where, $A$ can be represented as $$ [ B\ N ]\ [x_b\ x_n]^T = b $$ $B = m\ x\ m$ and $ N = m\ x\ (n-m)$. Then we consider $B^{-1}$ and so on to proceed towards Simplex Algorithm.

I wanted to know how do we exclude the fact that $A$ can have $m >n $. Or is it possible to convert it back to standard form?

Also, why is it necessary that $A$ has rank $m$?

EDIT: $m$ is number of rows and $n$ is number of columns.

1

There are 1 best solutions below

1
On BEST ANSWER

I assume $x \in \mathbb{R}^n$ and $b \in \mathbb{R}^k$ (and therefore $A \in \mathbb{R}^{k \times n}$).

If $A$ has rank $n$ (and therefore $k\geq n$), there is only one point $x$, that satisfies the linear constraints. It comes down to solving a linear system of equation, which is hardly worthy to be called optimization.

It is impossible to have $rank(A) >n$, since $A$ has a maximum of $n$ collumns.

The only option, that leaves us with an optimization procedure is $rank(A)<n$. You just choose your $m$ accordingly.