# Complexity of $\{0,\pm1\}$ determinant in sparse cases?

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.

• 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) Jul 2, 2017 at 3:24
• @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. Jul 2, 2017 at 4:02

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

• explained more in comment above. i think your proof does not hold in the needed case. Jul 2, 2017 at 4:03
• @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... Jul 2, 2017 at 5:33
• 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 Jul 2, 2017 at 5:45
• 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. Jul 2, 2017 at 18:28
• @Turbo: I don't think planarity helps in general. See doi.org/10.1145/1714450.1714453. Of course, it's possible for two GapL-complete problems to have different time complexities... Jul 21, 2017 at 20:08