How to prove there are unreachable states in this bit flipping algorithm only for lengths $n=3k+2$?

Question

This is similar to Bit flipping algorithm, but the algorithm is a little different. Specifically, we have bit string of length $n$, and we can choose any bit to flip and then we flip also the two surrounding bits, if there are any. So we can either flip three consecutive bits inside or flip the left-most/right-most two bits. For example for $n=3$ we can draw transitions between states in a graph:

Now if we make a graph for $n=2$, the graph splits into two non-connected isomorphic sub-graphs as shown:

The same occurs for $n=2,5,8,11,14$, so I assume it holds for $n=3k+2$. For other $n$'s it is a graph with single connected component. Can we prove that the graph splits for $n\equiv 2 \pmod 3$?

My attempts:

I was trying to find some attribute that is invariant for the bit flipping and show that there are two states with this attribute being different (for $n=3k+2$ that is). This is easy for $n=2$ case as we can see that bits parity is always preserved. However the same does not work for $n=5$: as an example there are two states such as $00100$ and $00010$ that cannot be reached from one another, but bits have the same parity. There is probably some simple argument for this, but I don't see it.

By the way here is a Python code that can be used to generate such graphs, it requires graphviz:

length=5

def flip(N, bit):
    pattern = 3 if bit == 0 else 7 << bit-1
    return (N ^ pattern) & ((1 << length)-1)

def binary(n):
    return format(n, '0%ib' % length)[::-1]

from graphviz import Graph
dot = Graph()

for v1 in range(2**length):
    for b in range(length):
        v2 = flip(v1, b)
        if v1 <= v2:
            dot.edge(binary(v1),binary(v2),str(b+1)+".")
dot.render('graph_complete%i' % length, view=True)

Answer 1

Almost complete solution, or at least a very broad hint

This is a 1D version of the game "lights out". Philip Klein in his book on The Matrix in Computer Science has a nice analysis for the 2D case that should apply here. But the gist is this:

Start from any bit vector in $F^k$ where $F$ is the field of 2 elements. Applying an operation amounts to adding to it one of the $k$ vectors $$ \pmatrix{1&1&0&\ldots& 0} \\ \pmatrix{1&1&1&\ldots& 0} \\ \pmatrix{0 & 1&1&1&\ldots& 0} \\ \pmatrix{0 & 0 & 1&1&1&\ldots& 0} \\ \vdots\\ \pmatrix{0 & \ldots&1&1&1& 0} \\ \pmatrix{0 & \ldots & 0 &1&1&1} \\ \pmatrix{0 & \ldots & 0 &0&1&1} \\ $$ so you can put these in a matrix, row-reduce it, and compute its rank. If the rank is not $k$, then not every target bit-vector is reachable from the all-zero vector, and your graph has at least two components.

Row reduction for this matrix appears to be relatively simple and methodical. Give it a shot.

Answer 2

Based on @JohnHughes answer, I was able to prove this. Basically the matrix corresponding to the vectors is actually a Tridiagonal matrix, for which determinant is well known and is given by recurrence formula $$ f_n=f_{n-1}-f_{n-2}\, ,f_0=1\, , f_{-1}=0 $$ which gives a sequence of (starting from $n=1$) $$ 1,0,-1,-1,0,1,1,0,-1,-1,\dots $$ which can be easily seen to be $0$ for $n=3k+2$, so there the rank of the matrix is $<n$ and not all states can be reachable by these linear combinations.