Determinant equivalence test over finite fields and over q

Ankit Garg, Nikhil Gupta, Neeraj Kayal, Chandan Saha

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

The determinant polynomial Detn(x) of degree n is the determinant of a n × n matrix of formal variables. A polynomial f is equivalent to Detn(x) over a field F if there exists a A ∈ GL(n2, F) such that f = Detn(A · x). Determinant equivalence test over F is the following algorithmic task: Given black-box access to a f ∈ F[x], check if f is equivalent to Detn(x) over F, and if so then output a transformation matrix A ∈ GL(n2, F). In (Kayal, STOC 2012), a randomized polynomial time determinant equivalence test was given over F = C. But, to our knowledge, the complexity of the problem over finite fields and over Q was not well understood. In this work, we give a randomized poly(n, log |F|) time determinant equivalence test over finite fields F (under mild restrictions on the characteristic and size of F). Over Q, we give an efficient randomized reduction from factoring square-free integers to determinant equivalence test for quadratic forms (i.e. the n = 2 case), assuming GRH. This shows that designing a polynomial-time determinant equivalence test over Q is a challenging task. Nevertheless, we show that determinant equivalence test over Q is decidable: For bounded n, there is a randomized polynomial-time determinant equivalence test over Q with access to an oracle for integer factoring. Moreover, for any n, there is a randomized polynomial-time algorithm that takes input black-box access to a f ∈ Q[x] and if f is equivalent to Detn over Q then it returns a A ∈ GL(n2, Ł) such that f = Detn(A · x), where Ł is an extension field of Q and [Ł: Q] ≤ n. The above algorithms over finite fields and over Q are obtained by giving a polynomial-time randomized reduction from determinant equivalence test to another problem, namely the full matrix algebra isomorphism problem. We also show a reduction in the converse direction which is efficient if n is bounded. These reductions, which hold over any F (under mild restrictions on the characteristic and size of F), establish a close connection between the complexity of the two problems. This then leads to our results via applications of known results on the full algebra isomorphism problem over finite fields (Rónyai, STOC 1987 and Rónyai, J. Symb. Comput. 1990) and over Q (Ivanyos et al., Journal of Algebra 2012 and Babai et al., Mathematics of Computation 1990).

Original languageEnglish (US)
Title of host publication46th International Colloquium on Automata, Languages, and Programming, ICALP 2019
EditorsChristel Baier, Ioannis Chatzigiannakis, Paola Flocchini, Stefano Leonardi
PublisherSchloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
ISBN (Electronic)9783959771092
DOIs
StatePublished - Jul 1 2019
Event46th International Colloquium on Automata, Languages, and Programming, ICALP 2019 - Patras, Greece
Duration: Jul 9 2019Jul 12 2019

Publication series

NameLeibniz International Proceedings in Informatics, LIPIcs
Volume132
ISSN (Print)1868-8969

Conference

Conference46th International Colloquium on Automata, Languages, and Programming, ICALP 2019
CountryGreece
CityPatras
Period7/9/197/12/19

Keywords

  • Determinant equivalence test
  • Full matrix algebra isomorphism
  • Lie algebra

ASJC Scopus subject areas

  • Software

Fingerprint Dive into the research topics of 'Determinant equivalence test over finite fields and over q'. Together they form a unique fingerprint.

Cite this