Document Open Access Logo

On Solving (Non)commutative Weighted Edmonds' Problem

Author Taihei Oki

PDF
Thumbnail PDF

File

LIPIcs.ICALP.2020.89.pdf
  • Filesize: 469 kB
  • 14 pages

Document Identifiers

Author Details

Taihei Oki
  • Department of Mathematical Informatics, Graduate School of Information Science and Technology, University of Tokyo, Japan

Funding

This work was supported by JST CREST Grant Number JPMJCR14D2, Japan, Grant-in-Aid for JSPS Research Fellow Grant Number JP18J22141, Japan and JST ACT-I Grant Number JPMJPR18U9, Japan.

Acknowledgements

The author thanks Satoru Iwata and Hiroshi Hirai for careful reading and helpful suggestions, and Christian Engels, Tasuku Soma, Shuichi Hirahara and Yuni Iwamasa for discussions.

Cite As Get BibTex

Taihei Oki. On Solving (Non)commutative Weighted Edmonds' Problem. In 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 168, pp. 89:1-89:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020) https://doi.org/10.4230/LIPIcs.ICALP.2020.89

Abstract

In this paper, we consider computing the degree of the Dieudonné determinant of a polynomial matrix A = A_l + A_{l-1} s + ⋯ + A₀ s^l, where each A_d is a linear symbolic matrix, i.e., entries of A_d are affine functions in symbols x₁, …, x_m over a field K. This problem is a natural "weighted analog" of Edmonds' problem, which is to compute the rank of a linear symbolic matrix. Regarding x₁, …, x_m as commutative or noncommutative, two different versions of weighted and unweighted Edmonds' problems can be considered. Deterministic polynomial-time algorithms are unknown for commutative Edmonds' problem and have been proposed recently for noncommutative Edmonds' problem.
The main contribution of this paper is to establish a deterministic polynomial-time reduction from (non)commutative weighted Edmonds' problem to unweighed Edmonds' problem. Our reduction makes use of the discrete Legendre conjugacy between the integer sequences of the maximum degree of minors of A and the rank of linear symbolic matrices obtained from the coefficient matrices of A. Combined with algorithms for noncommutative Edmonds' problem, our reduction yields the first deterministic polynomial-time algorithm for noncommutative weighted Edmonds' problem with polynomial bit-length bounds. We also give a reduction of the degree computation of quasideterminants and its application to the degree computation of noncommutative rational functions.

Subject Classification

ACM Subject Classification
  • Theory of computation → Algebraic complexity theory
  • Computing methodologies → Linear algebra algorithms
  • Computing methodologies → Combinatorial algorithms
