<p>Depends how you feel about the exponent of matrix multiplication, as this would come very close to showing $\omega=2$.</p>

<p>If the answer to your question were positive, then you could compute the determinant of an arbitrary symmetric $n \times n$ $\{0,1\}$ matrix $M$ (=adjacency matrix of an undirected graph, possibly with self-loops) in $O(n^2)$ time. As the algebraic complexity of matrix multiplication and the determinant are essentially the same, this comes very close* to showing the exponent of matrix multiplication is 2.</p>

<p>More precisely: given a matrix $M$ as above, embed it as the upper-left corner of an $n^2 \times n^2$ matrix as follows:</p>

<p>$M' = \left(\begin{array}{cc} M &amp; 0 \\ 0 &amp; I_{n^2-n} \end{array}\right)$</p>

<p>Then $M'$ is an $N \times N$ matrix $(N=n^2)$ satisfying your conditions, and $\det M' = \det M$, so if your question had a positive answer then we could compute $\det M' = \det M$ in $O(N) = O(n^2)$ operations.</p>

<p>*-The main differences are: (1) using bit complexity, and (2) restriction to $\{0,1,-1\}$ entries. However, while it is possible, I have little reason to suspect that these restrictions significantly change the complexity of matrix multiplication from $O(n^\omega)$.</p>

CC BY-SA 3.0
2017-07-02T04:03:16.007Z
explained more in comment above. i think your proof does not hold in the needed case.
Turbo
CC BY-SA 3.0
2017-07-02T05:33:04.000Z
@Turbo: Your motivation makes the question very interesting. However, the "needed case" - planar - was not what you asked about. This is why it is good to really ask the precise question you want to ask and to state your motivation. Now I feel as though my time in thinking about and writing this answer was wasted...
Joshua Grochow
CC BY-SA 3.0
2017-07-02T05:45:09.723Z
I posted such a question before someone downvoted. So I killed that question and made this thinking I made a mistake. I will reinstantiate that question as evidence
Turbo
CC BY-SA 3.0
2017-07-02T18:28:41.983Z
Josh answered the question you asked, so accept his answer. Maybe someone else would answer your other question, but don't try to ask the same thing in two different questions.
Sasho Nikolov
CC BY-SA 3.0
2017-07-20T00:40:18.887Z
@JoshuaGrochow  do you know if sparsity affects formula size for determinant?
Turbo
CC BY-SA 3.0
2017-07-20T02:00:23.770Z
@Turbo: By the same argument, it doesn't seem to affect it much, since quasi-poly(sqrt(n)) = quasi-poly(n). So if sparse Det had, say, poly size formulae, then so would general Det.
Joshua Grochow
CC BY-SA 3.0
2017-07-21T08:31:41.887Z
@JoshuaGrochow what if the weighted bipartite graph represented by the matrix is planar also?
Turbo
CC BY-SA 3.0
2017-07-21T20:08:13.213Z
@Turbo: I don't think planarity helps in general. See https://doi.org/10.1145/1714450.1714453. Of course, it's possible for two GapL-complete problems to have different time complexities...
Joshua Grochow
CC BY-SA 3.0
2017-07-21T21:35:16.293Z
@JoshuaGrochow thank you but that reference does not cover formula size (am I wrong?).
Turbo
CC BY-SA 3.0
2017-07-22T18:46:25.870Z
@Turbo: The reduction given in Section 4.2 (ibid.) is easily seen to be a projection, so it preserves formula size.
Joshua Grochow
CC BY-SA 3.0
2017-07-02T03:23:14.147Z
2017-07-02T03:23:14.147Z
Joshua Grochow
<p>If $M\in\{-1,0,+1\}^{n\times n}$ be a matrix with only $O(n)$ non-zero entries and hadamard product $M\odot M$ being symmetric can we compute $Det(M)$ in $O(n)$ bit complexity?</p>

<p>Assume that the matrix is given in form a list where $1,-1$ locations are and so the presentation is only $O(n)$ sized.</p>

CC BY-SA 3.0
2017-07-02T03:24:31.003Z
I don't know why someone downvoted; seems like a perfectly reasonable question to me... (though the motivation for the Hadamard product being symmetric is a bit obscure - it might be good if you could say a bit about the motivation)
Joshua Grochow
CC BY-SA 3.0
2017-07-02T04:02:38.293Z
@JoshuaGrochow can we compute $\#$ perfect matchings in planar graphs in linear time? The symmetry condition comes from matrix being adjacency and sign condition comes from pfaffian orientation. So I think your proof will not work since embedding the matrix in a corner would still preserve non-planarity if original adjacency $M$ was non-planar. However I am avoiding adjacency $M$ to be non-planar. I think $\#$ perfect matchings of planar graph is in $O(n)$ (which is still possible as this is not covered by your proof). This is where symmetry and sign conditions come from.
Turbo
<cc.complexity-theory><ds.algorithms><matrices><sparse-matrix><determinant>
Complexity of $\{0,\pm1\}$ determinant in sparse cases?
Turbo
# Complexity of $\{0,\pm1\}$ determinant in sparse cases?

