### Abstract

Let vectors v_{1}, ..., v_{p} be chosen at random from the ±1 vectors of length n. The probability that there is at least one ±1 vector in the subspace (over the reals) spanned by v_{1}, ..., v_{p} that is different from the ±v_{j} is shown to be 4 p 3 3 4^{n} +O 7 10^{n}, as n → ∞, for p ≤ n - 10n (log n), where the constant implied by the O-notation is independent of p. The main term in this estimate is the probability that some three of the v_{j} contain another ±1 vector in their linear span. This result answers a question that arose in the work of Kanter and Sompolinsky on associative memories.

Original language | English (US) |
---|---|

Pages (from-to) | 124-133 |

Number of pages | 10 |

Journal | Journal of Combinatorial Theory, Series A |

Volume | 47 |

Issue number | 1 |

DOIs | |

State | Published - Jan 1 1988 |

Externally published | Yes |

### Fingerprint

### Cite this

**On subspaces spanned by random selections of ±1 vectors.** / Odlyzko, Andrew.

Research output: Contribution to journal › Article

*Journal of Combinatorial Theory, Series A*, vol. 47, no. 1, pp. 124-133. https://doi.org/10.1016/0097-3165(88)90046-5

}

TY - JOUR

T1 - On subspaces spanned by random selections of ±1 vectors

AU - Odlyzko, Andrew

PY - 1988/1/1

Y1 - 1988/1/1

N2 - Let vectors v1, ..., vp be chosen at random from the ±1 vectors of length n. The probability that there is at least one ±1 vector in the subspace (over the reals) spanned by v1, ..., vp that is different from the ±vj is shown to be 4 p 3 3 4n +O 7 10n, as n → ∞, for p ≤ n - 10n (log n), where the constant implied by the O-notation is independent of p. The main term in this estimate is the probability that some three of the vj contain another ±1 vector in their linear span. This result answers a question that arose in the work of Kanter and Sompolinsky on associative memories.

AB - Let vectors v1, ..., vp be chosen at random from the ±1 vectors of length n. The probability that there is at least one ±1 vector in the subspace (over the reals) spanned by v1, ..., vp that is different from the ±vj is shown to be 4 p 3 3 4n +O 7 10n, as n → ∞, for p ≤ n - 10n (log n), where the constant implied by the O-notation is independent of p. The main term in this estimate is the probability that some three of the vj contain another ±1 vector in their linear span. This result answers a question that arose in the work of Kanter and Sompolinsky on associative memories.

UR - http://www.scopus.com/inward/record.url?scp=38249029967&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=38249029967&partnerID=8YFLogxK

U2 - 10.1016/0097-3165(88)90046-5

DO - 10.1016/0097-3165(88)90046-5

M3 - Article

VL - 47

SP - 124

EP - 133

JO - Journal of Combinatorial Theory - Series A

JF - Journal of Combinatorial Theory - Series A

SN - 0097-3165

IS - 1

ER -