# 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) – Joshua Grochow Jul 2 '17 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. – 1.. Jul 2 '17 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. – 1.. Jul 2 '17 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... – Joshua Grochow Jul 2 '17 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 – 1.. Jul 2 '17 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. – Sasho Nikolov Jul 2 '17 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... – Joshua Grochow Jul 21 '17 at 20:08