Rank of the Vertex-Edge Incidence Matrix of r-Out Hypergraphs
Authors: 
Colin Cooper, Alan FriezeAuthors Info & Claims
Colin Cooper, Alan FriezeAuthors Info & ClaimsPages 2238 - 2257
Abstract
We consider the rank of a class of sparse Boolean matrices of size $n \times n$. In particular, we show that the probability that such a matrix has full rank, and is thus invertible, is a positive constant with value about 0.2574 for large $n$. The matrices arise as the vertex-edge incidence matrix of 1-out 3-uniform hypergraphs. The result that the null space is bounded in expectation can be contrasted with results for the usual models of sparse Boolean matrices, based on the vertex-edge incidence matrix of random $k$-uniform hypergraphs. For this latter model, the expected co-rank is linear in the number of vertices $n$, [A. Coja-Oghlan et al., in Proceedings of SODA, 2020, pp. 579--591], [C. Cooper, A. M. Frieze, and W. Pegden, in Proceedings of SODA, 2019, pp. 946--955]. For fields of higher order, the co-rank is typically Poisson distributed.
References
[1]
D. Achiloptas and M. Molloy, The solution space geometry of random linear equations, Random Structures Algorithms, 46 (2015), pp. 197--231.
[2]
B. Bollobas, Random Graphs, 2nd ed., Cambridge University Press, Cambridge, 2001.
[3]
R. Brualdi and H. Ryser, Combinatorial Matrix Theory, Cambridge University Press, Cambridge, 1991.
[4]
T. Bohman and A. M. Frieze, Hamilton cycles in 3-out, Random Structures Algorithms, 35 (2009), pp. 393--417.
[5]
A. Coja-Oghlan, A. Ergür, P. Gao, S. Hetterich, and M. Rolvien, The rank of sparse random matrices, in Proceedings of SODA, 2020, pp. 579--591.
[6]
C. Cooper, On the rank of random matrices, Random Structures Algorithms, 16 (2000), pp. 209--232.
[7]
C. Cooper, On the distribution of rank of a random matrix over a finite field, Random Structures Algorithms, 17 (2000), pp. 197--212.
[8]
C. Cooper, A. M. Frieze and W. Pegden, On the rank of a random binary matrix, in Proceedings of SODA, 2019, pp. 946--955.
[9]
C. Cooper and A. M. Frieze, Rank of the Vertex-Edge Incidence Matrix of $r$-Out Hypergraphs, https://arxiv.org/pdf/2107.05779.pdf, 2021.
[10]
T. Fenner and A. M. Frieze, On the connectivity of random m-orientable graphs and digraphs, Combinatorica, 2 (1982), pp. 347--359.
[11]
A. M. Frieze, Maximum matchings in a class of random graphs, J. Combin. Theory B, 40 (1986), pp. 196--212.
[12]
A. M. Frieze and M. Karoński, Introduction to Random Graphs, Cambridge University Press, Cambridge, 2016.
[13]
M. Ibrahimi, Y. Kanoria, M. Kraning and A. Montanari, The set of solutions of random XORSAT formulae, Ann. Appl. Probab., 25 (2015), pp. 2743--2808.
[14]
I. N. Kovalenko, A. A. Levitskya, and M. N. Savchuk, Selected Problems in Probabilistic Combinatorics, Naukova Dumka, Kyiv, 1986 (in Russian).
Index Terms
- Rank of the Vertex-Edge Incidence Matrix of r-Out Hypergraphs
Index terms have been assigned to the content through auto-classification.
Recommendations
Reliable Krylov-based algorithms for matrix null space and rank
ISSAC '04: Proceedings of the 2004 international symposium on Symbolic and algebraic computationKrylov-based algorithms have recently been used, in combination with other methods, to solve systems of linear equations and to perform related matrix computations over finite fields. For example, large and sparse systems of linear equations ;2; are ...
Computing the rank and a small nullspace basis of a polynomial matrix
ISSAC '05: Proceedings of the 2005 international symposium on Symbolic and algebraic computationWe reduce the problem of computing the rank and a null-space basis of a univariate polynomial matrix to polynomial matrix multiplication. For an input n x n matrix of degree, d over a field K we give a rank and nullspace algorithm using about the same ...
Detection Thresholds in Very Sparse Matrix Completion
AbstractWe study the matrix completion problem: an underlying matrix P is low rank, with incoherent singular vectors, and a random matrix A is equal to P on a (uniformly) random subset of entries of size dn. All other entries of A are equal to ...
Comments
Information & Contributors
Information
Published In
© 2022, Society for Industrial and Applied Mathematics.
Publisher
Society for Industrial and Applied Mathematics
United States
Publication History
Published: 01 January 2022
Author Tags
Author Tags
Qualifiers
- Research-article
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 0Total Downloads
- Downloads (Last 12 months)0
- Downloads (Last 6 weeks)0
Reflects downloads up to 22 Sep 2024
Other Metrics
Citations
View Options
View options
Get Access
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in