Singularity of Sparse Circulant Matrices is NP-complete

It is shown by Karp reduction that deciding the singularity of $(2^n - 1) \times (2^n - 1)$ sparse circulant matrices (SC problem) is NP-complete. We can write them only implicitly, by indicating values of the $2+n(n+1)\mathrm{/}2$ eventually nonzero entries of the first row and can make all matrix operations with them. The positions are $0,1,2^i+2^j$. The complexity parameter is $n$. Mulmuley’s work on the rank of matrices \cite{Mulmuley87} makes SC stand alone in a list of 3,000 and growing NP-complete problems.