  We take a first small step to extend the validity of Rudelson-Vershynin type
estimates to some sparse random matrices, here random permutation matrices. We
give lower (and upper) bounds on the smallest singular value of a large random
matrix D+M where M is a random permutation matrix, sampled uniformly, and D is
diagonal. When D is itself random with i.i.d terms on the diagonal, we obtain a
Rudelson-Vershynin type estimate, using the classical theory of random walks
with negative drift.
