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.

  • 1
    $\begingroup$ 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) $\endgroup$ – Joshua Grochow Jul 2 '17 at 3:24
  • 1
    $\begingroup$ @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. $\endgroup$ – T.... 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)$.

| cite | improve this answer | |
  • $\begingroup$ explained more in comment above. i think your proof does not hold in the needed case. $\endgroup$ – T.... Jul 2 '17 at 4:03
  • 1
    $\begingroup$ @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... $\endgroup$ – Joshua Grochow Jul 2 '17 at 5:33
  • $\begingroup$ 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 $\endgroup$ – T.... Jul 2 '17 at 5:45
  • 3
    $\begingroup$ 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. $\endgroup$ – Sasho Nikolov Jul 2 '17 at 18:28
  • 1
    $\begingroup$ @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... $\endgroup$ – Joshua Grochow Jul 21 '17 at 20:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.