# Structure of eigenvectors of random regular digraphs

@article{Litvak2019StructureOE, title={Structure of eigenvectors of random regular digraphs}, author={Alexander E. Litvak and Anna Lytova and Konstantin E. Tikhomirov and Nicole Tomczak-Jaegermann and Pierre Youssef}, journal={Transactions of the American Mathematical Society}, year={2019} }

Let $n$ be a large integer, let $d$ satisfy $C\leq d\leq \exp(c\sqrt{\ln n})$ for some universal constants $c, C>0$, and let $z\in {\mathcal C}$. Further, denote by $M$ the adjacency matrix of a random $d$-regular directed graph on $n$ vertices. In this paper, we study structure of the kernel of submatrices of $M-z\,{\rm Id}$, formed by removing a subset of rows. We show that with large probability the kernel consists of two non-intersecting types of vectors, which we call very steep and… Expand

#### 13 Citations

Circular law for sparse random regular digraphs

- Mathematics
- 2018

Fix a constant $C\geq 1$ and let $d=d(n)$ satisfy $d\leq \ln^{C} n$ for every large integer $n$. Denote by $A_n$ the adjacency matrix of a uniform random directed $d$-regular graph on $n$ vertices.… Expand

Invertibility of adjacency matrices for random d-regular graphs

- Mathematics
- Duke Mathematical Journal
- 2021

Let $d\geq 3$ be a fixed integer and $A$ be the adjacency matrix of a random $d$-regular directed or undirected graph on $n$ vertices. We show there exist constants $\mathfrak d>0$, \begin{align*}… Expand

Invertibility of adjacency matrices for random d-regular directed graphs

- Mathematics
- 2018

Let $d\geq 3$ be a fixed integer, and a prime number $p$ such that $\gcd(p,d)=1$. Let $A$ be the adjacency matrix of a random $d$-regular directed graph on $n$ vertices. We show that as a random… Expand

The smallest singular value of a shifted d-regular random square matrix

- Mathematics
- Probability Theory and Related Fields
- 2018

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< c n/\log ^2… Expand

The rank of random regular digraphs of constant degree

- Mathematics, Computer Science
- J. Complex.
- 2018

It is shown that A_n has rank at least at least $n-1$ with probability going to one as $n$ goes to infinity. Expand

Singularity of sparse Bernoulli matrices

- Mathematics
- 2020

Let $M_n$ be an $n\times n$ random matrix with i.i.d. Bernoulli(p) entries. We show that there is a universal constant $C\geq 1$ such that, whenever $p$ and $n$ satisfy $C\log n/n\leq p\leq C^{-1}$,… Expand

Cokernels of adjacency matrices of random $r$-regular graphs

- Mathematics
- 2018

We study the distribution of the cokernels of adjacency matrices (the Smith groups) of certain models of random $r$-regular graphs and directed graphs, using recent mixing results of M\'esz\'aros. We… Expand

Singularity of Bernoulli matrices in the sparse regime $pn = O(\log(n))$

- Mathematics
- 2020

Consider an $n\times n$ random matrix $A_n$ with i.i.d Bernoulli($p$) entries. In a recent result of Litvak-Tikhomirov, they proved the conjecture $$ \mathbb{P}\{\mbox{$A_n$ is singular}\}=(1+o_n(1))… Expand

On delocalization of eigenvectors of random non-Hermitian matrices

- Mathematics
- 2018

We study delocalization of null vectors and eigenvectors of random matrices with i.i.d entries. Let A be an $$n\times n$$ n × n random matrix with i.i.d real subgaussian entries of zero mean and unit… Expand

Eigenvectors and controllability of non-Hermitian random matrices and directed graphs

- Mathematics
- 2020

We study the eigenvectors and eigenvalues of random matrices with iid entries. Let $N$ be a random matrix with iid entries which have symmetric distribution. For each unit eigenvector $\mathbf{v}$ of… Expand

#### References

SHOWING 1-10 OF 63 REFERENCES

Circular law for sparse random regular digraphs

- Mathematics
- 2018

Fix a constant $C\geq 1$ and let $d=d(n)$ satisfy $d\leq \ln^{C} n$ for every large integer $n$. Denote by $A_n$ the adjacency matrix of a uniform random directed $d$-regular graph on $n$ vertices.… Expand

Adjacency matrices of random digraphs: singularity and anti-concentration

- Mathematics
- 2015

Let ${\mathcal D}_{n,d}$ be the set of all $d$-regular directed graphs on $n$ vertices. Let $G$ be a graph chosen uniformly at random from ${\mathcal D}_{n,d}$ and $M$ be its adjacency matrix. We… Expand

On the singularity of adjacency matrices for random regular digraphs

- Mathematics
- 2014

We prove that the (non-symmetric) adjacency matrix of a uniform random d-regular directed graph on n vertices is asymptotically almost surely invertible, assuming $$\min (d,n-d)\ge C\log… Expand

On the almost eigenvectors of random regular graphs

- Mathematics
- The Annals of Probability
- 2019

Let $d\geq 3$ be fixed and $G$ be a large random $d$-regular graph on $n$ vertices. We show that if $n$ is large enough then the entry distribution of every almost eigenvector $v$ of $G$ (with entry… Expand

The spectral gap of dense random regular graphs

- Mathematics
- The Annals of Probability
- 2019

For any $\alpha\in (0,1)$ and any $n^{\alpha}\leq d\leq n/2$, we show that $\lambda(G)\leq C_\alpha \sqrt{d}$ with probability at least $1-\frac{1}{n}$, where $G$ is the uniform random $d$-regular… Expand

Functional limit theorems for random regular graphs

- Mathematics
- 2013

Consider $$d$$ uniformly random permutation matrices on $$n$$ labels. Consider the sum of these matrices along with their transposes. The total can be interpreted as the adjacency matrix of a random… Expand

Expansion of random graphs: new proofs, new results

- Mathematics
- 2015

We present a new approach to showing that random graphs are nearly optimal expanders. This approach is based on recent deep results in combinatorial group theory. It applies to both regular and… Expand

The smallest singular value of a shifted d-regular random square matrix

- Mathematics
- Probability Theory and Related Fields
- 2018

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< c n/\log ^2… Expand

The rank of random regular digraphs of constant degree

- Mathematics, Computer Science
- J. Complex.
- 2018

It is shown that A_n has rank at least at least $n-1$ with probability going to one as $n$ goes to infinity. Expand

The Circular Law for random regular digraphs

- Mathematics
- Annales de l'Institut Henri Poincaré, Probabilités et Statistiques
- 2019

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… Expand