How to Navigate an Enormous Matrix Group by Shrinking One Matrix

Suppose we are handed a few matrices that generate a finite group. We may multiply them, invert them, and multiply again. Somewhere among all the resulting words lie every element of the group.

But how long do those words have to be?

For a classical group such as $\mathrm{PSL}_d(\mathbb F_q)$, this is not a small search problem. Its size grows roughly like $q^{d^2}$. Even when $q$ is fixed, increasing the natural matrix dimension $d$ quickly produces groups with an astronomical number of elements.

What makes the question stranger is that the generating set is arbitrary. It need not contain elementary matrices, sparse matrices, or any other convenient moves.

Yet a conjecture of László Babai predicts something remarkably strong: for every nonabelian finite simple group $G$ and every symmetric generating set $S$, the Cayley-graph diameter should be bounded by a fixed power of $\log |G|$.

The problem is therefore not merely to show that the generators eventually reach everything. By definition they do.

The problem is to show that no generating set can hide parts of a simple group very far away.

For high-rank groups of Lie type, this remains a difficult open problem. The article makes substantial progress by borrowing an idea from permutation groups and translating it into linear algebra. Its argument revolves around an object that at first sounds almost useless: a matrix that is very close to the identity. (London Mathematical Society)

The surprising part is that once such a matrix has been manufactured, the rest of the group becomes much easier to reach.

Distance inside a group

Given a finite group $G$ and a symmetric generating set $S$, form the Cayley graph $\Gamma(G,S)$. Its vertices are the elements of $G$. From $g$, multiplying by one generator $s\in S$ moves us to $sg$.

A path of length $d$ therefore corresponds to a word of length $d$ in the generators.

The diameter is the smallest $d$ for which every element of $G$ can be expressed using at most $d$ generators:

$$G=\bigcup_{j=0}^{d} S^j.$$

There is no reason for arbitrary finite groups to have small diameter. A cyclic group generated by one element may require on the order of $|G|$ steps to move across its Cayley graph.

Babai’s conjecture asserts that nonabelian finite simple groups behave completely differently:

$$\operatorname{diam}(G)\leq (\log |G|)^{O(1)}.$$

The constant hidden in $O(1)$ should be universal.

For groups of Lie type of bounded rank, this polylogarithmic behavior was established through the work initiated by Helfgott and developed by Pyber–Szabó and Breuillard–Green–Tao. The difficult regime is when the rank itself grows. Recent mathematical accounts still describe that high-rank, arbitrary-generating-set case as wide open. (Journal of the American Mathematical Society)

The article proved the following intermediate bound.

Theorem. Let $G$ be a finite simple group of Lie type with Lie rank $r$, defined over $\mathbb F_q$. Then

$$\operatorname{diam}(G) \leq q^{O\left(r(\log r+\log q)^3\right)}.$$

The implied constant is absolute. The result applies independently of the chosen generating set. (London Mathematical Society)

For a classical family of Lie rank $r$ over $\mathbb F_q$,

$$\log |G|=\Theta(r^2\log q).$$

Thus, when $q$ is fixed, $\log |G|=\Theta(r^2)$ and the theorem gives approximately

$$\operatorname{diam}(G) \leq \exp\!\left(O(r(\log r)^3)\right) = \exp\!\left( O\!\left( \sqrt{\log |G|}\,(\log\log |G|)^3 \right) \right).$$

This is still far larger than Babai’s predicted polylogarithmic diameter. But it is dramatically smaller than the naive scale $|G|$, which is exponential in $r^2$ for fixed $q$.

The real interest lies in how the argument gets there.

The matrix analogue of moving only a few points

For permutations, one particularly useful kind of group element is a permutation with small support: it moves only a few points and fixes all the others.

A transposition, for example, disturbs exactly two points.

For the large-rank part of the theorem, the classification reduces the problem to classical families and their natural matrix actions. Write $d$ for the natural representation dimension, which is comparable to $r$ in these families. The article looks for the linear-algebraic analogue. For a matrix $A$, define

