Place $n^2$ coins on an $n\times n$ board, all coins in the grid are heads at the beginning.
Then makes a series of moves; for each move, select one column and one row, flip over all coins in the selected column and row. After that we will get a configurations of coins. For each configuration, we have a way that use the fewest number of moves to achieve. What I want to know is how to prove that, without considering the order of moving, such way of fewest moving is unique.
For example, for the first move, we choose the $1$st column and $1$st row, and then we choose the $2$nd column and $2$nd row. This will leads to a configuration that all coins in the first and second rows and columns are tails, except coins at position $(1,2)$ and $(2,1)$. And this is the minimum number of moves to achieve such configuration. But is this way of moving unique, are there other ways to make the coins reach the same configuration with also $2$ moves?
Flip the coins in the same row and column on a board of $n \times n$ grids.
combinatoricsdiscrete mathematics
Best Answer
$\def\eqd{\stackrel{\text{def}}{=}} $ This is a problem in linear algebra over the field $\ \Bbb{F}_2\ $ of numbers $\ 0,1\ $ under addition and multiplication mod $2$. Any $\ n\times n\ $ configuration of coins can be represented by an $\ n\times n\ $ matrix whose entry in its $\ i^\text{th}\ $ row and $\ j^\text{th}\ $ column is $\ 0\ $ if the coin in the corresponding row and column of the coin configuration shows heads or $\ 1\ $ if that coin shows tails.
If you modify a configuration represented by the matrix $\ A\ $ by flipping all the coins in the $\ i^\text{th}\ $ row and $\ j^\text{th}\ $ column, then the matrix $\ B\ $ representing the new configuration will be given by $$ B=A+M(i,j)\ $$ where $\ M(i,j)\ $ is the $\ n\times n\ $ matrix with $\ 1$s along its $\ i^\text{th}\ $ row and down its $\ j^\text{th}\ $ column. Thus, if your target configuration is represented by the matrix $\ T\ $, then your problem is equivalent finding the smallest number $\ m\ $ of matrices $\ M\big(i_1,j_1\big), M\big(i_2,j_2\big),\dots,M\big(i_m,j_m\big)\ $ such that $$ T=\sum_{k=1}^mM\big(i_k,j_k\big)\ .\label{eq1}\tag{1} $$ When $\ n\ $ is even, the set $\ \big\{\,M(i,j)\,|\,1\le i,j\le n\,\big\}\ $ of matrices is linearly independent, and spans the space of $\ n\times n\ $ matrices over $\ \Bbb{F}_2\ $, so for any such matrix, there's a unique set $\ \big\{M\big(i_1,j_1\big), M\big(i_2,j_2\big),\dots,M\big(i_m,j_m\big)\big\}\ $ of distinct matrices $\ M\big(i_k,j_k\big)\ $ such that equation \eqref{eq1} holds, and $\ m\ $ will then be the minimum number of moves needed to obtain the configuration with matrix $\ T\ $.
When $\ n\ge3\ $ is odd, the set $\ \big\{\,M(i,j)\,|\,1\le i,j\le n\,\big\}\ $ of matrices is linearly dependent, so there will be configurations which will be impossible to reach, and for those configurations that are reachable, there will always be more than one set of distinct matrices $\ M\big(i_k,j_k\big)\ $ for which equation \eqref{eq1} holds and there may well be more than one of minimum size. If $\ e_i\ $ is the $\ i^\text{th}\ $ column of the $\ n\times n\ $ identity matrix, and $\ \mathbf{1}\eqd\sum_\limits{i=1}^ne_i\ $ the $\ 1\times n\ $ column vector all of whose entries are $\ 1\ $, then $$ M(i,j)=e_i\mathbf{1}^T+\mathbf{1}e_j^T+e_ie_j^T\ , $$ and \begin{align} \sum_{i=1\\i\ne s}^nM(i,t)&+\sum_{j=1\\j\ne t}^nM(s,j)\\ &=\sum_{i=1\\i\ne s}^n\big(e_i\mathbf{1}^T+\mathbf{1}e_t^T+e_ie_t^T\big)+\sum_{j=1\\j\ne t}^n\big(e_s\mathbf{1}^T+\mathbf{1}e_j^T+e_se_j^T\big)\\ &=\big(e_s+\mathbf{1}\big)\big(\mathbf{1}+e_t\big)^T+(n-1)\mathbf{1}e_t^T\\ &\hspace{1em}+(n-1)e_s\mathbf{1}^T+\big(e_s+\mathbf{1}\big)\big(\mathbf{1}+e_t\big)^T\\ &=(n-1)\big(e_s\mathbf{1}^T+\mathbf{1}e_t^T\big)\\ &=\cases{0&if $\ n\ $ is odd\\ e_s\mathbf{1}^T+\mathbf{1}e_t^T=\\ M(s,t)+e_se_t^T&if $\ n\ $ is even.} \end{align} Thus, when $\ n\ge3\ $ is odd, the set of matrices $\ M(i,j)\ $ is linearly dependent. When $\ n\ $ is even, $$ e_se_t^T=M(s,t)+\sum_{i=1\\i\ne s}^nM(i,t)+\sum_{j=1\\j\ne t}^nM(s,j)\ , $$ and since the matrices $\ e_se_t^T\ $ span the space of $\ n\times n\ $ matrices over $\ \Bbb{F}_2\ $, then so do the matrices $\ M(i,j)\ $. Since there are only $\ n^2\ $ matrices in the set $\ \big\{\,M(i,j)\,|\,1\le i,j\le n\,\big\}\ $, and they span a space of dimension $\ n^2\ $ they must be linearly independent.
Here's an example of non-unique minimal solutions for $\ n=3\ $. \begin{align} \pmatrix{0&0&0\\0&1&1\\0&1&1}&= \pmatrix{1&0&0\\1&1&1\\1&0&0}+\pmatrix{1&0&0\\1&0&0\\1&1&1}\\ &=\pmatrix{1&1&1\\0&1&0\\0&1&0}+\pmatrix{1&1&1\\0&0&1\\0&0&1}\ . \end{align}
Solution for even $\ n\ $
It turns out there's a simple method of solution when $\ n \ $ is even. Let $\ T\ $ be the matrix representing the target configuration, with entry $\ t_{ij}\ $ in it's $\ i^\text{th}\ $ row and $\ j^\text{th}\ $ column, and $\ (i_1,j_1),$$\, (i_2,j_2),$$\,\dots,$$\,(i_t,j_t)\ $ the pairs of rows and columns for which $\ t_{i_kj_k}=1\ $. Let \begin{align} C&=\sum_{i=1}^n\sum_{i=1}^nt_{ij}M(i,j)\\ &=\sum_{k=1}^tM\big(i_k,j_k\big)\ . \end{align} If $\ \mu\ $ is the number of ones in the matrix $\ C\ ,$ $\ c_{ij}\ $ the entry in its $\ i^\text{th}\ $ row and $\ j^\text{th}\ $ column, and $\ (c_1,d_1),$$\,(c_1,d_1),$$\,\dots,$$\,(c_\mu,d_\mu)\ $ the pairs of rows and columns for which $\ C_{c_kd_k}=1\ ,$ then $\ \mu\ $ is the minimum number of moves needed to reach the target, and $\ (c_1,d_1),$$\,(c_1,d_1),$$\,\dots,$$\,(c_\mu,d_\mu)\ $ are the row-column pairs that need to be flipped. In other words, \begin{align} T&=\sum_{i=1}^n\sum_{i=1}^nc_{ij}M(i,j)\\ &=\sum_{k=1}^\mu M\big(c_k,d_k\big)\ . \end{align}
Example
If $$ T=\pmatrix{0&0&0&0\\ 1&1&0&0\\ 0&1&1&0\\ 0&1&1&0}\, $$ then \begin{align} C&=M(2,1)+M(2,2)+M(3,2)\\ &\hspace{2em}+M(3,3)+M(4,2)+M(4,3)\\ &=\pmatrix{1&0&0&0\\1&1&1&1\\1&0&0&0\\1&0&0&0}+\pmatrix{0&1&0&0\\1&1&1&1\\0&1&0&0\\0&1&0&0}\\ &\hspace{1em}+\pmatrix{0&1&0&0\\0&1&0&0\\1&1&1&1\\0&1&0&0}+\pmatrix{0&0&1&0\\0&0&1&0\\1&1&1&1\\0&0&1&0}\\ &\hspace{1em}+\pmatrix{0&1&0&0\\0&1&0&0\\0&1&0&0\\1&1&1&1}+\pmatrix{0&0&1&0\\0&0&1&0\\0&0&1&0\\1&1&1&1}\\ &=\pmatrix{1&1&0&0\\0&0&0&0\\1&0&1&0\\1&0&1&0}\ . \end{align} Thus, the smallest number of moves needed to obtain the configuration represented by the matrix $\ T\ $ is $6$, and the unique set of moves required to reach the configuration in $6$ moves is to flip the coins in row $1$ column $1$, row $1$ column $2$, row $3$ column $1,$ row $3$ column $3,$ row $4$ column $1$ and row $4$ column $3$.