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: 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: 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

norm(A*x - b)

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

norm(A*x - b)