Statistics of ranks, determinants and characteristic polynomials of rational matrices

This paper establishes upper and lower bounds on the number of $n \times n$ rational matrices with bounded height for a given rank, and subsequently applies these results to count matrices with specific determinants or characteristic polynomials.

The Gist

Imagine you are a librarian in a massive, infinite library. But instead of books, this library is filled with matrices (grids of numbers).

In the past, mathematicians have mostly studied libraries where the numbers are integers (whole numbers like 1, 2, 3). They know exactly how many of these integer grids have a specific shape, a specific "rank" (how many independent rows they have), or a specific "determinant" (a single number that summarizes the grid's scaling power).

This paper opens a new wing of the library. Here, the numbers aren't just whole numbers; they are fractions (rational numbers). But there's a catch: these fractions can't be too "messy." The top number (numerator) and bottom number (denominator) must be smaller than a certain limit, $H$. Think of $H$ as the size of the shelf. If $H$ is 100, you can have $1/99$, but you can't have $1/1000$.

The authors, Muhammad Afifurrahman, Vivian Kuperberg, Alina Ostafe, and Igor Shparlinski, ask three big questions about these "restricted fraction" matrices:

1. How many have a specific rank? (How many are "flat" or "collapsed"?)
2. How many have a specific determinant? (How many scale space by a specific amount?)
3. How many have a specific "characteristic polynomial"? (This is a fancy fingerprint that describes the matrix's internal behavior.)

They also look at a special, even stricter type of fraction called Egyptian Fractions (where the top number is always 1, like $1/2, 1/5, 1/100$).

The Big Challenge: The "Addition Trap"

Why is this hard? Imagine you are adding two simple fractions: $1/2 + 1/3$. The answer is $5/6$. The numbers got bigger!
If you add two fractions with small denominators, the result often has a much larger denominator.

In the world of whole numbers, if you add two numbers under 100, you get a number under 200. It's predictable.
In the world of fractions, adding two "small" fractions can create a "huge" fraction that breaks the rules of the library (exceeds the shelf size $H$). This makes standard counting tricks fail. The authors had to invent new ways to count without getting lost in the explosion of denominators.

The Three Main Discoveries

1. The "Rank" Count (How many are collapsed?)

Think of a matrix's rank as how many dimensions it actually uses. A rank of 1 is like a flat sheet of paper; a rank of 2 is a 3D object.

• The Finding: The authors found that as the shelf size ($H$) gets bigger, the number of matrices with a specific rank grows at a predictable rate.
• The Analogy: It's like counting how many ways you can stack bricks to build a wall of a certain height. They found that for most cases, the number of ways grows roughly like $H$ raised to a specific power. They proved that "collapsed" matrices (low rank) are actually quite rare compared to the total number of possible matrices, but they still exist in huge quantities.

2. The "Determinant" Count (The Scaling Factor)

The determinant is like a volume meter. If the determinant is 0, the matrix squashes everything into a flat line (it's singular). If it's 1, it preserves volume.

• The Finding:
  • For 2x2 matrices: The number of ways to get a specific determinant is surprisingly small.
  • For larger matrices: The number grows, but the authors found a "ceiling" (an upper bound) on how many there can be.
  • The Surprise: For Egyptian fractions (the $1/n$ type), the number of matrices with a determinant of 0 is much smaller than you might guess. It's like finding that it's incredibly hard to build a "flat" structure out of these specific bricks.

3. The "Characteristic Polynomial" (The Fingerprint)

This is the most complex part. Every matrix has a unique polynomial equation that describes its behavior.

• The Finding: The authors counted how many matrices share the exact same fingerprint.
• The Result: For 2x2 matrices, they found an exact formula involving logarithms (a slow-growing curve). For larger matrices, they found that the number of matches is much smaller than the total number of matrices.
• The "Egyptian" Twist: When they looked at matrices made only of Egyptian fractions ($1/2, 1/3, \dots$), they found a beautiful pattern for the case where the fingerprint is $X^2$ (meaning the matrix does nothing but flip signs or zero out). The count turned out to be related to how many pairs of numbers multiply to make a perfect square (like $2 \times 8 = 16$).

Why Does This Matter?

You might ask, "Who cares about counting fraction grids?"

1. Mathematical Hygiene: Just as biologists need to know how many species exist in a forest to understand the ecosystem, mathematicians need to know the "density" of these matrices to understand the structure of numbers.
2. Cryptography: Many encryption systems rely on the difficulty of solving problems with matrices. Knowing exactly how many solutions exist helps determine if a code is safe or if there are too many "backdoors" (solutions) for a hacker to find.
3. New Tools: The methods the authors developed to handle the "Addition Trap" (where fractions get messy) are new tools. Other mathematicians can now use these tools to solve different problems involving fractions, not just matrices.

The Bottom Line

This paper is a census of a very specific, tricky population of numbers. The authors successfully built a map showing where the "crowds" of these fraction matrices are and where they are empty. They showed that while these matrices are infinite in theory, when you restrict their size, their behavior follows strict, predictable laws—laws that are different from the whole numbers we use every day.

They didn't just count them; they figured out the rules of the game for how these fractions interact, proving that even in a chaotic world of fractions, there is a hidden order.

Technical Summary

1. Problem Statement and Motivation

The paper addresses the arithmetic statistics of matrices with rational entries of restricted height, a setting distinct from the well-studied case of integer matrices.

• The Sets: The authors define two primary sets of $m \times n$ matrices:
  1. $\mathcal{M}_{m,n}(\mathbb{Q}; H)$: Matrices with entries from the set of Farey fractions $\mathcal{F}(H) = \{a/b : \gcd(a,b)=1, |a|, b \le H\}$.
  2. $\mathcal{M}_{m,n}(\mathbb{Z}^{-1}; H)$: Matrices with entries from the set of Egyptian fractions $\mathcal{E}(H) = \{1/a : 1 \le |a| \le H\}$.
• The Questions: The authors investigate the cardinality of subsets of these matrices defined by specific algebraic properties:
  • Rank: Counting matrices of a fixed rank $r$ ($L_{m,n,r}$).
  • Determinant: Counting matrices with a fixed determinant $\delta$ ($D_n$).
  • Characteristic Polynomial: Counting matrices with a fixed characteristic polynomial $f$ ($P_n$).
• Motivation: While counting problems for integer matrices (entries in $[-H, H]$) are well-understood (often using geometry of numbers), rational matrices present unique challenges. The "height" (size of numerator/denominator) of rational numbers is not preserved linearly under addition or multiplication. For instance, the sum of two fractions of height $H$ can result in a fraction of height $O(H^2)$. This prevents the direct application of lattice-point counting methods used for integer matrices.

2. Methodology

The authors employ a combinatorial and analytic number theory approach, avoiding geometry of numbers. Their methodology relies on three main pillars:

1. Reduction to Diophantine Equations:

   • To bound the number of matrices with a fixed rank, determinant, or characteristic polynomial, the authors reduce the problem to counting solutions to systems of linear and non-linear equations over the sets $\mathcal{F}(H)$ and $\mathcal{E}(H)$.
   • For rank problems, they fix a non-singular minor and express remaining rows/columns as linear combinations of the basis rows. This leads to linear equations with rational coefficients.
   • For determinant and characteristic polynomial problems, they expand the determinant or trace formulas to derive linear equations in the matrix entries (or their reciprocals for Egyptian fractions).

2. Counting Solutions to Linear Equations:

   • A core component of the paper is deriving sharp upper bounds for the number of solutions to linear equations of the form $\sum Q_i x_i = Q_0$ where $x_i \in \mathcal{F}(H)$ or $x_i \in \mathcal{E}(H)$.
   • For Farey Fractions: They utilize and refine results by Shparlinski regarding the number of solutions to linear equations in Farey fractions.
   • For Egyptian Fractions: They develop new, non-trivial bounds for equations of the form $\sum Q_i/x_i = Q_0$. This involves sophisticated number-theoretic techniques, including:
     • Analyzing the least common multiple (LCM) of denominators.
     • Decomposing variables into square-free and square parts.
     • Using bounds on the divisor function $\tau_k(n)$.
     • Applying results on squares in arithmetic progressions (Rudin's conjecture context).
   • Key Lemmas:
     • Lemma 3.4: Bounds solutions for Farey fractions ($H^{n+o(1)}$).
     • Lemma 3.5 & 3.8: Bounds solutions for Egyptian fractions, showing significantly fewer solutions ($H^{n/2 + o(1)}$ or better) due to the restrictive nature of unit fractions.

3. Case-by-Case Analysis for Small Dimensions:

   • For small matrices ($n=2, 3$), the authors perform direct algebraic manipulations to derive tighter bounds than the general asymptotic formulas.
   • For $n=2$ and Egyptian fractions, they relate the determinant condition to the equation $x_1 x_4 = x_2 x_3$ and use the distribution of perfect squares.
   • For characteristic polynomials, they utilize the trace ($Tr(A)$) and the trace of the square ($Tr(A^2)$) to constrain the diagonal and off-diagonal elements.

3. Key Contributions and Results

The paper provides upper bounds (and in some cases, matching lower bounds) for the cardinalities of the sets defined above. The bounds are given in terms of $H$ (the height parameter) with an error factor of $H^{o(1)}$.

A. Rank Statistics

• Rational Matrices ($\mathbb{Q}$): For $n \ge m > r$, the number of matrices of rank $r$ is bounded by $H^{2mr + nr + n - r^2 - r + o(1)}$ (if $2m \ge n+r$) or $H^{2nr + 2m - 2r + o(1)}$ (if $2m < n+r$).
• Egyptian Fractions ($\mathbb{Z}^{-1}$): The bounds are generally lower due to the sparsity of Egyptian fractions.
  • For $r=1$: $H^{n+o(1)}$.
  • For $r=2$: $H^{2n+m-3+o(1)}$ (with a specific exception for $3 \times 3$ matrices).
  • For $r \ge 3$: Bounds depend on the relationship between $m, n, r$, generally scaling as $H^{(n-r)(r+1)/2 + mr}$.

B. Determinant Statistics

• Rational Matrices:
  • For $n=2$: $H^{4+o(1)}$.
  • For $n \ge 3$: $H^{2n^2 - n + o(1)}$.
  • Note: The lower bound for singular matrices ($\delta=0$) is $H^{2n^2-2n}$, suggesting a gap for $\delta \neq 0$.
• Egyptian Fractions:
  • For $n=2$: $H^{o(1)}$ (very sparse).
  • For $n=3$: $H^{7+o(1)}$.
  • For $n \ge 4$: $H^{n^2 - n/2 - 1/(2n-2) + o(1)}$ for $\delta \neq 0$.
  • The authors show that the number of Egyptian fraction matrices with determinant 0 is significantly larger than those with non-zero determinant, but still much smaller than the total space.

C. Characteristic Polynomial Statistics

• Rational Matrices:
  • For $n=2$: $H^{2+o(1)}$.
  • For $n \ge 3$: $H^{n^2+o(1)}$.
  • The authors note that for $n \ge 3$, the upper bound relies only on the first two coefficients (Trace and Trace of square), suggesting the true count might be lower (closer to $H^{n^2-n}$).
• Egyptian Fractions:
  • For $n=2$ and $f(X)=X^2$: An asymptotic formula is derived: $\frac{24}{\pi^2} H \log H + O(H)$. This is a precise result linking the count to the number of pairs of integers whose product is a square.
  • For $n \ge 3$: Bounds are $H^{n^2/2 + o(1)}$ (if the coefficient of $X^{n-1}$ is 0) or slightly lower otherwise.

4. Significance and Implications

• New Arithmetic Landscape: This work establishes the first systematic framework for counting rational matrices with restricted height. It highlights that the statistical behavior of rational matrices differs fundamentally from integer matrices due to the non-linear growth of heights under field operations.
• Methodological Innovation: The paper introduces powerful techniques for counting solutions to linear equations in Egyptian fractions. These techniques (involving LCM analysis and square-free decomposition) are of independent interest in Diophantine analysis and could be applied to other problems involving unit fractions.
• Tightness of Bounds: The authors provide lower bounds that match their upper bounds in several specific cases (e.g., rank 1 Egyptian matrices, $2 \times 2$ determinants), validating the sharpness of their methods. However, they identify gaps in other cases (e.g., $n \ge 3$ characteristic polynomials), suggesting directions for future research.
• Applications: Understanding the distribution of ranks and determinants in rational matrices is relevant to:
  • Coding Theory: Analysis of rank-deficient matrices over finite fields and their rational lifts.
  • Cryptography: Potential implications for lattice-based cryptography or problems involving rational approximations.
  • Number Theory: Deepening the understanding of the distribution of rational points on algebraic varieties (specifically determinantal varieties).

5. Conclusion

The paper successfully extends the theory of arithmetic statistics from integer matrices to rational matrices with bounded height. By combining combinatorial matrix theory with advanced analytic number theory, the authors derive precise upper bounds for rank, determinant, and characteristic polynomial distributions. The results reveal that matrices with Egyptian fraction entries are significantly rarer than those with general rational entries, and the authors provide a roadmap for future improvements, particularly regarding the tightness of bounds for higher-dimensional characteristic polynomials.