Document Open Access Logo

Symbolic Determinant Identity Testing and Non-Commutative Ranks of Matrix Lie Algebras

Authors Gábor Ivanyos , Tushant Mittal , Youming Qiao

PDF
Thumbnail PDF

File

LIPIcs.ITCS.2022.87.pdf
  • Filesize: 0.79 MB
  • 21 pages

Document Identifiers

Author Details

Gábor Ivanyos
  • Institute for Computer Science and Control, Eötvös Loránd Research Network (ELKH), Budapest, Hungary
Tushant Mittal
  • Department of Computer Science, University of Chicago, IL, USA
Youming Qiao
  • Centre for Quantum Software and Information, University of Technology Sydney, Australia

Funding

  • Qiao, Youming: Australian Research Council DP200100950.

Acknowledgements

T. M. would like to thank Pallav Goyal for helping him understand Lie algebras. The authors would like to thank Visu Makam for communicating [Derksen and Makam, 2020] to them, and the anonymous reviewers for their detailed and helpful feedback.

Cite As Get BibTex

Gábor Ivanyos, Tushant Mittal, and Youming Qiao. Symbolic Determinant Identity Testing and Non-Commutative Ranks of Matrix Lie Algebras. In 13th Innovations in Theoretical Computer Science Conference (ITCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 215, pp. 87:1-87:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022) https://doi.org/10.4230/LIPIcs.ITCS.2022.87

Abstract

One approach to make progress on the symbolic determinant identity testing (SDIT) problem is to study the structure of singular matrix spaces. After settling the non-commutative rank problem (Garg-Gurvits-Oliveira-Wigderson, Found. Comput. Math. 2020; Ivanyos-Qiao-Subrahmanyam, Comput. Complex. 2018), a natural next step is to understand singular matrix spaces whose non-commutative rank is full. At present, examples of such matrix spaces are mostly sporadic, so it is desirable to discover them in a more systematic way.
In this paper, we make a step towards this direction, by studying the family of matrix spaces that are closed under the commutator operation, that is, matrix Lie algebras. On the one hand, we demonstrate that matrix Lie algebras over the complex number field give rise to singular matrix spaces with full non-commutative ranks. On the other hand, we show that SDIT of such spaces can be decided in deterministic polynomial time. Moreover, we give a characterization for the matrix Lie algebras to yield a matrix space possessing singularity certificates as studied by Lovász (B. Braz. Math. Soc., 1989) and Raz and Wigderson (Building Bridges II, 2019).

Subject Classification

ACM Subject Classification
  • Theory of computation → Algebraic complexity theory
  • Theory of computation → Pseudorandomness and derandomization
Keywords
  • derandomization
  • polynomial identity testing
  • symbolic determinant
  • non-commutative rank
  • Lie algebras

Metrics

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

Related Versions

