Why are several of the decision variables zero at the corner point of a polytope?

Question

I have the following equational Linear Program: \begin{align}\max&\quad c^T x\\\text{s.t.}&\quad Ax=b\\&\quad x\ge0\end{align}

The matrix $A$ is $m\times n$, where $m\le n$, $c\in \mathbb{R}^n, x \in \mathbb{R}^n$ and $b\in\mathbb{R}^m$. Also the rank of $A$ is $m$.

Now I understand the following :

(1) The feasible region is a convex polytope formed by the intersection of hyperplanes (constraints).

(2) At least one of the vertices of the polytope will give us the optimal solution if it exists.

• What I don't understand is why only at the corner points (basic feasible solutions) $(m)$ variables are not zero (basic) and rest $(n-m)$ variables are zero (non-basic)?

Also, let's say that we have a basic feasible solution $x_B$. Now for every $x>0 \,\,\,in\,\,\, x_B$, we build the $m \times m$ matrix $A_B$, the columns of which form linearly independent vectors. I understand that this fact allows us to calculate the inverse of $A_B$ and that is useful for calculating $x_B =A_B^{-1}b\,\,+A_B^{-1}A_Nx_N $ where $A_N$ is a $m\times(n-m)$ matrix of non-basic variables and $x_N$ is the set of non-basic variables.

• But what is the geometric significance of linear independence that is why do the corner points show such behavior?

Answer 1

Each equation constraint defines a hyperplane in $\mathbb{R}^n$, as does each lower bound ($x_i =0$). When hyperplanes intersect, the dimension of the intersection is $n$ minus the number of hyperplanes with linearly independent normal vectors. When $n=3$, the intersection of two independent planes is a line. If you intersect that with a third plane, you either get a point (if the planes have independent normals) or the same line (if the normal of the third hyperplane is a linear combination of the first two normals).

So at a corner point there are $n$ binding constraints with independent normals. Note that you have $m+n$ constraints total, not $m$, thanks to the sign restriction $x\ge 0.$ You know the equations are all binding because they are equations, which means $n-m$ of the sign restrictions are binding. So at least $n-m$ variables are 0 at the corner. The number of zeroes could actually be higher, as one or more basic variables could be zero.

The geometric significance of linear independence is that adding another hyperplane to the intersection only drops the dimension of the intersection by 1 if the normal of the new hyperplane is independent of the normals of the hyperplanes already participating in the intersection.