# Doubt in proof of equivalence of basic feasible solution and vertex of a polyhedron

(Ref. page 9 of the following notes)

The problem is to prove that if $U \in \mathbb{R}^n$ is the feasible region of a linear program, then $x \in U$ is a basic feasible solution iff it's a vertex. Initial steps in the proof:

Suppose $x$ is a basic feasible solution and also that $x$ is a convex combination of $y$ and $z$, both in $U$. Let $C$ be a matrix whose rows are $n$ linearly independent active constraints at $x$, and $c$ be the vector of corresponding constraint values. Because $C$ has linearly independent rows, it has full rank and is invertible. Also $Cy \leq c, Cz \leq c$ and $Cx = c$ ...

$Cx = c$ is obviously correct by definition, but why are the other two inequalities valid: $Cy \leq c, Cz \leq c$ ? How is $C$ related in any way to $U$? If the feasible region is characterized by a polyhedron $\mathcal{P} = \{x \in \mathbb{R}^n\ |\ Ax \leq b\}$, then it's understandable to say that $Ay \leq b, Az \leq b$, since $y,z \in U$.

$C$ is solely defined as the matrix of linearly independent constraints active at $x$ and I don't see why it has anything to do with the feasible region.

• Since $y$ is in the feasible region, $Ay \leq b$. Then the inequality $Cy \leq c$ follows since $C$ and $c$ are defined by just selecting a subset of the rows from $A$ and $b$. – Joppy Mar 27 '18 at 13:07
• @Joppy: But by definition, $C$ necessarily has $n$ independent rows. And $A$ might have $m \leq n$ rows (in case there are $m \leq n$ constraints). Or probably I'm misunderstanding. – Shirish Kulhari Mar 27 '18 at 13:16
• It shouldn't matter whether the rows are independent or not, the fact is that you're just selecting a subset of the rows out of the inequality $Ay \leq b$. Also note that if $x$ is a basic feasible solution, then by definition of basic there are $n$ independent constraints which are tight at $x$, and so the matrix $A$ must have at least $n$ rows. – Joppy Mar 27 '18 at 13:24
• @Joppy: In other words, if there are $m < n$ constraints on the linear program, i.e. $m$ rows in $A$, no basic feasible solution exists? – Shirish Kulhari Mar 27 '18 at 13:29
• Think about the space $\mathbb{R^3}$, and impose two linear constraints. There are no vertices of this polytope. – Joppy Mar 27 '18 at 13:32

Let $I := \lbrace i \vert A_{i \cdot} x = b_i \rbrace$ be the set of indices corresponding to the active constraints at $x$. Then $C$ is can be defined by $C := A_{I \cdot}$ and $c = b_I$ . Since $y$ is feasible we have $Cy = A_{I \cdot}y \leq b_I = c$ and similarly for $z$.
In your case the rows should be linearly independent and this is done by selecting an appropriate subset of $I$. In any case the constraints in $C$ are chosen from the constraints in $A$ and the above still holds.