Show that $S=\{\mathbf x \in \mathbb R^n:\mathbf A \mathbf x=\mathbf b,\mathbf x \ge \mathbf 0\} \ne \emptyset$ has at least one extreme point Show that the standard polyhedron defined by $S=\{\mathbf x \in \mathbb R^n:\mathbf A \mathbf x=\mathbf b,\mathbf x \ge \mathbf 0\} \ne \emptyset $ has at least one extreme point and the set of its extreme points is a finite set.

I know that we need to find $\mathbf x \in S$ such that $$\forall \mathbf A,\mathbf B \in S, \forall \lambda \in (0,1):\mathbf x= \lambda \mathbf A+(1-\lambda)\mathbf B \implies \mathbf A=\mathbf B$$
And that shows that the set has at least one extreme point, I can find such $\mathbf x$ but unfortunately it depends on $\mathbf A$ and so it does not work for arbitrary $\mathbf A,\mathbf B \in S$.
I've seen the theorem in many sources, but could not find any proof of that.
 A: Here's another approach, which is less quantitative and more geometric/combinatorial.
We can write $S = \{x^T : x(A^T,I) \leq (\mathbf{1},\mathbf{0})\}$ by adding the $d$ constraints $x_i \geqslant 0$ and normalizing the rows of $A$ by their inner product with $x$.
We prove this by induction on the number of rows of the constraint matrix. Consider $A$ a $(n+1) \times d$ matrix, and let $A'$ be $A$ without the first row. By induction, $S' = \{x^T : x((A')^T, I) \leqslant (\mathbf{1},\mathbf{0})\}$ has a finite nonempty set of extreme points, say of size $N$.
An extreme point of a polyhedron is found at the intersection of $d$ constraints, so $S$ has at most $N + {n \choose d}$ extreme points. Moreover, the set of extreme points of $S$ is nonempty, as there is some extreme point of $S$ which is in the (nonempty!) extreme point set of $S''$, where $S''$ removes a different constraint from $S$ than $S'$. Induction completes the proof.
A: We prove the result in two steps. First, we show that if the column vectors of $A$ associated with positive elements of $x$ are linearly independent, $x$ is an extreme point. Second, we use this result to show that there exists an extreme point.
Let $x=(x_1,\ldots,x_r,0,\ldots,0)$ with $x_i>0$ and let $a^1,\ldots,a^r$ be the corresponding column vectors of $A$ Assume that $a^1,\ldots,a^r$ are linearly independent. We show that $x$ is an extreme point.
Case 1: $r=0$. In this case $x=0$. Let $y,z\in S$ and $0=x=\lambda y + (1-\lambda) z$ with $\lambda \in (0,1)$. As $y,z \geq 0$, it follows directly $x=y=z=0$.
Case 2: $r>0$. It holds $\sum\limits_{i=1}^ra^ix_i=b$. Let $y,z\in S$ and $x=\lambda y + (1-\lambda) z$ with $\lambda \in (0,1)$.  As $y,z \geq 0$, it follows $y_i=z_i=0$ for $i>r$. Moreover, as $y,z \in S$ we have $Ay=Az=b$, it follows $$A(y-z)=\sum_{i=1}^r a^i(y_i-z_i)=0.$$ As $a^1,\ldots,a^r$ are linearly independent, it follows $y=z$. Thus, $x$ is an extreme point.
Now the second step. Define by $r(x)$ the number of positive entries $x_i>0$ in $x \in S$. Define $z\in S$ by $r(z)=\min\{r(x):x\in S\}$. We show that $z$ is an extreme point. If $r(z)=0$, then $z=0$. Thus, an extreme point. Assume that $r(z)>0$. We show that $a^1,\ldots, a^{r(z)}$ are linearly independent. Assume to the contrary $a^1,\ldots, a^{r(z)}$ is linearly dependent. Then there exists $d_1,\ldots,d_{r(z)}\neq 0$ such that $$\sum_{i=1}^{r(z)}a^i d_i =0.$$ Define $$\mu:=\min\{\frac{z_i}{|d_i|}:d_i\neq 0\}=\frac{z_k}{|d_k|}>0$$
for some $k$. Without loss assume $d_k>0$. Define
$$d=(d_1,\ldots,d_{r(z)},0,\ldots,0) \in \mathbb{R}^n$$ and $y=z-\mu d$. Due to $Ad=0$, it follows, $Ay=Az-\mu Ad =Az =b$. Therefore, $y\in S$. It holds, $$y_i=z_i-\frac{z_k}{d_k}d_i\geq 0$$ by definition of $\mu$. Moreover it holds, $$y_k=z_k-\frac{z_k}{d_k}d_k=0.$$ Thus, $r(y)<r(z)$, which is a contradiction. Thus, $a^1,\ldots, a^{r(z)}$ are linearly independent and $z$ an extreme point.
A: I think that I can prove the existence at least one extreme point if $A$ is a $n \times n$ matrix.
Proof:
I will do the proof by induction.
Case $n=1$:
If $A$ is not singular and $S \neq \emptyset$ then $S=\{a\}$ (consecuence of Rouche-Frobeniu´s theorem) for some $a \in \mathbb{R}$ and then $S$ has one extreme point.
If $A$ is singular then $S=\mathbb{R}^{+} \cup \{0\}$ and then $\{0\}$ is the extreme point.
Case general:n=k
If $A$ is not singular and $S \neq \emptyset$ then $S=\{a\}$ (consecuence of Rouche-Frobeniu´s theorem) for some $a \in \mathbb{R}^{n}$ and then $S$ has one extreme point.
If $A$ is singular and $S \neq \emptyset$ then we have that $S=(a+V) \cap \{x \geq 0\}$ for some $a \in \mathbb{R}^{n}$ and a subespace $V \subseteq \mathbb{R}^{n}$.
How $A$ is singular, then exists $v=(v_{1},...,v_{n}) \in V : v \neq 0$ so exists $j \in \{1,...,n\} : v_{j} \neq 0$, and we can suppose that some index is negative (doing $\cdot (-1)$).
Then rearranging if necessary we can suppose that $a=(a_{1},...,a_{n})$, $v=(v_{1},...,v_{n})$ and $v_{n} < 0$ and $\frac{|v_{n}|}{|a_{n}|} \leq \frac{|v_{j}|}{|a_{j}|} \forall j \in \{1,...,n\}$.
Then we have that $a+\frac{v_{n}}{a_{n}}v=(a_{1}+\frac{v_{1}v_{n}}{a_{n}},...,a_{n-1}+\frac{v_{n-1}v_{n}}{a_{n}},0)$ and $a_{i}+\frac{v_{i}v_{n}}{a_{n}} \geq 0$ with $i \in \{1,...,n-1\}$, so $a+\frac{v_{n}}{a_{n}}v \in S$.
But $S \subseteq \{x \geq 0\}$ so if $a+\frac{v_{n}}{a_{n}}v=\lambda c + (1-\lambda) d$ with $\lambda \in (0,1)$ and $c,d \in S$ then $c_{n}=d_{n}=0$.
So $a+\frac{v_{n}}{a_{n}}v,c,d$ are solutions of the sistem:
$$
\begin{pmatrix}
a_{11}& \cdots & a_{1n} \\
\vdots & \ddots & \vdots \\
a_{n1} & \cdots & a_{nn} \\
\end{pmatrix}
\begin{pmatrix}
x_{1} \\
\vdots \\
x_{n-1}\\
0
\end{pmatrix}
=
\begin{pmatrix}
b_{1} \\
\vdots \\
b_{n}
\end{pmatrix}
$$
and how $x_{n}=0$ we can delete the last column of our matrix and our solutions are solutions of the sistem:
$$
\begin{pmatrix}
a_{11}& \cdots & a_{1n-1} \\
\vdots & \ddots & \vdots \\
a_{n1} & \cdots & a_{nn-1} \\
\end{pmatrix}
\begin{pmatrix}
x_{1} \\
\vdots \\
x_{n-1}
\end{pmatrix}
=
\begin{pmatrix}
b_{1} \\
\vdots \\
b_{n}
\end{pmatrix}
$$
we denote
$$A'=
\begin{pmatrix}
a_{11}& \cdots & a_{1n-1} \\
\vdots & \ddots & \vdots \\
a_{n1} & \cdots & a_{nn-1} \\
\end{pmatrix},
X'=
\begin{pmatrix}
x_{1}\\
\vdots\\
x_{n-1}
\end{pmatrix},
B=
\begin{pmatrix}
b_{1}\\
\vdots\\
b_{n}
\end{pmatrix}
$$
then we have that $rg(A') \leq n-1$, and how $a+\frac{v_{n}}{a_{n}}v$ is solution of $A'X'=B$ we have that $rg(A')=rg(A'|B) \leq n-1$, so we can delete one row of $A'$ and $B$. We can suppose that we delete the $n$-row.
So our sistem is equivalent to the sistem:
$$
\begin{pmatrix}
a_{11}& \cdots & a_{1n-1} \\
\vdots & \ddots & \vdots \\
a_{n-11} & \cdots & a_{n-1n-1} \\
\end{pmatrix}
\begin{pmatrix}
x_{1} \\
\vdots \\
x_{n-1}
\end{pmatrix}
=
\begin{pmatrix}
b_{1} \\
\vdots \\
b_{n-1}
\end{pmatrix}
$$
and by induction hipotesis we have that this last sistem restricted to $\{x' \geq 0\}$ has at least one extreme point.
A: First, I prove existence of an extreme value:
Let $C$ be the set of points $\mathbf x \in \mathbb R^n$ that have norm $1$ and satisfy the equation
$$\mathbf A \mathbf x = k\mathbf b.$$
for some real number $k$.  This is closed because it is the inverse of a closed set ($\{\mathbf b\}$) under a continuous function ($\mathbf A$).  By definition, $C$ is bounded.  So, $C$ is compact.  Then, by the Extreme Value Theorem, there exists a unique $\mathbf x_0 \in C$ that maximizes $\|\mathbf x\|$.  Then the vector
$$\frac{\|\mathbf b\|\mathbf x_0}{\|\mathbf x_0\|}$$
is an extreme value of $S$.
I now show that this value is unique:
If $|S| = 1$, this is obvious.  Otherwise, $S$ contains some line.  Then $S$ has no element with maximum norm.  So, I only need to show that the minimum vector is unique.  If $\mathbf b = 0$, then $\mathbf 0$ obviously is the unique element of $S$ with minimum norm.  So, assume that $\mathbf b \ne 0$.
Suppose that $\mathbf x \in S$ and $\mathbf y \in S$ both have minimum norms.  Then $\|\mathbf x\| = \|\mathbf y\|$.  Consider the point $(\mathbf x + \mathbf y) / 2.$  This point is in $S$.  Notice that
$$\left\|\frac{\mathbf x + \mathbf y}{2}\right\|^2 = \frac14(\|\mathbf x\|^2 + \|\mathbf y\|^2 + 2\mathbf x \cdot \mathbf y) \le \frac14(\|\mathbf x\|^2 + \|\mathbf y\|^2 + 2\|\mathbf x\|\|\mathbf y\|) = \frac14(\|\mathbf x\| + \|\mathbf y\|)^2$$
by the Cauchy-Schwartz inequality.  Equality occurs only when $\mathbf x$ is a multiple of $\mathbf y$.  Taking square roots on both sides,
$$\left\|\frac{\mathbf x + \mathbf y}{2}\right\| \le \frac12(\|\mathbf x \| + \|\mathbf y\|) = \|\mathbf x\|$$
with equality only when $\mathbf x$ is a multiple of $\mathbf y$.  But we must have equality, because $\mathbf x$ has the minimum norm in all of $S$.  So, $\mathbf x = k\mathbf y$ for some $k \in \mathbb R$.  But because
$$\mathbf b = \mathbf A \mathbf x = \mathbf A (k\mathbf y) = k\mathbf A \mathbf y = k\mathbf b,$$
$k = 1$.  Thus, $\mathbf x = \mathbf y$, as desired.
A: Consider a lexicographic ordering $≺$ on $ℝ^n$, e.g. $x≺y$ if and only if $x_1 < y_1$ or $(x_1 = y_1) ∧ (x_2 < y_2)$, etc.
Claim: $z = \displaystyle\min_{≺} S$ exists, is unique and an extremal point.
Proof:

*

*existence: $z = \min_{x_n}(\min_{x_{n-1}}(… \min_{x_1}(S)))$, each of these minima exists since the set is always a convex and the objective function is bounded below.

*uniqueness: because $x⪯y$ and $y⪯x$ if and only if $x=y$.

*extremality: Assume $z = (1-λ)a + λb$ for some $a, b∈S$, $λ∈(0,1)$ then by construction $z_1 ≤ a_1, b_1$. But since $z_1 = (1-λ)a_1 + λb_1$ the only solution is $a_1 = b_1 = z_1$, etc.

