I'm a person who is preparing graduated school in Korea.
My English may be not enough.
Please understand.
This site is my only hope.
I'm trying to solve this question.(with MATLAB)
But, I couldn't figure out the second question (b).
The question is like this.
(Question from "Linear Algebra – A modern introduction" by David Poole 2nd Edition, 2.4 – Question Number 29)
==========(Question)===========
Fig. 1
Fig. 2
The array is composed of $3 \times 3$ squares that can be either white or black.
When I choose a square, the status of this square and some adjacent squares are affected.
To explain more specificaly, see the second figure.
When a square is selected (signaled by a circle), the status of neighboring squares with "*" is changed. (black -> white or white -> black)
The objective of this puzzle is to make every square black.
(a) If initial status is like figure 1, show that this game is won, and explain the process.
(b) No matter what the initial status, show that the game is always won.
==========(Question)===========
To solve this question, I made a $9 \times 9$ matrix explaining how squares change their status.
For example, if I choose square #1, then #1,#2,#4,#5 will change their status. I render this under the form of a vector.
[1 1 0 1 1 0 0 0 0]
Number 1 means : status is changed and 0 means status is kept.
If instead of square #1, I choose another square, I'll get another vector. I gather these vectors into a $9 \times 9$ matrix.
I'll call this matrix "Action Matrix".
1 1 0 1 1 0 0 0 0
1 1 1 0 0 0 0 0 0
0 1 1 0 1 1 0 0 0
1 0 0 1 0 0 1 0 0
0 1 0 1 1 1 0 1 0
0 0 1 0 0 1 0 0 1
0 0 0 1 1 0 1 1 0
0 0 0 0 0 0 1 1 1
0 0 0 0 1 1 0 1 1
And I made another matrix which represents status of square, and this is a $1 \times 9$ matrix. If square is black, I express with number 1, if square is white, I use number 0.
(For example, the status of figure 1 is expressed like this
[1 0 0 0 1 0 0 0 1])
I'll call this matrix "Status Matrix".
For question (a),
In order to make every square black, I considered the squares that need to be changed, and I made a new Status Matrix like below.
[0 1 1 1 0 1 1 1 0]
After transposing this matrix, combine Action matrix and Status matrix to make a new augmented matrix.
After that, I just solve this augmented matrix using MATLAB.
Then MATLAB gives me the answer like below.
1 0 0 0 0 0 0 0 0 0
0 1 0 0 0 0 0 0 0 0
0 0 1 0 0 0 0 0 0 1
0 0 0 1 0 0 0 0 0 0
0 0 0 0 1 0 0 0 0 0
0 0 0 0 0 1 0 0 0 0
0 0 0 0 0 0 1 0 0 1
0 0 0 0 0 0 0 1 0 0
0 0 0 0 0 0 0 0 1 0
So, if I choose square #3, #7, I can win.
I think that I have solved this question.
But the problem is (b).
If I can show that every single square is changed by some actions, I think that I prove this question.
But the result is different from my expectation.
I made Status matrices which express change of only one square about each 9 squares.
Then MATLAB gave me answers with rational number and negative.
I think that this result means "impossible change".
Because we can't choose 0.4 times or -0.6 times.
But, the question implies me this puzzle always be won.
Am I wrong ? or is the book wrong?
Actually, it is hard for me to ask question in English.
But I want to know answer.
I think that many geniuses here can help me.
Thank you for reading this word.
Have a nice day~
Best Answer
A first remark is that it is a variant of "Lights Out" Puzzle https://gaming.stackexchange.com/q/11123 http://perfectweb.org/ddo/solver/vale_puzzle.html
The $3 \times 3$ board can be in $2^9=512$ possible "status" (plural of "status" looks to be ... "status"), each status being encoded by a $9$ bits column vector (with your convention $0\to$"white" and $1\to$"black").
The mathematical framework for studying this game is vector space $\mathbb{F}^9$ over finite field $\mathbb{F}=\{0,1\}$ ; its additive operation $\oplus$ that is called "xor" (exclusive or), alias "adding mod $2$" accounts for toggling operation ($0 \leftrightarrow 1$).
More precisely, "toggling" operation can be described as "adding $1$", i.e., by using implicitly transformation $x \to x \oplus 1$ which changes $0 \to 1$ and $1 \to 0$ .
In this way, a move from status $s_1$ to another $s_2$ under a certain action (for example the first one) "a" fits into this framework :
$$s_1+a=s_2 \ \ \iff \ \ \begin{pmatrix}1\\0\\0\\1\\0\\0\\0\\0\\0\end{pmatrix}\oplus \begin{pmatrix}1\\1\\1\\0\\0\\0\\0\\0\\0\end{pmatrix}= \begin{pmatrix}0\\1\\1\\1\\0\\0\\0\\0\\0\end{pmatrix}$$
The matrix of "actions" will then be presented columnwise (instead of linewise as you did) as the gathering of actions $a_1,a_2,\cdots a_9$ under the form of a matrix :
$$A=\begin{pmatrix} 1&1&0&1&0&0&0&0&0\\ 1&1&1&0&1&0&0&0&0\\ 0&1&1&0&0&1&0&0&0\\ 1&0&0&1&1&0&1&0&0\\ 1&0&1&0&1&0&1&0&1\\ 0&0&1&0&1&1&0&0&1\\ 0&0&0&1&0&0&1&1&0\\ 0&0&0&0&1&0&1&1&1\\ 0&0&0&0&0&1&0&1&1 \end{pmatrix}.$$
The following solution is based on a double interpretation of the product $AV$ of matrix $A$ and any vector $V$ with $9$ coordinates $0/1$.
Proposition 1 : $A_1,A_2,...A_9$ constitute a basis of $\mathbb{F}^9$.
Proof : $\det(A)=1$ (technically, using for example Matlab, we have to do it in two steps $\det(A)=5$, then mod$(\det(A),2)=1$). This determinant is not $0$, thus all actions are linearly independent ; as there are $9$ actions and the dimension of vector space $\mathbb{F}^9$ is $9$, they constitute a basis. $\square$
Thus, in particular, any "position" vector can be expressed as a linear combination of $A_1, A_2, ... A_9$, moreover in a unique manner.
These linear combinations have an interpretation as successive actions ; for example, combining actions $A_1$ and $A_4$ is the same as the linear combination :
$$1A_1+0A_2+0A_3+1A_4+0A_5+0A_6+0A_7+0A_8+0A_9$$
(intuitive interpretation : coefficient 1 = I take, coefficient 0 = I don't take). But the expression above can be rendered as the application of matrix $A$ to the column vector $V$ with components $1,0,0,1,0,0,0,0,0$ as shown below :
$$AV=\begin{pmatrix} 1&1&0&1&0&0&0&0&0\\ 1&1&1&0&1&0&0&0&0\\ 0&1&1&0&0&1&0&0&0\\ 1&0&0&1&1&0&1&0&0\\ 1&0&1&0&1&0&1&0&1\\ 0&0&1&0&1&1&0&0&1\\ 0&0&0&1&0&0&1&1&0\\ 0&0&0&0&1&0&1&1&1\\ 0&0&0&0&0&1&0&1&1 \end{pmatrix}\begin{pmatrix} 1\\ 0\\ 0\\ 1\\ 0\\ 0\\ 0\\ 0\\ 0 \end{pmatrix}.$$
What we have done for this particular case can be extended to any $V$ with coordinates $v_1, v_2, ... v_9 \in \mathbb{F}^9$, otherwise said with all possible linear combinations :
$$v_1a_1+v_2a_2+...+v_9a_9 \ \ \text{where} \ \ v_i=0,1 \tag{1}$$
In this way, we can generate $2^9$ such linear combinations (no one is the same due to the unicity of decomposition onto a basis) ; we can represent all the possibilities by a binary tree with $2^9$ "leaves" as shown on figure 1.
Fig. 1 : A way to consider $\mathbb{F}^9$ as a tree with $2^9$ (very agglomerate !) leaves, the traversal of this tree from left to right to a given leaf giving the decomposition of the leaf into the sum (= linear combination) of certain $A_k$s.
In this way, we cover the totality of vector space $\mathbb{F}^9$. We have thus proven the following proposition :
Proposition 2 : Each "status" of the $3 \times 3$ board can be written $S=AV$ for a certain (unique) $V$.
Proposition 3 : Being given two status represented by $AV_1$ and $AV_2$, one can always find a sequence of actions that change $AV_1$ into $AV_2$. Moreover this sequence is given by the "ones" coefficients in $V_2-V_1$. We have thus a winning strategy !
Proof : We are looking for a column vector $W$ such that $AV_1+W=AV_2$ ; i.e., we want to express
$$W=AV_2-AV_1 = A(V_1-V_2) \tag{2}$$
as a linear combination of $V_1,V_2,...V_9$ ; we know that this combination exists because $V_1,V_2,...V_9$ is a basis ; but looking at the last expression in (2), it is served on a tray taking Prop. 2 into account : in fact entries "$1$ "in $V_2-V_1$ indicate which "actions" are to be used... $\square$
Remark : Being given a status vector $S$, how can it be written under the form $S=AV$ ? Simply take $V=BS$ with $B$ being the inverse of matrix $A$.
Here is a very simple Matlab program implementing this method :
Other remarks :
The order of actions doesn't matter due to the commutativity of sum $\oplus$.
We have obtained a stronger result than the fact that status "$111111111$" can be reached : all status can be reached.
The inverse $B=A^{-1}$ (see program) has been obtained with the following composite instruction using the so-called "adjugate" matrix :
B = mod(round(det(A)*inv(A)),2)
To be read in a second step : A very different method :
We have been lucky here that the vector space of configurations being $9$-dimensional, there are precisely $9$ rules (the same figure) with the further property that they are linearly independent and, moreover, that the toggling rule $0 \leftrightarrow 1$ is rendered by the "xor" operator.
If such had not been the case, I would have proposed you to switch to another data representation, i.e., an oriented graph with :
$2^9=512$ vertices, each vertex corresponding to a possible "status" of your $3 \times 3$ board.
two vertices $(V_1,V_2)$ being connected by an edge whenever $V_2$ results from $V_1$ by applying some of the given rules.
Now, the initial issue is converted into this one : show that the special vertex "$111111111$" ("all squares black", binary notation is very handy here) can be reached from any other vertex (or, in an equivalent way, reversing all orientations, can one proceed from vertex "$111111111$" to any other one).