How many nilpotent matrices are there in $M_n(\mathbb R)$ up to similarity?

Question

I am trying to count all nilpotent matrices in $M_n(\mathbb R)$ up to similarity.

I did the same exercise for idempotent matrices and it was quite simple. I realised that rank of an idempotent matrix is a non-negative integer and two idempotent matrices are similar iff they have the same rank. So I got the answer $n+1$.

However, it doesn't seem to be simple for nilpotent matrices. Things which are clear to me:

1. If two nilpotent matrices are similar, they must have the same order of nilpotence.
2. There is exactly one class of similarity for nilpotent matrices of order $n$.

The question I would like to ask:

How many nilpotent matrices of order $k$ are there up to similarity?

The answer is $1$ if $k=n$.

The answer is $1$ again if $k=1$. (The null matrix is the only matrix which has nilpotence of order $1$ and it is its own similarity class.)

What about other values of $k$?

---

By looking at Jordan normal form, here's what I found about $n=2$ and $n=3$. How to generalize?

For $n=2$, order of nilpotence vs number of matrices up to similarity. $\begin{array}{l|l} k& \text{#}\\ \hline 1&1\\ 2& 1\end{array}\tag*{}$

For $n=3$, $\begin{array}{l|l} k& \text{#}\\ \hline 1&1\\ 2& 1\\ 3&1\end{array}\tag*{}$

The answer is $1$ for $k=2$ because there is only one unique way to create blocks along the diagonal so that one of the blocks is nilpotent of order $2$. The arrangement if $2+1$. $\begin{pmatrix}\color{red}{0}&\color{red}1&0\\ \color{red}0&\color{red}0&0\\0&0&\color{blue}0\end{pmatrix}\tag*{}$

Note that each block should be nilpotent in itself and hence, the choice of zero and non-zero entries.

For $n=4$,

$\quad k=2$: From $2+2$ and $2+1+1$, I get one matrix each. If I consider $3+1$, I would overcount.

$\displaystyle \begin{pmatrix} 0 & 1 & & \\ 0 & 0 & & \\ & & 0 & 1\\ & & 0 & 0 \end{pmatrix} \ \begin{pmatrix} 0 & 1 & & \\ 0 & 0 & & \\ & & 0 & \\ & & & 0 \end{pmatrix}\tag*{}$

$\quad k=3$: From $3+1$, I get one matrix.

$\displaystyle \begin{pmatrix} 0 & 1 & 0 & \\ 0 & 0 & 1 & \\ 0 & 0 & 0 & \\ & & & 0 \end{pmatrix}\tag*{}$

Thus,$\begin{array}{l|l} k& \text{#}\\ \hline 1&1\\ 2& 2\\ 3&1\\ 4 & 1\end{array}\tag*{}$

I am not sure how to generalize. It seems to me that there should be a recursive formula.

Answer 1

This is just a guess, but is seems to fit the general idea of what you have found. Consider the number of partitions $p(n)$. This is the number of distinct possible Jordan decompositions of an $n\times n$ matrix.

Given any specific partition, say $n_1 + \cdots + n_k$, $n_1 \geq \cdots \geq n_k$, the nilpotency index of a matrix with this Jordan decomposition is $n_1$, since matrix multiplication can be done block-wise in the diagonal.

So the number of $n \times n$ matrices with nilpotency class $n_1$, up to equivalency, but allowing for permuted blocks, is the number of partitions whose biggest term is $n_1$ (call this $p(n, n_1)$, say) times the distinct (i.e., factoring multiplicities) permutations of the blocks. If you just want it up to equivalency, the answer is $p(n, n_1)$.

I think the former is very hard to know a general formula for, though, because it depends heavily on the specific partition. However, using a combinatorial argument outlined by @zwim, the total number of those is $2^{n-1}$. For the latter, see the edit.

I’ll be happy to know if there’s some general method which avoids this issue!

EDIT: This link gives a recursive formula for $p(n, n_1)$

Answer 2

A matrix $A$ is nilpotent if and only if $0$ is its only eigenvalue, hence if and only if its Jordan canonical form is a direct sum $\bigoplus J_{k_i}$ of Jordan blocks $$J_{k_i} := J_{k_i}(0) = \pmatrix{0&1\\&0&\smash{\ddots}\\&&\smash{\ddots}&\smash{\ddots}\\&&&0&1\\&&&&0}$$ of size $k_i$ and eigenvalue $0$; if $A$ has size $n \times n$, then the sum of the sizes of the Jordan blocks is $\sum k_i = n$.

On the other hand, two matrices are similar if they have the same Jordan canonical form (allowing permutations of blocks), so the map $J_{k_1} \oplus \cdots \oplus J_{k_r} \leftrightarrow (k_1, \ldots, k_r)$ defines a bijection between the set of similarity classes of $n \times n$ nilpotent matrices (represented by their Jordan canonical form) and the set of (unordered) partitions of $n$. The counts $a(n)$ of the similarity classes thus comprise OEIS A000041. For small $n$, the counts $a(n)$ are as follows. $$ \begin{array}{rcccccccccc} \hline n & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 \\ \hline a(n) & 1 & 2 & 3 & 5 & 7 & 11 & 15 & 22 & 30 & 42 \\ \hline \end{array} $$ There isn't a nice closed form for $a(n)$ as a function of $n$, but there are recursive formulas, including via the celebrated Pentagonal Number Theorem, which gives that

\begin{align*} 0 &= \sum_{{k \in P}, \, {k \leq n}} (-1)^\frac{k + 1}{2} a(n - k) \\ &= a(n) - a(n-1) - a(n-2) + a(n-5) + a(n-7) - a(n-12) + \cdots, \end{align*} where the index $k$ in the summation varies over the generalized pentagonal numbers $\leq n$. For example, the number of similarity classes of $5 \times 5$ nilpotent matrices is $$a(5) = a(4) + a(3) - a(0) = 5 + 3 - 1 = 7 .$$

The generating function for $a(n)$ has a natural, compact form: $$\sum_{n \geq 0} a(n) x^n = \prod_{k > 0} \frac{1}{1 - x^k} .$$

The same argument shows that the number $T(n, k)$ of nilpotent matrices of order (exactly) $k$ is exactly the number of (unordered) partitions of $n$ whose greatest part is $k$, and those counts comprise OEIS A008284. Again there is not a nice closed form for $T(n, k)$, but there are various recursive formulas.

The $7$ similarity classes of $5 \times 5$ nilpotent matrices, arranged by order $k$, are represented below by their Jordan canonical forms. $$ \begin{array}{rrrrl} \hline k & T(5, k) & \textrm{partition} & & \!\!\!\!\!\!\textrm{matrix} \\ \hline 1 & 1 & 11111 & 5 J_1 \!\!\!\!&= \pmatrix{ \cdot \\ & \cdot \\ && \cdot \\ &&& \cdot \\ &&&& \cdot} \\ \hline 2 & 2 & 2111 & J_2 \oplus 3 J_1 \!\!\!\!&= \pmatrix{ \cdot & 1 \\ \cdot & \cdot \\ && \cdot \\ &&& \cdot \\ &&&& \cdot} \\ & & 221 & 2 J_2 \oplus J_1 \!\!\!\!&= \pmatrix{ \cdot & 1\\ \cdot & \cdot \\ && \cdot & 1\\ && \cdot & \cdot \\ &&&& \cdot} \\ \hline 3 & 2 & 311 & J_3 \oplus 2 J_1 \!\!\!\!&= \pmatrix{ \cdot & 1 & \cdot \\ \cdot & \cdot & 1 \\ \cdot & \cdot & \cdot \\ &&& \cdot \\ &&&& \cdot}\\ & & 32 & J_3 \oplus J_2 \!\!\!\!&= \pmatrix{ \cdot & 1 & \cdot \\ \cdot & \cdot & 1 \\ \cdot & \cdot & \cdot \\ &&& \cdot & 1 \\ &&& \cdot & \cdot} \\ \hline 4 & 1 & 41 & J_4 \oplus J_1 \!\!\!\!&= \pmatrix{ \cdot & 1 & \cdot & \cdot \\ \cdot & \cdot & 1 & \cdot \\ \cdot & \cdot & \cdot & 1 \\ \cdot & \cdot & \cdot & \cdot \\ &&&& \cdot}\\ \hline 5 & 1 & 5 & J_5 \!\!\!\!&= \pmatrix{ \cdot & 1 & \cdot & \cdot & \cdot \\ \cdot & \cdot & 1 & \cdot & \cdot \\ \cdot & \cdot & \cdot & 1 & \cdot \\ \cdot & \cdot & \cdot & \cdot & 1 \\ \cdot & \cdot & \cdot & \cdot & \cdot} \\ \hline \end{array}$$