Linear Algebra – Counting Nilpotent Matrices in M_n(?) Up to Similarity

combinatoricslinear algebramatrices

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.

Best Answer

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

Related Question