<p>The following question arose as a side product of some work I have been part of recently.
An $m$ by $n$ $(0,1)$-matrix $M$ is partial circulant if it can be formed by taking the first $m$ rows of a <a href="http://en.wikipedia.org/wiki/Circulant_matrix" rel="nofollow noreferrer">circulant matrix</a> and all its entries are either $0$ or $1$.  We assume that $m\leq n$.  </p>

<p>Given such a partial circulant matrix $M$, what is the computational complexity of the following question?</p>

<blockquote>
  <p>Is there a non-zero vector $v\in \{-1,0,1\}^n$ such that $Mv=0$?</p>
</blockquote>

<p>The problem is clearly in NP but my guess is that it is not NP-hard (unlike <a href="https://cstheory.stackexchange.com/questions/20277/decide-whether-a-matrixs-kernel-contains-any-non-zero-vector-all-of-whose-entri">this related question</a>).  I have not, however, found a poly time solution.</p>

CC BY-SA 3.0
2015-06-24T18:24:47.447Z
would it be more natural to study the circulant case 1st vs the partial circulant? also (idea) the other problem answers are formulated in terms of subset sum problem, how would this problem be formulated that way (ie as a constrained or special case of subset sum problem)? note there are many subset sum variants studied in the literature that might be close...
vzn
CC BY-SA 3.0
2015-06-24T18:40:54.767Z
The circulant case was in fact considered at http://mathoverflow.net/questions/168474/how-to-determine-if-there-exists-a-non-zero-vector-in-the-kernel . However, it seems that there is fatal bug in one of the answers and the other answer is not a complete solution.
Simd
<cc.complexity-theory><ds.algorithms><matrices>
Partial circulant matrices: Is there a non-zero vector $v\in \{-1,0,1\}^n$ such that $Mv=0$?
Simd
# Partial circulant matrices: Is there a non-zero vector $v\in \{-1,0,1\}^n$ such that $Mv=0$?

(Asked by: username_0 on 2014-11-04)

The following question arose as a side product of some work I have been part of recently.
An $m$ by $n$ $(0,1)$-matrix $M$ is partial circulant if it can be formed by taking the first $m$ rows of a [circulant matrix](http://en.wikipedia.org/wiki/Circulant_matrix) and all its entries are either $0$ or $1$. We assume that $m\leq n$.

Given such a partial circulant matrix $M$, what is the computational complexity of the following question?

> Is there a non-zero vector $v\in \{-1,0,1\}^n$ such that $Mv=0$?

The problem is clearly in NP but my guess is that it is not NP-hard (unlike [this related question](https://cstheory.stackexchange.com/questions/20277/decide-whether-a-matrixs-kernel-contains-any-non-zero-vector-all-of-whose-entri)). I have not, however, found a poly time solution.

**Tags:** cc.complexity-theory, ds.algorithms, matrices

> **Comments:**
> **username_1**: would it be more natural to study the circulant case 1st vs the partial circulant? also (idea) the other problem answers are formulated in terms of subset sum problem, how would this problem be formulated that way (ie as a constrained or special case of subset sum problem)? note there are many subset sum variants studied in the literature that might be close...  
> **username_0**: The circulant case was in fact considered at http://mathoverflow.net/questions/168474/how-to-determine-if-there-exists-a-non-zero-vector-in-the-kernel . However, it seems that there is fatal bug in one of the answers and the other answer is not a complete solution.  

---

## 0 answers

