On random pm 1 matrices

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

On random pm 1 matrices: singularity and determinant

Full text

Pdf (242 KB)

Source

Annual ACM Symposium on Theory of Computing archive
Proceedings of the thirty-seventh annual ACM symposium on Theory of computing table of contents

Baltimore, MD, USA

SESSION: Session 9B table of contents

Pages: 431 - 440

Year of Publication: 2005

ISBN:1-58113-960-8

Authors

Terence Tao	UCLA, Los Angeles, CA
Van Vu	UCSD, La Jolla, CA

Sponsors

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory
ACM: Association for Computing Machinery

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 13, Downloads (12 Months): 54, Citation Count: 1

Additional Information:

abstract references cited by index terms collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/1060590.1060655 What is a DOI?

ABSTRACT

We proved several results concerning the determinant of a random pm 1 matrix. In particular, we show that with high probability, the determinant has absolute value very close to √n!.

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	Z. Bai and Y. Yin, Limit of the smallest eigenvalue of a large-dimensional sample covariance matrix, Ann. Probab. 21 (1993), no. 3, 1275--1294.
	2	J. Bourgain, personal communication.
	3	P. Erdös, On a lemma of Littlewood and Offord, Bull. Amer. Math. Soc. 51 (1945), 898--902.
	4	C.G. Esséen, On the Kolmogorov-Rogozin inequality for the concentration function, Z. Wahrsch. Verw. Gebiete 5 (1966), 210--216.
	5	G. Halasz, On the distribution of additive arithmetic functions, Acta Arith. 27 (1975), 143--152.
	6	J. Kahn, J. Komlós, E. Szemerédi, On the probability that a random pm 1 matrix is singular, J. Amer. Math. Soc. 8 (1995), 223--240.
	7	J. Komlós, On the determinant of (0,1) matrices, Studia Sci. Math. Hungar. 2 (1967) 7--22.
	8	J. Komlós, On the determinant of random matrices, Studia Sci. Math. Hungar. 3 (1968) 387--399.
	9	A.M. Macbeath, On measure of sum sets II. The sum-theorem for the torus, Proc. Cambridge Phil. Soc. 49 (1953), 40--43.
	10	A. M. Odlyzko, On subspaces spanned by random selections of ±1 vectors, Journal of Combinatorial Theory Series A, v.47 n.1, p.124-133, January 1988 [doi>10.1016/0097-3165(88)90046-5]
	11	P. Turán, On extremal problems concerning determinants, (Hungarian) Math. Naturwiss. Anz. Ungar. Akad. Wiss. 59, (1940). 95--105