MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Given the vector space $\mathbb{R}^n$, endowed with the standard inner (dot) product $\langle\cdot,\cdot\rangle:\mathbb{R}^n\times \mathbb{R}^n\to\mathbb{R}$, the problem of almost-orthogonal sets asks, for each $\epsilon> 0$, for the construction (or at the very least, bounds on the cardinality) of a maximal subset $S$ of $U_n$, the set of unit vectors of $\mathbb{R}^n$, such that

$\forall x,y\in S: x\ne y\implies |\langle x,y\rangle|\le\epsilon$.

For known results, see Matt Cheung's Major Qualifying Project monograph at this link.

Question: What are known results, if we restrict ourselves to some subset of $U_n$? Specifically, I am interested in the subset $\lbrace\frac{1}{\sqrt{n}},-\frac{1}{\sqrt{n}}\rbrace^n$ consisting of the vertices of the scaled-down unit cube inscribed inside the unit ball centered at $0$.

share|cite|improve this question
For your particular subset, the first step would be to generate $S$ randomly. Here, inner products will be in terms of a binomial distribution, and then a union bound will tell you how big $S$ can be in terms of $\epsilon$. This will at least give you a (decent) lower bound on the largest possible size of $S$. – Dustin G. Mixon May 23 '13 at 16:35
Well, for a random subset (where random can mean various things) the Johnson-Lindenstrauss lemma gives $ \exp ( b \epsilon^2 m)$ for some positive constant $b$ independent of $n$ and $\epsilon$, Dustin. Presumably the OP is interested in more precise results and low dimensions. – Bill Johnson May 23 '13 at 18:41
^ More precision, yes. Dimensions, not necessarily low. But anything is worth hearing. – Seraj May 23 '13 at 18:54
up vote 3 down vote accepted

Nearly two months after I asked the above question, I have come across a paper where Noga Alon has given an explicit result in Problems and results in Extremal Combinatorics, Part I in section 9, On ranks of perturbations of identity matrices. He says

Lemma 9.1. Let $A = (a_{ij})$ be an $n \times n$ real, symmetric matrix with $a_{ii} = 1$ for all $i$ and $|a_{ij}|\le\epsilon$ for all $i\ne j$. If the rank of $A$ is $d$, then $d\ge \frac{n}{1+(n-1)\epsilon^2}$. In particular, if $\epsilon\le \frac{1}{\sqrt{n}}$ then $d\ge\frac{n}{2}$.

His proof is rather pretty. I apply the lemma to the question at hand as follows.

Application. Suppose $S$ is an $m\times n$ matrix with row vectors $(s_1,\ldots, s_m)$, an $m$-element subset of $\lbrace\frac{1}{\sqrt{n}},-\frac{1}{\sqrt{n}}\rbrace^n$ such that $\forall s_i,s_j\in S: i\ne j\implies |\langle s_i,s_j\rangle|\le\epsilon$.

Let $A=(a_{ij})$ be its Gram matrix, which is symmetric $m\times m$ with $a_{ii} = \langle s_i,s_i\rangle = 1$ for all $i$ and $|a_{ij}|=|\langle s_i, s_j \rangle|\le\epsilon$ for all $i\ne j$, and rank $d$. Note that the rank of $S$ also $d$.

By the lemma, since $n\ge d$, we get $\boxed{n\ge \frac{m}{1+(m-1)\epsilon^2}}$.

Assuming $\epsilon\le \frac{1}{\sqrt{n}}$, some manipulation also yields $\boxed{m\le \frac{n(1-\epsilon^2)}{1-n\epsilon^2}}$.

Bill Johnson's reference to the Johnson-Lindenstrauss lemma led me to its Wikipedia page, which had the paper as a reference.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.