LU Factorization of Discrete Random Matrices

Le résumé fourni par la source

We consider the probability that a discrete random matrix $M_n(ξ)$ 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 $ξ$ with finite support and $|ξ|_\infty < 1$, there is a constant probability that $M_n(ξ)$ is strongly non-singular with a growth factor bounded by $n^{5/2+δ}$. Furthermore, we provide a tight asymptotic lower bound for this probability as $|ξ|_\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.

Ce résumé expose les affirmations des auteurs. BNTIC ne l’interprète pas comme une validation indépendante des résultats.