<p>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.</p>

<p>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).</p>

CC BY-SA 3.0
2013-05-03T13:07:30.800Z
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
CC BY-SA 3.0
2013-05-06T16:58:08.177Z
@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
CC BY-SA 3.0
2013-05-07T13:51:40.773Z
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
CC BY-SA 3.0
2013-05-10T19:43:17.110Z
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
CC BY-SA 3.0
2013-05-03T10:40:37.073Z
2013-05-03T10:40:37.073Z
Magnus Wahlström
<p>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?</p>

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

CC BY-SA 3.0
2013-05-03T13:10:41.330Z
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
<determinant><cc.complexity-theory>
Implications of approximating the determinant
Lior Eldar
# Implications of approximating the determinant

(Asked by: username_0 on 2013-05-02)

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).

**Tags:** determinant, cc.complexity-theory

> **Comments:**
> **username_0**: 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.  

---

## 1 answers

### Answer by username_1 on 2013-05-03. Score: 4

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).

> **Comments:**
> **username_0**: 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.  
> **username_2**: @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?  
> **username_0**: Hi username_2, 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\|$.  
> **username_3**: 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)$.  

---

