  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.
