Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It only takes a minute to sign up.
Sign up to join this community
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.
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)$.
