## Abstract

We derive a lower bound on the smallest singular value of a random d-regular matrix, that is, the adjacency matrix of a random d-regular directed graph. Specifically, let C _{1} < d< cn/ log ^{2} n and let M _{n} _{,} _{d} be the set of all n× n square matrices with 0 / 1 entries, such that each row and each column of every matrix in M _{n} _{,} _{d} has exactly d ones. Let M be a random matrix uniformly distributed on M _{n} _{,} _{d} . Then the smallest singular value s _{n} (M) of M is greater than n ^{- 6} with probability at least 1-C2log2d/d, where c, C _{1} , and C _{2} are absolute positive constants independent of any other parameters. Analogous estimates are obtained for matrices of the form M-zId, where Id is the identity matrix and z is a fixed complex number.

Original language | English (US) |
---|---|

Pages (from-to) | 1301-1347 |

Number of pages | 47 |

Journal | Probability Theory and Related Fields |

Volume | 173 |

Issue number | 3-4 |

DOIs | |

State | Published - Apr 5 2019 |

## Keywords

- Adjacency matrices
- Anti-concentration
- Condition number
- Invertibility
- Littlewood–Offord theory
- Random graphs
- Random matrices
- Regular graphs
- Singular probability
- Singularity
- Smallest singular value
- Sparse matrices

## ASJC Scopus subject areas

- Analysis
- Statistics and Probability
- Statistics, Probability and Uncertainty