next up previous
Next: Gale-Berlekamp Switching Game Up: Hadamard Matrices Previous: Introduction

Discrepancy and Ramsey Theory for $(\pm 1)$-Matrices

Lemma 2.1   (Lindsey's Lemma) Let $H=(h_{ij})$ be a Hadamard matrix. Let $S,T \subseteq [n]$ and $s=\vert S\vert$, $t=\vert T\vert$. Then

\begin{displaymath}
\left\vert \sum_{i\in S}\sum_{j\in T}h_{ij}\right\vert \leq \sqrt{stn}.
\end{displaymath}

Definition 2.2   We call the submatrix on the entries corresponding to $S\times T$ an $s\times t$ rectangle in $H$. We call the sum $\left\vert \sum_{i\in S}\sum_{j\in T}h_{ij}\right\vert$ the discrepancy of this rectangle.

Discrepancy measures the deviation from uniform distribution.
\begin{exercise}
% latex2html id marker 525
Prove Lindsey's Lemma.\\
{\em ...
...vert{a}\vert\vert\cdot\vert\vert{b}\vert\vert).\end{displaymath}
\end{exercise}

Definition 2.3   A rectangle is homogeneous if all of its entries are equal.


\begin{exercise}
% latex2html id marker 530
If $H$\ is an $n\times n$\ Hadamar...
...as
no homogeneous rectangles of area ($=st$) greater than
$n$.
\end{exercise}

\begin{exercise}
% latex2html id marker 532
{(\bf Erd\H{o}s)}\\
Prove: For all...
... In fact it will be
$o(1)$\ (almost all matrices are \lq\lq good'').
\end{exercise}

\begin{exercise}
% latex2html id marker 534
Construct an explicit family of $(...
...n$\ has no homogeneous $t\times t$\ rectangles for $t>\sqrt{n}$.
\end{exercise}

OPEN PROBLEM 2.4   Construct an explicit family of $(n\times n)$ $(\pm 1)$ matrices $A_n$ (for infinitely many values of $n$) such that $A_n$ has no homogeneous $t\times t$ rectangles for $t > n^{0.49}$.



Laszlo Babai 2003-06-19