Euclidean Buildings in Combinatorial Optimization Hiroshi Hirai Department of Mathematical Informatics Graduate School of Information Science and Technology The University of Tokyo JST PRESTO [email protected] Buildings, Varieties, and Applications MPI Leipzig, Germany 12 November 2019 Contents Noncommutative Edmonds problem (nc-rank) optimization on spherical building Its weighted version (degree of determinant) optimization on Euclidean building Edmonds Problem
Edmonds 1967 Can we compute the rank of linear symbolic matrix in polynomial time ? : variables matrices over field matrix over ( 1 , 2 , , ) 3 Motivation Algebraic Interpretation of Bipartite Matching 1 1 1 2
3 4 12 32 = 23 24 41 1 2 2 3 3 ( 2 3
4 4 ) 4 =( , ; ) Lem. # maximum matching of det = min-max formula ( Knig-Egervry ) polynomial time algorithm
4 Linear matroid intersection ----- = =1 Linear matroid matching -----
= ( ) =1 min-max theorem + polynomial time algorithm Edmonds 1970, Lovsz 1981 Open Deterministic polynomial time rank computation of general Randomized polynomial time algorithm (Lovsz 1979) Connection to circuit complexity (Kabanets-Impagliazzo 2004) 5 Non-commutative Edmonds Problem Ivanyos-Qiao-Subrahmanyam 2015 ncCan we compute the rank of linear symbolic matrix in polynomial time ? : variables nc-rank rank
= holds for bipartite matching, linear matroid intersection matrices over field matrix over free ring > holds for non-bipartite matching, linear matroid matching,... Amitsur 1966 free skew field 6 What is free skew field ? skew field = ring s.t. nonzero element has inverse := all rational expressions of modulo
if p,q defined () It is much difficult to handle elements in than , but ... 7 nc-rank in P Garg-Gurvits-Oliveira-Wigderson 2015 (FOCS16): Gurvits operator scaling Ivanyos-Qiao-Subrahmanyam 2015 (ITCS17): arbitrary Wong sequence --- vector-space analogue of augmenting path Hamada-H. 2017: arbitrary but bit-size issue for Submodular optimization on the lattice of vector subspaces spherical building of type A + CAT(0)-space relaxation c.f. Submodular function on a lattice : 8
Formula of nc-rank (Fortin-Reutenauer 2004) = 0 + 1 1 + 2 2+ + generalizes min-max formula for bipartite matching, etc. - = s.t. , G L ( ) 0 Max . dim +dim
( ) This is optimization over spherical building ) s . t . ( , ( ) =0 , vector subspaces where reverse of c.f. spherical building of the order complex of Hamada-Hs approach to solve Each term & the objective function are submodular on ), orthoscheme complex (Brady-McCammond 12) ) is CAT(0) (Haettel-Kielak-Schwer 15) spherical building is CAT(1)
is geodesically convex (H.18) Minimize by splitting proximal point algorithm (Bak 14) Orthoscheme Complex (Brady-McCammond 2012) : graded poset := the geometric realization of the order complex of , where each simplex is metrized by orthoschemes 3 111 2 ( ,2) 110 1 0 000 100
Thm. [Haettel-Kielak-Schwer 15(13), Chalopin-Chepoi-H-Osajda 14] : modular lattice is CAT(0) Thm. [H.18] : modular lattice is submodular : is geodesically convex 11 Weighted Edmonds problem: Motivation capture weighted combinatorial optimization problems from (non-commutative) linear algebra Ex: Weighted bipartite matching 1 12 1 2 2 edge-weight 3 4
3 43 4 Max. s.t. perfect matching 12 Algebraic Interpretation of Weighted Matching 1 12 2 2 3 3
43 4 1 1 1 12 2 14 4 3 32 12 14 32 ()= 43 44
( 2 43 44 3 4 4
Lem. Max weight of perfect matching deg det =deg () () =max 13 ) Weighted Edmonds Problem Can we compute of in polynomial time ? : variable matrices over
matrix over Goal: develop a non-commutative version 14 Contribution of [H.18] Formulate weighted non-commutative Edmonds problem by using Dieudonn determinant Det. Establish a formula for deg Det L-convex function on Euclidean building Algorithm: minimization of the L-convex func. nc-rank computation, max degree Special case of deg det = deg Det: weighted linear matroid intersection, mixed matrix 15 How to see Matrix over (skew) polynomial ring Ore ring ---- 0
Matrix over Ore quotient ring 0 Degree: 16 How to define determinant of matrices over skew field nonsingular over (Our case:) Bruhat decomposition: LU-decomposition of matrices over skew field uni-lower-triangular uni-upper-triangular = diagonal permutation unique Dieudonn determinant
Abelianization of Det sgn ( ) 11 22 mod[ , ] commutator group Lem. 17 Weighted Non-commutative Edmonds Problem Can we compute of in polynomial time ? : variables matrices over matrix over Rem. is well-defined since is zero on commutators deg ( 1 1 =0 18 Formula for deg Det ()= 0 ()+ 1() 1++ () Thm. [H. 18]
deg Det = Min . deg det deg det Q s.t. , G L ( ( )) This is optimization over Euclidean building (Proof of ; Murota 95 for deg det) deg ( ) 0( , )deg ( ) 0 ( ) deg Det 0deg(Det Det Det) 0 deg Det + deg Det +deg Det 0 deg d et deg d et 19 deg Det =Min . deg det deg det Q
s.t. , G L ( ( )) Min . deg deg s.t. lattices in where ( ) { / ( )|deg / 0 } full-rank free -submodule in Lattice Euclidean building for = simplicial complex of lattices / The lattice of all lattices in is a uniform modular lattice Def. [H.17] A uniform modular lattice := a modular lattice s.t. is an order-preserving bijection ( )+
Digression: Lattice-theoretic characterization of Euclidean buildings & tropical linear spaces Thm. [H.17] Uniform modular lattices Euclidean buildings of type A Fact: Complemented modular lattices Spherical buildings of type A Tits,Birkhoff Thm. [H.18] Uniform semimodular lattices integer-valued valuated matroids Fact: Geometric lattices simple matroids deg Det = Min . deg deg s.t. ( , ) the lattice of lattices, inclusion order its reverse Lem. [H.18] The objective function is L-convex on uniform modular lattice
Def. [H. 17] is L-convex: Original def. [Murota] : , Algorithm for deg Det ( minimization of L-convex func.) Input: 0: Choose s.t. 1: 2: Choose s.t. with maximum 0
Optimization over the link at (= spherical building) = nc-rank computation nc-nonsingular 3: If optimal; 4: If , ( ,
) ( 1 moves on the 1-skeleton of the Euclidean building ) ; go to 1 24 Remarks Essence in combinatorial relaxation method (Murota 90) for deg det, partial optimization over apartments () Bipartite matching Hungarian method Linear matroid intersection Franks weight splitting algorithm (Furue-H 2019)
Computation of deg Det for skew polynomial matrix (Oki 2019) 25 Summary Appearances of buildings in combinatorial optimization and its algebraic generalization Submodular/discrete convex optimization on buildings Lattice-theoretic approach to buildings. Appearances of buildings (type C) in multicommodity flow problems [H. 18, Ikeda-H. 19] 26 References M.Hamada and H.Hirai: Maximum vanishing subspace problem, CAT(0)-space relaxation, and block-triangularization of partitioned matrix, arXiv H. Hirai: Uniform modular lattices and affine buildings, Adv. in Geometry H. Hirai: Uniform semimodular lattices and valuated matroids, JCTA H. Hirai: Computing the degree of determinants via discrete convex optimization over Euclidean buildings, SIAGA Papers & slides are available at http://www.misojiro.t.u-tokyo.ac.jp/~hirai/
Thank you for your attention ! 27
