How can the equation $Ax=b$ represent a polyhedron?

762 Views Asked by At

I can understand how inequalities can be used to define a polyhedron, for example, each plane in a 3d setting would be one face and putting all the planes together we would get a closed body with the points in the inner volume satisfying all the inequalities.

But when it comes to equations I cannot understand how you can replicate the above behaviour. The intersection of inequalities would give me a volume, but intersection of two equations of planes would give me a line or a point.

Most texts seem to have a standard form for polyhedrons using equations like $Ax = b$ with $x\geq 0$.

1

There are 1 best solutions below

0
On

This seems to more appropriately be called the standard form of a linear program, not the standard form of a polyhedron. I did find one website calling it the standard form of a polyhedron, but there are reasons to reject this as error.

In particular, suppose you are analyzing a linear program with domain in the polyhedron $P_0 = \{x \in \mathbb{R}^k \mid Ax \leq b\}$ with $b \in \mathbb{R}^n.$ In particular, this means $$a_{1,1}x_1 + a_{1,2}x_2 + \cdots + a_{1,k}x_k \leq b_1 \\ a_{2,1}x_1 + a_{2,2}x_2 + \cdots + a_{2,k}x_k \leq b_2 \\ \vdots \\ a_{n,1}x_1 + a_{n,2}x_2 + \cdots + a_{n,k}x_k \leq b_n$$ By writing each $x_i = x_i^+ - x_i^-$ where $x_i^+, x_i^- \geq 0$ and introducing $n$ new variables $y_1,y_2,\ldots,y_n \geq 0$ we can write this same system of inequalities as an equivalent system of equalities: $$a_{1,1}x_1^+ - a_{1,1}x_1^- + a_{1,2}x_2^+ - a_{1,2}x_2^- + \cdots + a_{1,k}x_k^+-a_{1,k}x_k^- + y_1 = b_1 \\ a_{2,1}x_1^+-a_{2,1}x_1^- + a_{2,2}x_2^+-a_{2,2}x_2^- + \cdots + a_{2,k}x_k^+-a_{2,k}x_k^- + y_2 = b_2 \\ \vdots \\ a_{n,1}x_1^+-a_{n,1}x_1^- + a_{n,2}x_2^+-a_{n,2}x_2^- + \cdots + a_{n,k}x_k^+-a_{n,k}x_k^- +y_n = b_n$$

In other words, this takes a polyhedral domain $P_0 = \{x \in \mathbb{R}^k \mid Ax\leq b\}$ for a linear program and translates it to a polyhedral domain $P_1 = \{x \in \mathbb{R}^{2k+n} \mid A_1x = b, x \geq \mathbf{0}\}$ for an equivalent linear program.