# Implications of approximating the determinant

It is known that one can compute exactly the determinant of an $n\times n$ matrix in determinstic $\log^2(n)$ space. What would be the complexity implications of approximating the determinant of a real matrix, of norm at most $1$ ($\left\|A\right\|\leq 1$) in randomized logarithmic space, up to say, a $1/\text{poly}$ accuracy?

In this respect, what would be the "correct" approximation to ask for - multiplicative or additive? (see one of the answers below).

• Are these supposed to be on a Real RAM? $\:$ – user6973 May 2 '13 at 19:03
• I'm not sure I properly understand the question, but if you refer to the precision of the arithmetic, then I'd assume that each real number is stored in log(n) bits. – Lior Eldar May 3 '13 at 13:10

## 1 Answer

With a risk of not having understood the details of the question properly: Being able to approximate the determinant within any factor requires being able to decide whether a square matrix is singular or not, which should have some consequences.

For one thing, it gives a randomized test for whether a general graph has a perfect matching (via the Tutte matrix and Schwarz-Zippel). I don't think the latter is known in randomized logspace (e.g., the Complexity Zoo lists bipartite perfect matching as hard for NL).

• Thanks Magnus, though I was actually thinking of an additive approximation error, in which case you won't be required to tell apart whether a matrix is singular or not. Multilipcative approximation may also be of interest, so right now, I'm not sure what's the best definition. – Lior Eldar May 3 '13 at 13:07
• @LiorEldar, surely even with additive approximation error, if the entries in the matrix are integers and the additive error bound is less than 0.5 you have a foolproof singularity test? – Peter Taylor May 6 '13 at 16:58
• Hi Peter Taylor, I think that to speak of, say 0.5 precision you first need somehow to specify the largest operator norm you support. So for example if your input $A$ has $\left\|A\right\|\leq 1$, then your determinant additive error can be $1/poly(n)$. So even if your input is given to you as truncated integers, each of $log(n)$ bits, then the maximal norm for which you are required to approximate the determinant would be $n^n$ in terms of integers, meaning that $0.5$ approximation error is much smaller than $1/poly(n)$ relative to $\left\|A\right\|$. – Lior Eldar May 7 '13 at 13:51
• I think the trouble with additive error relative to the norm is that it doesn't really scale nicely. Say I had an algorithm that gave a $1/poly(n)$ approximation error relative to $||A||$. Now let $A'$ be the $n^3 \times n^3$ block diagonal matrix formed using $n^2$ copies of $A$ as blocks. Then $||A||=||A'||$, but $\det(A')=\det(A)^{n^2}$, so a $||A'||/poly(n)$ additive error for $det(A')$ scales to a $O(1)$ additive error for $det (A)$. – Kevin Costello May 10 '13 at 19:43