Determinant equivalence test over finite fields and over Q

摘要

The determinant polynomial De t n ( x ) of degree n is the determinant of a n n matrix of formal variables. A polynomial f is equivalent to De t n over a field F if there exists a A G L ( n 2 F ) such that f = D e t n ( 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 De t n over F , and if so then output a transformation matrix A G L ( n 2 F ) . In Kayal (2012), a randomized polynomial time determinant equivalence test was given over C . But, to our knowledge, the complexity of the problem over finite fields and over rationals was not well understood. In this work, we give a randomized pol y ( n log F ) time determinant equivalence test over finite fields F (under mild restrictions on the characteristic and size of F ). Over rationals, 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 rationals is a challenging task. Nevertheless, we show that determinant equivalence test over rationals is decidable: For bounded n , there is a randomized polynomial-time determinant equivalence test over rationals 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 rational polynomial f and if f is equivalent to De t n over rationals then it returns a A G L ( n 2 L ) such that f = D e t n ( A x ) , where L is an extension field of Q of degree at most n . The above algorithms over finite fields and over rationals 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 lead to our results via applications of known results on the full algebra isomorphism problem over finite fields and over Q .