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 (a
0,a₁,a₂,..an) and there is not the thing that all these vertices are included in
   n-1-dimensional subspace of R.ⁿ  (a
0-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 a
0,a1 and has the following property.
   
(λ0a0+λ0a1 |λ0+λ1=1 λi≥0).
   2 simplex consists of three vertices a
0,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 a
0a1.
   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 verticesa1.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 verticesa1.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.j1i.j2i.j3,......,āi.jm)
   
(j1~jm=natural number,j1<j2<j3<...<jm)                (n≥m)
    If n>m, then set of vertices (āi.j1i.j2i.j3,......,āi.jm) is rewritten in set of vertices
   (
āi.j1,āi.j2j3,...,āi.jm,āi.jm+1i.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.ji.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 σ2ii  τia2.1 ⇒ σ2ji σ2i≠σ2j   only certain n simplex σ2j which satisfies this relation exist.
    Case of σ2i>τi  τi a2.1  σ2ji ⇒ σ2i2j   σ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   V2ia2.2  V2ja2.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<σ3ij3j   σ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<σ3ij3j   σ3i ≠σ3j
    and only n-1 face of  τi<σ3i which satisfy following relations exist.
    τi=τj,τi<σ3i,τj<σ3j⇒σ3i3j 
    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.ji-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⇒σijik
    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.ji-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.ji-1.j∈Ri-1 and
   set of n vertex that we choose in step 2 of P
ij= set of n vertex that constitute n-1 face of τj
   τj=τk   τj<σ
i-1.j,τk<σi-1.k  ⇒σi-1.ji-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.ji.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,a
3,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)=((μ11)t+λ1)a1.1+((μ22)t+λ2)a1.2+((μ33)t+λ3)a1.3+・・・+((μn+1n+1)t+λn+1)a1.n+1 
      
where t=t*  Fomula (3)
         formula (3) can be rewritten as
        ((μ11)t+λ1)a1+((μ22)t+λ2)a2+((μ33)t+λ3)a3+((μi-1-λi)t+λi-1)ai-1+((μi+1i+1)t+λi+1)ai+1+・・・+((μnn+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∈Sii.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+1=1 λi≥0)
        We see that a point of F(x*)∈τj can be written in form of
        ((μ22)t+λ2)a1.2+((μ33)t+λ3)a1.3+・・・+((μnn+1)t+λn+1)a1.n+1    max{(μii)t+λi|(i=2~n+1)}=(μ22)t2  
        then (μ22)t2 satisfy the condition of (μ22)t2≥1/n+1
        and a vertex ai.j ∈σij(x*∈σij)that satisfy the follwoing condition exist.
        F(ai.j)=(μ11)t+λ1)a1+(μ22)t+λ2)a2+(μ33)t+λ3)a3+...+(μnn)t+λn)an+(μn+1n+1)t+λn+1)an+1((μ22)t+λ2)=0)
        At this time, the condition of d(F(ai.j),F(x*) )≥1/n+1 is satisfied.