$$\deg(A)=\operatorname{rank}(A-I).$$

Equivalently,

$$\deg(A) = d-\dim\ker(A-I).$$

So a matrix of degree $k$ fixes a subspace of codimension $k$.

If $k\ll d$, the matrix is the identity on almost the entire vector space.

This is the first conceptual move in the proof:

Instead of trying to expand the generating set directly, try to manufacture one nontrivial element that acts on only a small number of dimensions.

Why should this help?

Because small degree behaves well under commutators. If

$$[A,B]=ABA^{-1}B^{-1},$$

then

$$\deg([A,B]) \leq 2\min(\deg A,\deg B).$$

The calculation is short:

$$\begin{aligned} \deg([A,B]) &=\operatorname{rank}(AB-BA)\\ &=\operatorname{rank}\big((A-I)(B-I)-(B-I)(A-I)\big)\\ &\leq 2\operatorname{rank}(A-I). \end{aligned}$$

By symmetry the same bound holds with $B$ in place of $A$.

A commutator can therefore inject new structure into a matrix without making its degree uncontrollably large.

That becomes crucial later.

How arbitrary generators give local control

There is an immediate obstacle. Our generating set $S$ is arbitrary. Why should short words in $S$ contain matrices whose action on a carefully chosen subspace can be prescribed?

The answer comes from what the article calls a $t$-transversal set.

Take a $t$-dimensional subspace $W\subseteq V$. A collection $T\subseteq \mathrm{GL}(V)$ is $t$-transversal if every linear embedding

$$X:W\rightarrow V$$

is the restriction of some matrix in $T$.

In other words, $T$ gives us complete control over what happens on a small $t$-dimensional piece of the ambient space.

Why can short words in an arbitrary generating set provide such a collection?

Let the generated group act on all embeddings of $W$ into $V$. This produces a Schreier graph. Since the generators generate the group, the relevant orbit graph is connected.

There are at most $q^{dt}$ linear maps $W\to V$, hence at most that many possible vertices.

A connected graph with at most $q^{dt}$ vertices has diameter at most $q^{dt}$. Consequently, every desired local embedding can be realized by a word of length at most roughly $q^{dt}$.

This is a crude estimate. But crude is enough—as long as $t$ is very small compared with $d$.

So an arbitrary global generating set secretly provides bounded-cost local programmability.

The next problem is deciding what program to install on that small subspace.

A matrix designed to survive exponentiation

The authors introduce special matrices called $P$-matrices.

Let $p$ be the characteristic of $\mathbb F_q$, and choose primes

$$p_1,\ldots,p_m$$

coprime to $p(q-1)$.

A $P(m)$-matrix is required to have, for every $p_i$, a primitive $p_i$-th root of unity among its eigenvalues over the algebraic closure of $\mathbb F_q$.

This is not an arbitrary spectral decoration. Those roots of unity let exponentiation act as a selective eraser.

Suppose $A$ has finite order $m$. Consider $A^{m/p_i}$. An eigenvalue whose multiplicative order is not divisible by $p_i$ is killed: after raising it to $m/p_i$, it becomes $1$.

Only eigenvalues whose orders contain the selected factor $p_i$ can remain nontrivial.

The aim is therefore to arrange the primes so that one $p_i$ occurs in the orders of only a small fraction of the nontrivial eigenvalues.

Then one power of $A$ annihilates most of the action of $A$.

Its degree collapses.

Why prime numbers enter a problem about matrix groups

There is a cost to inserting a primitive $p_i$-th root of unity into a matrix over $\mathbb F_q$.

If $o_{p_i}(q)$ denotes the multiplicative order of $q$ modulo $p_i$, then the relevant cyclotomic polynomial has irreducible factors of degree $o_{p_i}(q)$ over $\mathbb F_q$.

So forcing such an eigenvalue costs at least $o_{p_i}(q)$ dimensions.

The authors need a collection of primes satisfying two competing requirements.

