The n-Category Café

First let me explain what I just said about the probability of a random endofunction being eventually constant, and why the answer is essentially Cayley’s formula.

Let $V$ be a finite set. A function $T : V \to V$ is eventually constant if $T^n$ is constant for some $n \geq 0$, or equivalently $T^n$ is constant for all $n \gg 0$, or equivalently $T$ has only one periodic point (which must then be a fixed point). An eventually constant function looks like this:

Here I’ve drawn an arrow from $v$ to $T(v)$ for every $v \in V$, except when $v$ is the eventual constant value, which I’ve circled and coloured in pink. Actually, the arrows add no information, because they all flow in the direction towards the pink vertex. So we might as well remove them:

What we have now is just a rooted tree with $V$ as its set of vertices. Cayley’s formula tells us how many unrooted trees there are with vertex-set $V$: there are $n^{n - 2}$ of them, where $n = \#V$. Hence there are $n^{n - 1}$ rooted trees, or equivalently $n^{n - 1}$ eventually constant endofunctions of $V$. But since there are $n^n$ endofunctions of $V$ in all, the probability that a randomly-selected endofunction is eventually constant is

$$n^{n - 1}/n^n = 1/n = 1/\#V.$$

That’s the situation for plain, unadorned sets. But this post is about vector spaces. Of course, when we’re dealing with vector spaces we only consider the linear endomorphisms, and by linearity, the eventually constant ones are exactly the nilpotents. So:

nilpotent operators are the linear analogue of rooted trees.

The root of the tree corresponds to the origin of the vector space.

I’m going to show you a proof that a random linear operator on a finite vector space $V$ is eventually constant (nilpotent) with probability $1/\#V$.

First, though, let me mention a mystery, in the hope that someone can shed some light. You’ll have noticed from the beginning of the post that two probabilities are the same: for a finite vector space $V$, the probability of a random endomorphism being eventually constant isn’t affected by whether we’re consider all endofunctions or just the linear ones. In probabilistic notation,

P(eventually constant | linear) = P(eventually constant).

So the conditions “eventually constant” and “linear” on an endofunction are independent, in the sense of probability theory. I have no intuition for why this should be true. Does anyone else?

Background linear algebra

For the proof, we’ll need a few linear algebra facts that are absolutely elementary and general, but not as well-known as they could be.

One way in which vector spaces are more complex than sets is that every subset of a set has just one complement, a subspace of a vector space has many. By a “complement” of a linear subspace $Y$ I mean what’s usually called a complementary subspace, that is, another subspace $X$ such that $X \cap Y = \{0\}$ and $X + Y$ is the whole space.

So, given a subspace $Y$ of $V$ and any two subspaces $X, W$ complementary to $Y$ —

$$X \oplus Y = V = W \oplus Y$$

— it may be that $X$ and $W$ are not equal. However, they are canonically isomorphic. Indeed, we have projection maps

$$V = X \oplus Y \to X, \qquad V = W \oplus Y \to W$$

both with kernel $Y$, so by the first isomorphism theorem, there’s a unique isomorphism $i: X \to W$ commuting with the projections:

For a point $x$ of $X$, we can characterize $i(x)$ as the unique point of $W$ such that $i(x) - x \in Y$. So $i$ moves points in a direction parallel to $Y$.

Now here’s a crucial fact: for vector spaces $X$ and $Y$,

$Lin(X, Y) \cong \{$subspaces of $X \oplus Y$ complementary to $Y\}$.

This correspondence is given from left to right by the graph construction. That is, given a linear map $f: X \to Y$, we have its graph

$$W_f = \{(x, y) \in X \oplus Y : y = f(x) \},$$

which is a subspace of $X \oplus Y$ complementary to $Y$.

Conversely, given a subspace $W$ of $X \oplus Y$ complementary to $Y$, we have the canonical isomorphism $i: X \to W$ defined above — and as we noted, it gives a map $x \mapsto i(x) - x$ from $X$ to $Y$. All we’re doing here is reading a function off from its graph in the usual way. Starting from a point $x \in X$, you take the unique point $(x, y)$ on the graph ($W$) that’s above $x$, and then $y = f(x)$.

