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

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

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.
% latex2html id marker 525
Prove Lindsey's Lemma.\\
{\em ...

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

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

% 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'').

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

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