Putnam 2011, Problem A-4

For which positive integers $n$ is there an $n \times n$ matrix with integer entries such that every dot product of a row with itself is even, while every dot product of two different rows is odd?

Solution:
The answer is \(n\) odd. Let \(I\) denote the \(n \times n\) identity matrix, and let \(A\) denote the \(n \times n\) matrix all of whose entries are \(1\). If \(n\) is odd, then the matrix \(A - I\) satisfies the conditions of the problem: the dot product of any row with itself is \(n - 1\), and the dot product of any two distinct rows is \(n - 2\).  
Conversely, suppose \(n\) is even, and suppose that the matrix \(M\) satisfied the conditions of the problem. Consider all matrices and vectors mod \(2\). Since the dot product of a row with itself is equal mod \(2\) to the sum of the entries of the row, we have \(Mv = 0\) where \(v\) is the vector \((1,1,\dots,1)\), and so \(M\) is singular. On the other hand, \(MM^T = A - I\); since  
\[
(A - I)^2 = A^2 - 2A + I = (n - 2)A + I = I,
\]  
we have \((\det M)^2 = \det(A - I) = 1\) and \(\det M = 1\), contradicting the fact that \(M\) is singular.