9
$\begingroup$

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.

$\endgroup$
6
  • $\begingroup$ 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... $\endgroup$
    – zwim
    Feb 18 at 9:55
  • $\begingroup$ @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. $\endgroup$ Feb 18 at 10:05
  • 1
    $\begingroup$ 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/… $\endgroup$
    – zwim
    Feb 18 at 10:09
  • $\begingroup$ 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 $\endgroup$
    – Gauss
    Feb 18 at 10:12
  • 1
    $\begingroup$ @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 $\endgroup$
    – Gauss
    Feb 18 at 11:13

2 Answers 2

3
$\begingroup$

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

$\endgroup$
3
  • $\begingroup$ 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! $\endgroup$ Feb 18 at 12:31
  • $\begingroup$ 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 :) $\endgroup$ Feb 18 at 12:39
  • 1
    $\begingroup$ @Nothingspecial Don’t worry! In fact, I should edit my answer, since it should be just $p(n, n_1)$ $\endgroup$
    – Gauss
    Feb 18 at 13:06
1
$\begingroup$

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

$\endgroup$
5
  • 1
    $\begingroup$ 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. $\endgroup$ Feb 19 at 8:31
  • 1
    $\begingroup$ Yes, thanks. I've fixed the typo. $\endgroup$ Feb 19 at 8:34
  • 1
    $\begingroup$ Your OEIS hyperlinks seem to be the sequence number only... Was that intentional? $\endgroup$ Feb 19 at 8:38
  • 1
    $\begingroup$ No, I'm not sure why that happened to the second link. At any rate it's fixed now. $\endgroup$ Feb 19 at 8:43
  • $\begingroup$ 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?" $\endgroup$ Feb 20 at 15:20

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .