# Prove vertices of a simplex are affinely independent

I'm given that the definition of a simplex $T$ is $x \in\mathbb R^n$ such that $x$ satisfies $n+1$ linear inequalities: $(u_k, x) \lt c_k$ for $k = 1,\ldots,n+1$ (i.e. $T$ is the intersection of $n+1$ half spaces)

If we additionally impose the condition that $T$ must be bounded and nonempty, I was able to show that the $k^\text{th}$ vertex of $T$ can be defined $v_k$ as the unique solution to the system $(v_k,u_j)=c_j$ for all $j \ne k$

The existence of such a solution comes from the fact that any size $n$ subset of the $u_k$ are independent. Or else we could write $u_k$'s out as rows of a matrix and pick an arbitrarily large vector l in the nullspace. Adding that on to any existing $x \in T$ would show $T$ is unbounded since $x+l \in T$ since the inequalities $(u_k, x) \lt c_k \iff (u_k, x+l) \lt c_k$.

It's intuitive to me that $v_k$'s must be affinely independent. It's also intuitive that the closure of $T$ should be the convex hull of all the $v_k$. In fact, I think either fact implies the other. But I'm unable to prove either of them. I was, however, able to prove that the convex hull of $v_k \subset T$.

Is there a simple proof that the $v_k$ are affinely independent?

• Is it given that $u_1,\ldots,u_{n+1}$ are affinely independent? Or maybe that any $n$ of them are linearly independent? Or something like that? Could that be used? ${}\qquad{}$ – Michael Hardy Aug 4 '14 at 18:47
• @MichaelHardy I edited my post with a proof that any $n$ of the $u_k$ are independent. – Mark Aug 4 '14 at 18:56

The closure of $T$ is $x$ s.t. $(u_k,x)\le c_k$, which is a convex polytope. Define an extreme point of a set to be a point which cannot be written as an intermediate point on a line segment between two other distinct points in the set.
It can be demonstrated that all the $v_k$ lie in the closure of $T$. I will now argue that $v_k$ are the extreme points of closure $T$, and hence closure $T$ is the convex hull of $v_k$.
Suppose $t$ is an extreme point which satisfies $C$ of the constraints $(u_k, t) = c_k$ where $C \lt n$. Another way of saying this is $U t = c$ where $U$ is the matrix with rows $u_k$ and $c$ is the column vector with entries $c_k$. Since $U$ is $C \times n$ dimensional, it has only rank $C$ and therefore it has nonempty kernel. Then we may perturb $t$ by adding a small kernel element and remain inside closure $T$ which contradicts $t$ being an extreme point.
So the only possible extreme points are points which satisfy $n$ constraints. So the $v_k$ are the only possible extreme points. Now I check that $v_k$ are in fact extreme points. Suppose that we have a $v_k$ which is strictly interior to a line segment $[a, b]$ with $a$ and $b$ in closure $T$. Then $a$ and $b$ must satisfy the same $n$ constraints as $v_k$ or else by convexity, the line between them would not satisfy $n$ constraints. But then $v_k$ would equal $a$ and $b$. So then $v_k$ are exactly the extreme points.
A theorem of Linear Programming then tells us that the closure of $T$ is the convex hull of the $v_k$. If the $v_k$ were not affine independent, the closure of $T$ would have measure 0, which is a contradiction since $T$ is non-empty and open.