### Counting Nilpotents

#### Posted by Tom Leinster

What is the probability that a random linear operator is nilpotent?

Recall that a linear operator $T$ on a vector space $V$ is called “nilpotent” if $T^n = 0$ for some $n$. Assuming that $V$ is finite-dimensional and over a finite field, there are only finitely many operators on $V$. Choose one at random. It turns out that the probability of it being nilpotent is

$\frac{1}{\# V}$

— the reciprocal of the number of elements of $V$.

I’ll explain why. Along the way, we’ll meet some dynamical linear algebra, some $q$-formalism, and a kind of generating function adapted to linear algebra over a finite field.

This post was inspired by John’s recent series on random permutations, but is free-standing and self-contained. Enjoy!

## Dynamical linear algebra

I have a soft spot for what I call “dynamical linear algebra”: studying linear operators by looking at what happens when you iterate them a large number of times. Since a nilpotent operator is one which becomes trivial when iterated a large number of times, we’re squarely in the context of dynamical linear algebra.

Let $V$ be a vector space, which in this post will always mean “finite-dimensional vector space”. For the moment, the base field can be absolutely anything. The first significant result in dynamical linear algebra is that

every operator decomposesuniquelyas the direct sum of an automorphism and a nilpotent.

If you know the (much more complicated) Jordan normal form theorem then you
*almost* already know this, at least for algebraically closed fields: think
about the subspace corresponding to the Jordan $0$-blocks and the subspace
corresponding to all the other Jordan blocks. But what the Jordan theorem
doesn’t tell you — at least, as it’s usually stated — is that
this decomposition is unique.

Anyway, this result is far simpler than the Jordan normal form theorem, and
it works like this. Let $T$ be a linear operator on $V$. The **eventual
image** and **eventual kernel** of $T$ are the subspaces defined by

$im^\infty(T) = \bigcap_{i = 0}^\infty \im(T^i), \qquad ker^\infty(T) = \bigcup_{i = 0}^\infty \ker(T^i).$

It’s a pleasant exercise to show the following basic facts:

$V = im^\infty(T) \oplus ker^\infty(T)$;

$T$ restricts to an automorphism of $im^\infty(T)$;

$T$ restricts to a nilpotent operator on $ker^\infty(T)$.

And that’s the decomposition of an arbitrary operator into an automorphism and a nilpotent. With a little extra work, you can prove it’s the only such decomposition.

It follows that the set $End(V)$ of endomorphisms of $V$ (i.e. operators on $V$) can itself be decomposed in a canonical way:

$End(V) \cong \coprod_{U \oplus W = V} Aut(U) \times Nil(W),$

where the disjoint union is over all pairs $(U, W)$ of complementary subspaces of $V$, and I’m writing $Aut(U)$ and $Nil(W)$ for the sets of automorphisms of $U$ and nilpotent operators on $W$, respectively.

Anyone familiar with species will now be itching to rephrase that isomorphism… but I’ll leave that to you, and instead move on to counting.

## $q$-formalism

Our initial question — what’s the probability that a random operator is nilpotent? — is a counting problem for finite vector spaces. It’s “linear combinatorics”. So let’s warm up to it with some much simpler counting problems for finite vector spaces, keeping in mind throughout the analogous problems for finite sets (“ordinary combinatorics”).

As ever, let $V$ be a vector space. We’re still assuming that all vector spaces are finite-dimensional, and from now on we’ll also assume that the base field is finite, with $q$ elements. I’ll write $\mathbb{F}_q$ for the field itself.

One of the most basic facts in ordinary combinatorics is that there are
$n!$ total orders on an $n$-element set. The analogous question in linear
algebra is: how many totally ordered *bases* are there for an
$n$-dimensional space?

Let’s write $n!_q$ for the answer. The first basis element can be anything
except $0$, so there are $q^n - 1$ ways of choosing it. The second basis
element can be anything that isn’t in the span of the first, so there are
$q^n - q$ ways of choosing *it*. Continuing in this way, we get

$n!_q = (q^n - 1)(q^n - q) \cdots (q^n - q^{n - 2})(q^n - q^{n - 1}).$

Now here’s a useful observation which at the moment I only understand as a little algebraic trick, but which I’d like to understand conceptually — maybe someone can help me here. Trivially,

$n!_q = q^0(q^n - 1) \cdot q^1 (q^{n - 1} - 1) \cdot \cdots \cdot q^{n - 2}(q^2 - 1) \cdot q^{n - 1}(q^1 - 1).$

Now here’s the trick: reverse the order of the powers of $q$, to give

$n!_q = q^{n - 1}(q^n - 1) \cdot q^{n - 2}(q^{n - 1} - 1) \cdot\cdots\cdot q^1(q^2 - 1) \cdot q^0(q^1 - 1).$

It follows that if we define

$n_q = q^{n - 1}(q^n - 1)$

then

$n!_q = n_q \cdot (n - 1)_q \cdot\cdots\cdot 2_q \cdot 1_q.$

Equivalently, the sequence $(n!_q)_{n \geq 0}$ is defined by $0!_q = 1$ and $n!_q = n_q \cdot (n - 1)!_q$.

Let’s use this formalism to answer another basic question about the combinatorics of finite vector spaces: given $0 \leq k \leq n$, how many ways are there of expressing a given $n$-dimensional space as the direct sum of a $k$-dimensional subspace $U$ and an $(n - k)$-dimensional subspace $W$?

The analogous question for sets is “how many ways are there of expressing a given $n$-element set as the disjoint union of a $k$-element subset and an $(n - k)$-element subset”, to which the answer is $\binom{n}{k}$. So let’s write

$\binom{n}{k}_q$

for the number of pairs $(U, W)$ of subspaces of $\mathbb{F}_q^n$ such that $U \oplus W = \mathbb{F}_q^n$ and $dim U = k$ (and, therefore, $dim W = n - k$).

To discover what $\binom{n}{k}_q$ actually is, we compute in two ways the
number of such pairs $(U, W)$ *together with* an ordered basis of $U$ and
an ordered basis of $W$. On the one hand, by what we’ve just shown about
ordered bases, it’s

$\binom{n}{k}_q \cdot k!_q \cdot (n - k)!_q.$

On the other, it’s the same as the number of ordered bases of $\mathbb{F}_q^n$ itself, which is $n!_q$. Comparing the two methods, we’ve got our answer:

$\binom{n}{k}_q = \frac{n!_q}{k!_q (n - k)!_q}.$

That’s the number of direct sum decompositions of an $n$-dimensional vector space over $\mathbb{F}_q$ into subspaces of dimensions $k$ and $n - k$.

DigressionWith this kind of stuff, interesting things sometimes happen when you substitute $q = 1$. For example, $\frac{n_q}{q - 1} \Big|_{q = 1} = n,$ hence $\frac{n!_q}{(q - 1)^n} \Big|_{q = 1} = n!,$ from which it follows that $\binom{n}{k}_q \Big|_{q = 1} = \binom{n}{k}.$ Of course, there is no field of order $q = 1$, but this is part of the lore of the “field with one element”: a vector space over the field with one element is supposed to be something like a set.

## The number of nilpotents

We’re now ready to count the number of nilpotents on a vector space.

Let $V$ be an $n$-dimensional vector space over $\mathbb{F}_q$. Earlier, we showed that

$End(V) \cong \coprod_{U \oplus W = V} Aut(U) \times Nil(W).$

Taking cardinalities on each side, and writing $end_n$ for the number of endomorphisms of an $n$-dimensional space, and similarly $aut_n$ and $nil_n$, this implies that

$end_n = \sum_{U, W} aut_{dim U} nil_{dim W},$

where the sum is over all pairs $(U, W)$ such that $U \oplus W = V$. There are $\binom{n}{k}_q$ such pairs in which $dim U = k$, so

$end_n = \sum_{k = 0}^n \binom{n}{k}_q aut_k nil_{n - k}.$

By the explicit expression for $\binom{n}{k}_q$, this says that

$end_n = \sum_{k = 0}^n \frac{n!_q}{k!_q (n - k)!_q} aut_k nil_{n - k},$

or equivalently

$\frac{end_n}{n!_q} = \sum_{k = 0}^n \frac{aut_k}{k!_q} \frac{nil_{n - k}}{(n - k)!_q}.$

If you’re familiar with generating functions, you’ll recognize that now is
the time to bring them into play! But what we need are not *ordinary*
generating functions (which are adapted to finite totally ordered sets), or
*exponential* generating functions (which are adapted to finite unordered
sets), but what might be called “$q$-exponential generating functions”,
adapted to finite-dimensional vector spaces over $\mathbb{F}_q$.
Specifically, the last equation gives an equality

$\sum_{n = 0}^\infty end_n \frac{x^n}{n!_q} = \Bigl( \sum_{n = 0}^\infty aut_n \frac{x^n}{n!_q} \Bigr) \Bigl( \sum_{n = 0}^\infty nil_n \frac{x^n}{n!_q} \Bigr)$

of formal power series. This equation is going to lead us to the value of $nil_n$, which is our goal.

The first step is to find $aut_n$, which by definition is the number of automorphisms of an $n$-dimensional vector space $V$ over $\mathbb{F}_q$. This is sort of trivial, but I want to make a song and dance about it for categorical reasons. If we fix (arbitrarily) an ordered basis of $V$ then applying any automorphism to it yields another ordered basis, and every ordered basis arises uniquely in this way. Thus, $aut_n$ is the same as the number of ordered bases of $V$, which is $n!_q$.

That’s the answer, but the important point is that there’s no *natural*
bijection between ordered bases and automorphisms. It’s exactly like the
situation for finite sets, where the number of (total) orders on an
abstract set is equal to the number of permutations, but there’s no
canonical bijection between orders and permutations. (Because if there was,
which order would correspond to the identity permutation?) Abstractly,
what we’ve got in both situations is a “torsor”: a group (automorphisms or
permutations) that acts freely and transitively on a nonempty set (the
ordered bases or orders). The group and the set are then in bijection, but
not *canonically* so.

In any case, $aut_n = n!_q$, so the generating function of $aut$ is very simple:

$\sum_{n = 0}^\infty aut_n \frac{x^n}{n!_q} = \sum_{n = 0}^\infty x^n = \frac{1}{1 - x}.$

Hence

$\sum_{n = 0}^\infty nil_n \frac{x^n}{n!_q} = (1 - x) \sum_{n = 0}^\infty end_n \frac{x^n}{n!_q}.$

After a couple of lines of algebra, taking advantage of the equality $n!_q = n_q \cdot (n - 1)!_q$, this gives $nil_0 = end_0$ and

$nil_n = end_n - n_q \cdot end_{n - 1}$

($n \geq 1$). But the number of endomorphisms is also easy to compute! By the universal property of bases, a linear map from a vector space to itself amounts to a map of sets from any given basis to the space. In the case of $\mathbb{F}_q^n$, there are $n$ elements in a basis and $q^n$ elements in the space, so

$end_n = (q^n)^n = q^{n^2}.$

Substituting this into the expression for $\nil_n$ and simplifying gives the answer:

$nil_n = q^{n(n - 1)}.$

And that’s the number of nilpotents on an $n$-dimensional vector space over the field with $q$ elements.

The original question I asked was: what’s the probability that a
randomly-chosen linear operator on $V \cong \mathbb{F}_q^n$ is nilpotent?
We’ve just shown that there are $q^{n^2}$ such operators, and when I say
“randomly-chosen” I mean chosen *uniformly* at random: all the operators
get an equal chance. So the answer to that question is

$\frac{q^{n(n - 1)}}{q^{n^2}} = \frac{1}{q^n} = \frac{1}{\# V}.$

We’re done!

The final answer is almost suspiciously simple. It’s not a surprise that the generating function method works, but a fair amount of lucky cancellation happened towards the end, leading to an answer that’s simpler than we had a right to expect. This suggests that there should be a better proof, revealing why that simple answer is what it is.

I have an idea about how such a proof might look, roughly. But I’m out of energy now, so let me save that for another day.

## Re: Counting Nilpotents

What a great proof of an enigmatically easy-to-state fact! I wonder if the probability that the eventual image is $k$-dimensional has a similarly simple formula for values of $k$ other than $0$.

Other thoughts: how far can we push an analogy between cycles of a random permutation and Jordan blocks of a linear transformation (or blocks in rational canonical form)? For $n\times n$ matrices, we end up with a partition of $n$ into block sizes, but with extra data on each block (such as whether the block is nilpotent or invertible).