A combinatorial algorithm for computing the entire sequence of the maximum degree of minors of a generic partitioned polynomial matrix with $$2 \times 2$$ submatrices | Mathematical Programming Skip to main content
Springer Nature Link
Log in

A combinatorial algorithm for computing the entire sequence of the maximum degree of minors of a generic partitioned polynomial matrix with \(2 \times 2\) submatrices

  • Full Length Paper
  • Series A
  • Published:
Mathematical Programming Submit manuscript

Abstract

In this paper, we consider the problem of computing the entire sequence of the maximum degree of minors 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 \(\textbf{F}\), \(x_{\alpha \beta }\) is an indeterminate, and \(d_{\alpha \beta }\) is an integer for \(\alpha = 1,2,\dots , \mu \) and \(\beta = 1,2,\dots ,\nu \), and t is an additional indeterminate. This problem can be viewed as an algebraic generalization of the maximum weight bipartite matching problem. The main result of this paper is a combinatorial -time algorithm for computing the entire sequence of the maximum degree of minors of a \((2 \times 2)\)-type generic partitioned polynomial matrix of size \(2\mu \times 2\nu \). We also present a minimax theorem, which can be used as a good characterization (NP \(\cap \) co-NP characterization) for the computation of the maximum degree of minors of order k. Our results generalize the classical primal-dual algorithm (the Hungarian method) and minimax formula (Egerváry’s theorem) for the maximum weight bipartite matching problem.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
¥17,985 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price includes VAT (Japan)

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2
Fig. 3
Fig. 4
Fig. 5
Fig. 6
Fig. 7
Fig. 8

Similar content being viewed by others

Notes

  1. The original definition of weighted Edmonds’ problem is the computation of \(\deg \det A(t)\) of a square matrix A(t) of the form (1.2). Using the valuated-bimatroid property, the problem in our definition is polynomially equivalent to the original problem; see e.g., [33, Section 5.2.5].

