Saturday, March 16, 2024

Combinatorics of the nilpotent cone

\global\def\Card{\operatorname{Card}}\global\def\GL{\mathrm{GL}}\global\def\im{\operatorname{im}}\gdef\KVar{\mathrm{KVar}}

Let nn be an integer and FF be a field. Nilpotent matrices NMn(F)N\in \mathrm M_n(F) are those matrices for which there exists an integer pp with Np=0N^p=0. Their characteristic polynomial is χN(T)=Tn\chi_N(T)=T^n, and they satisfy Nn=0N^n=0, which shows that the set Nn\mathscr N_n of nilpotent matrices is an algebraic variety. The equation Nn=0N^n=0 is homogeneous of degree nn, so that Nn\mathscr N_n is a cone.

The classification of nilpotent matrices is an intermediate step in the theory of Jordan decomposition: In an adequate basis, a nilpotent matrix can be written as a diagonal block matrix of “basic” nilpotent matrices, p×pp \times p matrices of the form  (00001001000010) \begin{pmatrix} 0 & 0 & \dots & 0 & 0 \\ 1 & 0 & & & \vdots \\ 0 & 1 & \ddots & & 0 \\ \vdots & \ddots & \ddots & \ddots & 0 \\ 0 & & 0 & 1 & 0\end{pmatrix} whose minimal polynomial is TpT^p. The sum of the sizes of these blocks is nn and in this way, it is associated with any n×nn\times n nilpotent matrix a partition π\pi of~nn. It is known that two nilpotent matrices are conjugate if and only if they are associated with the same partition. For any partition π\pi of~nn, let us denote by JπJ_\pi the corresponding matrix whose sizes of blocks are arranged in increasing order, and Nπ\mathscr N_\pi the set of nilpotent matrices that are associated with the partition π\pi.

The theorem of Fine and Herstein (1958)

Having to teach “agrégation” classes made me learn about a classic combinatorial result: counting the number of nilpotent matrices when FF is a finite field.

Theorem (Fine, Herstein, 1958). — Let FF be a finite field with qq elements. The cardinality of Nn(F)\mathscr N_n(F) is qn2nq^{n^2-n}. Equivalently, the probability that an n×nn\times n matrix with coefficients in FF be nilpotent is qnq^{-n}.

The initial proof of this results relies on the action of GLn(F)\GL_n(F) on Nn(F)\mathscr N_n(F): we recalled that the orbits correspond with the partitions of nn, hence a decomposition  Card(Nn(F))=πCard(Nπ(F)). \Card(\mathscr N_n(F)) = \sum_{\pi} \Card(\mathscr N_\pi(F)). We know that Nπ(F)\mathscr N_\pi(F) is the orbit of the matrix JπJ_\pi under the action of GLn(F)\GL_n(F). By the classic orbit-stabilizer formula, one thus has  Card(Nπ(F))=Card(GLn(F))Card(Cπ(F)), \Card(\mathscr N_\pi(F)) = \frac{\Card(\GL_n(F))}{\Card(C_\pi(F))}, where Cπ(F)C_\pi(F) is the set of matrices AGLn(F)A\in\GL_n(F) such that AJπ=JπAAJ_\pi=J_\pi A. The precise description of Cπ(F)C_\pi(F) is delicate but their arguments go as follow.

They first replace the group Cπ(F)C_\pi(F) by the algebra Aπ(F)A_\pi(F) of all matrices AMn(F)A\in\mathrm M_n(F) such that AJπ=JπAAJ_\pi=J_\pi A. For any integer, let mim_i be the multiplicity of an integer ii in the partition π\pi, so that n=imin=\sum i m_i. The block decomposition of JπJ_\pi corresponds with a decomposition of FnF^n as a direct sum of invariant subspaces ViV_i, where ViV_i has dimension imii m_i. In fact, V1=ker(Jπ)V_1=\ker(J_\pi), V1V2=ker(Jπ2)V_1\oplus V_2=\ker(J_\pi^2), etc. This shows that Aπ(F)A_\pi(F) is an algebra of block-triangular matrices. Moreover, the possible diagonal blocks can be shown to be isomorphic to Mmi(F)\mathrm M_{m_i}(F). In other words, we have a surjective morphism of algebras  Aπ(F)iMmi(F), A_\pi(F) \to \prod_i \mathrm M_{m_i}(F), whose kernel consists of nilpotent matrices. In particular, the proportion of invertible elements in Aπ(F)A_\pi(F) is equal to the proportion of invertible elements in the product iMmi(F)\prod_i \mathrm M_{m_i}(F).