The total dimensional cost $\sum_i o_{p_i}(q)$ must remain small.

But the arithmetic information encoded by these orders must collectively be large enough that no degree-$k$ matrix can distribute all the chosen prime factors too evenly among its eigenvalues.

This is the number-theoretic core of the argument.

Using an estimate ultimately based on a theorem of Fouvry concerning large prime factors of $p-1$, the article obtains primes for which

$$\sum_i o_{p_i}(q) = O\!\left((\log d+\log q)^3\right),$$

while an associated least common multiple is larger than $d^4$.

The two statements pull in opposite directions: the spectral pattern occupies only a polylogarithmic number of dimensions, yet it carries enough arithmetic complexity to force a reduction.

From this they prove the key degree-reduction lemma.

If $A$ is a $P(m)$-matrix of degree $k$, then some power $A^\ell$ is nontrivial and satisfies

$$\deg(A^\ell)\leq \frac{k}{4}.$$

Moreover, its only eigenvalue lying in the base field $\mathbb F_q$ is $1$.

That last condition is not cosmetic. It gives enough linear independence to run the construction again.

The problem with shrinking only once

Suppose we have successfully turned a matrix of degree $k$ into one of degree $k/4$.

There is a catch.

The resulting matrix need no longer be a $P$-matrix. We have used up the spectral structure that made the reduction possible.

So the proof needs a way to reinstall the cyclotomic pattern without losing the small degree already achieved.

This is where the commutator inequality becomes the central mechanism.

Let $A$ now be the reduced matrix. Because its nontrivial eigenvalues lie outside $\mathbb F_q$, one can find a reasonably large subspace $W$ for which

$$W\cap AW=\{0\}.$$

Choose a short word $M$ from a suitable transversal set so that it acts on $W$ with the desired $P$-matrix structure while behaving appropriately on $AW$.

Now form the commutator-type expression $MA^{-1}M^{-1}A$. On $W$, the construction makes this new matrix reproduce the desired cyclotomic behavior. It is therefore a $P$-matrix again.

But the general commutator estimate gives

$$\deg(MA^{-1}M^{-1}A) \leq 2\deg(A).$$

We can now apply the powering argument once more, dividing the degree by four. The combined operation changes

$$k \quad\longrightarrow\quad 2k \quad\longrightarrow\quad \frac{2k}{4} = \frac{k}{2}.$$

So each cycle reduces the degree by a constant factor.

Repeat this $O(\log d)$ times and the degree falls from order $d$ to $O\!\left((\log d+\log q)^3\right)$. This repeated sequence—

$$\text{install spectral structure} \;\longrightarrow\; \text{take a power} \;\longrightarrow\; \text{commute} \;\longrightarrow\; \text{install it again}$$

—is the heart of the proof.

The authors are not expanding the group directly.

They are compressing the action of a single element.

The geometry needed for the other classical groups

For $\mathrm{PSL}_d(\mathbb F_q)$, ordinary subspaces and linear embeddings are enough.

Symplectic, unitary, and orthogonal groups introduce another constraint: their matrices must preserve a bilinear, Hermitian, or quadratic form.

An arbitrary linear map on a small subspace may therefore fail to extend to an element of the group.

The appropriate replacement for ordinary transversal sets uses totally singular subspaces, on which the preserved form vanishes.

Witt’s extension theorem supplies the local-to-global principle: appropriate isometries between such subspaces can be extended to isometries of the whole formed space.

The technical geometry becomes considerably more elaborate. The authors must construct subspaces $W$ satisfying conditions such as

$$W\cap AW=\{0\}, \qquad W\perp AW,$$

while retaining enough dimensions to insert the same cyclotomic blocks.

But the architecture of the argument does not change.

Local control builds a $P$-matrix. Powers reduce its degree. Commutators restore the structure required for another reduction.

That robustness is one reason the method reaches all the large-rank classical families.

Why an almost-identity matrix can fill the whole group

We have now arrived at what appears to be the opposite of our original goal.

