Invertibility probability of binary matrices

Angela Dai Dos Pueblos High School, Goleta, California, USA Caroline Kim Dos Pueblos High School, Goleta, California, USA John Kim Dos Pueblos High School, Goleta, California, USA

S.-T. Yau High School Science Awarded Papers mathscidoc: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.
No keywords uploaded!
[ Download ] [ 2016-08-13 21:51:54 uploaded by yauawardadmin ] [ 2306 downloads ] [ 0 comments ]
@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.
Please log in for comment!
 
 
Contact us: office-iccm@tsinghua.edu.cn | Copyright Reserved