LU Factorization of Discrete Random Matrices

Abstract

We consider the probability that a discrete random matrix $M_n(\xi )$ is \emph{strongly non-singular}, meaning all its leading principal submatrices are non-singular. This property is equivalent to the existence of an LU factorization. We show that for any discrete random variable $\xi$ with finite support and $|\xi {|}_{\infty }<1$, there is a constant probability that $M_n(\xi )$ is strongly non-singular with a growth factor bounded by $n^{5/2+\delta }$. Furthermore, we provide a tight asymptotic lower bound for this probability as $|\xi {|}_{\infty }\to 0$. Finally, we provide exact counts for strongly non-singular binary matrices up to $n=9$ and use these to derive improved upper bounds for the Bernoulli case.