Aside From this correspondence we can easily work out how many complements any given subspace has, if we’re talking about finite-dimensional spaces over finite fields. Let $Y$ be a $k$-dimensional subspace of an $n$-dimensional space $V$ over a field with $q$ elements. Choose, arbitrarily, a complementary subspace $X$ of $Y$ in $V$. Then the fact just proved implies that there are the same number of complementary subspaces of $Y$ in $V$ as there are linear maps $X \to Y$. Since $dim X = n - k$, there are $q^{k(n - k)}$ such maps. Hence $Y$ has $q^{k(n - k)}$ complements.

This formula fits with the folklore idea that a vector space over the mythical field with one element is a set (or should I say pointed set?). For if we put $q = 1$ in the formula just established, we come to the conclusion that a subset of a set has exactly $1$ complement — which is indeed correct.

The next linear algebra fact we’ll need is this:

$$endomorphism = nilpotent \oplus automorphism.$$

That is, for any linear operator $T$ on a finite-dimensional vector space $V$ (over any field), there are unique subspaces $W$ and $Y$ of $V$ such that:

• $V = W \oplus Y$
• $T$ restricts to a nilpotent operator on $W$
• $T$ restricts to an automorphism of $Y$.

For today it doesn’t matter what $W$ and $Y$ actually are, but if you’re interested you can find the answer here or here: they’re the eventual kernel and eventual image, respectively.

Finally, it’s a fact that for any finite-dimensional vector space $Y$, there’s a (non-canonical) bijection

$Aut(Y) \cong \{$ordered bases of $Y\}$.

This is closely analogous to the fact that for a finite sets, the permutations are in bijection with the total orders. Both are proved using a torsor argument: we’ve got a group acting freely and transitively on a nonempty set, which implies that the group and set are in bijection.

Concretely, in this case, the proof goes like this. Choose an ordered basis $\mathbf{y} = (y_1, \ldots, y_k)$ of $Y$. For any automorphism $S$ of $Y$, we get a new ordered basis $S\mathbf{y} = (S(y_1), \ldots, S(y_k))$. And it’s easy to see that the assignment $S \mapsto S\mathbf{y}$ defines a bijection between automorphisms and ordered bases.

Pre-proof throat-clearing

Let $V$ be a finite-dimensional vector space over any field. Write $Nil(V)$ and $End(V)$ for the set of nilpotent operators on $V$ and endomorphisms of (linear operators on) $V$. We’re going to show that there’s a bijection

$$Nil(V) \times V \cong End(V).$$

When the base field is finite, this immediately implies that the probability of a random linear operator on $V$ being nilpotent is $1/#V$. It also gives a formula for the number of nilpotents on $V$. For if $V$ is $n$-dimensional over a field with $q$ elements, there are $(q^n)^n = q^{n^2}$ linear operators on $V$, since to specify one we have to choose for each of $n$ basis elements one of the $q^n$ elements of $V$. Hence there are

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

nilpotents on $V$.

The bijection is not canonical. We’re going to need to choose, for each linear subspace $Y$ of $V$:

• a complementary subspace $Y^\bot$
• a bijection between the ordered bases of $Y$ and the automorphisms of $Y$.

If we were working over $\mathbb{R}$ or $\mathbb{C}$ then we could choose the complementary subspaces by choosing an inner product on $V$ — but we’re probably not. In any case, it’s certainly true that every subspace has at least one complement, and we can just choose arbitrarily.

Aside The situation in Joyal’s proof of Cayley’s formula is very similar. There, to get a bijection between endomorphisms and vertebrates (bipointed trees), we have to choose for each subset $Y$ a bijection between the total orders on $Y$ and the permutations of $Y$. It’s unsurprising that we don’t also have to choose a complement of $Y$, since in the world of sets, subsets have a unique complement anyway!

Once these choices have been made, we get a bijection between $Nil(V) \times V$ and $End(V)$ as follows.

