If $H$ has an $a\times b$ submatrix of all $1$s, please prove that $ab\le n$. Let $H$ be an $n\times n$ matrix with entries $\pm1$. Its rows are mutually orthogonal. If $H$ has an $a\times b$ submatrix of all $1$s, please prove that $ab\le n$.
 A: Since the rows of $H$ are orthogonal, we have $HH^T=nI$; and given any $n$-vector $v$, we have $v^THH^Tv=nv^Tv$.
If the $a\times b$ sub-matrix is not in the top left-hand corner of $H$, permute the rows and columns so that it is, and consider the $2\times 2$ blocking of $H$
$$H \triangleq \begin{bmatrix} H_{11} & H_{12} \\ H_{21} & H_{22} \end{bmatrix}$$
where $H_{11}$ is the $a\times b$ submatrix in question.
Let $v$ be an $\{0,1\}$ vector with $1$s in the first $a$ rows, and $0$s elsewhere; so
$v^Tv=a$. We have $$v^T H = \vec{1}_a^T \begin{bmatrix} H_{11} & H_{12} \end{bmatrix}$$ where $\vec{1}_a$ is the $a$-vector of all ones; and
$$v^T H^T H v = \vec{1}_a^T H_{11} H_{11}^T \vec{1}_a + \vec{1}_a H_{12} H_{12}^T \vec{1}_a = nv^Tv = na.$$
Since both terms on the left are nonnegative,
$$\vec{1}_a^T H_{11} H_{11}^T \vec{1}_a \leq na.$$
Now $H_{11}^T\vec{1}_a=a\vec{1}_b$, where $\vec{1}_b$ is the $b$-vector of all ones. So $\vec{1}_a^T H_{11} H_{11}^T \vec{1}_a=a^2b$, and
$$a^2b \leq na\quad\Longrightarrow\quad ab \leq n.$$