References

  1. M. D. Atkinson and R. Westwick. Spaces of linear transformations of equal rank. Linear and Multilinear Algebra, 13(3):231-239, 1983. URL: https://doi.org/10.1080/03081088308817522.
  2. Jean-Marie Bois. Generators of simple Lie algebras in arbitrary characteristics. Mathematische Zeitschrift, 262(4):715-741, 2009. URL: https://doi.org/10.1007/s00209-008-0397-3.
  3. Jonathan F. Buss, Gudmund S. Frandsen, and Jeffrey O. Shallit. The computational complexity of some problems of linear algebra. Journal of Computer and System Sciences, 58(3):572-596, 1999. URL: https://doi.org/10.1006/jcss.1998.1608.
  4. W.A. de Graaf. Lie Algebras: Theory and Algorithms, volume 56 of North-Holland Mathematical Library. Elsevier Science, 2000. URL: https://www.sciencedirect.com/bookseries/north-holland-mathematical-library/vol/56/.
  5. Willem De Graaf, Gábor Ivanyos, and Lajos Rónyai. Computing cartan subalgebras of lie algebras. Applicable Algebra in Engineering, Communication and Computing, 7(5):339-349, September 1996. URL: https://doi.org/10.1007/BF01293593.
  6. H. Derksen and V. Makam. Polynomial degree bounds for matrix semi-invariants. Advances in Mathematics, 310:44-63, 2017. URL: https://doi.org/10.1016/j.aim.2017.01.018.
  7. Harm Derksen and Visu Makam. Private communication, 2020. Google Scholar
  8. Jan Draisma. Counting components of the null-cone on tuples. Transformation Groups, 11:609-624, 2006. URL: https://doi.org/10.1007/s00031-005-1120-7.
  9. Jan Draisma. Small maximal spaces of non-invertible matrices. Bulletin of the London Mathematical Society, 38(5):764-776, 2006. URL: https://doi.org/10.1112/S0024609306018741.
  10. David Eisenbud and Joe Harris. Vector spaces of matrices of low rank. Advances in Mathematics, 70(2):135-155, 1988. URL: https://doi.org/10.1016/0001-8708(88)90054-0.
  11. Ankit Garg, Leonid Gurvits, Rafael Mendes de Oliveira, and Avi Wigderson. Operator scaling: Theory and applications. Found. Comput. Math., 20(2):223-290, 2020. URL: https://doi.org/10.1007/s10208-019-09417-z.
  12. Brian C. Hall. Lie Groups, Lie Algebras, and Representations. Springer International Publishing, 2015. URL: https://doi.org/10.1007/978-3-319-13467-3.
  13. James E Humphreys. Introduction to Lie algebras and representation theory, volume 9 of Graduate Texts in Mathematics. Springer Science & Business Media, 2012. URL: https://doi.org/10.1007/978-1-4612-6398-2.
  14. Gábor Ivanyos, Marek Karpinski, Youming Qiao, and Miklos Santha. Generalized Wong sequences and their applications to Edmonds' problems. Journal of Computer and System Science, 81(7):1373-1386, 2015. URL: https://doi.org/10.1016/j.jcss.2015.04.006.
  15. Gábor Ivanyos, Youming Qiao, and K. V. Subrahmanyam. Non-commutative edmonds' problem and matrix semi-invariants. Computational Complexity, 26(3):717-763, September 2017. URL: https://doi.org/10.1007/s00037-016-0143-x.
  16. Gábor Ivanyos, Youming Qiao, and K. V. Subrahmanyam. Constructive non-commutative rank computation is in deterministic polynomial time. Computational Complexity, 27(4):561-593, December 2018. URL: https://doi.org/10.1007/s00037-018-0165-7.
  17. Gábor Ivanyos, Tushant Mittal, and Youming Qiao. Symbolic determinant identity testing and non-commutative ranks of matrix Lie algebras, 2021. URL: http://arxiv.org/abs/2109.06403.
  18. V. Kabanets and R. Impagliazzo. Derandomizing polynomial identity tests means proving circuit lower bounds. Computational Complexity, 13(1/2):1-46, 2004. URL: https://doi.org/10.1007/s00037-004-0182-6.
  19. Masatake Kuranishi. On everywhere dense imbedding of free groups in Lie groups. Nagoya Math. J., 2:63-71, 1951. URL: http://projecteuclid.org/euclid.nmj/1118764740.
  20. László Lovász. Singular spaces of matrices and their application in combinatorics. Boletim da Sociedade Brasileira de Matemática-Bulletin/Brazilian Mathematical Society, 20(1):87-99, 1989. URL: https://doi.org/10.1007/BF02585470.
  21. Visu Makam and Avi Wigderson. Singular tuples of matrices is not a null cone (and the symmetries of algebraic varieties). Journal für die reine und angewandte Mathematik (Crelles Journal), 2021(780):79-131, 2021. URL: https://doi.org/10.1515/crelle-2021-0044.
  22. Orit E. Raz and Avi Wigderson. Subspace Arrangements, Graph Rigidity and Derandomization Through Submodular Optimization, pages 377-415. Springer Berlin Heidelberg, Berlin, Heidelberg, 2019. URL: https://doi.org/10.1007/978-3-662-59204-5_12.
  23. Jacob 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.
  24. Jean-Pierre Serre. Complex Semisimple Lie Algebras. Springer Berlin Heidelberg, 2001. URL: https://doi.org/10.1007/978-3-642-56884-8.
  25. Richard Zippel. Probabilistic algorithms for sparse polynomials. In Symbolic and Algebraic Computation, volume 72 of Lecture Notes in Computer Science, pages 216-226. Springer-Verlag, 1979. URL: https://doi.org/10.1007/3-540-09519-5_73.
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