Computing the sign or the value of the determinant of an integer matrix, a complexity survey

摘要

Computation of the sign of the determinant of a matrix and the determinant itself is a challenge for both numerical and exact methods. We survey the complexity of existing methods to solve these problems when the input is an n×n matrix A with integer entries. We study the bit-complexities of the algorithms asymptotically in n and the norm of A. Existing approaches rely on numerical approximate computations, on exact computations, or on both types of arithmetic in combination.