2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Every number is the determinant of a matrix. Just take $\mathrm{diag}(\lambda, 1,...,1)$. But your question might be "what's the fastest way to determine the determinant of a given matrix". $\endgroup$ – Tlön Uqbar Orbis Tertius Apr 24 '15 at 11:29
  • $\begingroup$ @HerbertQuain The matrix is given. Updated the question with some motivation as well. $\endgroup$ – musically_ut Apr 24 '15 at 11:30
  • $\begingroup$ But you also need to know if the matrix's determinant is greater or less than your possible value (for binary search), not just if equal. $\endgroup$ – Alvaro Fuentes Apr 24 '15 at 11:33
  • $\begingroup$ @xndrme It would be great if I could use binary search. However, a linear search might not be out of the question completely. I am hoping that the answer will allow for it. $\endgroup$ – musically_ut Apr 24 '15 at 11:37
  • $\begingroup$ @musically_ut OK, I was just pointing out for the binary search. Anyways I have serious doubt about the possibility of performing the comparison in less than $O(n^2)$. Maybe you should ask here $\endgroup$ – Alvaro Fuentes Apr 24 '15 at 11:44
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.