References

  1. Améndola, C., Kohn, K., Reichenbach, P., Seigal, A.: Invariant theory and scaling algorithms for maximum likelihood estimation. SIAM J. Appl. Algebra Geom. 5(2), 304–337 (2021)

    Article  MathSciNet  MATH  Google Scholar 

  2. Camerini, P.M., Galbiati, G., Maffioli, F.: Random pseudo-polynomial algorithms for exact matroid problems. J. Algorithms 13, 258–273 (1992)

    Article  MathSciNet  MATH  Google Scholar 

  3. Cohn, P.M.: Skew Fields: Theory of General Division Rings. Cambridge University Press (1995)

  4. Dieudonné, J.: Les déterminants sur un corps non commutatif. Bull. Soc. Math. France 71, 27–45 (1943)

    Article  MathSciNet  MATH  Google Scholar 

  5. Dutilleul, P.: The MLE algorithm for the matrix normal distribution. J. Stat. Comput. Simul. 64(2), 105–123 (1999)

    Article  MATH  Google Scholar 

  6. Edmonds, J.: Systems of distinct representatives and linear algebra. J. Res. Natl. Bur. Stand. 71B(4), 241–245 (1967)

    Article  MathSciNet  MATH  Google Scholar 

  7. Egerváry, J.: Matrixok kombinatorius tulajdonságairól. Matematikai és Fizikai Lapok, 16–28 (1931)

  8. Fortin, M., Reutenauer, C.: Commutative/noncommutative rank of linear matrices and subspaces of matrices of low rank. Sém. Lothar. Combin. 52, B52f (2004)

    MathSciNet  MATH  Google Scholar 

  9. Frank, A., Tardos, É.: An application of simultaneous Diophantine approximation in combinatorial optimization. Combinatorica 7, 49–65 (1987)

    Article  MathSciNet  MATH  Google Scholar 

  10. Garg, A., Gurvits, L., Oliveira, R., Wigderson, A.: Operator scaling: theory and applications. Found. Comput. Math. 20, 223–290 (2020)

    Article  MathSciNet  MATH  Google Scholar 

  11. Gurvits, L.: Classical complexity and quantum entanglement. J. Comput. Syst. Sci. 69, 448–484 (2004)

    Article  MathSciNet  MATH  Google Scholar 

  12. Hamada, M., Hirai, H.: Maximum vanishing subspace problem, CAT(0)-space relaxation, and block-triangularization of partitioned matrix. arXiv:1705.02060 (2017)

  13. Hamada, M., Hirai, H.: Computing the nc-rank via discrete convex optimization on CAT(0) spaces. SIAM J. Appl. Algebra Geom. 5(3), 455–478 (2021)

    Article  MathSciNet  MATH  Google Scholar 

  14. Hirai, H.: Computing the degree of determinants via discrete convex optimization on Euclidean buildings. SIAM J. Appl. Algebra Geom. 3(3), 523–557 (2019)

    Article  MathSciNet  MATH  Google Scholar 

  15. Hirai, H., Ikeda, M.: A cost-scaling algorithm for computing the degree of determinants. Comput. Complex., 31:Article 10 (2022)

  16. Hirai, H., Iwamasa, Y.: A combinatorial algorithm for computing the rank of a generic partitioned matrix with \(2 \times 2\) submatrices. Math. Program. Ser. A 195, 1–37 (2022)

    Article  MathSciNet  MATH  Google Scholar 

  17. Ito, H., Iwata, S., Murota, K.: Block-triangularizations of partitioned matrices under similarity/equivalence transformations. SIAM J. Matrix Anal. Appl. 15(4), 1226–1255 (1994)

    Article  MathSciNet  MATH  Google Scholar 

  18. Ivanyos, G., Qiao, Y., Subrahmanyam, K.V.: Non-commutative Edmonds’ problem and matrix semi-invariants. Comput. Complex. 26, 717–763 (2017)

    Article  MathSciNet  MATH  Google Scholar 

  19. Ivanyos, G., Qiao, Y., Subrahmanyam, K.V.: Constructive non-commutative rank computation is in deterministic polynomial time. Comput. Complex. 27, 561–593 (2018)

    Article  MathSciNet  MATH  Google Scholar 

  20. Iwamasa, Y.: A combinatorial algorithm for computing the degree of the determinant of a generic partitioned polynomial matrix with \(2 \times 2\) submatrices. In: Proceedings of the 22nd Conference on Integer Programming and Combinatorial Optimization (IPCO 2021), volume 12707 of LNCS, pp. 119–133 (2021)

  21. Iwata, S.: Computing the maximum degree of minors in matrix pencils via combinatorial relaxation. Algorithmica 36, 331–341 (2013)

    Article  MathSciNet  MATH  Google Scholar 

  22. Iwata, S., Kobayashi, Y.: A weighted linear matroid parity algorithm. SIAM J. Comput. 51(2):STOC17–238–STOC17–280 (2022)

  23. 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)

    Article  MathSciNet  MATH  Google Scholar 

  24. Iwata, S., Murota, K., Sakuta, I.: Primal–dual combinatorial relaxation algorithms for the maximum degree of subdeterminants. SIAM J. Sci. Comput. 17(4), 993–1012 (1996)

    Article  MathSciNet  MATH  Google Scholar 

  25. Iwata, S., Takamatsu, M.: Computing the maximum degree of minors in mixed polynomial matrices via combinatorial relaxation. Algorithmica 66, 346–368 (2013)

    Article  MathSciNet  MATH  Google Scholar 

  26. Kabanets, V., Impagliazzo, R.: Derandomizing polynomial identity tests means proving circuit lower bounds. Comput. Complex. 13, 1–46 (2004)

    Article  MathSciNet  MATH  Google Scholar 

  27. Kuhn, H.W.: The Hungarian method for assignment problems. Nav. Res. Logist. Q. 2, 83–97 (1955)

    Article  MathSciNet  MATH  Google Scholar 

  28. Kunkel, P., Mehrmann, V.: Differential-Algebraic Equations: Analysis and Numerical Solution. European Mathematical Society, Zürich (2006)

    Book  MATH  Google Scholar 

  29. Lovász, L.: On determinants, matchings, and random algorithms. In: International Symposium on Fundamentals of Computation Theory (FCT’79) (1979)

  30. Lovász, L.: Singular spaces of matrices and their application in combinatorics. Bol. Soc. Brasil. Mat. 20(1), 87–99 (1989)

    Article  MathSciNet  MATH  Google Scholar 

  31. Lu, N., Zimmerman, D.L.: The likelihood ratio test for a separable covariance matrix. Stat. Probab. Lett. 73, 449–457 (2005)

    Article  MathSciNet  MATH  Google Scholar 

  32. Murota, K.: Combinatorial relaxation algorithm for the maximum degree of subdeterminants: computing Smith–McMillan form at infinity and structural indices in Kronecker form. Appl. Algebra Eng. Commun. Comput. 6, 251–273 (1995)

    Article  MathSciNet  MATH  Google Scholar 

  33. Murota, K.: Matrices and Matroids for Systems Analysis. Springer, Heidelberg (2000)

    MATH  Google Scholar 

  34. Oki, T.: Computing valuations of the Dieudonné determinants. J. Symb. Comput. 116, 284–323 (2023)

    Article  MathSciNet  MATH  Google Scholar 

  35. Sato, S.: Combinatorial relaxation algorithm for the entire sequence of the maximum degree of minors in mixed polynomial matrices. JSIAM Lett. 7, 49–52 (2015)

    Article  MathSciNet  MATH  Google Scholar 

  36. Sato, S.: Combinatorial relaxation algorithm for the entire sequence of the maximum degree of minors. Algorithmica 77, 815–835 (2017)

    Article  MathSciNet  MATH  Google Scholar 

  37. Schrijver, A.: Combinatorial Optimization: Polyhedra and Efficiency. Springer, Heidelberg (2003)

    MATH  Google Scholar 

  38. Schwartz, J.T.: Fast probabilistic algorithms for verification of polynomial identities. J. ACM 27(4), 701–717 (1980)

    Article  MathSciNet  MATH  Google Scholar 

  39. Tutte, W.T.: The factorization of linear graphs. J. Lond. Math. Soc. 22(2), 107–111 (1947)

    Article  MathSciNet  MATH  Google Scholar 

  40. Verghese, G.C., Kailath, T.: Rational matrix structure. IEEE Trans. Autom. Control AC 26(2):434–439 (1981)