Ultimately, Fine and Herstein obtain an explicit sum over the set of partitions of nn which they prove equals qn2nq^{n^2-n}, after an additional combinatorial argument.

Soon after, the theorem of Fine and Herstein was given easier proofs, starting from Gerstenhaber (1961) to Kaplansky (1990) and Leinster (2021).

A proof

The following proof is borrowed from Caldero and Peronnier (2022), Carnet de voyage en Algébrie. It can be seen as a simplification of the proofs of Gerstenhaber (1961) and Leinster (2021).

Let us start with the Fitting decomposition of an endomorphism uNn(F)u\in \mathrm N_n(F): the least integer pp such that ker(up)=ker(up+1)\ker(u^p)=\ker(u^{p+1}) coincides with the least integer pp such that im(up)=im(up+1)\im(u^p)=\im(u^{p+1}), and one has Fn=ker(up)im(up)F^n=\ker(u^p)\oplus \im(u^p). The subspaces N(u)=ker(up)N(u)=\ker(u^p) and I(u)=im(up)I(u)=\im(u^p) are invariant under uu, and uu acts nilpotently on ker(up)\ker(u^p) and bijectively on im(up)\im(u^p). In other words, we have associated with uu complementary subspaces N(u)N(u) and I(u)I(u), a nilpotent operator of N(u)N(u) and an invertible operator on I(u)I(u). This map is bijective.

