Samuel Orellana Mateo
MIT Department: Mathematics
Faculty Mentor: Prof. John Urschel
Research Supervisor:
Undergraduate Institution: Duke University
Website:
Biography
Samuel Orellana Mateo is a student at Duke University pursuing a Bachelor of Sciencein Mathematics and Computer Science. His research interests lie in algebra and topology. Aspart of the MSRP program, he is working with Prof. John Urschel in the MIT Department of Mathematics to investigate the probability that a random binary matrix admits an LU factorization. His prior research experience includes work on problems in the mathematicsof juggling during a summer program at Iowa State University. Samuel enjoys competitive mathematics, having earned multiple silver medals in the Spanish Mathematical Olympiad, a bronze certificate in the Mediterranean Mathematics Competition, and placed in the top 10%of participants in the William Lowell Putnam Mathematical Competition. He is also passionate about making STEM accessible, having led several sessions to help students prepare for math olympiads in Spain and serving as a mentor for the Aditus Program to help underrepresented students navigate the college application process. Samuel plans to pursue a Ph.D. in mathematics.
Abstract
LU Factorization of Binary Matrices
Samuel Orellana Mateo1, and John Urschel2
1Department of Mathematics, Duke University
2Department of Mathematics, Massachusetts Institute of Technology
Random matrices are the standard model for systems whose inputs are governed by an explicit yet uncertain distribution. LU factorization is the workhorse that extracts usable structure from the resulting data. Although the singularity probability of such matrices has been exhaustively analyzed, the probability that a random n × n binary matrix actually admits an LU decomposition (meaning every leading principal minor is non-zero) remains an open question. We close this gap for discrete distributions. For any non-constant random variable ξ taking values in a finite set, we prove that the probability that an n × n matrix with i.i.d. ξ entries is LU-factorizable is bounded away from zero for every n, and we compute upper bounds of this probability as n → ∞ for Ber(p). We also treat the behavior of the degenerate limits Ber(p) with p → 0 and p → 1. These supply the first rigorous guarantees for randomized LU-based algorithms on large-scale discrete data, while opening new avenues in the average-case analysis of discrete random matrices.