Rank of Matrices with Entries from a Multiplicative Group

Noga Alon, József Solymosi

TL;DR

This paper proves that if a matrix has off-diagonal entries from a "simple" multiplicative group (one with low rank) but diagonal entries that are not, the matrix must have a high rank. The authors use this to show that geometric distance sets cannot be algebraically "too simple" and that small-rank multiplicative groups cannot contain large sumsets.

What Problem Does This Paper Address?

The paper explores the intersection of linear algebra, number theory, and additive combinatorics. Specifically, it asks: How does the algebraic structure of a matrix's entries constrain its rank?

In many areas of computer science and combinatorics, we want to prove that certain matrices have high rank. A classic example is showing that a matrix is "far" from being low-rank if its diagonal entries are significantly different from its off-diagonal entries. This paper takes that idea further by assuming the off-diagonal entries belong to a multiplicative group of small rank (meaning all entries can be generated by a small number of elements, like powers of 2).

The authors aim to establish lower bounds on the rank of such matrices and apply these bounds to solve problems in discrete geometry (like the properties of points with integral distances) and additive combinatorics (the "incompatibility" of additive and multiplicative structures).

Methods

The authors provide two distinct proofs for their main theorem, both relying on a heavy-duty tool from number theory: the Subspace Theorem (specifically the version by Evertse, Schlickewei, and Schmidt). This theorem provides a uniform bound on the number of solutions to linear equations where variables come from a multiplicative group of finite rank.

  1. The Ramsey Approach: The first proof uses Ramsey’s Theorem to find a large principal submatrix where the off-diagonal entries are "well-behaved." By applying the Subspace Theorem to this submatrix, they bound the number of distinct entries in each row, which then allows them to apply known rank-lower-bounding techniques.
  2. The Polynomial Approach: To improve the quantitative bounds, the second proof replaces the Ramsey argument with a linear algebra argument involving multivariate polynomials and Hadamard products (element-wise multiplication of matrices). This avoids the massive "loss" in size typically associated with Ramsey-type arguments.

Datasets

Not applicable. This is a theoretical mathematics paper; no empirical datasets or benchmarks were used.

Key Insights and Ideas

  • Multiplicative vs. Additive Incompatibility: A recurring theme is that multiplicative groups with few generators are "rigid." They don't play well with addition. If you try to build a large set where sums ($A+A$) stay within a small-rank multiplicative group, you hit a wall—the set cannot be very large.
  • The Power of the Subspace Theorem: The authors demonstrate that the Subspace Theorem is not just for number theorists; it's a potent tool for bounding the rank of matrices in combinatorial contexts.
  • Geometric Rigidity: In $\mathbb{R}^d$, the distances between points are constrained by the dimension. The paper shows that if you have many points, their distances must generate a multiplicative group of high rank. Essentially, you can't have a huge set of points where every distance is, for example, a power of 2.
  • The "Rectangle Condition": The authors introduce a condition (Definition 8) that allows them to generalize their results to matrices where the diagonal entries aren't necessarily outside the group, but simply satisfy a specific algebraic relationship with the off-diagonal entries.

Key Results

  • Theorem 1 (Main Result): For any multiplicative subgroup $G$ of rank $r$, an $n \times n$ matrix $M$ with off-diagonal entries in $G$ and diagonal entries not in $G$ has a rank that grows with $n$. Specifically, for large $n$, $\text{rank}(M) \ge D$.
  • Improved Bound: The second proof yields a quantitative bound: for sufficiently large $n$, $\log n \le r \cdot \text{rank}(M)^8$.
  • Sumsets: They prove that if the sumset $\{A+A\}$ of a finite set $A$ is contained in a multiplicative group of rank $r$, then the size of $A$ is bounded by a function of $r$ alone.
  • Integral Distances (Theorem 12): They show that for any prime $p$, a sufficiently large set of points in $\mathbb{R}^d$ with integral distances must contain at least one distance divisible by $p$. This provides a new perspective on the structure of "integral pointsets."

Limitations and Future Work

  • Quantitative Gaps: The authors admit that their quantitative bounds (the relationship between $n$, $r$, and the rank) are likely "quite weak." There is a significant gap between their lower bounds and known upper-bound constructions.
  • The "Powers of 2" Case: A specific open problem mentioned is determining the minimum possible rank of an $n \times n$ matrix where all non-diagonal entries are powers of 2. The paper proves this rank goes to infinity with $n$, but the exact rate of growth remains a mystery.
  • Higher-Order Distances: The authors suggest that their methods could be extended to more general polynomials and different types of distance metrics (like $\ell_{2r}$ norms), opening doors for further research in discrete geometry.

Summary updated

Abstract

Abstract We establish lower bounds on the rank of matrices in which all but the diagonal entries lie in a multiplicative group of small rank. Applying these bounds we show that the distance sets of finite pointsets in $\mathbb {R}^d$ generate high-rank multiplicative groups and that multiplicative groups of small rank cannot contain large sumsets.
BibTeX
@inproceedings{alon2022rank,
  author = {Noga Alon and József Solymosi},
  title = {{Rank of Matrices with Entries from a Multiplicative Group}},
  booktitle = {International Mathematics Research Notices},
  year = {2022},
  doi = {10.1093/imrn/rnac183},
}

Loading related content...

Figure