8
$\begingroup$

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.

Improve this question
$\endgroup$
4
  • 3
    $\begingroup$ The problem is certainly NP-complete for general matrices, see cstheory.stackexchange.com/questions/20277. The restriction to circulant matrices could well make a difference, but I can’t tell. $\endgroup$
    – Emil Jeřábek
    Commented May 29, 2014 at 21:02
  • $\begingroup$ @EmilJeřábek The reductions in that linked question do not seem to apply here unless there is a clever trick I have missed. $\endgroup$
    – Simd
    Commented May 30, 2014 at 7:18
  • 4
    $\begingroup$ Here's a matrix-free reformulation: Given a set $S$ in $Z/nZ$, are there disjoint sets $T$ and $U$ such that $|(S+i)\cap T|=|(S+i)\cap U|$ for all $i$? Here, $S$ encodes the first row of the matrix, $T$ encodes the positive part of the vector, and $U$ encodes the negative part of the vector. $\endgroup$
    – user44143
    Commented May 31, 2014 at 23:54
  • 2
    $\begingroup$ @MattF. — (And the union of $T$ and $U$ should be non-empty.) $\endgroup$
    – jmc
    Commented Jun 5, 2014 at 10:02

2 Answers 2

Reset to default
2
+25
$\begingroup$

Let $C$ denote your circulant matrix and $P$ the cyclic permutation matrix as defined in http://en.wikipedia.org/wiki/Circulant_matrix such that $P^n=I$ is the identity matrix. After rotating the first 1 to the first entry your $C$ assumes the form $C=I+\sum \limits_{k=1}^{n-1} a_k\,P^k,$ where $a_k\in\{0,1\}$.

Now assume there is a non-zero $\{-1,0,1\}$-vector $v$ in the kernel $K$, then also $P^k\,v\in K$, because $C\,P^k\,v ~=~ P^k\,C\,v~=~0$. Also, $v$ cannot contain only 0,-1 entries. It is therefore possible to rotate the first 1 of $v$ to the first position. After doing this, consider the matrix $V=I+\sum \limits_{k=1}^{n-1} v_k\,P^k.$

From the previous properties follows that $C\, V ~=~0.$ It is therefore possible to expand $C\, V $ in terms of $P$ using $P^n=I$ and solve the linear system $C\, V ~=~0$ for $v_k$. If there is a vector $v$ with $v_k\in\{-1,0,1\}$ in the kernel $K$ then it is a solution to this linear system of $n$ equations in $n-1$ variables, and this can readily be checked in polynomial time. This provides an efficient polynomial algorithm to test whether a solution exists and to find it.

Addition: Here is a proof-of-concept Mathematica Code to find the $v_k$:

n = 500;
res = Reap[Do[
c = Table[RandomInteger[{0, 1}], {n}]; (* Create random first row of C  *)
While[c[[1]] == 0, c = RotateLeft[c]]; (* rotate such that c[[1]]=1 *)
Clear[v]; vv = Table[v[k], {k, 1, n}]; vv[[1]] = 1; (* variable rotated v *)
lc = ListConvolve[c, vv, {1, -1}, 0]; (* Polynomial multiplication *)
lc = Take[lc, n] + Append[Drop[lc, n], 0];  (* Using P^n =Id  *)
s = Solve[lc == 0, Drop[vv, 1]];  (* Solve linear system for v *)
If[s != {}, Sow[{c, vv /. s}]], {20}]][[2, 1]] (* collect cases with solution *)

One solution for n=500 is 