Download references

Acknowledgements

The author thanks Hiroshi Hirai and the anonymous reviewers for careful reading and helpful comments. This work was supported by JSPS KAKENHI Grant Numbers JP17K00029, JP20K23323, JP20H05795, JP22K17854, Japan.

Author information

Authors and Affiliations

  1. Department of Communications and Computer Engineering, Graduate School of Informatics, Kyoto University, Kyoto, 606-8501, Japan

    Yuni Iwamasa

Authors
  1. Yuni Iwamasa
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Yuni Iwamasa.

Additional information

Publisher's Note

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

A preliminary version of this paper [20] has appeared in the proceedings of the 22nd Conference on Integer Programming and Combinatorial Optimization (IPCO 2021).

Rights and permissions

Springer Nature or its licensor (e.g. a society or other partner) holds exclusive rights to this article under a publishing agreement with the author(s) or other rightsholder(s); author self-archiving of the accepted manuscript version of this article is solely governed by the terms of such publishing agreement and applicable law.

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Iwamasa, Y. A combinatorial algorithm for computing the entire sequence of the maximum degree of minors of a generic partitioned polynomial matrix with \(2 \times 2\) submatrices. Math. Program. 204, 27–79 (2024). https://doi.org/10.1007/s10107-023-01949-1

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10107-023-01949-1

Keywords

Mathematics Subject Classification

Search

Navigation