Exact cospectrality probabilities for uniform random matrices

Technical Summary: Exact Cospectrality Probabilities for Uniform Random Matrices

Problem Statement
The paper addresses the spectral characterization problem for discrete matrices, specifically investigating the probability that a random symmetric matrix with entries in a discrete set (such as the ring of integers $\mathcal{O}_K$ of an algebraic number field $K$) remains within that set after conjugation by an orthogonal matrix $Q$.

While the "generic" case suggests that a random graph or matrix is uniquely characterized by its spectrum (Haemers' conjecture), the existence of non-trivial orthogonal matrices $Q$ such that $Q^\top X Q$ shares the same spectrum as $X$ (cospectrality) complicates this. The core question is: Given a fixed orthogonal matrix $Q$ (potentially with algebraic entries) and a random symmetric matrix $X$ with entries uniformly distributed in $\mathcal{O}_K$, what is the exact probability that the conjugate $Q^\top X Q$ also has entries in $\mathcal{O}_K$?

Previous work, such as Wang and Zhao [33], established asymptotic upper bounds for rational orthogonal matrices with bounded denominators as the dimension $n \to \infty$. This paper aims to provide exact, non-asymptotic formulas for this probability for fixed dimensions and arbitrary algebraic number fields, moving beyond the asymptotic regime.

Methodology
The author employs a combination of algebraic number theory, ideal theory in Dedekind domains, and probabilistic invariance arguments.

1. Algebraic Framework: The study is set within an algebraic number field $K$ with ring of integers $\mathcal{O}_K$. The "level" $\ell$ of a matrix $Q$ is defined as the smallest integer such that $\ell Q \in \mathcal{O}_K^{n \times n}$. The analysis utilizes the Smith normal form and Smith ideals ($\mathfrak{d}_i$) associated with the matrix $\ell Q$.
2. Probabilistic Invariance: The proof relies on the translation invariance of the uniform distribution over the quotient ring $\mathcal{O}_K / \ell^2 \mathcal{O}_K$. By leveraging the fact that the law of a random symmetric matrix $X$ is invariant under translation by deterministic symmetric matrices, the author demonstrates that the probability of $Q^\top X Q$ being integral depends only on the Smith normal form of $\ell Q$, allowing $Q$ to be effectively replaced by a diagonal matrix in the probability calculation.
3. Ideal-Theoretic Reduction: The problem is reduced to counting solutions to congruences involving the Smith ideals. The orthogonality of $Q$ imposes specific structural constraints on these ideals (specifically, relations between $\mathfrak{d}_i$ and $\mathfrak{d}_{n-i+1}$), which simplifies the general formula derived for arbitrary matrices.

Key Contributions and Results

• Exact Probability Formula (Theorem 1.3): The primary result is an exact formula for the probability $\mathbb{P}(Q^\top X Q \in \mathcal{O}_K^{n \times n})$. For a random symmetric matrix $X$ with entries uniformly distributed modulo $\ell^2$, the probability is given by:
  $$\mathbb{P}(Q^\top X Q \in \mathcal{O}_K^{n \times n}) = \prod_{i=1}^{\lfloor n/2 \rfloor} \prod_{j=i}^{n-i} \frac{\mathrm{N}_{\mathcal{O}_K}(\mathfrak{d}_i \mathfrak{d}_j)}{\mathrm{N}_{\mathcal{O}_K}(\ell^2 \mathcal{O}_K)}$$
  where $\mathfrak{d}_i$ are the Smith ideals of $\ell Q$ and $\mathrm{N}$ denotes the ideal norm. This formula holds for any algebraic number field and applies to both symmetric and Hermitian ensembles.

• Rational Cospectrality in Low Dimensions (Theorems 1.6 & 1.7): The paper derives explicit formulas for the expected number of rational orthogonal matrices with a given denominator $\ell$ that preserve integrality for dimensions $n=2$ and $n=3$:

  • Dimension 2: The expected number is non-zero only if the prime factors of $\ell$ are all congruent to $1 \pmod 4$. The expectation is $\mathbb{E}[N_2(\ell)] = 2^{r+3}/\ell^2$, where $r$ is the number of distinct prime factors.
  • Dimension 3: The expected number is non-zero only if $\ell$ is odd. The expectation is $\mathbb{E}[N_3(\ell)] = \frac{48}{\ell^2} \prod_{p|\ell} (1 + 1/p)$.

• Non-Monotonicity: A significant finding is that the dependence of the expected number of preserving conjugations on the denominator $\ell$ is non-monotone. While the $1/\ell^2$ factor suggests a general decay, number-theoretic fluctuations in the prime factorization of $\ell$ (specifically the number and size of prime factors) cause local increases in the probability.

• Bounds on Rational Cospectrality (Corollary 1.8): Using the exact expectations, the author establishes that for $n \le 3$, the probability that a random integer matrix is cospectral to another via a rational orthogonal matrix (with bounded but arbitrarily large denominator) is strictly less than 1.

  • For $n=2$, the limit is bounded by approximately $0.114$.
  • For $n=3$, the limit is bounded by approximately $0.296$.
    This provides a rigorous, non-asymptotic variant of Haemers' conjecture for low dimensions.

Significance and Claims
The paper claims to provide the first exact, non-asymptotic formulas for the probability of integrality preservation under orthogonal conjugation, linking this probability directly to the Smith ideals of the conjugating matrix.

The author highlights that these results reveal a new phenomenon in low-dimensional settings: the non-monotonic dependence on the denominator due to arithmetic fluctuations. This contrasts with simpler asymptotic trends where probability typically decays monotonically.

The work connects the probabilistic study of random matrices with deterministic sufficient conditions for spectral characterization (referencing work by Qiu, Wang, and Zhang [23] and Wang and Yu [32]), suggesting that Smith normal forms play a fundamental role in determining whether a matrix is uniquely characterized by its spectrum. The paper concludes by proposing a conjecture (Conjecture 1.9) that this strict inequality (probability $< 1$) holds for all fixed dimensions $n$, though proving this for general $n$ remains an open and challenging problem.