{{{1, 0, 1, 0, 0, 1, 0, 1, 0, 0, 0, 1, 1, 0, 0, 1, 0, 1, 0, 1, 1, 0, 
0, 1, 1, 1, 1, 1, 0, 0, 1, 1, 1, 0, 0, 1, 1, 1, 0, 1, 1, 1, 0, 1, 
1, 0, 1, 1, 0, 0, 1, 1, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 1, 1, 0, 1, 
0, 0, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 
0, 0, 1, 1, 0, 0, 1, 1, 0, 0, 0, 1, 0, 1, 1, 0, 1, 0, 1, 1, 1, 0, 
1, 1, 0, 0, 0, 0, 1, 1, 1, 0, 1, 1, 0, 1, 1, 0, 0, 1, 1, 1, 1, 0, 
0, 0, 1, 0, 0, 1, 1, 1, 0, 0, 1, 1, 1, 0, 1, 0, 1, 1, 0, 1, 1, 1,  
1, 0, 1, 0, 0, 1, 1, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 1, 0, 1, 
1, 1, 1, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 1, 1, 0, 0, 0, 1, 1, 
1, 0, 0, 0, 1, 1, 1, 1, 1, 1, 0, 0, 1, 1, 0, 1, 0, 1, 1, 0, 1, 1, 
1, 0, 0, 1, 0, 0, 1, 1, 0, 1, 1, 1, 0, 0, 0, 1, 0, 1, 0, 1, 1, 1, 
1, 1, 0, 0, 1, 0, 1, 1, 0, 1, 1, 1, 0, 1, 1, 0, 1, 1, 1, 1, 1, 1, 
0, 0, 0, 0, 0, 1, 0, 1, 0, 1, 0, 0, 1, 0, 0, 0, 0, 1, 1, 1, 1, 0, 
0, 0, 1, 1, 0, 1, 1, 0, 1, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 1, 
0, 0, 1, 0, 0, 0, 1, 0, 1, 0, 1, 0, 0, 1, 0, 1, 0, 0, 1, 0, 1, 1, 
0, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 0, 1, 0, 1, 0, 1, 1, 1, 1, 1, 
1, 1, 0, 0, 1, 0, 0, 1, 1, 1, 0, 0, 1, 1, 1, 1, 1, 0, 1, 1, 0, 1, 
0, 1, 1, 0, 1, 1, 1, 0, 1, 0, 1, 0, 1, 0, 0, 1, 1, 0, 0, 1, 0, 1, 
0, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 1, 0, 1, 1, 0, 1, 0, 0, 0, 0, 0, 
1, 0, 0, 1, 1, 0, 0, 1, 0, 1, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 1, 0, 
0, 0, 1, 1, 1, 0, 1, 0, 0, 1, 0, 0, 0, 1, 0, 0, 1, 0, 1, 1, 0, 1, 
0, 1, 0, 0, 1, 1, 0, 0, 1, 0, 1, 0, 0, 1, 0, 1, 1, 0, 1, 0, 0, 0, 
1, 1, 1, 0, 1, 0, 1, 1, 0, 1, 0, 1, 1, 1, 0, 
0}, {{1, -1, 1, -1, 1, -1, 1, -1, 1, -1, 1, -1, 1, -1, 1, -1, 
1, -1, 1, -1, 1, -1, 1, -1, 1, -1, 1, -1, 1, -1, 1, -1, 1, -1, 
1, -1, 1, -1, 1, -1, 1, -1, 1, -1, 1, -1, 1, -1, 1, -1, 1, -1, 
1, -1, 1, -1, 1, -1, 1, -1, 1, -1, 1, -1, 1, -1, 1, -1, 1, -1, 
1, -1, 1, -1, 1, -1, 1, -1, 1, -1, 1, -1, 1, -1, 1, -1, 1, -1, 
1, -1, 1, -1, 1, -1, 1, -1, 1, -1, 1, -1, 1, -1, 1, -1, 1, -1, 
1, -1, 1, -1, 1, -1, 1, -1, 1, -1, 1, -1, 1, -1, 1, -1, 1, -1, 
1, -1, 1, -1, 1, -1, 1, -1, 1, -1, 1, -1, 1, -1, 1, -1, 1, -1, 
1, -1, 1, -1, 1, -1, 1, -1, 1, -1, 1, -1, 1, -1, 1, -1, 1, -1, 
1, -1, 1, -1, 1, -1, 1, -1, 1, -1, 1, -1, 1, -1, 1, -1, 1, -1, 
1, -1, 1, -1, 1, -1, 1, -1, 1, -1, 1, -1, 1, -1, 1, -1, 1, -1, 
1, -1, 1, -1, 1, -1, 1, -1, 1, -1, 1, -1, 1, -1, 1, -1, 1, -1, 
1, -1, 1, -1, 1, -1, 1, -1, 1, -1, 1, -1, 1, -1, 1, -1, 1, -1, 
1, -1, 1, -1, 1, -1, 1, -1, 1, -1, 1, -1, 1, -1, 1, -1, 1, -1, 
1, -1, 1, -1, 1, -1, 1, -1, 1, -1, 1, -1, 1, -1, 1, -1, 1, -1, 
1, -1, 1, -1, 1, -1, 1, -1, 1, -1, 1, -1, 1, -1, 1, -1, 1, -1, 
1, -1, 1, -1, 1, -1, 1, -1, 1, -1, 1, -1, 1, -1, 1, -1, 1, -1, 
1, -1, 1, -1, 1, -1, 1, -1, 1, -1, 1, -1, 1, -1, 1, -1, 1, -1, 
1, -1, 1, -1, 1, -1, 1, -1, 1, -1, 1, -1, 1, -1, 1, -1, 1, -1, 
1, -1, 1, -1, 1, -1, 1, -1, 1, -1, 1, -1, 1, -1, 1, -1, 1, -1, 
1, -1, 1, -1, 1, -1, 1, -1, 1, -1, 1, -1, 1, -1, 1, -1, 1, -1, 
1, -1, 1, -1, 1, -1, 1, -1, 1, -1, 1, -1, 1, -1, 1, -1, 1, -1, 
1, -1, 1, -1, 1, -1, 1, -1, 1, -1, 1, -1, 1, -1, 1, -1, 1, -1, 
1, -1, 1, -1, 1, -1, 1, -1, 1, -1, 1, -1, 1, -1, 1, -1, 1, -1, 
1, -1, 1, -1, 1, -1, 1, -1, 1, -1, 1, -1, 1, -1, 1, -1, 1, -1, 
1, -1, 1, -1, 1, -1, 1, -1, 1, -1, 1, -1, 1, -1, 1, -1, 1, -1, 
1, -1, 1, -1, 1, -1, 1, -1, 1, -1, 1, -1, 1, -1, 1, -1, 1, -1, 
1, -1, 1, -1, 1, -1, 1, -1, 1, -1, 1, -1, 1, -1, 1, -1}}}}

