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

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. More precisely, let

C_{1} < d < c_{1} n / l o g^{2} n

and let

m a t h c a l M_{n, d}

be the set of all

0 / 1

-valued square

n i m e s n

matrices such that each row and each column of a matrix

M i n m a t h c a l M_{n, d}

has exactly

d

ones. Let

M

be uniformly distributed on

m a t h c a l M_{n, d}

. Then the smallest singular value

s_{n} (M)

of

M

is greater than

c_{2} n^{- 6}

with probability at least

1 - C_{2} l o g^{2} d / s q r t d

, where

c_{1}

,

c_{2}

,

C_{1}

, and

C_{2}

are absolute positive constants independent of any other parameters.

Recommendations

Cites work

Cited in

(19)

This page was built for publication: The smallest singular value of a shifted $d$-regular random square matrix