My math notes

More convex hull - Krein-Milman

Published by Angel on Sunday, May 16, 2010 - 04:09:04 - Filed under Convex Sets

I kinda said I was going to post more often and stuff but I’ve been ( again ) very busy with school. The semester is almost over , also I’ve been waiting for more theorems or lemmas related to the convex hull of a set.
I’ve been waiting for this theorem for a while , I didnt knew what it said but it was an intuitive idea I thought it may be inside a theorem and guess what. Here it is :).
————————
[sub]Lemma:[/sub]
Let A be a convex compact set, then each supporting hyperplane on A contains at least one extreme point of A.

[sub]Proof[/sub]

Let H be a supporting hyperplane on A, we know that so it is also compact and convex.
Then there is a point x in the intersection of the hyperplane and A such that it is an extreme point of H intersection A, then x is also an extreme point of A.

[sub]Krein-Milman Theorem[/sub]
Let E be a convex and compact set on R^n, then the convex hull of the set of extreme points of E is the set E itself.

[sub]Proof:[/sub]
Its clear that E is a subset of the convex hull of the set of all extreme points of E since the extreme points belong to E.
Now we have to see that .
Lets use induction over k the dimension of E
If k =0 then E is a single point
If K = 1 then E is a closed line segment.
Lets use as induction hypothesis that the theorem is true for k-1 with k<n.
Let x be the relative interiorof E. Then by our lemma there is a supporting hyperplane of E that contains x.
Then is compact and convex with , so by our induction hypothesis we have that x is a convex combination of the extreme points of . Since the extreme points of are extreme in E we have that :

If x is in the relative interior of E then there is a line segment that contains x that also intersects the boundary of E. Then E and the line segment can be expressed as a convex combination of extreme points of E then

Then:
.

—————————–
This is by far my favorite theorem, Ive been tryin to use it along with Radon’s theorem or directly with Caratheodory’s but I havent found anything good enough.
:)

Add a comment (213 views) - Permalink

On Blaschke’s Theorem

Published by Angel on Wednesday, April 14, 2010 - 02:32:23 - Filed under Convex Sets

I know I havent been around lately, but Ive been very busy with school and stuff and I think thats a good thing, even for the blog, I have a few more theorems I want to post, Ill try to catch up as fast as possible.
I liked this one a lot, this is again on convex sets, I was going to post Jung’s theorem but the proof I have is all on Rober Webster’s Convexity book, I havent really checked if this one is in there but as far as I know it is not.
——————
Lemma
Let be a convex and compact set, then there is a point x in S such that every chord which includes x is divided by x leaving on each side more than one third of the chord.

Proof
Let y in the boundary of S, then we define the set Sy as the points on every chord that has as a boundary the point y, and that the distance to y its less than 2 thirds of the lenght of the chord.

Let y,z,w be on the boundary of S and lets define Sw,Sz and Sy as before.

Using the triange with vertices wzy we build the medians and define x as the centroid of the triangle, now we’ll show that .
This is because
but
then
then
, using the same argument we can show that with w’,z’ and y’ the boundary of the median with vertex w,y,z and a the midpoint of yz.
Now we have that
Then using Helly’s theorem
Let bb’ be a chord that includes x0, then
Then,
This proofs our lemma.

Theorem ( Blaschke’s ) :
Every convex, compact set S with width 1 contains a circle of radius 1/3.

Proof:
By the last lemma there exists on S.
Lets show that .
Let y in the boundary of and let ww’ be a chord that includes x0, then, since the width of the set is 1, all chords have lenght greather or equal than 1.
Now , then . QED.
———-
I hope you comment, Ill try to upload about other topics, maybe some algebra or number theory.
‘Till next time :)

Add a comment (218 views) - Permalink

Gauss-Lucas Theorem

Published by Angel on Sunday, February 28, 2010 - 22:29:55 - Filed under Convex Sets

Im back with a very known theorem, I like it a lot, even if the proof is already on the Wikipedia Id like to write it here with an example because its a direct consequence of the Convex Hull post I wrote before.
———————-
Gauss-Lucas Theorem:
The roots of the derivative of a non constant complex polynomial belong to the convex hull generated by the roots of the polynomial.

Proof:
Let
Since we know that where z1,…,zn are the roots of the polynomial .

We can also write
Now:

If z is a root of the derivative, then:
This means that:

Then :

Which means:

Then:

But with this we know that z is a convex combination of all the roots, this is because :

Then by this we know that z is in the convex hull of

QED.

Example:
Proof that the diameter of the set of roots of the polynomial :
cannot be less than

Proof:
We know that :
Now we just use that:
and
Now its clear that:
.
Since the roots of the derivative are inside the convex hull generated by the roots of the original polynomial, then the diameter between them cannot be less than the diameter between the set of the roots of the second derivative of the polynomial.

—————-
The example was one of the problems on my exam. Good luck I liked this theorem and I didnt forget about it :).

Add a comment (791 views) - Permalink

Convex sets - Convex Hull

Published by Angel on Wednesday, February 17, 2010 - 07:08:41 - Filed under Notes, Convex Sets

First post is on basic convex set theory, I liked this because it was simple, demonstration was not very hard either.

The convex hull for a set A ( Im using real A a subset of ) is the minimal convex set that contains A.
We’ll now define:

Lemma:

Let with A a convex set and then

Proof:

We’ll use induction over k.
If k=1 then x*1 is in A ( we choose x that way ).
Now we’ll asume that it works for every k.
Now, let where and

We wanna see that x is in A.

Since then at least there is one , lets say its .

Let
and
.

Then we know by our induction hypothesis that y is in A .
Now, since A is a convex set and then .

This shows that x is in A.

Definition:

A point its a convex combination of points if there is such that

Theorem:

Let then c(A) ( The convex hull of the set A ) is the set of all convex combinations of all points in A.

Proof:

Let B the set of all convex combinations of points in A.
We now have to show that B=c(A) (convex hull of A )

Let x be an element of B, then with and , since A is in c(A) then , then because c(A) is convex.
This shows that .

Note that if B is a convex set then A is a subset of B,this is because if x is in A then there is a such that px will be on B. Then c(A) is a subset of B