BAP: Lecture 3 (feb 14, 2002)

The notes for this lecture are available in

In this lecture, we bounded the largest singular value of a random matrix, using a 1-net. We also saw a demo of the instability of a bad example for Gaussian Elimination. The idea for the proof presented in class came from:

"Spaces with Large Distance to l^n_inf and Random Matrices", by Stanislaw J. Szarek, American Journal of Mathematics, Vol 112, Issue 6, Dec. 1990, pp. 899-942. (available at JSTOR).

Other related papers include:

"A Limit Theorem for the Norm of Random Matrices", bu Stuart Geman, appeared in Annals of Probability, Vol 8, Issue 2 (Apr. 1980), pp. 252-261. (available at JSTOR).
"Condition numbers of random matrices", by Stanislaw J. Szarek, appared in the Journal of Complexity, 7(2):131-149, June 1991.
"Eigenvalues and Condition Numbers of Random Matrices", by Alan Edelman, appeared in SIAM J. Matrix Anal. Appl., 1988, vol 9, no 4, pp. 543-560.

I still haven't found the ideal reference for the probability that the norm of a random matrix is large. If you do, please let me know.

In class, Igor Pak mentioned a paper that bounds the probability that a random +/-1 matrix is degenerate. The paper is:

"On the probability that a random +/- 1 matrix is singular", by Jeff Kahn, Janos Komlos, and Endre Szemeredi. It appeared in the Journal of the American Mathematical Society, Vol 8, Issue 1 (Jan 1995), pp. 223-240. (available at JSTOR)

The conjecture I made in class is strictly stronger than this result, so one might want to read this paper before working on the conjecture.

All of the matlab code used in this lecture may be found on the BAP matlab code directory. Today's matlab example was:

A = kahan2(100);
b = ones(100,1);
x = A \ b;

format short g
A*x

norm(A*x - b)

Ap = A + randn(100)/(10^7);
x = Ap \ b;

A*x
norm(A*x - b)