License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ITCS.2022.87
URN: urn:nbn:de:0030-drops-156837
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2022/15683/
Go to the corresponding LIPIcs Volume Portal

Ivanyos, Gábor ; Mittal, Tushant ; Qiao, Youming

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

pdf-format:
LIPIcs-ITCS-2022-87.pdf (0.8 MB)

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

BibTeX - Entry

@InProceedings{ivanyos_et_al:LIPIcs.ITCS.2022.87,
  author =	{Ivanyos, G\'{a}bor and Mittal, Tushant and Qiao, Youming},
  title =	{{Symbolic Determinant Identity Testing and Non-Commutative Ranks of Matrix Lie Algebras}},
  booktitle =	{13th Innovations in Theoretical Computer Science Conference (ITCS 2022)},
  pages =	{87:1--87:21},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-217-4},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{215},
  editor =	{Braverman, Mark},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2022/15683},
  URN =		{urn:nbn:de:0030-drops-156837},
  doi =		{10.4230/LIPIcs.ITCS.2022.87},
  annote =	{Keywords: derandomization, polynomial identity testing, symbolic determinant, non-commutative rank, Lie algebras}
}

Keywords: derandomization, polynomial identity testing, symbolic determinant, non-commutative rank, Lie algebras
Collection: 13th Innovations in Theoretical Computer Science Conference (ITCS 2022)
Issue Date: 2022
Date of publication: 25.01.2022

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI