I’ve arXived the paper “On the condition number of a randomly perturbed matrix”, authored with Van Vu, which will appear at STOC 2007. (This paper was actually finished and submitted several months ago, but for some reason I neglected to upload it to the arXiv until now.) Here we show that given an arbitrary 
What’s new
Updates on my research and expository papers, discussion of open problems, and other maths-related topics. By Terence Tao
10 comments
Comments feed for this article
14 March, 2007 at 11:08 am
MK
There is an interesting (to some) random matrix problem that when scaled by sqrt{n} the empirical distribution of an n times n matrix A with i.i.d. complex valued entries with mean zero and unit variance, converges to uniform distribution on the unit disk (”Girko’s circular law” - the non-Hermitian analogue of Wigner’s semicircle law).
Bai has shown that the essential problem is to get a bound on the probability that (zI-A) has a small singular value(which has been done only under certain conditions on the distribution of the entries). A much weaker bound than the type that you have in this paper is needed. I wonder if your results don’t actually settle this problem?
15 March, 2007 at 9:53 am
Terence Tao
Dear MK, Thank you for the interesting suggestion, which we will look into! My co-author Van pointed out to me that there is some precedent for this type of connection: a recent paper by Gotze and Tikhomirov uses (modifications of) some earlier work of Rudelson on bounding the least singular value of random matrices to justify a circular law in certain cases. Our work does share many features in common with Rudelson’s work, including the treatment of various exceptional directions and the use of inverse Littlewood-Offord technology.
15 March, 2007 at 12:43 pm
van vu
Dear MK,
Thanks for pointing it out. I have a quick look at a recent paper of Gotze and Tikhomirov and it seemed that our result can be applied directly to zI-A, and so one can skip
lots of calculations there.
There was another paper of Girko that we could not comprehend, about central limit theorem for the determinant of a random matrix (where the entries can have very general distributions, not just gaussians). Have you seen that ?
15 March, 2007 at 11:08 pm
Gil Kalai
Dear all, There are many nice open problems around the random 0-1 matrices and connections to Sperner’s theorem and Littlewood-Offord. Here is one problem which might be the most bizarre:
let
be the probability that a random n by n 0-1 matrix has determinant equal to k. So 
is exponentially small and 
is probably even smaller when k is not zero. (maybe 
, this is interesting but not yet bizarre)
The question is if
Here are two heuristics in favor and against it.
Heuristic 1: the determinant as a sum of n! signed random product clearly behave smoothly. OK,
is sort of a singular value, but you can expect that 
will be similar to 
when 
and 
are small (in absolute value) (even just 
.) Certainly 
and 
are very close.
Apropos this. Jeff Kahn challenged to prove that for
n by n matrices the permanent is zero with probability o(1). There you can also expect smoothness of the probabilities (beside that obvious parity condition.)
Heuristic 2: what is the probability that det = 0 (mod p) for a prime p? Well, 0-1 matrices should behave like random matrix mod p with entries 0,1,,…,p-1. But there the answer (denote it
} is known:
it is this familiar infinite product. (Not too far from 1/p.)
The probability
that a random such matrix has determinant 1 (mod p) is 
.
Next we can assume that the behavior is independent for different primes. So you get the prediction that the probability for 0-1 matrices that det = 1 differ by a constant from the probability that det = a power of 2.
And the probability that
should perhaps be similar for different 
.
All in all
is smaller than 
by a factor of n or 
or so.
And by this strange heuristic if |j| is not too large,
depends on how many prime factors 
has.
Heuristic 2 is rather dubious but perhaps enough to shed some doubts.
16 March, 2007 at 5:51 am
vanvu
Dear Gil,
To me, Heuristic 2 looks like the situation with sieves in number theory. For very small
p, the independence look OK. But for relatively large p, it is quite wrong. If we do sieve the trivial way (before Brunn), the estimate was quite miserable.
16 March, 2007 at 2:11 pm
MK
Dear Vu and Tao, Gotze and Tikhomirov apparently need Gaussian tails for the entries, so one point of interest would be to remove all such assumptions (Bai has a Lindeberg type condition to reduce the circular law problem to one of estimating smallest singular values and perhaps there should be no more assumptions on the entries at all?).
I do not know which paper of Girko you refer to, but his claimed proofs of circular law are incomplete as he skips over this issue of small singular values of ZI-A. There are also some other nonHermitian random matrix problems which were held up by this issue so far and should be accessible now (assuming there is no catch in extending your result to complex matrices).
16 March, 2007 at 4:10 pm
vanvu
Dear MK,
If I understand well, there is a standard machinery to reduce the CL to the problem of estimating the smallest singular value. If it is true, then what would be the most general assumption for which this machinery works ? (Then we just have to check whether our result still hold under that assumption; it is certainly hold for complex entries.)
Btw, can we know your full name ? (You can send private email to us if not want to disclose it here).
Thanks, Van Vu
17 March, 2007 at 10:21 am
Manjunath Krishnapur
The machinery for reducing CL to estimating small singular values is in Bai’s 1997 paper “Circular law” (Ann. Probab.) The recent book of Bai and Silverstein seems to say that the weakest known condition is (A is the
random matrix)
for any t>0 and some s>0. (page 326, “Spectral analysis of large dimensional random matrices”).
And thanks for confirming that your theorems remain valid for complex matrices!
17 March, 2007 at 12:13 pm
Gil Kalai
Dear all. Thanks for your comment, Van. Sure, if Heuristic 2 can be improved a la Brunn this is even better. I suppose my question is whether the probability that an n by n matrix with entries 0/1 (or plus or minus one,) has determinant equal to k, depends in a strong way on the arithmetic of k. Heuristic 2 suggests that this IS the case and this is an appealing conjecture simply because it will be more interesting.
For matrices with entries plus or minus one I would expect the probability for the permanent to be equal to 2k behave very smoothly for k, like the probability of a length n! random walk from the origin landing in location 2k. But for determinants the heuristic will suggest a very different and nicer picture.
12 June, 2007 at 2:23 pm
STOC talk: The condition number of a randomly perturbed matrix « What’s new
[...] with Van Vu on the condition number of randomly perturbed matrices, which was the subject of an earlier post on this blog. For this short talk (20 minutes), Van and I prepared some slides; of course, in such a short time [...]