Singularity of Sparse Circulant Matrices is NP-complete

Abstract

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

References are somewhere in the middle, before the appendices. 8 pages