# Prove that the Basis Solutions of a Linear Programming Problem are the Extreme Points of the Polyhedron of Allowed Solutions

Given a system of

$$(\text{P})\ \begin{cases} Ax=b \\ x \ge 0\end{cases}$$

where $$A \in \Bbb{R}^{m \times n}, m \le n, \ \text{rank}(A) = m, b \in \Bbb{R}^m, x \in \Bbb{R}^n$$. By $$x \ge 0$$, we mean termwise, each term is nonnegative.

By definition, the Polyhedron of the Allowed Solutions are:

$$P = \{x \in \Bbb{R}^n | Ax = b, x \ge 0\}$$

This is a polyhedron since each row of matrix $$A$$ gives a restriction to the solutionspace, and cuts off a halfspace from it. And a polyhedron is by definition the intersection of halfspaces.

Def. $$\overline{x} \in P$$ is called a basis solution if $$\ \overline{x} =(x_1, \dots, x_n),\ J_+ = \{j\in \{1,\dots,n\}| x_j > 0\},\ A = [a_j]_{j \in \{1,\dots n\}}$$ are the columvectors of $$A$$, and the set of vectors $$\{a_j\}_{j \in J_+}$$ are linearly independent. (These are the columns of $$A$$ such that their indicies are exactly those indicies where $$\overline{x}$$ is positive.)

Def. $$\overline{x} \in P$$ is called the extreme point of $$P$$, if $$\ \forall x_1,x_2 \in P$$ and $$0 < \lambda < 1$$: $$\overline{x} = \lambda x_1 + (1- \lambda) x_2 \ \Rightarrow\ \overline{x} = x_1 = x_2$$ (These are the "edges" of the $$P$$ polyhedron.)

Question: Why do these two definitions match up exactly? Why is the following theorem true?

Theorem: $$\overline{x}$$ is a basis solution $$\Longleftrightarrow$$ $$\overline{x}$$ is a emtreme point of $$P$$.

I'd like to understand both directions of the proof ($$\Leftarrow, \Rightarrow$$), and haven't found anything that explains this in a great detail. Thank you in advance!