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

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?
• Is your first question asking why $n-m$ variables are zero at a corner point, or is it asking why $n-m$ variables are zero only at a corner point?
– prubin
Apr 3, 2022 at 15:50
• I want to know why at corner points (m) variables are non-zero and rest (n-m) are zero. So I think I mean the latter. I am under the assumption that such a behavior is only seen at corner points. Sorry for the confusion. Apr 3, 2022 at 16:04

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.
• Just so I understand this clearly, effectively what you are saying is that any corner point of a polytope is just the intersection of $n$ hyperplanes in $\mathbb{R}^n$ which have linearly independent normal vectors. The corresponding constraints to these hyperplanes are always binding. Apr 3, 2022 at 18:39
• Correct, with one qualification. There may be more than $n$ hyperplanes intersecting at the corner, $n$ of which will have independent normals. When there are extra hyperplanes (extra binding constraints) the corner is termed "degenerate".