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

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.

• Consider the Jordan form as a starting point. Since nilpotent matrices will have all $0$ on diagonal, just count how many (combinations of) $1$ you can put on the sub-diagonal above...
– zwim
Commented Feb 18 at 9:55
• @zwim In my demonstration, I considered super-diagonal; anyways that's a non-issue because we can always take the transpose and have it in sub-diagonal. There are $n-1$ spots on the sub-diagonal. Which can be filled with 1's in $2^{n-1}$ ways. Commented Feb 18 at 10:05
• It's just me and my math's english, I said sub but I wasn't thinking lower or upper, just "not the main one". Now see Gauss answer, there are not necessarily $2^{n-1}$ ways, it is a bit more subtle, because you have to decompose in blocks, so it is effectively the number of partitions of $n$ which matters. See for instance math.stackexchange.com/questions/1645809/…
– zwim
Commented Feb 18 at 10:09
• Actually, @zwim, I think your suggestion does yield $2^{n-1}$ total classes - it just doesn’t break them down into how many per block, as OP did in his post. This, my answer does (if it’s correct), but at least for $n=2, 3, 4$, it also gives $2^{n-1}$ total Commented Feb 18 at 10:12
• @Nothingspecial, to be fair, I was going to ask you, because I was pretty sure the order didn’t matter for similarity. In that case, the answer should be $p(n, n_1)$ for each $n_1$ you want Commented Feb 18 at 11:13

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)$$

• Now I understand your answer... For $n=4$, up to similarity, the partitions are $4$, $3+1$, $2+2$, $2+1+1$ which correspond to nilpotence of order $4$, $3$, $2$ and $2$ respectively. And there's the null matrix (order $1$) too which can be accounted for by the partition $1+1+1+1$. At least I got a general way to write them all down without missing them, nice! Commented Feb 18 at 12:31
• And that does make sense, for $n=3$, the good partitions were $3$, $2+1$ and $1+1+1$ which we have orders $3$, $2$ and $1$ respectively. My bad, I was really confused, I considered $1+2$ as well separately (which just gives a rearrangement of the blocks, nothing new). I should have read your second paragraph more carefully :) Commented Feb 18 at 12:39
• @Nothingspecial Don’t worry! In fact, I should edit my answer, since it should be just $p(n, n_1)$ Commented Feb 18 at 13:06

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}$$

• Did you mean $T(5, 2)=2$ instead of $3$ in the table? I see only two partitions: $2+1+1+1$ and $2+2+1$ where $2$ is in the lead. Commented Feb 19 at 8:31
• Yes, thanks. I've fixed the typo. Commented Feb 19 at 8:34
• Your OEIS hyperlinks seem to be the sequence number only... Was that intentional? Commented Feb 19 at 8:38
• No, I'm not sure why that happened to the second link. At any rate it's fixed now. Commented Feb 19 at 8:43
• This answer is a great resource to feed questions like: a. "Why do nilpotent matrices share the same characteristic equation yet they are not all similar?" b. "Show that all $n\times n$ nilpotent matrices with order of nilpotency $n−1$ are similar." c. "Show that all $n\times n$ nilpotent matrices with order of nilpotency $n$ are similar." d. "Can you give example of two matrices which are not similar but have the same characteristic equation?" Commented Feb 20 at 15:20