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?

  • $\begingroup$ 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{}$ $\endgroup$ – Michael Hardy Aug 4 '14 at 18:47
  • $\begingroup$ @MichaelHardy I edited my post with a proof that any $n$ of the $u_k$ are independent. $\endgroup$ – Mark Aug 4 '14 at 18:56

Here is a not-so-great solution.

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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.