Angela DaiDos Pueblos High School, Goleta, California, USACaroline KimDos Pueblos High School, Goleta, California, USAJohn KimDos Pueblos High School, Goleta, California, USA
S.-T. Yau High School Science Awarded Papersmathscidoc:1608.35012
2008
Motivated by an extra credit problem from our Linear Algebra class, we study the invertibility probability of binary matrices (the number of invertible binary matrices divided by the total number of binary matrices). Binary matrices are of interest in combinatorics, information theory, cryptology, and graph theory. It is known that the invertibility probability of n × n binary matrices goes to 1 as n→∞. We conjecture that this probability monotonically increases as the size of the binary matrix increases, and we investigate this by exploring how n×n binary matrices of rank n and rank (n−1) can be enlarged to (n + 1) × (n + 1) invertible binary matrices. Calculating this explicitly for the identity matrix, we obtain a probable bound that would show that, in a sense, our conjecture is asymptotically true. With the use of a computer, we also computed how many (n + 1) × (n + 1) invertible binary matrices can be enlarged from n×n matrices of rank n and rank (n−1) for small n. In addition, we study the invertibility probability of matrices with entries in Z_q.
@inproceedings{angela2008invertibility,
title={Invertibility probability of binary matrices},
author={Angela Dai, Caroline Kim, and John Kim},
url={http://archive.ymsc.tsinghua.edu.cn/pacm_paperurl/20160813215154611241059},
year={2008},
}
Angela Dai, Caroline Kim, and John Kim. Invertibility probability of binary matrices. 2008. http://archive.ymsc.tsinghua.edu.cn/pacm_paperurl/20160813215154611241059.