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 blackbox 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 squarefree integers to determinant equivalence test for quadratic forms (i.e. the n=2 case), assuming GRH. This shows that designing a polynomialtime 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 polynomialtime determinant equivalence test over Q with access to an oracle for integer factoring. Moreover, for any n, there is a randomized polynomialtime algorithm that takes input blackbox 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 polynomialtime 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:162:15},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959771092},
ISSN = {18688969},
year = {2019},
volume = {132},
editor = {Christel Baier and Ioannis Chatzigiannakis and Paola Flocchini and Stefano Leonardi},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2019/10638},
URN = {urn:nbn:de:0030drops106382},
doi = {10.4230/LIPIcs.ICALP.2019.62},
annote = {Keywords: Determinant equivalence test, full matrix algebra isomorphism, Lie algebra}
}
04.07.2019
Keywords: 

Determinant equivalence test, full matrix algebra isomorphism, Lie algebra 
Seminar: 

46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)

Issue date: 

2019 
Date of publication: 

04.07.2019 