|
The work focuses on key typical properties of sparse random matrices with entries in GF(q), the Galois field of prime order q. These include the average dimension of their null space, their eigenvector spaces, distribution of the eigenvalues and the number of matrices for a given distribution of entries. These properties were analysed in the thermodynamic limit of large matrices. Generalising the usual transformation of representation/operation from GF(2) to the binary representation {±1}, using the group homeomorphism between GF(q) under addition mod q and the complex q-th roots of unity, we map the problem into a system of interacting spins, which allows for the use of methods developed for disordered spin lattices in statistical physics to obtain the required properties. A replica symmetric approach is then used to calculate the average dimension of the null space, the eigenvector spaces and the eigenvalue distribution. Using general arguments based on the analogy with thermodynamic quantities corresponding to the free energy, internal energy and Hamiltonian and the gauge invariance of the later, we show that there is no replica symmetry breaking in this problem. We introduce new techniques for taking averages over the matrices with random row/column connectivity, which is transparent and easy to implement. We show that the average dimension of the null space is equal to 1-M/N, where MxN is the matrix dimensionality, in all cases studied. Using the same techniques, we also calculate the total and average number of matrices for given relevant distributions. Our results have practical relevance in several areas which can be mapped onto sparse graphs of arbitrary connectivity profiles.
R. C. Alamino and D. Saad, Typical Kernel Size and Number of Sparse Random Matrices over Galois Fields: A Statistical Physics Approach, Phys. Rev. E, 77, 061123 (2008). |
|