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 matrix M with polynomially bounded entries (in particular, M could be highly singular), a random discrete perturbation M+N, where N is (say) a random Bernoulli matrix, will have polynomially bounded condition number with high probability (specifically, given any A there exists a B such that the condition number is with probability ). This is the discrete analogue of an analogous result by Spielman and Teng for continuous random perturbations. The proof uses the inverse Littlewood-Offord technology as well as a discretisation lemma for generalized arithmetic progressions, both from our previous paper (which essentially addressed the M=0 case). It turns out that the effect of M is essentially just to add a few deterministic rows to a random matrix which one needs to obtain lower bounds for the least singular value.

### Recent Comments

### Articles by others

- Gene Weingarten – Pearls before breakfast
- Isaac Asimov – The relativity of wrong
- Jonah Lehrer – Don't! – the secret of self-control
- Julianne Dalcanton – The cult of genius
- Nassim Taleb – The fourth quadrant: a map of the limits of statistics
- Paul Graham – What You'll Wish You'd Known
- Po Bronson – How not to talk to your kids
- Scott Aaronson – Ten signs a claimed mathematical proof is wrong
- Timothy Gowers – Elsevier — my part in its downfall
- Timothy Gowers – The two cultures of mathematics
- William Thurston – On proof and progress in mathematics

### Diversions

- Abstruse Goose
- Assembler
- BoxCar2D
- Factcheck.org
- FiveThirtyEight
- Gapminder
- Literally Unbelievable
- Planarity
- PolitiFact
- Quite Interesting
- snopes
- Strange maps
- Television tropes and idioms
- The Daily Show with Jon Stewart
- The Economist
- The Onion
- The Straight Dope
- This American Life on the financial crisis I
- This American Life on the financial crisis II
- What if? (xkcd)
- White whine
- xkcd

### Mathematics

- 0xDE
- A Mind for Madness
- A Portion of the Book
- Absolutely useless
- Alex Sisto
- AMS blogs
- AMS Graduate Student Blog
- Analysis & PDE
- Analysis & PDE Conferences
- Annoying Precision
- Area 777
- Ars Mathematica
- ATLAS of Finite Group Representations
- Automorphic forum
- Avzel's journal
- Blog on Math Blogs
- Blog On Mathematical Journals
- blogderbeweise
- Bubbles Bad; Ripples Good
- Cédric Villani
- Climbing Mount Bourbaki
- Coloquio Oleis
- Combinatorics and more
- Compressed sensing resources
- Computational Complexity
- Concrete nonsense
- David Mumford's blog
- Delta epsilons
- DispersiveWiki
- Disquisitiones Mathematicae
- Embûches tissues
- Emmanuel Kowalski’s blog
- Encyclopedia of Mathematics
- Equatorial Mathematics
- fff
- Floer Homology
- Frank Morgan’s blog
- Gérard Besson's Blog
- Gödel’s Lost Letter and P=NP
- Geometric Group Theory
- Geometry and the imagination
- Geometry Bulletin Board
- Girl's Angle
- God Plays Dice
- Good Math, Bad Math
- Graduated Understanding
- Hydrobates
- I Woke Up In A Strange Place
- Igor Pak's blog
- Images des mathématiques
- In theory
- James Colliander's Blog
- Jérôme Buzzi’s Mathematical Ramblings
- Joel David Hamkins
- Journal of the American Mathematical Society
- Kill Math
- Le Petit Chercheur Illustré
- Lemma Meringue
- Lewko's blog
- Libres pensées d’un mathématicien ordinaire
- LMFDB – L-functions and modular forms database
- LMS blogs page
- London number theory
- Low Dimensional Topology
- M-Phi
- MAA MinuteMath
- Math Overflow
- Mathbabe
- Mathblogging
- Mathematical musings
- Mathematics Illuminated
- Mathematics in Australia
- Mathematics Jobs Wiki
- Mathematics Stack Exchange
- Mathematics under the Microscope
- Mathlog
- MathOnline
- Mathtube
- Matt Baker's Math Blog
- Mixedmath
- Motivic stuff
- Much ado about nothing
- Multiple Choice Quiz Wiki
- neverendingbooks
- nLab
- Noncommutative geometry blog
- Nonlocal equations wiki
- Not "Not Even Wrong"
- Nuit-blanche
- Number theory web
- outofprintmath
- PDE blog
- Pengfei Zhang's blog
- Peter Cameron's Blog
- Phillipe LeFloch's blog
- ProofWiki
- Quomodocumque
- Random Math
- Reasonable Deviations
- Regularize
- Rigorous Trivialities
- Roots of unity
- Secret Blogging Seminar
- Selected Papers Network
- Sergei Denisov's blog
- Shtetl-Optimized
- Shuanglin's Blog
- Since it is not…
- Sketches of topology
- Soft questions
- Stacks Project Blog
- SymOmega
- tcs math
- TeX, LaTeX, and friends
- The accidental mathematician
- The capacity to be alone
- The Cost of Knowledge
- The Everything Seminar
- The Geomblog
- The Mathematics Literature Project
- The n-Category Café
- The n-geometry cafe
- The On-Line Blog of Integer Sequences
- The polylogblog
- The polymath blog
- The polymath wiki
- The Tricki
- The twofold gaze
- The Unapologetic Mathematician
- The value of the variable
- The World Digital Mathematical Library
- Theoretical Computer Science – StackExchange
- Tim Gowers’ blog
- Tim Gowers’ mathematical discussions
- Todd and Vishal’s blog
- Van Vu's blog
- Vaughn Climenhaga
- Vieux Girondin
- Visual Insight
- Vivatsgasse 7
- Williams College Math/Stat Blog
- Windows on Theory
- Wiskundemeisjes
- XOR’s hammer
- Zhenghe's Blog

