
We obtain lower tail estimates for the smallest singular value of random
matrices with independent but nonidentically distributed entries.
Specifically, we consider $n\times n$ matrices with complex entries of the form
\[ M = A\circ X + B = (a_{ij}\xi_{ij} + b_{ij}) \] where $X=(\xi_{ij})$ has iid
centered entries of unit variance and $A$ and $B$ are fixed matrices. In our
main result we obtain polynomial bounds on the smallest singular value of $M$
for the case that $A$ has bounded (possibly zero) entries, and $B= Z\sqrt{n}$
where $Z$ is a diagonal matrix with entries bounded away from zero. As a
byproduct of our methods we can also handle general perturbations $B$ under
additional hypotheses on $A$, which translate to connectivity hypotheses on an
associated graph. In particular, we extend a result of Rudelson and Zeitouni
for Gaussian matrices to allow for general entry distributions satisfying some
moment hypotheses. Our proofs make use of tools which (to our knowledge) were
previously unexploited in random matrix theory, in particular Szemer\'edi's
Regularity Lemma, and a version of the Restricted Invertibility Theorem due to
Spielman and Srivastava.

We consider random $n\times n$ matrices of the form
$Y_n=\frac1{\sqrt{d}}A_n\circ X_n$, where $A_n$ is the adjacency matrix of a
uniform random $d$regular directed graph on $n$ vertices, with $d=\lfloor p
n\rfloor$ for some fixed $p \in (0,1)$, and $X_n$ is an $n\times n$ matrix of
iid centered random variables with unit variance and finite $4+\eta$th moment
(here $\circ$ denotes the matrix Hadamard product). We show that as $n\to
\infty$, the empirical spectral distribution of $Y_n$ converges weakly in
probability to the normalized Lebesgue measure on the unit disk.

Let $\log^Cn\le d\le n/2$ for a sufficiently large constant $C>0$ and let
$A_n$ denote the adjacency matrix of a uniform random $d$regular directed
graph on $n$ vertices. We prove that as $n$ tends to infinity, the empirical
spectral distribution of $A_n$, suitably rescaled, is governed by the Circular
Law. A key step is to obtain quantitative lower tail bounds for the smallest
singular value of additive perturbations of $A_n$.

Let $\lambda$ be the second largest eigenvalue in absolute value of a uniform
random $d$regular graph on $n$ vertices. It was famously conjectured by Alon
and proved by Friedman that if $d$ is fixed independent of $n$, then
$\lambda=2\sqrt{d1} +o(1)$ with high probability. In the present work we show
that $\lambda=O(\sqrt{d})$ continues to hold with high probability as long as
$d=O(n^{2/3})$, making progress towards a conjecture of Vu that the bound holds
for all $1\le d\le n/2$. Prior to this work the best result was obtained by
Broder, Frieze, Suen and Upfal (1999) using the configuration model, which hits
a barrier at $d=o(n^{1/2})$. We are able to go beyond this barrier by proving
concentration of measure results directly for the uniform distribution on
$d$regular graphs. These come as consequences of advances we make in the
theory of concentration by size biased couplings. Specifically, we obtain
Bennetttype tail estimates for random variables admitting certain unbounded
size biased couplings.

We prove that the (nonsymmetric) adjacency matrix of a uniform random
$d$regular directed graph on $n$ vertices is asymptotically almost surely
invertible, assuming $\min(d,nd)\ge C\log^2n$ for a sufficiently large
constant $C>0$. The proof makes use of a coupling of random regular digraphs
formed by "shuffling" the neighborhood of a pair of vertices, as well as
concentration results for the distribution of edges recently obtained by the
author (arXiv:1410.5595). We also apply our general approach to prove a.a.s.\
invertibility of Hadamard products $\Sigma\circ \Xi$, where $\Xi$ is a matrix
of iid uniform $\pm1$ signs, and $\Sigma$ is a 0/1 matrix whose associated
digraph satisfies certain "expansion" properties.

For the uniform random regular directed graph we prove concentration
inequalities for (1) codegrees and (2) the number of edges passing from one set
of vertices to another. As a consequence, we can deduce discrepancy properties
for the distribution of edges essentially matching results for
Erd\H{o}sR\'enyi digraphs obtained from Chernofftype bounds. The proofs make
use of the method of exchangeable pairs, developed for concentration of measure
by Chatterjee. Exchangeable pairs are constructed using two involutions on the
set of regular digraphs: a wellknown "simple switching" operation, as well as
a novel "reflection" operation.

Fix $c\in (0,1)$ and let $\Gamma$ be a $\lfloor c n\rfloor$regular digraph
on $n$ vertices drawn uniformly at random. We prove that when $n$ is large, the
(nonsymmetric) adjacency matrix $M$ of $\Gamma$ is invertible with high
probability. The proof uses a couplings approach based on the switchings method
of McKay and Wormald. We also rely on discrepancy properties for the
distribution of edges in $\Gamma$, recently proved by the author, to overcome
certain difficulties stemming from the dependencies between the entries of $M$.