For any integer dd, let νd\nu_d be the cardinality of nilpotent matrices in Md(F)\mathrm M_d(F), and γd\gamma_d be the cardinality of invertible matrices in Md(F)\mathrm M_d(F). Let also Dd\mathscr D_d be the set of all pairs (K,I)(K,I), where KK and II are complementary subspaces of dimensions dd, ndn-d of FnF^n. We thus obtain  n2=(K,I)Ddνdγnd. n^2 = \sum_{(K,I)\in\mathscr D_d} \nu_d \cdot \gamma_{n-d}. We need to compute the cardinality of Dd\mathscr D_d. In fact, given one pair (K,I)Dd(K,I)\in\mathscr D_d, all other are of the form (gK,gI)(g\cdot K,g\cdot I), for some gGLn(F)g\in\GL_n(F): the group GLn(F)\GL_n(F) acts transitively on Dd\mathscr D_d. The stabilizer of (K,I)(K,I) can be identified with GLd(F)×GLnd(F)\GL_d(F)\times \GL_{n-d}(F). Consequently,  Card(Dd)=Card(GLn(F))Card(GLd(F)Card(GLnd(F))=γnγdγnd. \Card(\mathscr D_d) = \frac{\Card(\GL_n(F))}{\Card(\GL_d(F)\Card(\GL_{n-d}(F))} = \frac{\gamma_n}{\gamma_d \gamma_{n-d}}. We thus obtain qn2=d=0nγnγdγndνdγnd=γnd=0nνdγd. q^{n^2} = \sum_{d=0}^n \frac{\gamma_n}{\gamma_d \gamma_{n-d}} \nu_d \gamma_{n-d} = \gamma_n \sum_{d=0}^n \frac{\nu_d}{\gamma_d}. By subtraction, we get  νnγn=qn2γnq(n1)2γn1, \frac{\nu_n}{\gamma_n} = \frac {q^{n^2}}{\gamma_n} - \frac{q^{(n-1)^2}}{\gamma_{n-1}}, or  νn=qn2q(n1)2γnγn1. \nu_n = q^{n^2} - q^{(n-1)^2} \frac{\gamma_n}{\gamma_{n-1}}. It remains to compute γn\gamma_n: since an invertible matrix consists of a nonzero vector, a vector which does not belong to the line generated by the first one, etc., we have  γn=(qn1)(qnq)(qnqn1). \gamma_n = (q^n-1) (q^n-q)\dots (q^n-q^{n-1}). Then,  γn=(qn1)qn1(qn11)(qn1qn2)=(qn1)qn1γn1. \gamma_n = (q^n-1) q^{n-1} (q^{n-1}-1)\dots (q^{n-1}-q^{n-2}) = (q^n-1)q^{n-1} \gamma_{n-1}. We thus obtain  νn=qn2q(n1)2(qn1)qn1=qn2q(n1)2q2n1+q(n1)2qn1=qn2n, \nu_n = q^{n^2} - q^{(n-1)^2} (q^n-1) q^{n-1} = q^{n^2} - q^{(n-1)^2} q^{2n-1} + q^{(n-1)^2} q^{n-1} = q^{n^2-n}, as claimed.

The proof of Leinster (2021)

Leinster defines a bijection from Nn(F)×Fn\mathscr N_n(F)\times F^n to Mn(F)\mathrm M_n(F). The definition is however not very canonical, because he assumes given, for any subspace VV of FnF^n, a basis of VV.

Take a pair (u,x)(u,x), where uNn(F)u\in\mathscr N_n(F) and xFnx\in F^n and consider the subspace Vx=x,u(x),V_x=\langle x,u(x),\dots\rangle, the smallest uu-invariant subspace of FnF^n which contains xx. To describe uu, we observe that we know its restriction to VxV_x, and we need to describe it on the chosen complementary subspace VxV'_x.

To that aim, we have to give ourselves an endomorphism uxu'_x of VxV'_x and a linear map ϕx ⁣:VxVx\phi_x\colon V'_x\to V_x. Since we want uu to be nilpotent, it is necessary and sufficient to take uxu'_x nilpotent.

Instead of considering ϕx ⁣:VxVx\phi_x\colon V'_x\to V_x, we can consider the map yy+ϕx(y)y\mapsto y+\phi_x(y). Its image is a complement WxW_x of VxV_x in FnF^n, and any complement can be obtained in this way. The nilpotent endomorphism uxu'_x of VxV'_x transfers to a nilpotent endomorphism wxw_x of WxW_x.

All in all, what the given pair (u,x)(u,x) furnishes is a subspace VxV_x with a basis (x1=x,x2=u(x),)(x_1=x,x_2=u(x),\dots), a complement WxW_x, and a nilpotent endomorphism wxw_x of WxW_x. This is more or less what the Fitting decomposition of an endomorphism gives us! Recall that VxV_x was assumed to have been given a basis (e1,,ep)(e_1,\dots,e_p). There exists a unique automorphism of VxV_x which maps eie_i to ui1(x)u^{i-1}(x) for all ii. In other words, we have a pair of complementary subspaces (Vx,Wx)(V_x,W_x), a linear automorphism of VxV_x, and a nilpotent automorphism of WxW_x. By the Fitting decomposition, these data furnish in a bijective way an endomorphism of FnF^n, and that concludes the proof.

A remark about motivic integration

The framework of motivic integration suggests to upgrade these combinatorial results into equalities valid for all field FF, which hold in the Grothendieck ring of varieties KVarF\KVar_F. As an abelian group, it is generated by symbols [X][X], for all algebraic varieties XX over FF, with relations [X]=[Y]+[XY][X]=[Y]+[X\setminus Y], whenever YY is a closed subvariety of XX. The ring structure is defined so that the formula [X][Y]=[X×Y][X]\cdot[Y]=[X\times Y] for all algebraic varieties XX and YY over FF.

By construction of this ring, equalities [X]=[Y][X]=[Y] in KVarF\KVar_F imply that many invariants of XX and YY coincide. In particular, when FF is a finite field, they will have the same number of points.

The question is thus to compute the class [Nn][\mathscr N_n] of the variety Nn\mathscr N_n, for any field FF. The proofs that I described above can be more or less transferred to this context and imply the following theorem. We denote by LKVarF\mathbf L\in \KVar_F the class of the affine line A1\mathbf A^1.

Theorem. — One has an equality [Nn]Ln=Ln2[\mathscr N_n] \mathbf L^n = \mathbf L^{n^2} in the localization of the Grothendieck ring KVarF\KVar_F by the element (L1)(Ln11)(\mathbf L-1)\dots(\mathbf L^{n-1}-1).

The following question is then natural. (I have not thought about it at all.)

Question. — Does one have [Nn]=Ln2n[\mathscr N_n]=\mathbf L^{n^2-n} in KVarF\KVar_F?