Skip to the Main Content

Note:These pages make extensive use of the latest XHTML and CSS Standards. They ought to look great in any standards-compliant modern browser. Unfortunately, they will probably look horrible in older browsers, like Netscape 4.x and IE 4.x. Moreover, many posts use MathML, which is, currently only supported in Mozilla. My best suggestion (and you will thank me when surfing an ever-increasing number of sites on the web which have been crafted to use the new standards) is to upgrade to the latest version of your browser. If that's not possible, consider moving to the Standards-compliant and open-source Mozilla browser.

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 TT on a vector space VV is called “nilpotent” if T n=0T^n = 0 for some nn. Assuming that VV is finite-dimensional and over a finite field, there are only finitely many operators on VV. Choose one at random. It turns out that the probability of it being nilpotent is

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

— the reciprocal of the number of elements of VV.

I’ll explain why. Along the way, we’ll meet some dynamical linear algebra, some qq-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 VV 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 00-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 TT be a linear operator on VV. The eventual image and eventual kernel of TT are the subspaces defined by

im (T)= i=0 im(T i),ker (T)= i=0 ker(T i). 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 (T)ker (T)V = im^\infty(T) \oplus ker^\infty(T);

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

  • TT restricts to a nilpotent operator on ker (T)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)End(V) of endomorphisms of VV (i.e. operators on VV) can itself be decomposed in a canonical way:

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

where the disjoint union is over all pairs (U,W)(U, W) of complementary subspaces of VV, and I’m writing Aut(U)Aut(U) and Nil(W)Nil(W) for the sets of automorphisms of UU and nilpotent operators on WW, 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.

qq-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 VV 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 qq elements. I’ll write 𝔽 q\mathbb{F}_q for the field itself.

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

Let’s write n! qn!_q for the answer. The first basis element can be anything except 00, so there are q n1q^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 nqq^n - q ways of choosing it. Continuing in this way, we get

n! q=(q n1)(q nq)(q nq n2)(q nq n1). 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 n1)q 1(q n11)q n2(q 21)q n1(q 11). 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 qq, to give

n! q=q n1(q n1)q n2(q n11)q 1(q 21)q 0(q 11). 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 n1(q n1) n_q = q^{n - 1}(q^n - 1)

then

n! q=n q(n1) q2 q1 q. n!_q = n_q \cdot (n - 1)_q \cdot\cdots\cdot 2_q \cdot 1_q.

Equivalently, the sequence (n! q) n0(n!_q)_{n \geq 0} is defined by 0! q=10!_q = 1 and n! q=n q(n1)! qn!_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 0kn0 \leq k \leq n, how many ways are there of expressing a given nn-dimensional space as the direct sum of a kk-dimensional subspace UU and an (nk)(n - k)-dimensional subspace WW?

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

(nk) q \binom{n}{k}_q

for the number of pairs (U,W)(U, W) of subspaces of 𝔽 q n\mathbb{F}_q^n such that UW=𝔽 q nU \oplus W = \mathbb{F}_q^n and dimU=kdim U = k (and, therefore, dimW=nkdim W = n - k).

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

(nk) qk! q(nk)! q. \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 𝔽 q n\mathbb{F}_q^n itself, which is n! qn!_q. Comparing the two methods, we’ve got our answer:

(nk) q=n! qk! q(nk)! q. \binom{n}{k}_q = \frac{n!_q}{k!_q (n - k)!_q}.

That’s the number of direct sum decompositions of an nn-dimensional vector space over 𝔽 q\mathbb{F}_q into subspaces of dimensions kk and nkn - k.

Digression With this kind of stuff, interesting things sometimes happen when you substitute q=1q = 1. For example, n qq1| q=1=n, \frac{n_q}{q - 1} \Big|_{q = 1} = n, hence n! q(q1) n| q=1=n!, \frac{n!_q}{(q - 1)^n} \Big|_{q = 1} = n!, from which it follows that (nk) q| q=1=(nk). \binom{n}{k}_q \Big|_{q = 1} = \binom{n}{k}. Of course, there is no field of order q=1q = 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 VV be an nn-dimensional vector space over 𝔽 q\mathbb{F}_q. Earlier, we showed that

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

Taking cardinalities on each side, and writing end nend_n for the number of endomorphisms of an nn-dimensional space, and similarly aut naut_n and nil nnil_n, this implies that

end n= U,Waut dimUnil dimW, end_n = \sum_{U, W} aut_{dim U} nil_{dim W},

where the sum is over all pairs (U,W)(U, W) such that UW=VU \oplus W = V. There are (nk) q\binom{n}{k}_q such pairs in which dimU=kdim U = k, so

end n= k=0 n(nk) qaut knil nk. end_n = \sum_{k = 0}^n \binom{n}{k}_q aut_k nil_{n - k}.

By the explicit expression for (nk)\binom{n}{k}, this says that

end n= k=0 nn! qk! q(nk)! qaut knil nk, end_n = \sum_{k = 0}^n \frac{n!_q}{k!_q (n - k)!_q} aut_k nil_{n - k},

or equivalently

end nn! q= k=0 naut kk! qnil nk(nk)! q. \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 “qq-exponential generating functions”, adapted to finite-dimensional vector spaces over 𝔽 q\mathbb{F}_q. Specifically, the last equation gives an equality

n=0 end nx nn! q=( n=0 aut nx nn! q)( n=0 nil nx nn! q) \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 nnil_n, which is our goal.

The first step is to find aut naut_n, which by definition is the number of automorphisms of an nn-dimensional vector space VV over 𝔽 q\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 VV then applying any automorphism to it yields another ordered basis, and every ordered basis arises uniquely in this way. Thus, aut naut_n is the same as the number of ordered bases of VV, which is n! qn!_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! qaut_n = n!_q, so the generating function of autaut is very simple:

n=0 aut nx nn! q= n=0 x n=11x. \sum_{n = 0}^\infty aut_n \frac{x^n}{n!_q} = \sum_{n = 0}^\infty x^n = \frac{1}{1 - x}.

Hence

n=0 nil nx nn! q=(1x) n=0 end nx nn! q. \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(n1)! qn!_q = n_q \cdot (n - 1)!_q, this gives nil 0=end 0nil_0 = end_0 and

nil n=end nn qend n1 nil_n = end_n - n_q \cdot end_{n - 1}

(n1n \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 𝔽 q n\mathbb{F}_q^n, there are nn elements in a basis and q nq^n elements in the space, so

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

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

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

And that’s the number of nilpotents on an nn-dimensional vector space over the field with qq elements.

The original question I asked was: what’s the probability that a randomly-chosen linear operator on V𝔽 q nV \cong \mathbb{F}_q^n is nilpotent? We’ve just shown that there are q n 2q^{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

q n(n1)q n 2=1q n=1#V. \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

22 Comments & 0 Trackbacks

Re: Counting Nilpotents

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

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×nn\times n matrices, we end up with a partition of nn 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 (nk) qaut knil nkend n 1=(nk) qk! qq (nk)(nk1)q n 2=n! q(nk)! qq (2k+1)n+(k+1)k. \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 kk-dimensional. I admit, I’d been hoping it would be one of those formulas where substituting q=1q = 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,,k r)(k_1, \ldots, k_r) is (nk 1k 2k r) q\binom n{k_1\,k_2\,\cdots\,k_r}_q (with the obvious qq-multinomial notation), so that the question becomes why (k 1,,k r)n(nk 1k 2k r) q=q n(n1) \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 qn_q, so that the number of nilpotents of type (k 1,k 2,,k r)(k_1, k_2, \ldots, k_r) is (nk 1k 2k r) q i=1 r(k i) q\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=aut nn!_q = \operatorname{aut}_n, we can see n! q=n q(n1)! qn!_q = n_q(n - 1)!_q as the statement that choosing a direct-sum decomposition V=𝔽 qeVV = \mathbb{F}_q e \oplus V' identifies the subgroup A e={gA:ge=e}A_e = \{g \in A : g e = e\} of A=Aut(V)A = \operatorname{Aut}(V) with the direct product of A=Aut(V)A' = \operatorname{Aut}(V') and (V)*=Hom(V,𝔽 q)(V')* = \operatorname{Hom}(V', \mathbb{F}_q) by letting (g,λ)(g', \lambda) correspond to vgv+λ(v)ev' \mapsto g'v' + \lambda(v')e; so, since A/A eA/A_e is identified with V{0}V \setminus \{0\} by sending gg to geg e, we have that aut n=|A|=|A e||A/A e|=|A||W||V{0}|=aut n1q n1(q n1) \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 WW' in place of the dual of VV' 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 kk 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 gg. At each vertex ii we have a vector space V iV_i together with an automorphism g ig_i, so a k[t,t 1]k[t,t^{-1}]-module. A configuration of matrices is a fixed point for gg precisely when the matrix for each arrow is a homomorphism of k[t,t 1]k[t,t^{-1}]-modules. This number is now just a power of qq, the size of the finite field, depending on the conjugacy classes of the elements g ig_i, or maybe better, on the isomorphism classes of the k[t,t 1]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]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]k[t] other that tt 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]k[t]-modules says each factor is some generating function PP (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 dd) of the generating function PP to the power of the number of simples of dimension dd, and with each variable in PP raised to the power of dd.

Amazingly, this implies that the number of isomorphism classes of representations of a given dimension vector is polynomial in the cardinality qq 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 nn, let N λGL n(q)N_\lambda\in\mathrm{GL}_n(q) be a nilpotent endomorphism with this Jordan type, and set z λ(q)z_\lambda(q) to be the size of the centraliser of N λN_\lambda in GL n(q)\mathrm{GL}_n(q). (It is fairly straightforward to get a closed form for z λ(q)z_\lambda(q).)

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

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

and from the representation theory side we obtain the factorisation

P= i0(1q iX). 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?)

i0(1q iX)= i0q n(n1)X nn! q \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

λnn! qz λ(q)=q n(n1), \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 qn_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 n1q^{n-1} hyperplanes in nn-space not containing a given point, though. In dimension two this is easy, since there are q+1q+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 n1)/(q1)(q^n - 1)/(q - 1) hyperplanes (parameterised by non-0 functionals on VV, up to scalar multiples), and (q n11)/(q1)(q^{n - 1} - 1)/(q - 1) of them contain your point (parameterised by non-0 functionals on the quotient of VV 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 n1q^{n-1} hyperplanes in nn-space not containing a given [nonzero] point

Hi Andrew, thanks for your comments.

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

To prove that, take any nontrivial coset HH' of the given hyperplane HH. Every line not contained in HH intersects HH' in exactly one point, which completely determines the line; moreover, every point in HH' lies on exactly one line (which is obviously not contained in HH). Hence the lines not contained in HH are in bijection with the points of HH', of which there are q n1q^{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 TT is nilpotent iff every power of TT has trace 00. But what if we take the identity operator on the qq-dimensional vector space over 𝔽 q\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 gg (which are themselves polynomial in the traces of the powers gg, so maybe that’s where those powers cropped up).

(I’m troubled because Cayley–Hamilton seems to imply that the traces tr(g),,tr(g n)\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 nn 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 kp_k be the trace of g kg^k, and let e ke_k be the trace of kg\bigwedge^k g. In characteristic zero, by the Newton identities, (e 1,,e k)(e_1, \ldots, e_k) determine (p 1,,p k)(p_1,\ldots, p_k) and vice versa. In characteristic p, that’s not true, and what Alen should be saying is that gg is nilpotent if and only if the ee’s are 00.

It seems like a natural question, then, is whether the probabilities that e j=0e_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=0e_n=0, where n is the dimension, is the probability that X is not invertible, which is known to be 1 j=1 n(1q j)1-\prod_{j=1}^n (1-q^{-j}), not q 1q^{-1}.

A more reasonable question would be whether, conditioned on e 1=e 2==e k1=0e_1 = e_2 = \cdots = e_{k-1}=0, the probability of e k=0e_k=0 is q 1q^{-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 q2bmod3q \equiv 2 \bmod 3, I compute that the probability that e 1=e 2=0e_1=e_2=0, in other words, the probability of a characteristic polynomial of the form x 3ax^3-a, is q 4q 3+2q1q 6\frac{q^4-q^3+2q-1}{q^6}, not q 2q^{-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 qq-formalism used in the post: the definitions of n qn_q, n! qn!_q, (nk) 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 “qq-calculus” and “qq-algebra”, all involving a formal deformation parameter qq. 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 qq-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, (0 1 1 0)\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

Post a New Comment