We are given an $18\times 18$ table, all of whose cells may be black or white.

Question

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!

Answer 1

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$...)

Answer 2

Changing all entries of a row or column is equivalent to adding a row of all 1's to that row or adding a column of all 1's to that column (modulo 2). Suppose we have added $k$ rows and $l$ columns of all 1's to the zero matrix and have obtained a matrix with exactly 16 entries equal to 1. First note that we can eliminate two equal rows (addition is commutative and two equal rows add up to zero modulo 2). So we can assume all the rows are different and all the columns are different. In particular $0\leq k,l\leq 18$.

Now, by adding $k$ different rows of all 1's and $l$ different columns of all 1's we get exactly $18k+18l-kl$ entries equal to 1. So we want $$18k+18l-kl=16,~0\leq k,l \leq 18.$$ To solve this, rewrite it as $(18-k)(18-l)=18^2-16=4*7*11$. Since the product of every two of the numbers 4, 7, and 11 exceeds 18, this equation has no solutions within the required range.

Answer 3

Yes, this proof looks good to me.