  We prove that standard Gaussian random multipliers are expected to
numerically stabilize both Gaussian elimination with no pivoting and block
Gaussian elimination. Moreover we prove that such a multiplier (even without
the customary oversampling) is expected to support low-rank approximation of a
matrix. Our test results are in good accordance with this analysis. Empirically
random circulant or Toeplitz multipliers are as efficient as Gaussian ones, but
their formal support is more problematic.
