TY - JOUR

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

AU - Odlyzko, A. M.

PY - 1988/1

Y1 - 1988/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

AN - SCOPUS:38249029967

SN - 0097-3165

VL - 47

SP - 124

EP - 133

JO - Journal of Combinatorial Theory, Series A

JF - Journal of Combinatorial Theory, Series A

IS - 1

ER -