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:
Other related papers include:
- "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).
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.
- "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.
In class, Igor Pak mentioned a paper that bounds the probability that a random
+/-1 matrix is degenerate. The paper is:
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.
- "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)
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
norm(A*x - b)
Ap = A + randn(100)/(10^7);
x = Ap \ b;
norm(A*x - b)