(Asked by: username_0 on 2017-07-01)

If $M\in\{-1,0,+1\}^{n\times n}$ be a matrix with only $O(n)$ non-zero entries and hadamard product $M\odot M$ being symmetric can we compute $Det(M)$ in $O(n)$ bit complexity?

Assume that the matrix is given in form a list where $1,-1$ locations are and so the presentation is only $O(n)$ sized.

**Tags:** cc.complexity-theory, ds.algorithms, matrices, sparse-matrix, determinant
> **Comments:**
> **username_1**: I don't know why someone downvoted; seems like a perfectly reasonable question to me... (though the motivation for the Hadamard product being symmetric is a bit obscure - it might be good if you could say a bit about the motivation)  
> **username_0**: @JoshuaGrochow can we compute $\#$ perfect matchings in planar graphs in linear time? The symmetry condition comes from matrix being adjacency and sign condition comes from pfaffian orientation. So I think your proof will not work since embedding the matrix in a corner would still preserve non-planarity if original adjacency $M$ was non-planar. However I am avoiding adjacency $M$ to be non-planar. I think $\#$ perfect matchings of planar graph is in $O(n)$ (which is still possible as this is not covered by your proof). This is where symmetry and sign conditions come from.  

---

## 1 answers

### Answer by username_1 on 2017-07-02. Score: 6 | Accepted answer

Depends how you feel about the exponent of matrix multiplication, as this would come very close to showing $\omega=2$.

If the answer to your question were positive, then you could compute the determinant of an arbitrary symmetric $n \times n$ $\{0,1\}$ matrix $M$ (=adjacency matrix of an undirected graph, possibly with self-loops) in $O(n^2)$ time. As the algebraic complexity of matrix multiplication and the determinant are essentially the same, this comes very close\* to showing the exponent of matrix multiplication is 2.

More precisely: given a matrix $M$ as above, embed it as the upper-left corner of an $n^2 \times n^2$ matrix as follows:

$M' = \left(\begin{array}{cc} M & 0 \\ 0 & I\_{n^2-n} \end{array}\right)$

Then $M'$ is an $N \times N$ matrix $(N=n^2)$ satisfying your conditions, and $\det M' = \det M$, so if your question had a positive answer then we could compute $\det M' = \det M$ in $O(N) = O(n^2)$ operations.

\*-The main differences are: (1) using bit complexity, and (2) restriction to $\{0,1,-1\}$ entries. However, while it is possible, I have little reason to suspect that these restrictions significantly change the complexity of matrix multiplication from $O(n^\omega)$.

> **Comments:**
> **username_0**: explained more in comment above. i think your proof does not hold in the needed case.  
> **username_1**: @Turbo: Your motivation makes the question very interesting. However, the "needed case" - planar - was not what you asked about. This is why it is good to really ask the precise question you want to ask and to state your motivation. Now I feel as though my time in thinking about and writing this answer was wasted...  
> **username_0**: I posted such a question before someone downvoted. So I killed that question and made this thinking I made a mistake. I will reinstantiate that question as evidence  
> **username_2**: Josh answered the question you asked, so accept his answer. Maybe someone else would answer your other question, but don't try to ask the same thing in two different questions.  
> **username_0**: @JoshuaGrochow  do you know if sparsity affects formula size for determinant?  
> **username_1**: @Turbo: By the same argument, it doesn't seem to affect it much, since quasi-poly(sqrt(n)) = quasi-poly(n). So if sparse Det had, say, poly size formulae, then so would general Det.  
> **username_0**: @JoshuaGrochow what if the weighted bipartite graph represented by the matrix is planar also?  
> **username_1**: @Turbo: I don't think planarity helps in general. See https://doi.org/10.1145/1714450.1714453. Of course, it's possible for two GapL-complete problems to have different time complexities...  
> **username_0**: @JoshuaGrochow thank you but that reference does not cover formula size (am I wrong?).  
> **username_1**: @Turbo: The reduction given in Section 4.2 (ibid.) is easily seen to be a projection, so it preserves formula size.  

---

