Verifying whether a number is the determinant of a matrix

Question

What is the (computationally) fastest way to determine whether a number is the determinant of a given real matrix?

I am wondering if I have an upper bound on the absolute value of the determinant of a matrix, and the method allows for deciding whether a given number is higher or lower than the true determinant, perhaps I can use binary search to find the exact determinant faster than O(n^3). Otherwise, if I have a suitable lower bound, then via a linear search.

Answer 1

Let's focus on the topic of whether the matrix determinant's $O(n^3)$ floating point complexity of standard approaches (elimination or factorization) can be improved by having "an upper bound".

Knowing an upper bound on the determinant of a matrix does not immediately help lower the complexity of its computation. In the case of real (or complex) matrices, an upper bound on (the absolute value of) the determinant is readily found in $O(n^2)$ floating point operations.

However if we are concerned with the number of bit operations required to find the exact determinant of an $n\times n$ integer matrix $A$, then the size of the largest entry of $A$ does appear this estimate.

A good reference for the dense integer matrix case is Kaltofen and Villard, On the Complexity of Computing Determinants (2004). The algorithms discussed there are randomized "of the Las Vegas kind -- always correct, probably fast", which means that although the results are exact and deterministic, the number of bit operations is a random variable and it is the expected value of this count which is estimated.

Our algorithms compute the determinant ... of a dense $n \times n$ matrix $A$ with integer entries in $(n^{3.2} \log ||A||)^{1+o(1)}$ and $(n^{2.697263} \log ||A||)^{1+o(1)}$ bit operations [where] $||A||$ denotes the largest entry in absolute value and the exponent adjustment by “$+o(1)$” captures additional factors... The bit complexity $(n^{3.2} \log ||A||)^{1+o(1)}$ results from using the classical cubic matrix multiplication algorithm.

The "faster" estimate of $(n^{2.697263} \log ||A||)^{1+o(1)}$ bit operations results from using the best fast matrix multiplication algorithms (Coppersmith & Winograd 1990; Coppersmith 1997).

The methods there are "asymptotically" fast, but in practical terms they involve so much machinery (polynomial operations) that they would not be considered for implementation in numerical floating point libraries.