# On subspaces spanned by random selections of ±1 vectors

Research output: Contribution to journalArticle

26 Citations (Scopus)

### Abstract

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.

Original language English (US) 124-133 10 Journal of Combinatorial Theory, Series A 47 1 https://doi.org/10.1016/0097-3165(88)90046-5 Published - Jan 1 1988 Yes

### Fingerprint

Subspace
Associative Memory
Notation
Data storage equipment
Term
Estimate

### Cite this

In: Journal of Combinatorial Theory, Series A, Vol. 47, No. 1, 01.01.1988, p. 124-133.

Research output: Contribution to journalArticle

title = "On subspaces spanned by random selections of ±1 vectors",
abstract = "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.",
author = "Andrew Odlyzko",
year = "1988",
month = "1",
day = "1",
doi = "10.1016/0097-3165(88)90046-5",
language = "English (US)",
volume = "47",
pages = "124--133",
journal = "Journal of Combinatorial Theory - Series A",
issn = "0097-3165",
number = "1",

}

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 -