This problem is from Futulity Closet wonderful site who itself brought this from Ross Honsberger's book - Mathematical Delights:
"In a certain chess position, each row and each column contains an odd number of pieces. Prove that the total number of pieces on black squares is an even number."
You can see a nice "simple" solution in Futilty Closet, but I would like to post a different solution involving linear algebra.
Let \(A\) be the \(8\times8\) matrix that represents the pieces configuration. This matrix \(a_{ij}\) entry is \(1\) if there is a piece on that entry else it is \(0\). It can be thought of a matrix in \(\mathbb{F}_{2}^{8,8}\) - that is over the finite field of 2 elements.
Let \(v^{t}=\left(\begin{array}{cccccccc}1 & 1 & 1 & 1 & 1 & 1 & 1 & 1\end{array}\right)\in\mathbb{F}_{2}^{8}\) , from the given data it can be shown that
\(Av=v\), (sum of each row is odd ) and that \(v^{t}A=v^{t}\) (sum of each column is odd).
We want to prove that the sum of the pieces in the dark squares is even, it can be shown that this sum is actually the trace (sum of diagonal) of the multiplication of \(A\) with a certain matrix \(B\),
where \(B=\left(\begin{array}{cccccccc}
0 & 1 & 0 & 1 & 0 & 1 & 0 & 1\\
1 & 0 & 1 & 0 & 1 & 0 & 1 & 0\\
0 & 1 & 0 & 1 & 0 & 1 & 0 & 1\\
1 & 0 & 1 & 0 & 1 & 0 & 1 & 0\\
0 & 1 & 0 & 1 & 0 & 1 & 0 & 1\\
1 & 0 & 1 & 0 & 1 & 0 & 1 & 0\\
0 & 1 & 0 & 1 & 0 & 1 & 0 & 1\\
1 & 0 & 1 & 0 & 1 & 0 & 1 & 0
\end{array}\right)\).
If \(AB=C\), check that \(c_{11}\) is the number of pieces in the first black row, \(c_{22}\) is the number of all pieces in the second black row etc.
So we can see that the number of pieces in the black squares is even if and only if \(tr(AB)=0\) mod 2.
The matrix \(B\) can re presented as the sum of two 1-ranked matrices:
\(B=\left(\begin{array}{cccccccc}
0 & 1 & 0 & 1 & 0 & 1 & 0 & 1\\
0 & 0 & 0 & 0 & 0 & 0 & 0 & 0\\
0 & 1 & 0 & 1 & 0 & 1 & 0 & 1\\
0 & 0 & 0 & 0 & 0 & 0 & 0 & 0\\
0 & 1 & 0 & 1 & 0 & 1 & 0 & 1\\
0 & 0 & 0 & 0 & 0 & 0 & 0 & 0\\
0 & 1 & 0 & 1 & 0 & 1 & 0 & 1\\
0 & 0 & 0 & 0 & 0 & 0 & 0 & 0
\end{array}\right)+\left(\begin{array}{cccccccc}
0 & 0 & 0 & 0 & 0 & 0 & 0 & 0\\
1 & 0 & 1 & 0 & 1 & 0 & 1 & 0\\
0 & 0 & 0 & 0 & 0 & 0 & 0 & 0\\
1 & 0 & 1 & 0 & 1 & 0 & 1 & 0\\
0 & 0 & 0 & 0 & 0 & 0 & 0 & 0\\
1 & 0 & 1 & 0 & 1 & 0 & 1 & 0\\
0 & 0 & 0 & 0 & 0 & 0 & 0 & 0\\
1 & 0 & 1 & 0 & 1 & 0 & 1 & 0
\end{array}\right)\).
Each of those 1-ranked matrices can be represented as a multiplication of vectors:
\(B=\left(\begin{array}{c}
1\\
0\\
1\\
0\\
1\\
0\\
1\\
0
\end{array}\right)\left(\begin{array}{cccccccc}
1 & 0 & 1 & 0 & 1 & 0 & 1 & 0\end{array}\right)+\left(\begin{array}{c}
0\\
1\\
0\\
1\\
0\\
1\\
0\\
1
\end{array}\right)\left(\begin{array}{cccccccc}
0 & 1 & 0 & 1 & 0 & 1 & 0 & 1\end{array}\right)\).
Now we know that \(v\) is an eigen-vector of \(A\). Using that, we can compose \(v\) into two parts
\(Av=A\left(\begin{array}{c}
1\\
1\\
1\\
1\\
1\\
1\\
1\\
1
\end{array}\right)=A\left(\left(\begin{array}{c}
1\\
0\\
1\\
0\\
1\\
0\\
1\\
0
\end{array}\right)+\left(\begin{array}{c}
0\\
1\\
0\\
1\\
0\\
1\\
0\\
1
\end{array}\right)\right)=A\left(\begin{array}{c}
1\\
0\\
1\\
0\\
1\\
0\\
1\\
0
\end{array}\right)+A\left(\begin{array}{c}
0\\
1\\
0\\
1\\
0\\
1\\
0\\
1
\end{array}\right)=\left(\begin{array}{c}
1\\
1\\
1\\
1\\
1\\
1\\
1\\
1
\end{array}\right)\).
Thus
\(A\left(\begin{array}{c}
1\\
0\\
1\\
0\\
1\\
0\\
1\\
0
\end{array}\right)=\left(\begin{array}{c}
1\\
1\\
1\\
1\\
1\\
1\\
1\\
1
\end{array}\right)-A\left(\begin{array}{c}
0\\
1\\
0\\
1\\
0\\
1\\
0\\
1
\end{array}\right)=\left(\begin{array}{c}
1\\
1\\
1\\
1\\
1\\
1\\
1\\
1
\end{array}\right)+A\left(\begin{array}{c}
0\\
1\\
0\\
1\\
0\\
1\\
0\\
1
\end{array}\right)\).
The last equality is because \(-1 = 1\) mod 2.
Replacing this in the multiplication of \(AB\).
\(AB=A\left(\begin{array}{c}
1\\
0\\
1\\
0\\
1\\
0\\
1\\
0
\end{array}\right)\left(\begin{array}{cccccccc}
1 & 0 & 1 & 0 & 1 & 0 & 1 & 0\end{array}\right)+A\left(\begin{array}{c}
0\\
1\\
0\\
1\\
0\\
1\\
0\\
1
\end{array}\right)\left(\begin{array}{cccccccc}
0 & 1 & 0 & 1 & 0 & 1 & 0 & 1\end{array}\right)=\)
\(=\left(\left(\begin{array}{c}
1\\
1\\
1\\
1\\
1\\
1\\
1\\
1
\end{array}\right)+A\left(\begin{array}{c}
0\\
1\\
0\\
1\\
0\\
1\\
0\\
1
\end{array}\right)\right)\left(\begin{array}{cccccccc}
1 & 0 & 1 & 0 & 1 & 0 & 1 & 0\end{array}\right)+A\left(\begin{array}{c}
0\\
1\\
0\\
1\\
0\\
1\\
0\\
1
\end{array}\right)\left(\begin{array}{cccccccc}
0 & 1 & 0 & 1 & 0 & 1 & 0 & 1\end{array}\right)=\)
\(=\left(\begin{array}{c}
1\\
1\\
1\\
1\\
1\\
1\\
1\\
1
\end{array}\right)\left(\begin{array}{cccccccc}
1 & 0 & 1 & 0 & 1 & 0 & 1 & 0\end{array}\right)+\)
\(A\left(\begin{array}{c}
0\\
1\\
0\\
1\\
0\\
1\\
0\\
1
\end{array}\right)\left(\begin{array}{cccccccc}
1 & 0 & 1 & 0 & 1 & 0 & 1 & 0\end{array}\right)+A\left(\begin{array}{c}
0\\
1\\
0\\
1\\
0\\
1\\
0\\
1
\end{array}\right)\left(\begin{array}{cccccccc}
0 & 1 & 0 & 1 & 0 & 1 & 0 & 1\end{array}\right)\).
But note that the first matrix term \(\left(\begin{array}{c}
1\\
1\\
1\\
1\\
1\\
1\\
1\\
1
\end{array}\right)\left(\begin{array}{cccccccc}
1 & 0 & 1 & 0 & 1 & 0 & 1 & 0\end{array}\right)\) is a matrix with even trace, that means that we can neglect it.
\( tr(AB)=tr(A\left(\begin{array}{c}
0\\
1\\
0\\
1\\
0\\
1\\
0\\
1
\end{array}\right)\left(\begin{array}{cccccccc}
1 & 0 & 1 & 0 & 1 & 0 & 1 & 0\end{array}\right)+A\left(\begin{array}{c}
0\\
1\\
0\\
1\\
0\\
1\\
0\\
1
\end{array}\right)\left(\begin{array}{cccccccc}
0 & 1 & 0 & 1 & 0 & 1 & 0 & 1\end{array}\right))\).
\( = tr(A\left(\begin{array}{c}
0\\
1\\
0\\
1\\
0\\
1\\
0\\
1
\end{array}\right)(\left(\begin{array}{cccccccc}
1 & 0 & 1 & 0 & 1 & 0 & 1 & 0\end{array}\right)+\left(\begin{array}{cccccccc}
0 & 1 & 0 & 1 & 0 & 1 & 0 & 1\end{array}\right)))\) =
\(tr(A\left(\begin{array}{c}
0\\
1\\
0\\
1\\
0\\
1\\
0\\
1
\end{array}\right)\left(\begin{array}{cccccccc}
1 & 1 & 1 & 1 & 1 & 1 & 1 & 1\end{array}\right))\).
Now we use the famous equality \(tr(AB)=tr(BA)\).
\(=tr(\left(\begin{array}{c}
0\\
1\\
0\\
1\\
0\\
1\\
0\\
1
\end{array}\right)\left(\begin{array}{cccccccc}
1 & 1 & 1 & 1 & 1 & 1 & 1 & 1\end{array}\right)A)\).
But \(\left(\begin{array}{cccccccc}
1 & 1 & 1 & 1 & 1 & 1 & 1 & 1\end{array}\right)A= \left(\begin{array}{cccccccc}
1 & 1 & 1 & 1 & 1 & 1 & 1 & 1\end{array}\right)\) (remember?).
So, finally:
\(tr(AB)=tr(\left(\begin{array}{c}
0\\
1\\
0\\
1\\
0\\
1\\
0\\
1
\end{array}\right)\left(\begin{array}{cccccccc}
1 & 1 & 1 & 1 & 1 & 1 & 1 & 1\end{array}\right))=\)
\(tr\left(\begin{array}{cccccccc}
0 & 0 & 0 & 0 & 0 & 0 & 0 & 0\\
1 & 1 & 1 & 1 & 1 & 1 & 1 & 1\\
0 & 0 & 0 & 0 & 0 & 0 & 0 & 0\\
1 & 1 & 1 & 1 & 1 & 1 & 1 & 1\\
0 & 0 & 0 & 0 & 0 & 0 & 0 & 0\\
1 & 1 & 1 & 1 & 1 & 1 & 1 & 1\\
0 & 0 & 0 & 0 & 0 & 0 & 0 & 0\\
1 & 1 & 1 & 1 & 1 & 1 & 1 & 1
\end{array}\right)=0.\)
Let \(A\) be the \(8\times8\) matrix that represents the pieces configuration. This matrix \(a_{ij}\) entry is \(1\) if there is a piece on that entry else it is \(0\). It can be thought of a matrix in \(\mathbb{F}_{2}^{8,8}\) - that is over the finite field of 2 elements.
Let \(v^{t}=\left(\begin{array}{cccccccc}1 & 1 & 1 & 1 & 1 & 1 & 1 & 1\end{array}\right)\in\mathbb{F}_{2}^{8}\) , from the given data it can be shown that
\(Av=v\), (sum of each row is odd ) and that \(v^{t}A=v^{t}\) (sum of each column is odd).
We want to prove that the sum of the pieces in the dark squares is even, it can be shown that this sum is actually the trace (sum of diagonal) of the multiplication of \(A\) with a certain matrix \(B\),
where \(B=\left(\begin{array}{cccccccc}
0 & 1 & 0 & 1 & 0 & 1 & 0 & 1\\
1 & 0 & 1 & 0 & 1 & 0 & 1 & 0\\
0 & 1 & 0 & 1 & 0 & 1 & 0 & 1\\
1 & 0 & 1 & 0 & 1 & 0 & 1 & 0\\
0 & 1 & 0 & 1 & 0 & 1 & 0 & 1\\
1 & 0 & 1 & 0 & 1 & 0 & 1 & 0\\
0 & 1 & 0 & 1 & 0 & 1 & 0 & 1\\
1 & 0 & 1 & 0 & 1 & 0 & 1 & 0
\end{array}\right)\).
If \(AB=C\), check that \(c_{11}\) is the number of pieces in the first black row, \(c_{22}\) is the number of all pieces in the second black row etc.
So we can see that the number of pieces in the black squares is even if and only if \(tr(AB)=0\) mod 2.
The matrix \(B\) can re presented as the sum of two 1-ranked matrices:
\(B=\left(\begin{array}{cccccccc}
0 & 1 & 0 & 1 & 0 & 1 & 0 & 1\\
0 & 0 & 0 & 0 & 0 & 0 & 0 & 0\\
0 & 1 & 0 & 1 & 0 & 1 & 0 & 1\\
0 & 0 & 0 & 0 & 0 & 0 & 0 & 0\\
0 & 1 & 0 & 1 & 0 & 1 & 0 & 1\\
0 & 0 & 0 & 0 & 0 & 0 & 0 & 0\\
0 & 1 & 0 & 1 & 0 & 1 & 0 & 1\\
0 & 0 & 0 & 0 & 0 & 0 & 0 & 0
\end{array}\right)+\left(\begin{array}{cccccccc}
0 & 0 & 0 & 0 & 0 & 0 & 0 & 0\\
1 & 0 & 1 & 0 & 1 & 0 & 1 & 0\\
0 & 0 & 0 & 0 & 0 & 0 & 0 & 0\\
1 & 0 & 1 & 0 & 1 & 0 & 1 & 0\\
0 & 0 & 0 & 0 & 0 & 0 & 0 & 0\\
1 & 0 & 1 & 0 & 1 & 0 & 1 & 0\\
0 & 0 & 0 & 0 & 0 & 0 & 0 & 0\\
1 & 0 & 1 & 0 & 1 & 0 & 1 & 0
\end{array}\right)\).
Each of those 1-ranked matrices can be represented as a multiplication of vectors:
\(B=\left(\begin{array}{c}
1\\
0\\
1\\
0\\
1\\
0\\
1\\
0
\end{array}\right)\left(\begin{array}{cccccccc}
1 & 0 & 1 & 0 & 1 & 0 & 1 & 0\end{array}\right)+\left(\begin{array}{c}
0\\
1\\
0\\
1\\
0\\
1\\
0\\
1
\end{array}\right)\left(\begin{array}{cccccccc}
0 & 1 & 0 & 1 & 0 & 1 & 0 & 1\end{array}\right)\).
Now we know that \(v\) is an eigen-vector of \(A\). Using that, we can compose \(v\) into two parts
\(Av=A\left(\begin{array}{c}
1\\
1\\
1\\
1\\
1\\
1\\
1\\
1
\end{array}\right)=A\left(\left(\begin{array}{c}
1\\
0\\
1\\
0\\
1\\
0\\
1\\
0
\end{array}\right)+\left(\begin{array}{c}
0\\
1\\
0\\
1\\
0\\
1\\
0\\
1
\end{array}\right)\right)=A\left(\begin{array}{c}
1\\
0\\
1\\
0\\
1\\
0\\
1\\
0
\end{array}\right)+A\left(\begin{array}{c}
0\\
1\\
0\\
1\\
0\\
1\\
0\\
1
\end{array}\right)=\left(\begin{array}{c}
1\\
1\\
1\\
1\\
1\\
1\\
1\\
1
\end{array}\right)\).
Thus
\(A\left(\begin{array}{c}
1\\
0\\
1\\
0\\
1\\
0\\
1\\
0
\end{array}\right)=\left(\begin{array}{c}
1\\
1\\
1\\
1\\
1\\
1\\
1\\
1
\end{array}\right)-A\left(\begin{array}{c}
0\\
1\\
0\\
1\\
0\\
1\\
0\\
1
\end{array}\right)=\left(\begin{array}{c}
1\\
1\\
1\\
1\\
1\\
1\\
1\\
1
\end{array}\right)+A\left(\begin{array}{c}
0\\
1\\
0\\
1\\
0\\
1\\
0\\
1
\end{array}\right)\).
The last equality is because \(-1 = 1\) mod 2.
Replacing this in the multiplication of \(AB\).
\(AB=A\left(\begin{array}{c}
1\\
0\\
1\\
0\\
1\\
0\\
1\\
0
\end{array}\right)\left(\begin{array}{cccccccc}
1 & 0 & 1 & 0 & 1 & 0 & 1 & 0\end{array}\right)+A\left(\begin{array}{c}
0\\
1\\
0\\
1\\
0\\
1\\
0\\
1
\end{array}\right)\left(\begin{array}{cccccccc}
0 & 1 & 0 & 1 & 0 & 1 & 0 & 1\end{array}\right)=\)
\(=\left(\left(\begin{array}{c}
1\\
1\\
1\\
1\\
1\\
1\\
1\\
1
\end{array}\right)+A\left(\begin{array}{c}
0\\
1\\
0\\
1\\
0\\
1\\
0\\
1
\end{array}\right)\right)\left(\begin{array}{cccccccc}
1 & 0 & 1 & 0 & 1 & 0 & 1 & 0\end{array}\right)+A\left(\begin{array}{c}
0\\
1\\
0\\
1\\
0\\
1\\
0\\
1
\end{array}\right)\left(\begin{array}{cccccccc}
0 & 1 & 0 & 1 & 0 & 1 & 0 & 1\end{array}\right)=\)
\(=\left(\begin{array}{c}
1\\
1\\
1\\
1\\
1\\
1\\
1\\
1
\end{array}\right)\left(\begin{array}{cccccccc}
1 & 0 & 1 & 0 & 1 & 0 & 1 & 0\end{array}\right)+\)
\(A\left(\begin{array}{c}
0\\
1\\
0\\
1\\
0\\
1\\
0\\
1
\end{array}\right)\left(\begin{array}{cccccccc}
1 & 0 & 1 & 0 & 1 & 0 & 1 & 0\end{array}\right)+A\left(\begin{array}{c}
0\\
1\\
0\\
1\\
0\\
1\\
0\\
1
\end{array}\right)\left(\begin{array}{cccccccc}
0 & 1 & 0 & 1 & 0 & 1 & 0 & 1\end{array}\right)\).
But note that the first matrix term \(\left(\begin{array}{c}
1\\
1\\
1\\
1\\
1\\
1\\
1\\
1
\end{array}\right)\left(\begin{array}{cccccccc}
1 & 0 & 1 & 0 & 1 & 0 & 1 & 0\end{array}\right)\) is a matrix with even trace, that means that we can neglect it.
\( tr(AB)=tr(A\left(\begin{array}{c}
0\\
1\\
0\\
1\\
0\\
1\\
0\\
1
\end{array}\right)\left(\begin{array}{cccccccc}
1 & 0 & 1 & 0 & 1 & 0 & 1 & 0\end{array}\right)+A\left(\begin{array}{c}
0\\
1\\
0\\
1\\
0\\
1\\
0\\
1
\end{array}\right)\left(\begin{array}{cccccccc}
0 & 1 & 0 & 1 & 0 & 1 & 0 & 1\end{array}\right))\).
\( = tr(A\left(\begin{array}{c}
0\\
1\\
0\\
1\\
0\\
1\\
0\\
1
\end{array}\right)(\left(\begin{array}{cccccccc}
1 & 0 & 1 & 0 & 1 & 0 & 1 & 0\end{array}\right)+\left(\begin{array}{cccccccc}
0 & 1 & 0 & 1 & 0 & 1 & 0 & 1\end{array}\right)))\) =
\(tr(A\left(\begin{array}{c}
0\\
1\\
0\\
1\\
0\\
1\\
0\\
1
\end{array}\right)\left(\begin{array}{cccccccc}
1 & 1 & 1 & 1 & 1 & 1 & 1 & 1\end{array}\right))\).
Now we use the famous equality \(tr(AB)=tr(BA)\).
\(=tr(\left(\begin{array}{c}
0\\
1\\
0\\
1\\
0\\
1\\
0\\
1
\end{array}\right)\left(\begin{array}{cccccccc}
1 & 1 & 1 & 1 & 1 & 1 & 1 & 1\end{array}\right)A)\).
But \(\left(\begin{array}{cccccccc}
1 & 1 & 1 & 1 & 1 & 1 & 1 & 1\end{array}\right)A= \left(\begin{array}{cccccccc}
1 & 1 & 1 & 1 & 1 & 1 & 1 & 1\end{array}\right)\) (remember?).
So, finally:
\(tr(AB)=tr(\left(\begin{array}{c}
0\\
1\\
0\\
1\\
0\\
1\\
0\\
1
\end{array}\right)\left(\begin{array}{cccccccc}
1 & 1 & 1 & 1 & 1 & 1 & 1 & 1\end{array}\right))=\)
\(tr\left(\begin{array}{cccccccc}
0 & 0 & 0 & 0 & 0 & 0 & 0 & 0\\
1 & 1 & 1 & 1 & 1 & 1 & 1 & 1\\
0 & 0 & 0 & 0 & 0 & 0 & 0 & 0\\
1 & 1 & 1 & 1 & 1 & 1 & 1 & 1\\
0 & 0 & 0 & 0 & 0 & 0 & 0 & 0\\
1 & 1 & 1 & 1 & 1 & 1 & 1 & 1\\
0 & 0 & 0 & 0 & 0 & 0 & 0 & 0\\
1 & 1 & 1 & 1 & 1 & 1 & 1 & 1
\end{array}\right)=0.\)
