Singularity of Sparse Circulant Matrices is NP-complete

Details Singularity of Sparse Circulant Matrices is NP-complete Singularity of Sparse Circulant Matrices is NP-complete

2009-09-14

arxiv.org/abs/0909.2694v1

Computer Science

Computational Complexity

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

Scientific paper

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.

Affiliated with

Also associated with

No associations

Rating

Singularity of Sparse Circulant Matrices is NP-complete does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Singularity of Sparse Circulant Matrices is NP-complete, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Singularity of Sparse Circulant Matrices is NP-complete will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-555317