Random Symmetric Matrices/2005

Originator(s): Van Vu (UCSD, vanvu@ucsd.edu)


Question: What is the "usual" magnitude of the determinant of an n-by-n symmetric random matrix? That is, is there a function f(n) such that |det M(n)| is almost always close to f(n)? Here the entries ai,j of M(n), for all i,j\in [n], are generated as independent identically distributed Bernoulli random variables, taking values 1 or -1 with probability 1/2 each.

Background/motivation: This is a variant of the well known question of estimating det M(n), where M(n) is a random Bernoulli matrix not required to be symmetric. Komlos (1967) proved that almost surely M(n) is not singular. Thus det M(n) > 0, but det M(n) is divisible by 2n-1, so in fact det M(n) \ge 2n-1. Tao and Vu [TV] proved that almost surely det M(n) is n(1/2-o(1))n. It is not clear how to extend the arguments to symmetric matrices. The key difference here is that the row vectors are no longer independent.

Comments/Partial results: Tao, Vu, and Costello [in preparation] proved Komlos's statement for the symmetric problem: almost surely the matrix is non singular. This answers a question of Weiss. It does not seem that the apporoach is appropriate for the determinant.

[TV] Tao T. and Vu V. On random (-1,1) matrices: Singularity and Determinant, submitted (extended abstract in STOC 2005). See also http://www.math.ucsd.edu/~vanvu/papers.html.

Index Page; Glossary

Posted 04/06/05; Last update 04/06/05