We wanted to reach an enormous group.

Instead we spent most of the proof finding one element $A$ that does almost nothing:

$$\deg(A)=k\ll d.$$

Why is that useful?

First, a degree-$k$ matrix can be written

$$A=I+XY$$

with $X$ a $d\times k$ matrix and $Y$ a $k\times d$ matrix.

This severely limits how many distinct conjugates $A$ can have. The article obtains a rough bound of $q^{2nk}$ possibilities.

Once again a Schreier-graph argument implies that all these conjugates can be reached by words whose length is controlled by $q^{2nk}$.

The final ingredient is an external theorem of Liebeck and Shalev: for the relevant classical groups, a noncentral element of degree $k$ has a conjugacy class so large that every group element can be written as a product of only $O\!\left(\frac{d}{k}\right)$ of its conjugates.

The object that fixes almost everything is therefore not weak.

Its many conjugates let us move the small region where it acts throughout the vector space. Multiplying those conjugates eventually builds arbitrary group elements.

This is the second major conceptual reversal in the proof:

Make one transformation extremely local, then use symmetry to move that local transformation everywhere.

Combining the cost of constructing the small-degree element, reaching its conjugates, and multiplying sufficiently many of them produces

$$\operatorname{diam}(G) \leq q^{O\left(r(\log r+\log q)^3\right)}.$$

What the proof really changes

The paper does not prove Babai’s conjecture in high rank. Its bound remains much larger than a power of $\log |G|$.

What it establishes is a new way to escape the trivial scale of the problem.

A group of order around $q^{r^2}$ for fixed $q$ might a priori admit generating sets whose Cayley graphs require something comparably enormous to traverse. Instead, the argument brings the exponent down from a quantity of order $r^2$ to essentially $r$, apart from logarithmic factors.

More important than the numerical improvement is the mechanism connecting three apparently different kinds of mathematics.

Finite-field arithmetic determines which spectral patterns can fit inside a small-dimensional space. Linear algebra converts those patterns into matrices whose degree can be reduced. Group theory then turns a single small-degree element into a collection of conjugates capable of filling the whole group.

None of those steps by itself solves the diameter problem.

Together they produce a route through it.

Where the story stands now

The 2017 result is no longer the sharpest general bound of this type.

In 2019, Zoltán Halasi, Attila Maróti, László Pyber, and Youming Qiao improved it to

$$\operatorname{diam}(G) < q^{O\left(r(\log r)^2\right)}$$

for finite simple groups of Lie type of rank $r$. Their theorem is stronger in particular because the $\log q$ term disappears from the logarithmic factor. (arXiv)

Other work has obtained much stronger, sometimes polylogarithmic, diameter bounds when the generating set has extra structure—for example when it contains a transvection, or in several random-generator regimes. A 2024 result of Sean Eberhard proves Babai-type bounds for classical groups generated by sets containing a transvection, while recent expository accounts emphasize that the arbitrary-generator high-rank problem remains unresolved. (Journal of Algebra)

So the central puzzle survives.

Given completely arbitrary generators of a huge simple group, how can simplicity alone prevent the Cayley graph from developing extremely long corridors?

The article’s answer is not yet the final one. But it reveals a striking strategy.

Do not begin by trying to move everywhere.

First find a move that acts almost nowhere.

Then move that move everywhere.

---

Sources

• Biswas, Arindam and Yilong Yang, A diameter bound for finite simple groups of large rank, Journal of the London Mathematical Society 95 (2017), 455–474.
• Halasi, Zoltán, Attila Maróti, László Pyber and Youming Qiao, An improved diameter bound for finite simple groups of Lie type, Bulletin of the London Mathematical Society 51 (2019), 645–657.
• Eberhard, Sean and Urban Jezernik, Babai’s conjecture for high-rank classical groups with random generators, Inventiones Mathematicae 227 (2022), 149–210.
• Eberhard, Sean, Diameter of classical groups generated by transvections, Journal of Algebra (2024).