Typical kernel size and number of sparse random matrices over Galois fields: a statistical physics approach


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.

Publication DOI: https://doi.org/10.1103/PhysRevE.77.061123
Divisions: College of Engineering & Physical Sciences > School of Informatics and Digital Engineering > Mathematics
College of Engineering & Physical Sciences > Systems analytics research institute (SARI)
Additional Information: Copyright of the American Physical Society.
Uncontrolled Keywords: random matrices,Galois fields,statistical mechanics,replica theory,Mathematical Physics,Physics and Astronomy(all),Condensed Matter Physics,Statistical and Nonlinear Physics
Publication ISSN: 1550-2376
Full Text Link: http://link.aps ... sRevE.77.061123
Related URLs: http://www.scop ... tnerID=8YFLogxK (Scopus URL)
PURE Output Type: Article
Published Date: 2008-06-17
Authors: Alamino, Roberto C. (ORCID Profile 0000-0001-8224-2801)
Saad, David (ORCID Profile 0000-0001-9821-2623)

Export / Share Citation


Additional statistics for this record