License: 
Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ICALP.2019.62
URN: urn:nbn:de:0030-drops-106382
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2019/10638/
Garg, Ankit ;
Gupta, Nikhil ;
Kayal, Neeraj ;
Saha, Chandan
Determinant Equivalence Test over Finite Fields and over Q
Abstract
The determinant polynomial Det_n(x) of degree n is the determinant of a n x n matrix of formal variables. A polynomial f is equivalent to Det_n(x) over a field F if there exists a A in GL(n^2,F) such that f = Det_n(A * x). Determinant equivalence test over F is the following algorithmic task: Given black-box access to a f in F[x], check if f is equivalent to Det_n(x) over F, and if so then output a transformation matrix A in GL(n^2,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 in Q[x] and if f is equivalent to Det_n over Q then it returns a A in GL(n^2,L) such that f = Det_n(A * x), where L is an extension field of Q and [L : 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).
BibTeX - Entry
@InProceedings{garg_et_al:LIPIcs:2019:10638,
author = {Ankit Garg and Nikhil Gupta and Neeraj Kayal and Chandan Saha},
title = {{Determinant Equivalence Test over Finite Fields and over Q}},
booktitle = {46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)},
pages = {62:1--62:15},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-109-2},
ISSN = {1868-8969},
year = {2019},
volume = {132},
editor = {Christel Baier and Ioannis Chatzigiannakis and Paola Flocchini and Stefano Leonardi},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2019/10638},
URN = {urn:nbn:de:0030-drops-106382},
doi = {10.4230/LIPIcs.ICALP.2019.62},
annote = {Keywords: Determinant equivalence test, full matrix algebra isomorphism, Lie algebra}
}
|
Keywords: |
|
Determinant equivalence test, full matrix algebra isomorphism, Lie algebra |
|
Collection: |
|
46th International Colloquium on Automata, Languages, and Programming (ICALP 2019) |
|
Issue Date: |
|
2019 |
|
Date of publication: |
|
04.07.2019 |
