Typical kernel size and number of sparse random matrices over GF(q) - a statistical physics approach

Abstract

Using methods of statistical physics, we study the average number and kernel size of general sparse random matrices over GF(q), with a given connectivity profile, in the thermodynamical limit of large matrices. We introduce a mapping of $GF(q)$ matrices onto spin systems using the representation of the cyclic group of order q as the q-th complex roots of unity. This representation facilitates the derivation of the average kernel size of random matrices using the replica approach, under the replica symmetric ansatz, resulting in saddle point equations for general connectivity distributions. Numerical solutions are then obtained for particular cases by population dynamics. Similar techniques also allow us to obtain an expression for the exact and average number of random matrices for any general connectivity profile. We present numerical results for particular distributions.

16 pages, 3 figures

References in corpus (13)

• The Bethe lattice spin glass revisited
• Coloring random graphs
• The Entropy of the K-Satisfiability Problem
• Spectra of Euclidean Random Matrices
• On the top eigenvalue of heavy-tailed random matrices
• Error-correcting code on a cactus: a solvable model
• Statistical Mechanics of Low-Density Parity Check Error-Correcting Codes over Galois Fields
• Random Graph Coloring - a Statistical Physics Approach
• Spectral Density of Sparse Sample Covariance Matrices
• Disordered ensembles of random matrices
• Statistical Physics of Irregular Low-Density Parity-Check Codes
• Statistical Mechanics Analysis of LDPC Coding in MIMO Gaussian Channels
• Random matrices and the replica method

Cited by in corpus (4)

• Faster than Classical Quantum Algorithm for dense Formulas of Exact Satisfiability and Occupation Problems
• Chook -- A comprehensive suite for generating binary optimization problems with planted solutions
• Rank deficiency in sparse random GF[2] matrices
• Typical rank of coin-toss power-law random matrices over GF(2)