10
$\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.

$\endgroup$
  • 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 May 29 '14 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$ – dorothy May 30 '14 at 7:18
  • 3
    $\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$ – Matt F. May 31 '14 at 23:54
  • 1
    $\begingroup$ @MattF. — (And the union of $T$ and $U$ should be non-empty.) $\endgroup$ – jmc Jun 5 '14 at 10:02
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.

$\endgroup$
  • 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$ – dorothy Nov 24 '14 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$ – Matt F. Nov 25 '14 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$ – Raphael Nov 25 '14 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 Nov 26 '14 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$ – Raphael Nov 27 '14 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.

$\endgroup$
  • $\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 May 28 '14 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 May 29 '14 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 May 29 '14 at 0:45
  • $\begingroup$ ha! good point! $\endgroup$ – Nick Gill May 29 '14 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 Jun 1 '14 at 16:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.