The n-Category Café

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 decomposes uniquely as 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$.

Digression With 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.