A random sign matrix is a square grid of numbers where each entry is independently chosen to be either +1 or -1 with equal probability. A matrix is called "normal" if it commutes with its own transpose, meaning the order of multiplication does not matter. Normality is an important property in linear algebra because normal matrices have especially clean geometric and spectral behavior. The question this paper addresses is: how likely is it that a large random sign matrix happens to be normal?
The main result is that for an n-by-n random sign matrix, the probability of being normal is roughly 2 raised to the power of negative n-squared over 2, up to lower-order corrections in the exponent. In other words, the probability drops off exponentially fast as the matrix grows, and the paper pins down the exact exponential rate. The lower bound on this probability comes from symmetric sign matrices, which are automatically normal, and there are roughly that many of them. The surprising content is the matching upper bound, which shows that non-symmetric normal matrices are actually rare enough not to change the exponential rate.
The proof of the upper bound is a clever combinatorial argument. The key steps involve sorting the matrix entries by their symmetry pattern, then reducing the normality condition to a system of linear equations over a two-element field. A technique called rank duality converts the problem into counting pairs of commuting symmetric matrices over that finite field, and standard tools from the theory of finite fields give precise enough bounds to close the argument. As a bonus, the same result applies to random zero-one matrices, since those can be mapped to sign matrices without changing the essential structure of the problem.