Multi-Page Printing

3. Overview of the course 15 (ii) The Krein-Milman theorem states that each point of K can be written as an average of points in E(K). Symbolically: for each x ∈ K, there exists a probability measure ρx on E(K) such that x = E(K) y dρx(y). If one does not want to introduce probability measures, it is possible to state this theorem in the following simple form: for each x ∈ K, there is a sequence xn → x such that xn is a convex combination of a finite number of elements in E(K). Now, using the Krein-Milman theorem, prove the desired conclusion. (iii) Give an alternative, elementary proof when E is finite-dimensional. Hint: You may write as the limit of a family of strictly concave functions, and notice that E(K) is compact. 4. About Birkhoff’s theorem. Let Bn be the set of all bistochastic n × n matrices (recall the definition on p. 5). Note that Bn is convex and compact. The goal is to show that Bn admits exactly n! extremal points, which are the n × n permutation matrices. (i) Show that each permutation matrix is an extremal point. (ii) Show that we just need to prove the following: whenever M is an extremal point of Bn, all entries of M are either 0 or 1. (iii) Let M ∈ Bn, and assume that there is at least one entry of M, say ai0j0 , which lies in (0, 1). Construct a family of ai0j1 , ai1j1 , ai1j2 , ai2j2 , etc. of distinct entries which all lie strictly between 0 and 1, and repeat the process until jκ = j0, or iκ = i0. If the latter event arises first, then destroy ai0j0 from the list of chosen entries, so than you only keep a list with an even number of entries. Show that one can modify M by perturbing these entries, and only them, and still have a bistochastic matrix show finally that M can be written as the midpoint between two distinct elements in Bn, and therefore is not an extremal point of Bn.