I'm looking for solutions, $\vec{x}$, in $A\vec{x}=\vec{b}$ such that $||\vec{x}||_1$ is a minimum and $\vec{b}$ must have all even elements.
The A matrix is: $\begin{pmatrix}1&1&0&1&0&0\\1&1&0&0&0&0\\0&0&1&0&0&1\\1&0&0&1&1&0\\0&0&0&1&1&1\\0&0&1&0&1&1\end{pmatrix}$
I stumbled across a puzzle in a game and set $\vec{b}$ to the zero vector for a solution but I'm curious: is there a way, other than brute force combinations, to find "the fewest lever pulls" (i.e. $||\vec{x}||_1$) solution?
--EDIT--
To expand on the idea, here's a more involved situation which may demonstrate what I'm looking to answer:
Imagine three concentric circles with a single marker on each and six levers which may be pulled down or pushed up to rotate them. When a lever is pulled/pushed(+/-), circles(s) will rotate (clockwise [-] and counterclockwise [+]) so that the markers will end in one of four positions- North, South, West, and East (modulo 4 {0, 2, 1, 3}, respectively). Consider the following A matrix...
$\begin{pmatrix}1&0&0&-1&0&1\\0&1&0&1&1&0\\0&0&1&1&-1&1\end{pmatrix}$
...where column 1 indicates that "pulling down (+) lever 1 will move the innermost circle counterclockwise one position", column 4 indicates "pulling down (+) lever 4 will rotate the innermost ring CW 1, middle ring CCW 1, and outermost ring CCW 1", and so on.
So, obviously, I'd be able to achieve any desired final position configuration by only using levers 1, 2, and 3. My questions:
- What would be the problem setup to find the optimal lever pull combination and directions (i.e. fewest possible lever pulls/pushes total)?
- How would I take into account the repeating positions and directions? For example, given a random initial configuration, say that I want the inner ring to point North (0), the middle to point West (1), and the outer to point East (3). Maybe the fastest way to East (position 3 in modulo 4) is actually "-1" in its movement (i.e. instead of rotating 3 times CCW, it is just 1 rotation CW). If that makes sense?
Over the field $\Bbb Z_2 $ (integers modulo $2$) the inverse of $A$ is well defined and:
$$A^{-1} = \begin{pmatrix} 1&1&1&1&0&1\\1&0&1&1&0&1\\1&1&0&0&1&1\\1&1&0&0&0&0\\0&0&1&0&0&1\\1&1&1&0&1&1 \end{pmatrix} $$ As such, if $b$ is required to be a vector of ones, $x = A^{-1}b$: $$x = \begin{pmatrix} 1\\0\\0\\0\\0\\1 \end{pmatrix}$$
Which you can also check yourself since if I understand correctly, by flipping the first and last switch it is very evident that all lights will turn on. The method used is overkill in this case, but it very easily generalises (given enough computational power) for much more complicated problems. The solution is unique (so there is no minimising to do assuming you don't flip a switch twice!) and order doesn't matter.