### Selected articles

- A cheap version of nonstandard analysis
- A review of probability theory
- American Academy of Arts and Sciences speech
- Amplification, arbitrage, and the tensor power trick
- An airport-inspired puzzle
- Benford's law, Zipf's law, and the Pareto distribution
- Compressed sensing and single-pixel cameras
- Einstein’s derivation of E=mc^2
- On multiple choice questions in mathematics
- Quantum mechanics and Tomb Raider
- Real analysis problem solving strategies
- Sailing into the wind, or faster than the wind
- Simons lectures on structure and randomness
- Small samples, and the margin of error
- Soft analysis, hard analysis, and the finite convergence principle
- The blue-eyed islanders puzzle
- The cosmic distance ladder
- The federal budget, rescaled
- Ultrafilters, non-standard analysis, and epsilon management
- What is a gauge?
- What is good mathematics?
- Why global regularity for Navier-Stokes is hard

### Software

### The sciences

### Top Posts

- Embedding the SQG equation in a modified Euler equation
- The blue-eyed islanders puzzle
- Career advice
- Does one have to be a genius to do maths?
- The Euler-Maclaurin formula, Bernoulli numbers, the zeta function, and real-variable analytic continuation
- On writing
- Books
- Newton iteration and the Siegel linearisation theorem
- There’s more to mathematics than rigour and proofs
- Solving mathematical problems

### Archives

- April 2015 (4)
- March 2015 (3)
- February 2015 (4)
- January 2015 (4)
- December 2014 (6)
- November 2014 (5)
- October 2014 (4)
- September 2014 (3)
- August 2014 (4)
- July 2014 (5)
- June 2014 (5)
- May 2014 (5)
- April 2014 (2)
- March 2014 (4)
- February 2014 (5)
- January 2014 (4)
- December 2013 (4)
- November 2013 (5)
- October 2013 (4)
- September 2013 (5)
- August 2013 (1)
- July 2013 (7)
- June 2013 (12)
- May 2013 (4)
- April 2013 (2)
- March 2013 (2)
- February 2013 (6)
- January 2013 (1)
- December 2012 (4)
- November 2012 (7)
- October 2012 (6)
- September 2012 (4)
- August 2012 (3)
- July 2012 (4)
- June 2012 (3)
- May 2012 (3)
- April 2012 (4)
- March 2012 (5)
- February 2012 (5)
- January 2012 (4)
- December 2011 (8)
- November 2011 (8)
- October 2011 (7)
- September 2011 (6)
- August 2011 (8)
- July 2011 (9)
- June 2011 (8)
- May 2011 (11)
- April 2011 (3)
- March 2011 (10)
- February 2011 (3)
- January 2011 (5)
- December 2010 (5)
- November 2010 (6)
- October 2010 (9)
- September 2010 (9)
- August 2010 (3)
- July 2010 (4)
- June 2010 (8)
- May 2010 (8)
- April 2010 (8)
- March 2010 (8)
- February 2010 (10)
- January 2010 (12)
- December 2009 (11)
- November 2009 (8)
- October 2009 (15)
- September 2009 (6)
- August 2009 (13)
- July 2009 (10)
- June 2009 (11)
- May 2009 (9)
- April 2009 (11)
- March 2009 (14)
- February 2009 (13)
- January 2009 (18)
- December 2008 (8)
- November 2008 (9)
- October 2008 (10)
- September 2008 (5)
- August 2008 (6)
- July 2008 (7)
- June 2008 (8)
- May 2008 (11)
- April 2008 (12)
- March 2008 (12)
- February 2008 (13)
- January 2008 (17)
- December 2007 (10)
- November 2007 (9)
- October 2007 (9)
- September 2007 (7)
- August 2007 (9)
- July 2007 (9)
- June 2007 (6)
- May 2007 (10)
- April 2007 (11)
- March 2007 (9)
- February 2007 (4)