To test that this really is a solution:

Table[RotateLeft[res[[1, 1]], k].res[[1, 2, 1]], {k, 1, n}]

results in

 {0, 0, 0, ..., 0, 0, 0}

Multiple solutions can occur and require some polishing, but all is easily done in polynomial time.

Improve this answer
$\endgroup$
11
  • 1
    $\begingroup$ Thank you for this! Does your approach extend to partial circulant matrices (as the bounty offerer seems to be interested in these)? A partial circulant matrix is just the first $m \leq n$ rows of a circulant matrix. $\endgroup$
    – Simd
    Commented Nov 24, 2014 at 20:37
  • 1
    $\begingroup$ I ran your code on various $n$. The output suggests that positive answers occur only when either the first row of the matrix or the vector are periodic, with period properly dividing $n$. If so, that would probably establish polynomial time easily. $\endgroup$
    – user44143
    Commented Nov 25, 2014 at 2:56
  • 1
    $\begingroup$ Thank you as well. I have been working through it and I don't yet understand why "If a solution exists then all $v_k\in\{-1,0,1\}$." is true. I would be very grateful if you could expand this part. I would also be very interested to know if this approach worked for matrices with fewer rows than columns. $\endgroup$
    – Simd
    Commented Nov 25, 2014 at 12:05
  • 1
    $\begingroup$ What happens if $C$ is highly degenerate? I mean, how is the new system any better than the old one except you know that you have 1 in the first position (which, after all, is not a big deal because if you are totally stupid and just say that it is somewhere, all you lose is a factor of $n$). Am I missing something? $\endgroup$
    – fedja
    Commented Nov 26, 2014 at 22:53
  • 1
    $\begingroup$ @fedja I also don't get it unless it turns out that $\{0,1\}$ square circulant matrices have a non-zero $\{-1,0,1\}$ vector in their kernel if and only if they are singular. I wrote some code to look at small cases and the relationship holds for them. Do you think it could be true in general? $\endgroup$
    – Simd
    Commented Nov 27, 2014 at 10:46
1
$\begingroup$

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:

  1. 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.

  2. 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.

Improve this answer
$\endgroup$
12
  • $\begingroup$ Yes, but how many linear equations? If it's one system of equations for each vector, that's $3^n$ systems of equations, and one may not consider that to be efficient. Or am I misunderstanding your answer? $\endgroup$
    – Gerry Myerson
    Commented May 28, 2014 at 23:36
  • $\begingroup$ @Gerry, you are quite right, of course. I don't know what the OP considers efficient, so I can't say any more... $\endgroup$
    – Nick Gill
    Commented May 29, 2014 at 0:20
  • 6
    $\begingroup$ If you consider $3^n$ to be an efficient time, then you might as well just check all $\{-1,0,1\}$-vectors. $\endgroup$
    – Richard Stanley
    Commented May 29, 2014 at 0:45
  • $\begingroup$ ha! good point! $\endgroup$
    – Nick Gill
    Commented May 29, 2014 at 1:02
  • 1
    $\begingroup$ @dorothy: That’s quite unlikely. It is generally believed that NP-complete problems require exponential-size circuits, and it would be a major result to show the opposite. $\endgroup$
    – Emil Jeřábek
    Commented Jun 1, 2014 at 16:43

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .