Sharp Exponential Asymptotics for Normal Sign Matrices

Let $M_n$ be an $n\times n$ random matrix whose entries are independent Rademacher random variables, and put $N=\left(\genfrac{}{}{0px}{}{n}{2}\right)$. We prove $$Pr(M_n{M}_n^T=M_n^T{M}_n)=2^{-N+O(n)}\mathrm{.}$$ This gives the sharp exponential order for the probability that a random sign matrix is normal. The lower bound is supplied by symmetric sign matrices. We also record the immediate consequence that random $0$-$1$ matrices have the same sharp exponential normality probability. The proof of the matching upper bound is combinatorial: after conditioning on the symmetric/skew-symmetric type pattern of the off-diagonal entries, a mod-$4$ reduction gives a system of linear equations over $F_2$; a rank-duality argument converts the sum over type patterns into a count of commuting symmetric pairs over $F_2$; and this count is bounded by summing over rational canonical types, using balanced symmetric bilinear forms and the standard finite-field centralizer formula.