# 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, 2013 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. May 3, 2013 at 13:10

• 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\|$. May 7, 2013 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)$. May 10, 2013 at 19:43