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 Galois fields $\text{GF}\left(q\right)$, with a given connectivity profile, in the thermodynamical limit of large matrices. We introduce a mapping of $\text{GF}\left(q\right)$ 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 numbers of random matrices for any general connectivity profile. We present numerical results for particular distributions.

Figure 1

Average kernel dimension density (continuous lines) and average rank density (dashed lines) calculated as solutions to the replica-symmetric saddle point equations. The top left plot shows the thermodynamically favored solution (paramagnetic for $0\le \lambda \le 1$ and ferromagnetic for $\lambda >1$). The top right shows the regular case (1) for fixed $K$ and $C$. Cases (2) and (3) are presented at the bottom left and right, respectively. Note that numerical instabilities occur for specific $\lambda$ values.

Figure 2

Values of the quenched entropy $\Xi$ versus $\lambda$ for the different distributions and various $\mathbf{C}$ values $\left(\mathbf{C}=5,10,20\right)$, with multinomial $\mathbf{K}$: constant (continuous line), binomial (dashed line), and uniform (dotted line). The inset shows in detail the small-$\lambda$ regime, where just the binomial and constant distributions are represented. The higher lines on the right correspond to the higher $\mathbf{C}$ values.

Figure 3

Values of $\Xi$ versus $\lambda$ for the uniform distribution (dashed line) and the Zipf distribution (continuous lines) for $s=1,3,4,10$, respectively, from bottom to top.