Putnam 2005, Problem A-4

Let $H$ be an $n \times n$ matrix all of whose entries are $\pm 1$ and whose rows are mutually orthogonal. Suppose $H$ has an $a \times b$ submatrix whose entries are all 1. Show that $ab \leq n$.

Solution:
First solution: Choose a set of \(a\) rows \(r_1,\ldots,r_a\) containing an \(a \times b\) submatrix whose entries are all 1. Then for \(i,j \in \{1,\ldots,a\}\), we have \(r_i \cdot r_j = n\) if \(i = j\) and 0 otherwise. Hence
\[
\sum_{i,j=1}^a r_i \cdot r_j = an.
\]
On the other hand, the term on the left is the dot product of \(r_1 + \cdots + r_a\) with itself, i.e., its squared length. Since this vector has \(a\) in each of its first \(b\) coordinates, the dot product is at least \(a^2 b\). Hence \(an \geq a^2 b\), whence \(n \geq ab\) as desired.

Second solution: (by Richard Stanley) Suppose without loss of generality that the \(a \times b\) submatrix occupies the first \(a\) rows and the first \(b\) columns. Let \(M\) be the submatrix occupying the first \(a\) rows and the last \(n - b\) columns. Then the hypothesis implies that the matrix \(MM^T\) has \(n - b\)'s on the main diagonal and \(-b\)'s elsewhere. Hence the column vector \(v\) of length \(a\) consisting of all 1's satisfies \(MM^T v = (n - ab)v\), so \(n - ab\) is an eigenvalue of \(MM^T\). But \(MM^T\) is semidefinite, so its eigenvalues are all nonnegative real numbers. Hence \(n - ab \geq 0\).

Remarks: A matrix as in the problem is called a Hadamard matrix, because it meets the equality condition of Hadamard's inequality: any \(n \times n\) matrix with \(\pm 1\) entries has absolute determinant at most \(n^{n/2}\), with equality if and only if the rows are mutually orthogonal (from the interpretation of the determinant as the volume of a parallelepiped whose edges are parallel to the row vectors). Note that this implies that the columns are also mutually orthogonal. A generalization of this problem, with a similar proof, is known as Lindsey's lemma: the sum of the entries in any \(a \times b\) submatrix of a Hadamard matrix is at most \(\sqrt{ab}n\). Stanley notes that Ryser (1981) asked for the smallest size of a Hadamard matrix containing an \(r \times s\) submatrix of all 1's, and refers to the URL www3.interscience.wiley.com/cgi-bin/abstract/110550861/ABSTRACT for more information.