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

Research output: Contribution to journalArticle

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.
Original languageEnglish
Article number061123
Pages (from-to)1-12
Number of pages12
JournalPhysical Review E
Volume77
Issue number6
DOIs
Publication statusPublished - 17 Jun 2008

Fingerprint

Statistical Physics
Sparse matrix
Random Matrices
Galois field
Connectivity
kernel
Replica
replicas
physics
Q-matrix
Spin Systems
Roots of Unity
Cyclic group
saddle points
matrices
profiles
Population Dynamics
Saddlepoint
unity
derivation

Bibliographical note

Copyright of the American Physical Society.

Keywords

  • random matrices
  • Galois fields
  • statistical mechanics
  • replica theory

Cite this

@article{099ef4adeb3548d199627f143e08080d,
title = "Typical kernel size and number of sparse random matrices over Galois fields: 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.",
keywords = "random matrices, Galois fields, statistical mechanics, replica theory",
author = "Alamino, {Roberto C.} and David Saad",
note = "Copyright of the American Physical Society.",
year = "2008",
month = "6",
day = "17",
doi = "10.1103/PhysRevE.77.061123",
language = "English",
volume = "77",
pages = "1--12",
journal = "Physical Review E",
issn = "1539-3755",
publisher = "American Physical Society",
number = "6",

}

Typical kernel size and number of sparse random matrices over Galois fields: a statistical physics approach. / Alamino, Roberto C.; Saad, David.

In: Physical Review E, Vol. 77, No. 6, 061123, 17.06.2008, p. 1-12.

Research output: Contribution to journalArticle

TY - JOUR

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

AU - Alamino, Roberto C.

AU - Saad, David

N1 - Copyright of the American Physical Society.

PY - 2008/6/17

Y1 - 2008/6/17

N2 - 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.

AB - 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.

KW - random matrices

KW - Galois fields

KW - statistical mechanics

KW - replica theory

UR - http://www.scopus.com/inward/record.url?scp=45849147345&partnerID=8YFLogxK

U2 - 10.1103/PhysRevE.77.061123

DO - 10.1103/PhysRevE.77.061123

M3 - Article

VL - 77

SP - 1

EP - 12

JO - Physical Review E

JF - Physical Review E

SN - 1539-3755

IS - 6

M1 - 061123

ER -