Prove vertices of a simplex are affinely independent Given that the definition of a simplex T

flightwingsd2

flightwingsd2

Answered question

2022-06-21

Prove vertices of a simplex are affinely independent
Given that the definition of a simplex T is x R n such that x satisfies n + 1 linear inequalities: ( u k , x ) < c k for k = 1 , , 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 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 kThe 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 T would show T is unbounded since x + l T since the inequalities ( u k , x ) < c k ( u k , x + l ) < 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 T.
Is there a simple proof that the vk are affinely independent?

Answer & Explanation

Blaine Foster

Blaine Foster

Beginner2022-06-22Added 33 answers

Here is a not-so-great solution.
The closure of T is x s.t. ( u k , x ) 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 < 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 × 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.
skylsn

skylsn

Beginner2022-06-23Added 4 answers

Great expert answer!

Do you have a similar question?

Recalculate according to your conditions!

Ask your question.
Get an expert answer.

Let our experts help you. Answer in as fast as 15 minutes.

Didn't find what you were looking for?