Typical rank of coin-toss power-law random matrices over GF(2)
arXiv:1011.1563
Abstract
Random linear systems over the Galois Field modulo 2 have an interest in connection with problems ranging from computational optimization to complex networks. They are often approached using random matrices with Poisson-distributed or finite column/row-sums. This technical note considers the typical rank of random matrices belonging to a specific ensemble wich has genuinely power-law distributed column-sums. For this ensemble, we find a formula for calculating the typical rank in the limit of large matrices as a function of the power-law exponent and the shape of the matrix, and characterize its behavior through "phase diagrams" with varying model parameters.
References in corpus (10)
- Emergence of scaling in random networks
- On the nature of the low-temperature phase in discontinuous mean-field spin glasses
- Exact solutions for diluted spin glasses and optimization problems
- Replica bounds for diluted non-Poissonian spin systems
- Geometrical organization of solutions to random linear Boolean equations
- Scaling and Renormalization Group in Replica Symmetry Breaking space: Evidence for a simple analytical solution of the SK model at zero temperature
- Complexity transitions in global algorithms for sparse linear systems over finite fields
- Typical kernel size and number of sparse random matrices over GF(q) - a statistical physics approach
- Introduction to Phase Transitions in Random Optimization Problems
- Random Networks Tossing Biased Coins