On the Rank of Random, Symmetric Matrices over Z_2 via Random Graphs

Abstract

It is well-known that the game of \textit{Lights Out} on a graph $G$ with $|V(G)| = n$ is universally solvable if and only if the sum of the adjacency matrix of $G$ and the identity matrix $I_{n}$ is invertible over $\Z_2$. Denoting $G(n, 1/2)$ to be a graph on $n$ vertices chosen uniformly at random (each edge is chosen to be included or not independently with probability $1/2$), Forrest and Manno conjectured that as $n$ goes to infinity, the probability that $G(n, 1/2)$ is universally solvable is roughly $0.419$. We derive an explicit formula for this probability which, as a consequence, yields a more precise asymptotic probability. Moreover, we show that the probability that a random, symmetric matrix $M$ in $\Z_2^{n \times n}$ is invertible does not depend on the distribution of 0's and 1's along the main diagonal: we prove that the probabilities are identical for any given 0-1 distribution along the main diagonal over all matrices in $\Z_2^{n \times n}$ if $n$ is even, and over all matrices in $\Z_2^{n \times n}$ with at least one 1 along the main diagonal if $n$ is odd. We also develop expressions for the probability that, for $r \in \N$, $M$ has nullity $2r+1$ in the case that $n$ is odd, and $2r$ in the case that $n$ is even, in terms of closely related quantities.