How to determine if there exists a non-zero vector in the kernel If you are given a $0$-$1$  circulant matrix with $n$ rows and $n$ columns, is there an efficient way of determining if there exists a non-zero $\{-1,0,1\}$-vector in its kernel?

Could this problem in fact be NP-complete?

July 10 2015
Emil Jeřábek argues in the comments that the problem is (very) unlikely to be NP-complete.  Its complexity still remains open however.
 A: If $f(x)$ is the associated polynomial to a circulant matrix $C$, then the kernel of $C$ is spanned by vectors
$$v_i = (1,w_i,w_i^2, \dots, w_i^{n-1})$$
where the $w_i$ range through all $n$-th roots of unity that are also roots of $f(x)$. 
This gives an explicit description of the kernel, and so determining whether $ \{-1,0,1\}$-vector lies in its kernel can be done by solving a bunch of linear equations.
Added later, in response to comments: We don't really want to solve $3^n$ linear equations (and I apologise for suggesting that this could be in any way interpreted as efficient). Two points:


*

*If the kernel has dimension $d$, then one can reduce the system to $3^d$ linear equations so this naive approach is OK when the kernel is small.

*We should be able to use the fact that $C$ is a $\{0,1\}$-matrix: if $f$ has any root at all, then it will be divisible by an irreducible cyclotomic polynomial $\Phi_\ell$ of some degree $d$, thus the kernel will contain $v_1,\dots, v_d$, the vectors corresponding to the roots of this cyclotomic polynomial. I asserted earlier that the sum of these will be a $\{0,1,-1\}$-vector. This was wrong, however some progress can be made: 


*

*If $\ell=2^a$ for some integer $a$, then the sum of the corresponding vectors is a multiple of a a $\{0,1,-1\}$-vector and we are done.

*If $\ell=3\cdot 2^a$ for some integer $a$, then an alternating sum seems to  be a multiple of a a $\{0,1,-1\}$-vector and, again, we are done. (Although I don't have time to check this for $\ell>6$ just now.)



In particular, if $n=2^a$ or $3\cdot 2^a$, then one has a non-trivial $\{0,1,-1\}$-vector in the kernel whenever the kernel is non-trivial. And this, of course, can be checked in polynomial time. Whether one can extend this to account for all $n$, I do not know.