Keywords
  • skew fields
  • Edmonds' problem
  • Dieudonné determinant
  • degree computation
  • Smith - McMillan form
  • matrix expansion
  • discrete Legendre conjugacy

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. S. A. Abramov and M. A. Barkatou. On solution spaces of products of linear differential or difference operators. ACM Communications in Computer Algebra, 48(4):155-165, 2014. URL: https://doi.org/10.1145/2733693.2733719.
  2. S. A. Amitsur. Rational identities and applications to algebra and geometry. Journal of Algebra, 3(3):304-359, 1966. Google Scholar
  3. E. Artin. Geometric Algebra. Interscience Publishers, Inc., New York, NY, 1957. URL: https://doi.org/10.1002/9781118164518.
  4. B. Beckermann, H. Cheng, and G. Labahn. Fraction-free row reduction of matrices of Ore polynomials. Journal of Symbolic Computation, 41(5):513-543, 2006. URL: https://doi.org/10.1016/j.jsc.2005.10.002.
  5. P. M. Cohn. The embedding of firs in skew fields. Proceedings of the London Mathematical Society, s3-23(2):193-213, 1971. URL: https://doi.org/10.1112/plms/s3-23.2.193.
  6. P. M. Cohn. Free Rings and Their Relations, volume 19 of London Mathematical Society Monograph. Academic Press, London, 2nd edition, 1985. Google Scholar
  7. P. M. Cohn. Algebra, volume 3. John Wiley & Sons, Chichester, 2nd edition, 1991. Google Scholar
  8. P. M. Cohn. Skew Fields. Theory of General Division Rings. Cambridge University Press, Cambridge, 1995. Google Scholar
  9. J. Dieudonné. Les déterminants sur un corps non commutatif. Bulletin de la Société Mathématique de France, 71:27-45, 1943. Google Scholar
  10. J. Edmonds. Systems of distinct representatives and linear algebra. Journal of Research of the National Bureau of Standards, 71B(4):241-245, 1967. URL: https://doi.org/10.6028/jres.071B.033.
  11. A. Garg, L. Gurvits, R. Oliveira, and A. Wigderson. Operator scaling: theory and applications. Foundations of Computational Mathematics, 20(2):223-290, 2020. URL: https://doi.org/10.1007/s10208-019-09417-z.
  12. I. Gelfand, S. Gelfand, V. Retakh, and R. Lee Wilson. Quasideterminants. Advances in Mathematics, 193(1):56-141, 2005. URL: https://doi.org/10.1016/j.aim.2004.03.018.
  13. I. M. Gel'fand and V. S. Retakh. Determinants of matrices over noncommutative rings. Functional Analysis and Its Applications, 25(2):91-102, 1991. URL: https://doi.org/10.1007/BF01079588.
  14. M. Giesbrecht and M. S. Kim. Computing the Hermite form of a matrix of Ore polynomials. Journal of Algebra, 376:341-362, 2013. URL: https://doi.org/10.1016/j.jalgebra.2012.11.033.
  15. K. R. Goodearl and R. B. Warfield, Jr. An Introduction to Noncommutative Noetherian. Cambridge University Press, Cambridge, 2nd edition, 2004. Google Scholar
  16. L. Gurvits. Classical complexity and quantum entanglement. Journal of Computer and System Sciences, 69(3):448-484, 2004. Google Scholar
  17. M. Hamada and H. Hirai. Maximum vanishing subspace problem, CAT(0)-space relaxation, and block-triangularization of partitioned matrix, 2017. URL: http://arxiv.org/abs/1705.02060.
  18. H. Hirai. Computing the degree of determinants via discrete convex optimization on Euclidean buildings. SIAM Journal on Applied Geometry and Algebra, 3(3):523-557, 2019. Google Scholar
  19. P. Hrubeš and A. Wigderson. Non-commutative arithmetic circuits with division. Theory of Computing, 11(14):357-393, 2015. URL: https://doi.org/10.4086/toc.2015.v011a014.
  20. G. Ivanyos, Y. Qiao, and K. V. Subrahmanyam. Constructive non-commutative rank computation is in deterministic polynomial time. Computational Complexity, 27(4):561-593, 2018. Google Scholar
  21. S. Iwata and R. Shimizu. Combinatorial analysis of generic matrix pencils. SIAM Journal on Matrix Analysis and Applications, 29(1):245-259, 2007. Google Scholar
  22. V. Kabanets and R. Impagliazzo. Derandomizing polynomial identity tests means proving circuit lower bounds. Computational Complexity, 13(1-2):1-46, 2004. Google Scholar
  23. M. Khochtali, J. Rosenkilde né Nielsen, and A. Storjohann. Popov form computation for matrices of Ore polynomials. In Proceedings of the 42nd International Symposium on Symbolic and Algebraic Computation (ISSAC '17), pages 253-260, New York, NY, 2017. ACM Press. URL: https://doi.org/10.1145/3087604.3087650.
  24. L. Kronecker. Grundzüge einer arithmetischen Theorie der algebraischen Grössen. Journal für die reine und angewandte Mathematik, 92:1-122, 1882. Google Scholar
  25. T. Y. Lam. Lectures on Modules and Rings, volume 189 of Graduate Texts in Mathematics. Springer, New York, NY, 1999. Google Scholar
  26. V. Levandovskyy and K. Schindelar. Computing diagonal form and Jacobson normal form of a matrix using Gröbner bases. Journal of Symbolic Computation, 46(5):595-608, 2011. URL: https://doi.org/10.1016/j.jsc.2010.10.009.
  27. L. Lovász. Singular spaces of matrices and their application in combinatorics. Boletim da Sociedade Brasileira de Matemática, 20(1):87-99, 1989. Google Scholar
  28. S. Moriyama and K. Murota. Discrete Legendre duality in polynomial matrices (in Japanese). The Japan Society for Industrial and Applied Mathematics, 23(2):183-202, 2013. Google Scholar
  29. K. Murota. Combinatorial relaxation algorithm for the maximum degree of subdeterminants: Computing Smith-McMillan form at infinity and structural indices in Kronecker form. Applicable Algebra in Engineering, Communication and Computing, 6(4-5):251-273, 1995. Google Scholar
  30. K. Murota. Computing the degree of determinants via combinatorial relaxation. SIAM Journal on Computing, 24(4):765-796, 1995. URL: https://doi.org/10.1137/S0097539791201897.
  31. K. Murota. Matrices and Matroids for Systems Analysis. Springer, Berlin Heidelberg, 2000. Google Scholar
  32. K. Murota. Discrete Convex Analysis. SIAM, Philadelphia, 2003. Google Scholar
  33. K. Murota. Legendre duality in combinatorial study of matrix pencils. Japan Journal of Industrial and Applied Mathematics, 29(2):205-236, 2012. Google Scholar
  34. J. T. Schwartz. Fast probabilistic algorithms for verification of polynomial identities. Journal of the ACM, 27(4):701-717, 1980. URL: https://doi.org/10.1145/322217.322225.
  35. L. Taelman. Dieudonné determinants for skew polynomial rings. Journal of Algebra and Its Applications, 5(1):89-93, 2006. Google Scholar
  36. L. G. Valiant. Completeness classes in algebra. In Proceedings of the 11th Annual ACM Symposium on Theory of Computing (STOC '79), pages 249-261, New York, NY, 1979. ACM Press. URL: https://doi.org/10.1145/800135.804419.
  37. G. C. Verghese and T. Kailath. Rational matrix structure. IEEE Transactions on Automatic Control, 26(2):434-439, 1981. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact