## December 3, 2019

### 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 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.

Posted at December 3, 2019 4:37 PM UTC

TrackBack URL for this Entry:   https://golem.ph.utexas.edu/cgi-bin/MT-3.0/dxy-tb.fcgi/3168

### 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).

Posted by: Owen Biesel on December 3, 2019 6:13 PM | Permalink | Reply to this

### Re: Counting Nilpotents

I think that the same argument shows that the desired probability is $\binom n k_q\operatorname{aut}_k\operatorname{nil}_{n - k}\operatorname{end}_n^{-1} = \binom n k_q k!_q q^{(n - k)(n - k - 1)}q^{-n^2} = \frac{n!_q}{(n - k)!_q}q^{-(2k + 1)n + (k + 1)k}.$

(I can never seem to get blockquotes to work, so sorry for not quoting your specific question.)

Posted by: L Spice on December 3, 2019 8:22 PM | Permalink | Reply to this

### Re: Counting Nilpotents

Thanks for all the comments! Just to address the easiest thing for now:

I can never seem to get blockquotes to work

Assuming you haven’t chosen a text filter different from the default, you just stick a greater-than sign in front of the thing you want to quote. E.g. here’s what the source of the start of this comment looks like:

Thanks for all the comments!  Just to
address the easiest thing for now:

> I can never seem to get blockquotes to work

Assuming you haven't chosen...

Posted by: Tom Leinster on December 3, 2019 11:10 PM | Permalink | Reply to this

### Re: Counting Nilpotents

On the mathematical point, yes, I agree with your formula for the probability that the eventual image is $k$-dimensional. I admit, I’d been hoping it would be one of those formulas where substituting $q = 1$ gives you the answer to the analogous problem for sets rather than vector spaces. But apparently not.

I don’t understand when that miraculous phenomenon appears and when it doesn’t.

Posted by: Tom Leinster on December 3, 2019 11:17 PM | Permalink | Reply to this

### Allen

Next: what’s the probability of getting a nilpotent with fixed Jordan type? And why do those probabilities, summed over all partitions, give 1/#V? The first should be pretty easy since the space is an orbit of GL(V). The second sounds harder (without knowing your result in advance).

Posted by: Allen Knutson on December 3, 2019 7:04 PM | Permalink | Reply to this

### Re: Allen

I think that the number of nilpotents with type $(k_1, \ldots, k_r)$ is $\binom n{k_1\,k_2\,\cdots\,k_r}_q$ (with the obvious $q$-multinomial notation), so that the question becomes why $\sum_{(k_1, \ldots, k_r) \vdash n} \binom n{k_1\,k_2\,\cdots\,k_r}_q = q^{n(n - 1)}$ (which I don’t know how to answer).

Posted by: L Spice on December 3, 2019 8:28 PM | Permalink | Reply to this

### Re: Allen

Sorry, that would give 1 regular nilpotent, hence is nonsense. I think that the number of regular nilpotents is $n_q$, so that the number of nilpotents of type $(k_1, k_2, \ldots, k_r)$ is $\binom n{k_1\,k_2\,\cdots\,k_r}_q\cdot\prod_{i = 1}^r (k_i)_q$.

Posted by: L Spice on December 3, 2019 8:40 PM | Permalink | Reply to this

### Re: Counting Nilpotents

(Sorry for all the posts; combinatorics + linear algebra of finite vector spaces tickles my fancy.)

I don’t know if it counts as conceptual, but, using the fact that $n!_q = \operatorname{aut}_n$, we can see $n!_q = n_q(n - 1)!_q$ as the statement that choosing a direct-sum decomposition $V = \mathbb{F}_q e \oplus V'$ identifies the subgroup $A_e = \{g \in A : g e = e\}$ of $A = \operatorname{Aut}(V)$ with the direct product of $A' = \operatorname{Aut}(V')$ and $(V')* = \operatorname{Hom}(V', \mathbb{F}_q)$ by letting $(g', \lambda)$ correspond to $v' \mapsto g'v' + \lambda(v')e$; so, since $A/A_e$ is identified with $V \setminus \{0\}$ by sending $g$ to $g e$, we have that $\operatorname{aut}_n = \lvert A\rvert = \lvert A_e\rvert\cdot\lvert A/A_e\rvert = \lvert A'\rvert\cdot\lvert W'\rvert\cdot\lvert V \setminus \{0\}\rvert = \operatorname{aut}_{n - 1} q^{n - 1}(q^n - 1)$ (where I’ve written $W'$ in place of the dual of $V'$ because the complexities of the MathJax parser beat me).

Posted by: L Spice on December 3, 2019 9:13 PM | Permalink | Reply to this

### Re: Counting Nilpotents

If you like these generating formulae arguments over finite fields, you should like the relevant part of the proof of Kac’s Theorem for representations of quivers.

What follows is a brief outline of the main ideas, and is probably too long, too tangential to the post, and too difficult to follow, so apologies in advance.

Recall that a quiver is given by an arrangement of vertices and arrows between them, like an oriented graph except we allow vertex loops and multiple arrows between any pair of vertices. A representation over a field $k$ consists of a vector space at each vertex and a linear map for each arrow. Its dimension vector records the dimension of the vector space at each vertex.

The problem is now to find a formula for the number of isomorphism classes of representations of a given dimension vector over a finite field. Fixing bases for the vector spaces, we can represent every representation as a configuration of matrices. The product of the general linear groups then acts by base change (conjugation), and we need to count the number of orbits.

Using Burnisde’s Lemma, we can write this as a sum over the fixed points, so let us take some group element $g$. At each vertex $i$ we have a vector space $V_i$ together with an automorphism $g_i$, so a $k[t,t^{-1}]$-module. A configuration of matrices is a fixed point for $g$ precisely when the matrix for each arrow is a homomorphism of $k[t,t^{-1}]$-modules. This number is now just a power of $q$, the size of the finite field, depending on the conjugacy classes of the elements $g_i$, or maybe better, on the isomorphism classes of the $k[t,t^{-1}]$-modules.

We therefore consider the multivariable generating function, with one variable for each vertex, computing the number of isomorphism classes of each dimension vector. Every $k[t,t^{-1}]$-module is a direct sum of indecomposables, and each indecomposable has a unique composition series with only one simple occurring, so is determined by this simple (equivalently monic irreducible polynomial in $k[t]$ other that $t$ itself) and its length. The considerations above imply that we can factor this generating function as a product over the possible simples, and by a bit of magic concerning $k[t]$-modules says each factor is some generating function $P$ (defined directly in terms of the quiver) with all variables raised to the power of the dimension of the simple. Moreover, the number of simples of a given dimension is basically the number of monic irreducible polynomials.

In summary, we have a kind of Euler product formula, where on one side we have the multivariable generating function for the number of isomorphism classes of representations, and on the other side a product over the positive integers (the dimension $d$) of the generating function $P$ to the power of the number of simples of dimension $d$, and with each variable in $P$ raised to the power of $d$.

Amazingly, this implies that the number of isomorphism classes of representations of a given dimension vector is polynomial in the cardinality $q$ of the field.

Posted by: Andrew Hubery on December 3, 2019 9:20 PM | Permalink | Reply to this

### Re: Counting Nilpotents

I can’t resist adding to my previous answer, which also relates to Allen’s question above.

Given a partition $\lambda$ of $n$, let $N_\lambda\in\mathrm{GL}_n(q)$ be a nilpotent endomorphism with this Jordan type, and set $z_\lambda(q)$ to be the size of the centraliser of $N_\lambda$ in $\mathrm{GL}_n(q)$. (It is fairly straightforward to get a closed form for $z_\lambda(q)$.)

Then, in the simplest case of a quiver having a single vertex and no arrows, the generating function $P$ I referred to above has the form

$P = \sum_\lambda \frac{X^{|\lambda|}}{z_\lambda(q)}$

and from the representation theory side we obtain the factorisation

$P = \prod_{i\geq0}(1-q^i X).$

(In general, the factorisation will be more complicated, involving the positive roots of the quiver/Kac-Moody Lie algebra).

There is also the identity (due to Euler?)

$\prod_{i\geq0}(1-q^i X) = \sum_{i\geq0}\frac{q^{n(n-1)}X^n}{n!_q}$

Putting this together we see that

$\sum_{\lambda\vdash n} \frac{n!_q}{z_\lambda(q)} = q^{n(n-1)},$

or in words, the sum over the number of nilpotents of type $\lambda$ equals the number of nilpotents.

Posted by: Andrew Hubery on December 4, 2019 5:17 PM | Permalink | Reply to this

### Re: Counting Nilpotents

Regarding your numbers $n_q$, they can be thought of as choosing a non-zero point together with a complementary hyperplane (which will then be the span of the other basis vectors).

I can’t immediately see a simple argument as to why there are $q^{n-1}$ hyperplanes in $n$-space not containing a given point, though. In dimension two this is easy, since there are $q+1$ lines in 2-space and only one of them contains my point.

Posted by: Andrew Hubery on December 3, 2019 9:39 PM | Permalink | Reply to this

### Re: Counting Nilpotents

The same argument works in general: there are $(q^n - 1)/(q - 1)$ hyperplanes (parameterised by non-0 functionals on $V$, up to scalar multiples), and $(q^{n - 1} - 1)/(q - 1)$ of them contain your point (parameterised by non-0 functionals on the quotient of $V$ by the line through your point, up to scalar multiples).

Posted by: L Spice on December 3, 2019 11:04 PM | Permalink | Reply to this

### Re: Counting Nilpotents

I can’t immediately see a simple argument as to why there are $q^{n-1}$ hyperplanes in $n$-space not containing a given [nonzero] point

Here’s the simplest argument I’ve thought of so far. An equivalent statement to yours is: there are $q^{n - 1}$ hyperplanes in $n$-space not containing a given line (by which I mean a $1$-dimensional linear subspace). By duality, a further equivalent statement is: there are $q^{n - 1}$ lines in $n$-space not contained in a given hyperplane.

To prove that, take any nontrivial coset $H'$ of the given hyperplane $H$. Every line not contained in $H$ intersects $H'$ in exactly one point, which completely determines the line; moreover, every point in $H'$ lies on exactly one line (which is obviously not contained in $H$). Hence the lines not contained in $H$ are in bijection with the points of $H'$, of which there are $q^{n - 1}$.

Posted by: Tom Leinster on December 3, 2019 11:06 PM | Permalink | Reply to this

### 1/#V = (1/q)^n

What’s the probability that a random operator has trace 0?

1/q, obviously.

Of those, what’s the probability that its square also has trace 0?

If that were again 1/q, and so on for the first n powers, that feels like a good “reason” that the probability of being nilpotent is 1/q^n. Apparently it’s correct for n=2!

Posted by: Allen Knutson on December 4, 2019 1:51 AM | Permalink | Reply to this

### Re: 1/#V = (1/q)^n

I like the idea, but I’m not convinced… If I understand correctly, the background assumption is that an operator $T$ is nilpotent iff every power of $T$ has trace $0$. But what if we take the identity operator on the $q$-dimensional vector space over $\mathbb{F}_q$?

Posted by: Tom Leinster on December 4, 2019 9:15 AM | Permalink | Reply to this

### Re: 1/#V = (1/q)^n

Doubtless Allen meant the coefficients of the characteristic polynomial of $g$ (which are themselves polynomial in the traces of the powers $g$, so maybe that’s where those powers cropped up).

(I’m troubled because Cayley–Hamilton seems to imply that the traces $\tr(g), \cdots, \tr(g^n)$ cannot be independent, at least in some sense; but either that sense is nonsense, or the same sort of argument should give that the $n$ non-leading coefficients of the characteristic polynomial are not independent.)

I guess all power traces 0 implies nilpotent in characteristic 0, by the Newton identities.

Posted by: L Spice on December 4, 2019 2:29 PM | Permalink | Reply to this

