Brouwer's Fixed Point Theorem
Here, I introduce proof of the Brouwer's fixed point theorem using a Sperner's lemma.
For the proof method of the Brouwer's fixed point thorem, I think that it is the simplest method.
First, I explain n simplex for poof of Sperner's lemma.
There are vertices of the n+1 unit (a0,a₁,a₂,..an) and there is not the thing that all these vertices are included in
n-1-dimensional subspace of R.ⁿ (a0-ai|i=1~n) is linearly independent.
Then,(λ0a0+λ1a1+λ2a2+...+λnan|λ0+λ1+λ2+.. .+λn=1 λi≥0) is called n simplex.
For example, the vertex is 0 simplex and the line segment is 1 simplex.
When, 1 simplex consists of two vertices a0,a1 and has the following property.
(λ0a0+λ0a1 |λ0+λ1=1 λi≥0).
2 simplex consists of three vertices a0,a1,a2 and has the following property.
(λ0a0+λ1a1+λ2a2|λ0+λ1+λ2=1 λi≥0).
Barycentric subdivision
Barycentric subdivision of 1 simplex subdivide the line segment into two line segments by new vertex on the
midway point of line segment.
The chart below shows the barycentric subdivision of 1 simplex.
Line segment a0a1 was divided into two line segments a0a2,a2a1 by vertex a2, having been added to midway
point of the line segment a0a1.
Furthermore, it is divided like the chart below to four 1 simplex by barycentric subdivision.
The chart below shows the barycentric subdivision of 2 simplex.
Triangle (a0,a1,a2) was divided into six triangles (a0,a3,a6) (a0,a4,a6) (a1,a3,a6) (a1,a5,a6) (a2,a4,a6) (a2,a5,a6).
The following is description of barycentric subdivision of n simplex.
Step 1
New vertex a2.1is formed by this calculation.
Step 2 We choose set of n vertices among set of n+1 vertices(a1.1,a1.2,a1.3-----a1.n,a1.n+1).
It is clear that there are n+1 choices. Here we choose all vertics except a1.n+1 an example.
New vertex a2.2 is formed by this calculation.
Step 3 We choose set of n-1 vertices among set of n vertices(a1.1,a1.2,a1.3------a1.n)
It is clear that there are n choices. Here we choose all vertices except a1.n an example.
New vertex a2.n+3 is formed by this calculation.
↓ This operation is repeated until the amount of vertices becomes one.
・
・
・
↓
Step n+1 (a1.1)
There is n+1 step in this process, and vertices formed with this process are n+1 vertex of a new n simplex.
The total number of new simplex is (n+1)!, because all choices of vertex is (n+1)!.
Here, I explain subscripts i.j for the vertex ai.j.
i= The number of times of barycentric subdivision that formed vertex a.
j is decided according to the following rule.
Let us define order of the vertex that formed from this process.
Suppose
vertex ai+1 that was formed from set of vertices (ai.k1,ai.k2,ai.k3,......,ai.kn)
(k1~kn=natural number,k1<k2<k3<...<kn)
vertex āi+1 that was formed from set of vertices (āi.j1,āi.j2,āi.j3,......,āi.jm)
(j1~jm=natural number,j1<j2<j3<...<jm) (n≥m)
If n>m, then set of vertices (āi.j1,āi.j2,āi.j3,......,āi.jm) is rewritten in set of vertices
(āi.j1,āi.j2,āj3,...,āi.jm,āi.jm+1,āi.jm+2,...,āi.jn)(jm+1=jm+2=jm+3=.....=jn=0)
Case of in>jn, then vertex ai+1 is bigger than vertex āi+1.
Case of in<jn, then vertex ai+1 is smaller than vertex āi+1.
Case of in=jn, to make a comparison between in-1 and jn-1.
Case of in-1>jn-1, then vertex ai+1 is bigger than vertex āi+1.
Case of in-1<jn-1, then vertex ai+1 is smaller than vertex āi+1.
The similar processing is continued thereafter until two value are not same.
At this time, j= The number of vertices that are bigger than vertex ai +1.
Let σ be n simplex and let n-1 simplex that consists of a proper subset of σ be τ and let us denote this relation
by σ>τ .
If dim τ=k then τ is called an k-face.
The number of n-1 face (σ>τ) is equal to the number of ways we can choose n+1 from n points which is n.
Next, let us consider in what kind of case two n simplex has n-1 face in common.
Put S1= n simplex σ that consists of n+1 vertices (a1.1,a1.2,a1.3-----a1.n,a1.n+1).
S2= {σ|σ= n simplex of barycentric subdivision of S1}.
The new n simplex of σ∈S2 is denoted by σ2.j
If a certain n simplex σ2.j consists of set of vertices (a1.k1,a1.k2,a1.k3,......,a1.kn+1),
and vertex a2.k formed from set of vertices (a1.m1,a1.m2,a1.m3,......,a1.mn+1)
and satisfy the relation of (a1.k1,a1.k2,a1.k3,......,a1.kn+1)=(a1.m1,a1.m2,a1.m3,......,a1.mn+1) ,
then, put k=j.
Similarly,
Si={σi.j|σi.j= n simplex of barycentric subdivision of σi-1.j, all of σi-1.j∈Si-1}
The new n simplex of σ∈Si is denoted by σi.j.
If n simplex σi.j consists of set of vertices (ai-1.k1,ai-1.k2,ai-1.k3,......,ai-1.kn+1)
and vertex ai.k formed from set of vertices (ai-1.m1,ai-1.m2,ai-1.m3,......,ai-1.mn+1)
and satisfy the relation of (ai-1.k1,ai-1.k2,ai-1.k3,......,ai-1.kn+1)=(ai-1.m1,ai-1.m2,ai-1.m3,......,ai-1.mn+1),
then put k=j.
Put
Vr.j={au.k|au.k=vertex of σi.g∈Si}. r=i j=g.
The barycentric subdividion that form Vr.j is denoted by Pt.y r=t j=y.
The following is barycentric subdivision of two different n simplex σ2.i ,σ2.j.
Barycentric subdivision P2i
Step 1
New vertex a2.1is formed by this calculation.
Step 2 We choose n vertex among set of n+1 vertices(a1.1,a1.2,a1.3-----a1.n,a1.n+1).
Here we choose all vertex except a1.n+1 an example.
New vertex a2.2is formed by this calculation.
Step 3 We choose n-1 vertex among set of n vertices (a1.1,a1.2,a1.3------a1.n)
Here we choose all vertex except a1.n an example.
New vertex a2.n+3 is formed by this calculation.
↓This operation is repeated until the amount of vertex becomes one.
・
・
・
↓
Step n+1 (a1.1)
Barycentric subdivision P2j
Step 1
New vertex a2.1is formed by this calculation.
Step 2 We choose n vertex among set of n+1 vertices(a1.1,a1.2,a1.3-----a1.n,a1.n+1).
Here we choose all vertex except a1.n an example.
New vertex a2.3is formed by this calculation.
Step 3 We choose n-1 vertex among set of n vertices (a1.1,a1.2,a1.3------a1.n-1,a1.n+1)
Here we choose all vertex except a1.n+1 an example.
New vertex a2.n+3 is formed by this calculation.
↓This operation is repeated until the amount of vertex becomes one.
・
・
・
↓
Step n+1 (a1.1)
only step 2 is different between P2i and P2j, then between σ2.i and σ2.j satisfy the conditions of
V2i≠V2j V2i-a2.2=V2j-a2.3
Generally
Case of σ2i>τi τi∈a2.1 ⇒ σ2j>τi σ2i≠σ2j only certain n simplex σ2j which satisfies this relation exist.
Case of σ2i>τi τi ∉a2.1 σ2j>τi ⇒ σ2i=σ2j σ2i is only n simplex which has τi.
If satisfy the condition of σ2.i >τi σ2.j>τi σ2i≠σ2j then it follow that the only step k is defferrent between
P2.i and P2.j.(k=1~N+1)
Let us consider two simplex σ3i and σ3j.
Assums
The set of n+1 vertices of step1 of P3i is equal to V2i.
The set of n+1 vertices of step1 of P3j is equal to V2j.
V2i≠V2j V2i∋a2.2 V2j∋a2.3 V2i-a2.2=V2j-a2.3
The only step 2 is differrent between P3i and P3j.
In step2 of P3i, we choose all vertices except a2.2 from V2i.
In step2 of P3j, we choose all vertices except a2.3 from V2j.
At this time, σ3i and σ3j has common n-1 face.
If set of n vertices that we choose in step2 of P3i include a2.1 then any n-1 face
τi<σ3i satisfy the following relation.
τi=τj , τi<σ3i,τj<σ3j σ3i ≠σ3j
If set of n vertices that we choose in step2 of P3i does not include a2.1
then the number of n-1 face τi<σ3i which satisfy
following relation is n
τi=τj , τi<σ3i,τj<σ3j σ3i ≠σ3j
and only n-1 face of τi<σ3i which satisfy following relations exist.
τi=τj,τi<σ3i,τj<σ3j⇒σ3i=σ3j
Let us consider a certain n-1 face τi.
Assum
τi consints of n vertices (ai.j1,ai.j2,ai.j3,....,ai.jk-1,ai.jk+1,....,ai.jn+1)
case of k≠1
ai.jt is formed from set of vertices that we choose in step t of a certain barycentric subdivision Pij.
Vi-1.j(The set of vertices that consists of σi-1.j) =Set of n+1 vertices that form ai.j1
Now, consider barycentric subdevision ofσi-1.j to make n vertices(ai.j1,ai.j2,ai.j3,....,ai.jk-1,ai.jk+1,....,ai.jn+1).
The number of ways we can choose set of vertices in barycentric subdivesion of σi-1.j
from step 2 to step k-1 is 1.
Put
m=The set of vertices that we choose in step k-1 of barycentric subdivision of σi-1.j
=Set of vertices that form ai.jk-1
s=The set of vertices that we choose in step k of barycentric subdivision of σi-1.j
t=The set of vertices that we choose in step k+1 of barycenric subdivision of σi-1.j
=Set of vertices that form ai.jk+1
m and s and t satisfy the following relation.
m⊃s⊃t
The number of ways we can choose set of vertices in step k of barycentric subdivision
of σi-1.j which is fomula (1)
Fomula (1) can be rewitten in form of by relation of s⊃t.
When, |m|=n+1-(k-1) |s|=m-1 |t|=m-2 m-(m-2)C(m-1)-(m-2)=2
Hence the number of ways we can choose set of vertices in step k of barycentric subdivision of σi-1.j is 2.
The number of ways we can choose set of vertices in barycentric subdivision ofσi-1.j from step k+1
to step n+1 is 1.
Hence the number of n simplexσi.j that has n-1 face τi is 2
case of k=1
Put
h=The set of n vertices that consist of ai.j2
Assum
h=The set of n vertices that consists of τi. τi<σi-1.j,τi<σi-1.k, σi-1.j≠σi-1.k
The number of ways we can choose set of vertices in barycentric subdivision of σi-1.jfrom step 2 to step n+1 is 1.
The number of ways we can choose set of vertices in barycentric subdivision ofσi-1.kfrom step2 to step n+1 is 1.
Hense the number of n simplex that has n-1 face τi is 2.
It is clear that there is not the thing that a certain n-1 face τi is included
in more than three different n simplex σi.j by above discussion.
The following is property of n-1 face that is included in n simplex σi.j.
Put
g=set of n vertices that we choose in step 2 of Pij
When,if g satisfy the relation of g=set of n vertices that constitute a certain
n-1 face of τj τj<σi-1.j,τk<σi-1.k σi-1.j≠σi-1.k τj=τk
then any n-1 face τi <σij satisfy the relation of τi<σij,τk<σik σij≠σik τj=τk
If g satisfy the relation of g= set of n vertex that constitute a certain n-1 face of τj
τj<σi-1.j,τk<σi-1.k τj=τk ⇒σi-1.j=σi-1.k
then the number of n-1 face τi<σij which satisfies following relationship is n
τi<σi.j,τk<σi.k σi.j≠σi.k τi=τk
and only n-1 face τi<σij which satisfies following relations exist.
τi<σij,τk<σik τi=τk⇒σij=σik
The n simplex that satisfy following conditions is classified type 1.
g=set of n vertices that constitute a certin n-1 face of τj
τj<σi-1.j,τk<σi-1.k σi-1.j≠σi-1.k τj=τk
The n simplex that satisfy following conditions is classified type 2.
g= set of n vertices that constitute a certain n-1 face of τj
τj<σi-1.j,τk<σi-1.k τj=τk ⇒σi-1.j=σi-1.k
Let us consider the n-1 simplex that consists of set of n vertex (a1.1,a1.2,a1.3-----a1.n-1)
Put
R1=S1
R2={σ2j∈S2|set of n+1 vertex that we choose in step 2 of P2j is equal to (a1.1,a1.2,a1.3-----a1.n-1)}
Ri={σij∈Si|set of n+1 vertex that step 1 of Pij is equal to Vi-1.j,σi-1.j∈Ri-1 and
set of n vertex that we choose in step 2 of Pij= set of n vertex that constitute n-1 face of τj
τj=τk τj<σi-1.j,τk<σi-1.k ⇒σi-1.j=σi-1.k}
The following that n simplex σi.j∈Ri is type 2.
Put
ri={τi|τi<σij∈Ri ,τj=τk τj<σi.j,τk<σi.k ⇒σi.j=σi.k }
t1=n-1 face of S1 that consist of set of n vertex (a1.1,a1.2,a1.3-----a1.n-1)
ti={n-1 face τi|τi=n-1 face taht is formed from bary centric subdivision τi∈ti-1}
At this time, ri and ti satisfy the following relation
ri=ti
Sperner's lemma
We can write any vertex ai.j in the form of λ1a1.1+λ2a1.2+λ3a1.3+-----+λna1.n+λn+1a1.n+1
because vertex ai.j is a certain point in S1.
Let us consider the function that satisfy the following conditions.
A element of vertex ai.j in domain of all vertex is being paired with a element of natural number i in the range of
natural number that satisfy the relation of λi≠0 by function f.
For example.
ai.j=λ1a1.1+λ2a1.2+λ5a1.
f1(ai.j)=1,f2(ai.j)=2,f3(ai.j)=5, three function that satisfy this condition exsist.
Put
fk(σi.j)={fk(ai.j)|ai.j∈Vi.j} then reverse image g of f(σi.j)=g.f(σi.j)=σi.j that satisfy following condition
is called completly n simplex.
fk(σi.j)={i|i=natural number from 1 to n+1}.
fk(τj)={fk(ai.j)|ai.j∈set of n vertex that constitute n-1 face τj}
then reverse image g of f(τj)=g.f(τj)=τj that satisfy following condition
is called completly n-1 face.
fk(τj)={i|i=natural number from 1 to n}.
The number of completly n-1 face that any n simplex has is either of 0 or 1 of 2.
When,total number of completly n-1 face satisfy the following relation.
fomula(2)
Hense if the number of completly n-1 faceτi that is included in one simplex σi.j
is an odd number then fomula (2) is an odd number.
We can prove that the following statement by using mathematical induction.
Si has an odd number of completely n simplex.
Base case ; shown that statement hold for i=1.
The chart below shows barycentric subdivision of 1 simplex.
There are five vertices (a0,a1,a2,a3,a4) by this barycentric subdivision.
Then, vertex a0 is being paired with 1.
Let us denote this relation by a0→1.
When the following relation is satisfy
a3→1 or a3→2
a2→1 or a2→2
a4→1 or a4→2
a1→2
the set of vertices (a0,a3) →(1,1)or(a0,a3) →(1,2)
(a3,a2)→(1,1)or(a3,a2)→(1,2)or(a3,a2)→(2,1)or(a3,a2)→(2,2)
(a2,a4)→(1,1)or(a2,a4)→(1,2)or(a2,a4)→(2,1)or(a2,a4)→(2,2)
(a4,a1)→(1,2)or(a4,a1)→(2,2)
The completely 0 face as vertex ai is satisfy the condition of f(ai)=1 (i=0~4)
A vertex a0 is included in one set of vertices as (a0,a3).
The vertices a2,a3,a4 are included in two set of vertices.
Hence statement hold for i=1 by fomula(2)
Assume ti has an odd number of comletely n simplex.
(The number of completly n-1 face τi that is included in one n simplex)∈ri=ti
The value of fomula (2) is an odd number, since ri=ti holds by using the induction hypothesis.
Brower's Fixed Point Theorem
The continuous function f from n simplex S1 to S1 itself has a fixed point.
We show that this statement holds true by using reductio ad absurdum.
Let us consider following function.
We see that any point x∈Si can be written in form of x=λ1a1.1+λ2a1.2+λ3a1.3+...+λn+1a1.n+1
When, put f(x)=μ1a1.1+μ2a1.2+μ3a1.3+...+μn+1a1.n+1
t*=min{t|t∋R,((μk-λk)t+λk)=0(k=1~n+1)} i={k|k=1~n+1,((μk-λk)t*+λk)=0(k=1~n+1)}
F(x)=(1-t)x+tf(x)=((μ1-λ1)t+λ1)a1.1+((μ2-λ2)t+λ2)a1.2+((μ3-λ3)t+λ3)a1.3+・・・+((μn+1-λn+1)t+λn+1)a1.n+1
where t=t* Fomula (3)
formula (3) can be rewritten as
((μ1-λ1)t+λ1)a1+((μ2-λ2)t+λ2)a2+((μ3-λ3)t+λ3)a3+((μi-1-λi)t+λi-1)ai-1+((μi+1-λi+1)t+λi+1)ai+1+・・・+((μn-λn+1)t+λn+1)an+1
When we define the following function.
fk(ai.j)=i={k|k=1~n+1,((μk-λk)t*+λk)=0(k=1~n+1)}
We can apply the sperner's lemma to Si.
Hense f(Si) has an odd number of completely n simplex.
fk(σi.j∈Si),(σi.j is completely n simplex)={i|i=natural number from 1 to n+1}
Put
xi=1/n+1(λ1at1.k1+λ2at2.k2+λ3at3.k3+-----+λnatn.kn+λn+1atn+1.kn+1) xi∈σi.j∈Si(σi.j is completely n simplex)
It is true that any sequence in a compact metric space has a convergent
subsequence.
It follows that xi has a convergent subsequence .
Let this limit be x*=lim i→∞xi
Put.
d(x,y)=The distance between two points x,y∈σij
d(σij)=max{d(x,y)} then |ai.j-x*|≤|ai.j-xi|+|xi--x*|≤d(σij)+|xi-x*|
this fomula of right-hand side approaches as zero i→∞
At this time, since F is continues function, the relationship of |ai.j-x*|=ε ⇒ |F(ai.j)-F(x*)|=δ is satisfied.
Assume
F(x*)∈τj τj<S1,
x=λ2a1.2+λ2a1.3+-----+λ2a1.n+λ2a1.n+1 x∈τj (λ2+λ3+.. .+λn+λn+1=1 λi≥0)
We see that a point of F(x*)∈τj can be written in form of
((μ2-λ2)t+λ2)a1.2+((μ3-λ3)t+λ3)a1.3+・・・+((μn-λn+1)t+λn+1)a1.n+1 max{(μi-λi)t+λi|(i=2~n+1)}=(μ2-λ2)t+λ2
then (μ2-λ2)t+λ2 satisfy the condition of (μ2-λ2)t+λ2≥1/n+1
and a vertex ai.j ∈σij(x*∈σij)that satisfy the follwoing condition exist.
F(ai.j)=(μ1-λ1)t+λ1)a1+(μ2-λ2)t+λ2)a2+(μ3-λ3)t+λ3)a3+...+(μn-λn)t+λn)an+(μn+1-λn+1)t+λn+1)an+1((μ2-λ2)t+λ2)=0)
At this time, the condition of d(F(ai.j),F(x*) )≥1/n+1 is satisfied.