What would be an algorithm to shut down all lamps? I found an algorithm problem that I was unable to solve from http://www.ohjelmointiputka.net/postit/tehtava.php?tunnus=muslam. I guess as it requires linear algebra, this might a correct place to ask an algorithm.
We have $n$ lamp to form a circular loop with $n$ on/off switches. At the beginning, some lamps are on, denoted by the bit 1 and some are off, denoted by the bit 0. We have been given an integer $m$. Pressing each switch changes the state of the lamp that correspond the switch and its $m$ nearest lamps in each direction. Find out how many switches one has to press to shut down all the lamps and give a list of the pressed switches.
I tried to think that I need to solve a matrix equation over $\mathbb Z/2\mathbb Z$ but found out that the coefficient matrix I made has no inverse. I thought that I need a coefficient matrix such that $A_{i,j}=1$ if pressing switch $i$ changes the lamp state $j$ and $A_{i,j}=0$ if it does not change. 
Here is my code for the case there are six lamps with initial states 101101 and every switch affects to the given lamp and one of its nearest lamps in both directions.
# Generate the zero matrix
def generate_matrix(w, h):
    return [[0 for x in range(w)] for y in range(h)]

# Print matrix
def print_matrix(A):
    for row in range(0,len(A[0])):
        line = ""
        for col in range(0,len(A[0])):
            line += str(A[row][col])
            if col == len(A[0]):
                line += "\n"
        print(line)

# Swap two rows
def swap_rows(A,i,j):
    for k in range(0,len(A[0])):
        temp = A[k][i]
        A[k][i] = A[k][j]
        A[k][j] = temp
    return A

# Add one row to another
def mult_rows(A,i,j):
    for k in range(0,len(A[0])):
        A[k][j] += A[k][i]
    return A

# Distance between two indices
def dist(i,j,n):
    d1 = max(i-j,j-i)
    dist_beg = min(i,j)
    dist_end = n-max(i,j)
    d2 = dist_beg + dist_end
    return min(d1,d2)

# Initialize the coefficient matrix
def gen_coeff_matrix(n,effect_width):
    A = generate_matrix(n,n)
    for i in range(0,n):
        for j in range(0,n):
            if dist(i,j,n) <= effect_width:
                A[i][j] = 1
    return A

# Initialize the unit matrix
def init_unit_matrix(n):
    A = generate_matrix(n,n)
    for i in range(0,n):
        A[i][i] = 1
    return A

# Inverse of the matrix
def inv(M):
    n = len(M[0])
    U = init_unit_matrix(n)
    for column in range(0,n):
        if M[column][column] == 0:
            i = 1
            while M[column+i][column+i] != 0:
                ++i
            swap_rows(A,column,column+i)
            swap_rows(U,column,column+i)
        for c in range(0,n):
            if M[c][column] == 1:
                if c != column:
                    mult_rows(M,c,column)
                    mult_rows(U,c,column)
    return U

A = init_unit_matrix(5)
B = gen_coeff_matrix(6,1)
print_matrix(B)

It gives the matrix
110001
111000
011100
001110
000111
100011

but it is not invertible according to Sage:
sage: F = FiniteField(2)
sage: C = Matrix(F,[[1,1,0,0,0,1],[1,1,1,0,0,0],[0,1,1,1,0,0],[0,0,1,1,1,0],[0,0,0,1,1,1],[1,0,0,0,1,1]])
sage: C
[1 1 0 0 0 1]
[1 1 1 0 0 0]
[0 1 1 1 0 0]
[0 0 1 1 1 0]
[0 0 0 1 1 1]
[1 0 0 0 1 1]
sage: C^(-1)
---------------------------------------------------------------------------
ZeroDivisionError                         Traceback (most recent call last)
<ipython-input-4-48e78ab0a5de> in <module>()
----> 1 C**(-Integer(1))

sage/matrix/matrix0.pyx in sage.matrix.matrix0.Matrix.__pow__ (/usr/lib/sagemath//src/build/cythonized/sage/matrix/matrix0.c:36015)()

sage/structure/element.pyx in sage.structure.element.generic_power_c (/usr/lib/sagemath//src/build/cythonized/sage/structure/element.c:29266)()

sage/matrix/matrix_mod2_dense.pyx in sage.matrix.matrix_mod2_dense.Matrix_mod2_dense.__invert__ (/usr/lib/sagemath//src/build/cythonized/sage/matrix/matrix_mod2_dense.c:7868)()

ZeroDivisionError: Matrix does not have full rank.

I also tried with the following command:
sage: V=Matrix(F,[[1,0,1,1,0,1]])
sage: C\V

ValueError: number of rows of self must equal number of rows of B

Questions: Is this the right way to think about the problem? Is there a mistake in the reasoning how to make the coefficient matrix? Is the just a silly bug in my code?
 A: You are thinking about it in exactly the right way.  Multiplying your matrix by a vector will show what lights are on if you start with the lights all off and flip the switches represented by $1$s in the vector.  Then if you invert the matrix and multiply it by the starting state you will find out how to go from your starting state to all off.  The fact that your matrix is not invertible says there are states that you cannot get to the starting state from.  You can see the matrix is not invertible because the first and fourth lines sum to $[1\ 1\ 1\ 1\ 1\ 1]$ as do the second and fifth and the third and sixth.  You can still do Gaussian elimination to see of your initial state can reach all off.  The problem comes because the number of lights affected is not coprime with the number of lights.  Try it with eight lights instead of six and I believe you will find a working solution.  In your case none of the switches changes the number of lights that are on $\bmod 3$.  As you are starting with four on, you can't get to all off.  The linear algebra is not necessary, but it is a good way to attack it.  An intermediate approach is to try to find by hand a way to turn off a single lamp.  Any given lamp can be turned off by rotating the set of switches you use for the first lamp.  If you have a number of lamps to switch, just collect the list of switches for each lamp, remove duplicates in pairs, and you are done.  You are finding a basis for the vector space here.
