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{m}}$, 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.

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.

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 it 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{m}}$, 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.

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{m}}$, 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.