Algebraic combinatorial optimization on the degree of determinants of noncommutative symbolic matrices

The 26th Aussois Combinatorial Optimization Workshop (2024)

Transcript

1. Algebraic combinatorial optimization on the degree of determinants of noncommutative symbolic matrices Tasuku Soma (ISM) Joint work with Hiroshi Hirai (Nagoya) Yuni Iwamasa (Kyoto) Taihei Oki (Tokyo) 1 / 14
2. Matrix formulation of bipartite matching G = (V1 , V2 ; E): bipartite graph with |V1 | = |V2 | = n 1 2 3 1 2 3 2 / 14
3. Matrix formulation of bipartite matching G = (V1 , V2 ; E): bipartite graph with |V1 | = |V2 | = n Edmonds matrix: n × n symbolic matrix A s.t. aij = xij if ij ∈ E 0 otherwise 1 2 3 1 2 3 A =   x11 x12 x13 0 x22 x23 x31 0 x33   2 / 14
4. Matrix formulation of bipartite matching G = (V1 , V2 ; E): bipartite graph with |V1 | = |V2 | = n Edmonds matrix: n × n symbolic matrix A s.t. aij = xij if ij ∈ E 0 otherwise Then, det A = M: perfect matching ± ij∈M xij det A ̸= 0 ⇐⇒ G has a perfect matching. 1 2 3 1 2 3 A =   x11 x12 x13 0 x22 x23 x31 0 x33   det A = + x11 x22 x33 + x12 x23 x31 − x13 x22 x31 2 / 14
5. Edmonds’ problem [Edmonds, 1967] F: field Given: A = x1 A1 + · · · + xm Am (xi: indeterminate, Ai: n × n matrix over F) Compute: rank A (over F[x1 , . . . , xm ]) • If we can use randomness, it is easy! (Schwartz-Zippel lemma) Can we do deterministically? −→ polynomial identity testing • Includes linear matroid intersection, general matching, linear matroid parity, etc. [Lovász, 1989] 3 / 14
6. Various matrix formulations Linear matroid intersection ... rank-one Ai = ai b⊤ i General matching ... Tutte matrix: Ai = eu e⊤ v − ev e⊤ u for each edge uv Linear matroid parity ... rank-two skew-symmetric Ai = ai b⊤ i − bi a⊤ i 4 / 14
7. bipartite matching Edmonds matrix linear matroid intersection rank-one Ai general matching Tutte matrix linear matroid parity rank-two skew-symmetric Ai 5 / 14
8. Noncommutative Edmonds’ problem A = x1 A1 + · · · + xm Am Noncommutative rank nc-rank A = min{n − dim U + dim( i Ai U) : U subspace in Fn}. • “rank” of A where xi xj ̸= xj xi; formally defined over free skew field [Amitsur, 1966] • rank A ≤ nc-rank A ≤ 2 rank A • Optimal U is called a shrunk subspace; is dominant if dim U is minimum 6 / 14
9. Noncommutative Edmonds’ problem A = x1 A1 + · · · + xm Am Noncommutative rank nc-rank A = min{n − dim U + dim( i Ai U) : U subspace in Fn}. • “rank” of A where xi xj ̸= xj xi; formally defined over free skew field [Amitsur, 1966] • rank A ≤ nc-rank A ≤ 2 rank A • Optimal U is called a shrunk subspace; is dominant if dim U is minimum Noncommutative Edmonds’ problem Compute: nc-rank A Recent Breakthrough: Computing nc-rank of A is in P [Garg et al., 2020; Ivanyos, Qiao, and Subrahmanyam, 2018; Hamada and Hirai, 2021] 6 / 14
10. bipartite matching Edmonds matrix linear matroid intersection rank-one Ai general matching Tutte matrix linear matroid parity rank-two skew-symmetric Ai fractional matching Tutte matrix frac linear matroid parity rank-two skew-symmetric Ai rank nc-rank rank = nc-rank 7 / 14
11. Weighted Edmonds’ problem Given: A[w] = tw1 x1 A1 + · · · + twm xm Am (xi: indeterminate, Ai ∈ Fn×n, t: new indeterminate, weight wi ∈ Z) Compute: degt det A[w] 8 / 14
12. Weighted Edmonds’ problem Given: A[w] = tw1 x1 A1 + · · · + twm xm Am (xi: indeterminate, Ai ∈ Fn×n, t: new indeterminate, weight wi ∈ Z) Compute: degt det A[w] Example A: Edmonds matrix of a bipartite graph, w: edge weight det A[w] = M: perfect matching ±tw(M) ij∈M xij degt det A[w] = max M: perfect matching w(M) Maximum weight perfect matching! 8 / 14
13. Noncommutative weighted Edmonds’ problem Given: A[w] = tw1x1 A1 + · · · + twpxp Ap (xi: nc-indeterminate, Ai ∈ Fn×n, t: commutative indeterminate, weight wi ∈ Z) Compute: degt Det A[w] Here, Det is the Dieudonné determinant, an nc-version of ordinary determinant. • Known result: strongly polynomial deterministic algorithm [Hirai and Ikeda, 2022] • Caveat: not combinatorial; relies on Frank–Tardos framework (so time complexity is merely poly) 9 / 14
14. bipartite matching Edmonds matrix linear matroid intersection rank-one Ai general matching Tutte matrix linear matroid parity rank-two skew-symmetric Ai fractional matching Tutte matrix frac linear matroid parity rank-two skew-symmetric Ai det Det det = Det 10 / 14
15. Our results • Combinatorial algorithm for weighted noncommutative Edmonds’ problem without Frank–Tardos framework. • Time-complexity: O(n3NCRK), where NCRK = time complexity to find dominant shrunk subspace of n × n matrix. • Application: first poly-time membership algorithm for rank-2 Brascamp-Lieb polytope. (previous result: NP ∩ co-NP [Franks, Soma, and Goemans, 2023]) • Can be extended to compute degrees of all k × k minors: ∆k (A[w]) = max degt Det(A[w]S,T ) : S, T ∈ [n] k for k = 0, 1, . . . , n. 11 / 14
16. Min-max theorem of degDet Theorem (Hirai (2019)) degt Det A[w] = min P,Q∈GLn,α,β∈Zn i αi + βi : degt ((t−α)PAk Q(t−β))ij ≤ −wk (i, j ∈ [n], k ∈ [m]) , where (t−α) :=   t−α1 ... t−αn  . • Can recover min-max theorems for bipartite matching, linear matroid intersection, fractional matching, and fractional linear matroid parity. • Our algorithm maintains feasible P, Q, α, β. 12 / 14
17. Algorithm (at very high level) “Algebraic Hungarian method” feasible solution P, Q ∈ GLn, α, β ∈ Zn nc-rank algorithm 1. modified unweighted instance 2. optimal shrunk subspace 3. update dual • Nc-rank algorithm needs to find optimal shrunk subspace • Strongly poly-time if nc-rank alg finds the dominant shrunk subspace; possible by several (but not all) nc-rank algorithms [Ivanyos, Qiao, and Subrahmanyam, 2018; Franks, Soma, and Goemans, 2023] • Inspired by weighted fractional matroid parity algorithm by Gijswijt–Pap [Gijswijt and Pap, 2013] 13 / 14
18. Conclusion Our results • First combinatorial strongly polynomial algorithm for weighted noncommutative Edmonds’ problem • Application: first poly-time membership algorithm for rank-2 Brascamp–Lieb polytope Future direction • More applications in combinatorial optimization? 14 / 14
19. Conclusion Our results • First combinatorial strongly polynomial algorithm for weighted noncommutative Edmonds’ problem • Application: first poly-time membership algorithm for rank-2 Brascamp–Lieb polytope Future direction • More applications in combinatorial optimization? Thanks! Questions? 14 / 14
20. References I Amitsur, S. A. (1966). “Rational identities and applications to algebra and geometry”. In: Journal of Algebra 3, pp. 304–359. Barthe, F. (1998). “On a Reverse Form of the Brascamp-Lieb Inequality”. In: Inventiones Mathematicae 134.2, pp. 335–361. doi: 10.1007/s002220050267. Bennett, J., A. Carbery, M. Christ, and T. Tao (2008). “The Brascamp-Lieb inequalities: Finiteness, structure and extremals”. In: Geometric and Functional Analysis 17, pp. 1343–1415. Brascamp, H. and E. Lieb (1976). “Best constants in Young’s inequality, its converse, and its generalization to more than three functions”. In: Advances in Mathematics 20, pp. 151–173. Chang, S., D. C. Llewellyn, and J. H. Vande Vate (2001). “Two-lattice polyhedra: duality and extreme points”. In: Discrete Mathematics 237, pp. 63–95. Edmonds, J. (1967). “Systems of distinct representatives and linear algebra”. In: Journal of Research of the National Bureau of Standards 71B, pp. 241–245. Franks, C., T. Soma, and M. X. Goemans (2023). “Shrunk subspaces via operator Sinkhorn iteration”. In: Proceedings of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). SIAM, pp. 1655–1668. Garg, A., L. Gurvits, R. Oliveira, and A. Wigderson (2020). “Operator scaling: theory and applications”. In: Foundations of Computational Mathematics 20, pp. 223–290. Gijswijt, D. and G. Pap (2013). “An algorithm for weighted fractional matroid matching”. In: Journal of Combinatorial Theory, Series B 103, pp. 509–520. Hamada, M. and H. Hirai (2021). “Computing the nc-rank via discrete convex optimization on CAT(0) spaces”. In: SIAM Journal on Applied Geometry and Algebra 5, pp. 455–478. Hirai, H. (2019). “Computing the degree of determinants via discrete convex optimization on Euclidean buildings”. In: SIAM Journal on Applied Geometry and Algebra 3, pp. 523–557. 1 / 5
21. References II Hirai, H. and M. Ikeda (2022). “A cost-scaling algorithm for computing the degree of determinants”. In: Computational Complexity 31. Ivanyos, G., Y. Qiao, and K. V. Subrahmanyam (2018). “Constructive noncommutative rank computation in deterministic polynomial time over fields of arbitrary characteristics”. In: Computational Complexity 27, pp. 561–593. Lovász, L. (1989). “Singular spaces of matrices and their application in combinatorics”. In: Boletim da Sociedade Brasileira de Matemática 20, pp. 87–99. Vande Vate, J. H. (1992). “Fractional matroid matchings”. In: Journal of Combinatorial Theory, Series B 55, pp. 133–145. 2 / 5
22. Dieudonné determinant Bruhat decomposition Any square matrix A over a skew field K can be decomposed as A = LDPU where L is lower unitriangular, D diagonal, P permutation, U upper unitriangular over K. Dieudonné determinant Det A := sgn P · i dii mod [K×, K×] • Det(AB) = Det A Det B • Det A = 0 ⇐⇒ nc-rank A < n 3 / 5
23. Brascamp–Lieb Polyotope [Bennett et al., 2008] Bi: ni × n real matrix, row full-rank (i = 1, . . . , m) BLP =    x ∈ Rm : m i=1 xi dim(Bi V ) ≥ dim(V ) (V : subspace in Rn) m i=1 xi ni = n xi ≥ 0 (i = 1, . . . , m)    rank-r BL polytope △ ⇐⇒ ni = r (i = 1, . . . , m) • Characterization of optimal constant of Brascamp–Lieb inequality [Brascamp and Lieb, 1976] • rank-1 BL = base polytope of linear matroid [Barthe, 1998] • rank-2 BL = fractional linear matroid parity polytope ⊋ common base polytope of two linear matroids [Franks, Soma, and Goemans, 2023] 4 / 5
24. Frac linear matroid parity polytope [Vande Vate, 1992] Lines ℓi = span{ai , bi } ⊆ Fn (i = 1, . . . , m) FM := x ∈ Rm : m i=1 dim(ℓi ∩ V )xi ≤ dim V (V : subspace in Fn) xi ≥ 0 (i = 1, . . . , m) • Totally dual half-integrality [Vande Vate, 1992] • integral vertex of FM = parity base • For F = R, FM coincides with (down-closure of) rank-2 BL polytope [Franks, Soma, and Goemans, 2023] • Combinatorial alg for unweighted [Chang, Llewellyn, and Vande Vate, 2001] and weighted problems [Gijswijt and Pap, 2013]; polynomial-time in arithmetic model 5 / 5