1
$\begingroup$

I was reading this question and I think maybe somebody here could help.

This is the idea: Given a matrix $M$ of integers, and a number $d$ is there a way to compare the determinant of $M$ and $d$ in a fast way? Note that we don't need the calculation of the determinant, only comparison.

The motivation is this: if one could find a good (maybe less than $O(n^2)$) algorithm, and with an upper and lower bounds for the determinant, one could perform binary (or linear?, no, I don't think so) search over the interval in order to determine the determinant of the matrix.

$\endgroup$
  • $\begingroup$ What do you mean with comparing $M$ and $d$? Maybe I'm not trying hard enough, but do you mean you are comparing some value $d$ against every value in a matrix $M$? $\endgroup$ – Juho Apr 24 '15 at 12:13
  • $\begingroup$ @Juho I mean comparing the determinant of $M$ and $d$ $\endgroup$ – Alvaro Fuentes Apr 24 '15 at 12:14
  • 1
    $\begingroup$ An adversary argument should show that you need to look at all entries, and this gives an $\Omega(n^2)$ lower bound. $\endgroup$ – Yuval Filmus Apr 24 '15 at 12:27
  • $\begingroup$ @YuvalFilmus yes, but suppose that we have known bounds for the determinant and/or for the values of $M$, the idea of the question is if is there an approach, maybe with some restrictions of course. I just put the motivation as an example, but the question is still valid, maybe just to find the fastest way for the comparison. $\endgroup$ – Alvaro Fuentes Apr 24 '15 at 12:32
  • $\begingroup$ It is also known that computing the determinant exactly in the algebraic computation model (so no IFs) takes time $\tilde{O}(n^\omega)$, where $\omega$ is the exponent of matrix multiplication. Your algorithm has IFs, but they are not supposed to help. For concreteness, imagine that you are computing the determinant over $GL(2)$. In this setting, binary search doesn't seem helpful. $\endgroup$ – Yuval Filmus Apr 24 '15 at 12:43

Your Answer

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

Browse other questions tagged or ask your own question.