The proof

Start with a pair $(T, y)$, consisting of a nilpotent $T$ on $V$ and an element $y$ of $V$:

(I don’t want to clutter up this proof with further discussion of the analogy with Joyal’s proof of Cayley’s formula, but I’ve chosen the colours in these diagrams to match the ones in my presentation of Joyal’s proof. For full effect, you might want to open that post in another window and look at the two arguments side by side.)

Since $T$ is nilpotent, there’s a least $k \geq 0$ such that $T^k y = 0$. It’s easy to show that

$$y, T y, T^2 y, \ldots, T^{k - 1}y$$

are linearly independent, so they form a basis for the subspace $Y$ that they span. Here’s a picture with $k = 4$:

(This picture shouldn’t be taken too seriously: I’ve drawn $Y$ as if it were one-dimensional, in which case there’s no way we can have $k = 4$.)

Let’s write $y_i = T^i y$:

It looks as if we’ve thrown away $y$, but we haven’t: we recover it from the ordered basis $\mathbf{y} = (y_0, \ldots, y_{k - 1})$ as $y_0$ if $k \gt 0$, or as $0$ otherwise.

Now $T$ is completely determined on $Y$ by $\mathbf{y}$, since it’s given by $y_i \mapsto y_{i + 1}$ if $i \lt k - 1$, and by $y_{k - 1} \mapsto 0$. So given $Y$ and its ordered basis $\mathbf{y}$, to specify $T$ we only need to specify its restriction to $Y^\bot$. This restriction is a map $Y^\bot \to V = Y^\bot \oplus Y$, which in turn is determined by its two components

$$T_{Y^\bot Y^\bot} : Y^\bot \to Y^\bot, \qquad T_{Y^\bot Y} : Y^\bot \to Y.$$

So, our original pair $(T, y)$ is uniquely determined by the subspace $Y$, its ordered basis $\mathbf{y}$, and the linear maps $T_{Y^\bot Y^\bot}$ and $T_{Y^\bot Y}$. The original operator $T$ is nilpotent iff $T_{Y^\bot Y^\bot}$ is nilpotent, as you can easily check. (The background fact is this: given a linear operator $T$ on a direct sum $X \oplus Y$ such that $T Y \subseteq Y$, and writing $\begin{pmatrix} P &0 \\ R & S\end{pmatrix}$ for its block decomposition, $T$ is nilpotent iff $P$ and $S$ are nilpotent.) So what we’ve now got is data like this:

We saw earlier that linear maps $Y^\bot \to Y$ correspond one-to-one with subspaces of $Y^\bot \oplus Y = V$ complementary to $Y$, via the graph construction. So we can equivalently replace $T_{Y^\bot Y}$ by a subspace $W$ of $V$ complementary to $Y$:

On the other hand, we also saw that $Y^\bot$ and $W$ — both being subspaces of $V$ complementary to $Y$ — are canonically isomorphic. So we can equivalently replace the nilpotent operator $T_{Y^\bot Y^\bot}$ on $Y^\bot$ by a nilpotent operator $R$ on $W$:

Next, ordered bases of $Y$ are in bijection with automorphisms of $Y$. (There’s no canonical bijection, but that’s OK: we chose one earlier.) So we can equivalently replace the ordered basis $\mathbf{y}$ by an automorphism $S$ of $\mathbf{y}$:

So far we’ve shown that

pairs (nilpotent $T$ on $V$, element $y$ of $V$)

are in bijection with

quadruples (subspace $W$ of $V$, nilpotent $R$ on $W$, subspace $Y$ of $V$, automorphism $S$ of $Y$) with $W \oplus Y = V$.

But since every linear operator on $V$ decomposes uniquely as the direct sum of a nilpotent and an automorphism, such quadruples are in canonical bijection with linear operators on $V$:

Hence pairs (nilpotent $T$ on $V$, element $y$ of $V$) are in bijection with endomorphisms of $V$:

$$Nil(V) \times V \cong End(V),$$

as required.