### Categories

- expository (217)
- tricks (8)

- guest blog (9)
- Mathematics (610)
- math.AC (5)
- math.AG (37)
- math.AP (83)
- math.AT (15)
- math.CA (118)
- math.CO (142)
- math.CT (6)
- math.CV (13)
- math.DG (32)
- math.DS (64)
- math.FA (22)
- math.GM (9)
- math.GN (21)
- math.GR (76)
- math.GT (12)
- math.HO (9)
- math.IT (8)
- math.LO (46)
- math.MG (34)
- math.MP (25)
- math.NA (12)
- math.NT (114)
- math.OA (17)
- math.PR (78)
- math.QA (5)
- math.RA (23)
- math.RT (21)
- math.SG (4)
- math.SP (43)
- math.ST (4)

- non-technical (119)
- admin (41)
- advertising (16)
- diversions (4)
- media (11)
- journals (2)

- obituary (8)

- opinion (27)
- paper (155)
- question (95)
- polymath (68)

- talk (62)
- DLS (19)

- teaching (142)
- 245A – Real analysis (11)
- 245B – Real analysis (19)
- 245C – Real analysis (6)
- 254A – analytic prime number theory (16)
- 254A – ergodic theory (18)
- 254A – Hilbert's fifth problem (12)
- 254A – random matrices (14)
- 254B – expansion in groups (8)
- 254B – Higher order Fourier analysis (9)
- 285G – poincare conjecture (20)
- Logic reading seminar (8)

- travel (25)
- Uncategorized (1)

### Google+ feed

- An error has occurred; the feed is probably down. Try again later.

additive combinatorics
almost orthogonality
approximate groups
arithmetic progressions
Ben Green
Cauchy-Schwarz
Cayley graphs
characters
circular law
compactness
compressed sensing
concentration compactness
correspondence principle
eigenvalues
Elias Stein
Emmanuel Breuillard
entropy
equidistribution
ergodic theory
expander graphs
exponential sums
finite fields
Fourier transform
Four Moment Theorem
Freiman's theorem
Gowers uniformity norms
gradient shrinking solitons
graph theory
Gromov's theorem
GUE
Hilbert's fifth problem
hypergraphs
inverse conjecture
Kakeya conjecture
Lie algebras
Lie groups
Littlewood-Offord problem
Mobius function
multiple recurrence
Navier-Stokes equations
nilpotent groups
NLS
nonstandard analysis
parity problem
politics
polymath1
polymath8
polynomial method
polynomials
prime numbers
prime number theorem
project heatwave
random matrices
randomness
random walks
Ratner's theorem
regularity lemma
Ricci flow
Riemann zeta function
Schrodinger equation
Selberg sieve
sieve theory
spectral theorem
structure
Szemeredi's theorem
szemeredi regularity lemma
Tamar Ziegler
ultrafilters
ultraproducts
universality
Van Vu
wave maps
Weil conjectures
Wigner matrices
Yitang Zhang

### The Polymath Blog

- Two polymath (of a sort) proposed projects 20 January, 2014
- Polymath9: P=NP? (The Discretized Borel Determinacy Approach) 4 November, 2013
- Polymath8 – A Success ! 20 September, 2013
- Polymath7 research thread 5: the hot spots conjecture 9 August, 2013
- Polymath proposal: bounded gaps between primes 4 June, 2013
- Polymath proposal (Tim Gowers): Randomized Parallel Sorting Algorithm 2 March, 2013
- Next Polymath Project(s): What, When, Where? 14 February, 2013
- Polymath7 research threads 4: the Hot Spots Conjecture 10 September, 2012
- Minipolymath4 project, second research thread 13 July, 2012
- Minipolymath4 project: IMO 2012 Q3 12 July, 2012

### Mathematics in Australia

- Save pure mathematics at the VU University of Amsterdam 30 April, 2011
- ERA results for mathematical sciences in Australia 15 February, 2011
- Junior positions at ANU 8 November, 2010
- AustMS now on twitter 10 October, 2010
- Research not bad, but not stellar 9 May, 2010
- L’Oréal Australia For Women In Science Fellowships 11 April, 2010
- Postdoctoral position (Level A) in mathematics at Australian National University 18 January, 2010
- Cheryl Praeger named as 2009 Western Australian Scientist of the Year 2 December, 2009
- Positions at Australian National University 4 November, 2009
- Mathematics skills out for the count 26 October, 2009

## 10 comments

Comments feed for this article

14 March, 2007 at 11:08 am

MKThere 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 TaoDear 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 vuDear 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 KalaiDear 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

vanvuDear 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

MKDear 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

vanvuDear 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 KrishnapurThe 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 KalaiDear 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 […]