Theorem Proofs

Last Time: Proved Birkhoff-von Neumann Theorem: If P = {(Xij)nxn: Σxij=1, i,j=1,...,n; Σxij=1, j=1,...,n; xij≥0} The vertices are the permutation matrices. Corollary: Every doubly stochastic matrix is a convex hull of permutation matrices. Corollary (Schur Part of the Schur-Horn Theorem): The diagonal of an nxn symmetric matrix A = (aij) with eigenvalues λ₁ ≤ λ₂ ≤ ... ≤ λn lies in the convex hull P(λ) of all vectors obtained from (λ₁, λ₂, ..., λn) by permuting the coordinates. Proof: Consider A = UDU^T, where U is an orthogonal matrix, D = diag(λ₁, λ₂, ..., λn), and U^T is the transpose of U. Let Ui = (u₁i, u₂i, ..., uni)^T be the ith column of U. Then Aij = Σk=1^n UikDkjUjk = λi * Σk=1^n Uik^2 = λi Observation: U is orthogonal, so B = [U₁^T, U₂^T, ..., Un^T] is doubly stochastic. A = [U₁ U₂ ... Un] = B * [λ₁ 0 ... 0; 0 λ₂ ... 0; ...; 0 0 ... λn] By Birkhoff-von Neumann Theorem, B is a convex combination of permutation matrices. A is a convex combination of vectors obtained from (λ₁, λ₂, ..., λn) by permuting coordinates. Permutation Polytope: λ₁ ≥ λ₂ ≥ ... ≥ λn Convex Hull: P(λ) = conv({(λ₁, λ₂, ..., λn), (λ₂, λ₁, ..., λn), ..., (λn, λ₁, ..., λ₂)}) Exercise: Let us describe all faces containing (λ₁, λ₂, ..., λn). This is what they look like: λ₁ ≥ λ₂ ≥ ... ≥ λn Split the interval {1, 2, ..., n} into K subintervals. Take all possible permutations inside each interval. The convex hull of all obtained points is a face of P(λ) of codimension K - 1 where you measure codimension in the affine span {λ₁ + ξ₁n, λ₂ + ξ₂n, ..., λn + ξn}. EXERCISE (Rado's Theorem): λ₁ ≥ λ₂ ≥ ... ≥ λn The point (λ₁, λ₂, ..., λn) belongs to P(λ) if and only if: Σλi = Σμi and for any m ≤ n, Σi=1^m λi ≤ Σi=1^m μi Hint: You can deduce it from the previous exercise. EXERCISE: Prove that the entries of any extreme point of the polytope of symmetric doubly stochastic matrices (A = AT) are 0, 1/2, 1. Let Qn be the polytope of mxnxn tensors (Xijk), 1 ≤ i, j, k ≤ n. Xijk ≥ 0 Σj,k Xijk = 1, ∀i Σi,k Xijk = 1, ∀j Σi,j Xijk = 1, ∀k dim Qn = n^3 - 3n + 2 M.B. GRONOVA: For any rational 1 > σ₁ > ... > σp > 0, there is an integer b > 0 such that 1 - 1/b > σ₁ > ... > σp > 1/b AND the set of all (b - 1)/b, σ₁, ..., σp, 1/b is the set of non-zero coordinates of a vertex of Qn for some n (not counting multiplicities). TRANSPORTATION POLYHEDRA: Choose a directed graph G = (E, V) without loops. Assign to each vertex v ∈ V a real number βv. T(G, b) ⊂ ℝ^E consists of all vectors (ξe: e ∈ E) such that: ξe ≥ 0 for all e ∈ E Σ(e: h(e) = v) ξe = Σ(e: t(e) = v) ξe = βv for all v ∈ V Also called flow polytope. If βv > 0, then v is a demand in vertex v. If βv < 0, then v is a supply in vertex v. If βv = 0, then v is a transit vertex. Inflow - Outflow = βv (balance) EXAMPLE: Complete Bipartite Graph βv = -1 for v ∈ S βv = 1 for v ∈ T Get the polytope Pn of doubly stochastic matrices. THEOREM: Suppose that x = (ξe: e ∈ E) is a vertex of T(G, b). Let F = {e ∈ E: ξe > 0}. Then F does not contain cycles (directed or not). Proof: Suppose we have a cycle. Let us write x+ = x + ξ and x- = x - ξ. Choose an orientation. x+ = increase x by ξ for co-oriented edges, decrease x by ξ for counter-oriented edges. x- = increase x by ξ for counter-oriented edges, decrease x by ξ for co-oriented edges. So x is not a vertex. COROLLARY: If all βv are integer and x = (ξe: e ∈ E) is a vertex of T(G, b), then the coordinates of x are integer. Proof: Let F = {e ∈ E: ξe > 0}. Doesn't have cycles. Induction on |F|. If |F| = 0, then x = 0. Otherwise, there is a vertex v with one edge from F attached.