We are given an $18\times 18$ table, all
of whose cells may be black or white. Initially all the cells are
colored white. We may perform the following operation: choose one
column or one row and change the color of all cells in this column
or row. Is it possible by repeating the operation to obtain a
table with exactly $16$ black cells?
Now I wonder if a following solution is correct?
All the matrix here are $18\times 18$. Let $S$ be a matrix with all entry $1$ and $F$ be a matrix with exactly $16$ entries with $0$ and the other entries are $1$.
Let $A_i$ be a matrix with all entries $1$ on $i$-th row, for $1\leq
i\leq 18$ and the other are 0 and with all entries $1$ on
$(i-18)$-th column for $19\leq i\leq 36$ and the other are zero.
So, for example:
$$A_2 =\begin{bmatrix}
0 & 0 & \dots & 0&0\\
1&1&\dots &1&1\\
0 & 0 & \dots & 0&0\\
\vdots & \vdots & \dots & \vdots &\vdots\\
0 & 0 & \dots & 0&0
\end{bmatrix}
\;\;\;{\rm and}\;\;\; A_{19} =\begin{bmatrix}
1 & 0 & \dots & 0&0\\
1&0&\dots &0&0\\
1 & 0 & \dots & 0&0\\
\vdots & \vdots & \dots & \vdots &\vdots\\
1 & 0 & \dots & 0&0
\end{bmatrix}
$$
We can understand a table as a matrix with entry $1$ if
corresponding cell is white and $0$ if it is black. So $S$ is a
starting matrix and $F$ a final matrix. Now each recoloring of a
given matrix $M$ is actually $M+A_i$ for some $i\leq 36$
So after some transformations we have equality like this $$F = S +
a_1A_1+a_2A_2+…+a_{36}A_{36}$$ where $a_i\in \{ 0,1\}$ for all
$i$. Mark $F-S = D$, so $D$ is a matrix with exactly $16$ ones.
Now what can we say about $a_1,a_2,…$? Since $D$ has exactly $16$
ones it must have at least two columns and two rows with only
zeros. We can assume that all entries in first $2$ rows and first $2$
columns are $0$, so $D$ is like:
$$ D =\begin{bmatrix}
0 & 0 & 0&\dots & 0&0\\
0 & 0 &0 &\dots &0&0\\
0 & 0 & *& \dots & *&*\\
\vdots & \vdots & \vdots & \dots &\vdots& \vdots\\
0 & 0 & *&\dots & *&*
\end{bmatrix}
$$
If $a_1=1$ then each $a_{19},a_{20},…a_{36}$ must also be $1$
since in first row must be all $0$. But then we must have also
$a_2,…,a_{18}$ all $1$ since in first column are only $0$. This
means that $D$ is a zero matrix which is not true. So $a_1=0$ and thus
all $a_{19},a_{20},…a_{36}$ are $0$ and then also all
$a_2,…,a_{18}$ are $0$ so $D$ is zero matrix again. A
contradiction.
This is not a duplicate. I don't want a solution like in that link, I want a proof verification!
Best Answer
Let $V$ be the vector space over the field with two elements, $\Bbb F_2$, generated by all matrices of shape $N\times N$, $N=18$, which have exactly one row, or exactly one column with one entries, all other entries being zero. We consider the following map from $V$ to $\Bbb F_2$:
$X$ in $V$ is mapped to $$ f(X)= (x_{11}+x_{22}+\dots+x_{N-1,N-1}+x_{N,N}) + (x_{12}+x_{23}+\dots+x_{N-1,N}+x_{N,1})\ . $$ (Sum on two consecutive fixed diagonals of $X$, where the indices are considered modulo $N$.)
Then each generator of $V$ is mapped to zero, since the "bits" taken in $f(X)$ are exactly two in each row and/or column. So $f$ vanishes on $V$. But it does not vanish on any quadratic submatrix $A=A(I)$ with ones exactly on the positions $I\times I$, $I$ being a proper interval of $\{1,2,\dots,N\}$. (For instance $I=\{1,\dots,16\}$ for our $N=18$.)
So in our case the answer to the problem is negative. (The "change of the color on a line/columns" corresponds to adding a generator of $V$ to a matrix. We are starting with a zero matrix. The matrices that can be obtained are exactly those in the vector space $V$ of dimension $N+N-1$.)
Note: I can provide some simple computer check in sage, if needed.
Later edit: It is simpler to test the equations $$ x_{is}-x_{js}-x_{it}+x_{jt}=0\ ,\qquad 1\le i<j\le N\ ,\ 1\le s<t\le N\ , $$ that can be extracted from all $2\times 2$ minors of a matrix $X$ in order to test/decide if a matrix $X$ can be realized. (The minus is also a plus, but makes it simpler to see that e.g. each of the above "one row matrix of ones" satisfy the equation, explicitly $1-1-0+0=0$, and correspondingly for the column matrices in the base of $V$...)