### Re: 1/#V = (1/q)^n

Let $p_k$ be the trace of $g^k$, and let $e_k$ be the trace of $\bigwedge^k g$. In characteristic zero, by the Newton identities, $(e_1, \ldots, e_k)$ determine $(p_1,\ldots, p_k)$ and vice versa. In characteristic p, that’s not true, and what Alen should be saying is that $g$ is nilpotent if and only if the $e$’s are $0$.

It seems like a natural question, then, is whether the probabilities that $e_j=0$ are independent for different values of j.

Posted by: David E Speyer on December 9, 2019 6:24 PM | Permalink | Reply to this

### Re: 1/#V = (1/q)^n

Oh, should have thought more before I posted. The probability that $e_n=0$, where n is the dimension, is the probability that X is not invertible, which is known to be $1-\prod_{j=1}^n (1-q^{-j})$, not $q^{-1}$.

A more reasonable question would be whether, conditioned on $e_1 = e_2 = \cdots = e_{k-1}=0$, the probability of $e_k=0$ is $q^{-1}$.

Posted by: David E Speyer on December 9, 2019 6:27 PM | Permalink | Reply to this

### Re: 1/#V = (1/q)^n

I still lose. For $q \equiv 2 \bmod 3$, I compute that the probability that $e_1=e_2=0$, in other words, the probability of a characteristic polynomial of the form $x^3-a$, is $\frac{q^4-q^3+2q-1}{q^6}$, not $q^{-2}$.

Posted by: David E Speyer on December 9, 2019 6:32 PM | Permalink | Reply to this

### q-formalism

By the way, I don’t know who originated the $q$-formalism used in the post: the definitions of $n_q$, $n!_q$, $\binom{n}{k}_q$, and the like. As with so many things, I think I learned it years ago from some issue of This Week’s Finds in Mathematical Physics.

There are several mathematical theories that go by names such as “$q$-calculus” and “$q$-algebra”, all involving a formal deformation parameter $q$. My amateur impression is that some of them are quite unrelated to others, as far as we know. Thomas Ernst’s 500-page book A Comprehensive Treatment of $q$-Calculus covers some of these theories.

Posted by: Tom Leinster on December 4, 2019 2:12 PM | Permalink | Reply to this

### Re: Counting Nilpotents

Laymans thoughts

f in End(V) : f^r = 0 with r minimal. Then the minimal polynonimal min(f)(x) is x^r. The minimal poly divides the characteristic poly, hence CharPoly(f)(x) = x^n. So all eigenvalues are 0. After choosing a basis, i have to place n zeroes on the diagonal, elsewhere i am free to choose. So I can place q^(n^2-n) = q^((n*(n-1)) numbers. Hence nil(n) = q^(n(n-1)).

Where am I wrong?

Posted by: Gerd on December 5, 2019 7:03 PM | Permalink | Reply to this

### Re: Counting Nilpotents

Your answer is right, as Tom showed, but the reasoning is suspect for at least two reasons:

1. It is not true that a general matrix with 0’s on the diagonal is automatically nilpotent; for example, $\begin{pmatrix} 0 & 1 \\ 1 & 0 \end{pmatrix}$ is not.

2. It’s true that, for every nilpotent, you can choose a basis in which it has a nice matrix, but different nilpotents require different bases, and there can be more than one basis with respect to which a given nilpotent has a nice matrix, so this can complicate counting problems.

Posted by: L Spice on December 5, 2019 8:00 PM | Permalink | Reply to this

### Re: Counting Nilpotents

I finally found this argument in the literature. It appears in Section 2.1 of this:

Andries E. Brouwer, Rod Gow, John Sheekey, Counting symmetric nilpotent matrices. The Electronic Journal of Combinatorics 21 (2), 2014, article P2.4.

Although their argument is substantially the same as the one I gave, they don’t put it in terms of generating functions, instead using a little difference equation manoeuvre at the end.

Posted by: Tom Leinster on December 24, 2019 1:33 AM | Permalink | Reply to this

Post a New Comment