# Comparison of matrix determinant in less than $O(n^2)$

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.

• 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$? – Juho Apr 24 '15 at 12:13
• @Juho I mean comparing the determinant of $M$ and $d$ – Alvaro Fuentes Apr 24 '15 at 12:14
• An adversary argument should show that you need to look at all entries, and this gives an $\Omega(n^2)$ lower bound. – Yuval Filmus Apr 24 '15 at 12:27
• @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. – Alvaro Fuentes Apr 24 '15 at 12:32
• 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. – Yuval Filmus Apr 24 '15 at 12:43