Abstract
In this paper, we consider the problem of computing the degree of the determinant of a block-structured symbolic matrix (a generic partitioned polynomial matrix) \(A = (A_{\alpha \beta } x_{\alpha \beta } t^{d_{\alpha \beta }})\), where \(A_{\alpha \beta }\) is a \(2 \times 2\) matrix over a field \(\mathbf {F}\), \(x_{\alpha \beta }\) is an indeterminate, and \(d_{\alpha \beta }\) is an integer for \(\alpha , \beta = 1,2,\dots , n\), and t is an additional indeterminate. This problem can be viewed as an algebraic generalization of the maximum perfect bipartite matching problem.
The main result of this paper is a combinatorial \(O(n^5)\)-time algorithm for the deg-det computation of a \((2 \times 2)\)-type generic partitioned polynomial matrix of size \(2n \times 2n\). We also present a min-max theorem between the degree of the determinant and a potential defined on vector spaces. Our results generalize the classical primal-dual algorithm (Hungarian method) and min-max formula (Egerváry’s theorem) for maximum weight perfect bipartite matching.
The author was supported by JSPS KAKENHI Grant Number JP17K00029, 20K23323, 20H05795, Japan.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Cohn, P.M.: Skew Fields: Theory of General Division Rings. Cambridge University Press, Cambridge (1995)
Dieudonné, J.: Les déterminants sur un corps non commutatif. Bull. de la Société Mathématique de France 71, 27–45 (1943)
Edmonds, J.: Systems of distinct representatives and linear algebra. J. Res. Natl. Bureau Stand. 71B(4), 241–245 (1967)
Egerváry, J.: Matrixok kombinatorius tulajdonságairól. In: Matematikai és Fizikai Lapok, pp. 16–28 (1931)
Frank, A., Tardos, E.: An application of simultaneous Diophantine approximation in combinatorial optimization. Combinatorica 7, 49–65 (1987)
Garg, A., Gurvits, L., Oliveira, R., Wigderson, A.: Operator scaling: theory and applications. Found. Comput. Math. 20, 223–290 (2019)
Hamada, M., Hirai, H.: Maximum vanishing subspace problem, CAT(0)-space relaxation, and block-triangularization of partitioned matrix (2017). arXiv:1705.02060
Hamada, M., Hirai, H.: Computing the nc-rank via discrete convex optimization on CAT(0) spaces (2020). arXiv:2012.13651v1
Hirai, H.: Computing the degree of determinants via discrete convex optimization on Euclidean buildings. SIAM J. Appl. Geom. Algebra 3(3), 523–557 (2019)
Hirai, H., Ikeda, M.: A cost-scaling algorithm for computing the degree of determinants (2020). arXiv:2008.11388v2
Hirai, H., Iwamasa, Y.: A combinatorial algorithm for computing the rank of a generic partitioned matrix with \(2 \times 2\) submatrices. In: Proceedings of the 21st Conference on Integer Programming and Combinatorial Optimization (IPCO 2020). LNCS, vol. 12125, pp. 196–208 (2020)
Hirai, H., Iwamasa, Y.: A combinatorial algorithm for computing the rank of a generic partitioned matrix with \(2 \times 2\) submatrices (2020). arXiv:2004.10443
Ivanyos, G., Qiao, Y., Subrahmanyam, K.V.: Non-commutative Edmonds’ problem and matrix semi-invariants. Comput. Complexity 26, 717–763 (2017)
Ivanyos, G., Qiao, Y., Subrahmanyam, K.V.: Constructive non-commutative rank computation is in deterministic polynomial time. Comput. Complexity 27, 561–593 (2018). https://doi.org/10.1007/s00037-018-0165-7
Iwata, S., Kobayashi, Y.: A weighted linear matroid parity algorithm. SIAM J. Comput. (2021)
Iwata, S., Murota, K.: A minimax theorem and a Dulmage-Mendelsohn type decomposition for a class of generic partitioned matrices. SIAM J. Matrix Anal. Appl. 16(3), 719–734 (1995)
Kabanets, V., Impagliazzo, R.: Derandomizing polynomial identity tests means proving circuit lower bounds. Comput. Complexity 13, 1–46 (2004)
Kuhn, H.W.: The Hungarian method for assignment problems. Naval Res. Logist. Q. 2, 83–97 (1955)
Lovász, L.: On determinants, matchings, and random algorithms. In: International Symposium on Fundamentals of Computation Theory (FCT 1979) (1979)
Lovász, L.: Singular spaces of matrices and their application in combinatorics. Boletim da Sociedade Brasileira de Matemática 20(1), 87–99 (1989)
Oki, T.: On solving (non)commutative weighted Edmonds’ problem. In: Proceedings of the 47th International Colloquium on Automata, Languages and Programming (ICALP’20), Leibniz International Proceedings in Informatics (LIPIcs), vol. 168, pp. 89:1–89:14 (2020)
Schwartz, J.T.: Fast probabilistic algorithms for verification of polynomial identities. J. ACM 27(4), 701–717 (1980)
Tutte, W.T.: The factorization of linear graphs. J. Lond. Math. Soc. 22(2), 107–111 (1947)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2021 Springer Nature Switzerland AG
About this paper
Cite this paper
Iwamasa, Y. (2021). A Combinatorial Algorithm for Computing the Degree of the Determinant of a Generic Partitioned Polynomial Matrix with \(2\,\times \,2\) Submatrices. In: Singh, M., Williamson, D.P. (eds) Integer Programming and Combinatorial Optimization. IPCO 2021. Lecture Notes in Computer Science(), vol 12707. Springer, Cham. https://doi.org/10.1007/978-3-030-73879-2_9
Download citation
DOI: https://doi.org/10.1007/978-3-030-73879-2_9
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-030-73878-5
Online ISBN: 978-3-030-73879-2
eBook Packages: Computer ScienceComputer Science (R0)