Let $A\in\{0,1\}^{n\times n}$ be a $n\times n $ matrix with entries in the discrete set $\{0,1\}$.

My question: What is the number of matrices in $\{0,1\}^{n\times n}$ that are normal, that is, that satisfy $AA^\top-A^\top A=0$?

If we restrict the attention to the subclass of symmetric matrices, my question becomes quite trivial. However, the extension to the whole class of normal matrices seems quite involved. In particular, I would like to know if this problem has already been studied in the literature.

EDIT. OEIS has a page dedicated to this problem, as pointed out by @Wojowu in a comment. However, only a (trivial) lower bound (in terms of the number of symmetric matrices) is listed.

  • 15
    $\begingroup$ OEIS $\endgroup$ – Wojowu May 4 '19 at 17:09
  • 2
    $\begingroup$ @Wojowu Posting just this link is not very informative. Well, there is an entry in OEIS about these numbers, but is there any research about it? (Answer: The OEIS page does not give any links to literature (except general references), so it's not clear.) $\endgroup$ – Dirk May 4 '19 at 17:42
  • 9
    $\begingroup$ @Dirk That's why it's a comment and not an answer. $\endgroup$ – Wojowu May 4 '19 at 17:48
  • 4
    $\begingroup$ Sure, and a good one. Just saying that adding "There is an entry in..." would have been an even better comment. $\endgroup$ – Dirk May 4 '19 at 17:50
  • 6
    $\begingroup$ What about normal matrices over $\mathbb{F}_2$? Is this known? $\endgroup$ – Richard Stanley May 4 '19 at 23:48

For orders 1 to 9:

2, 8, 68, 1124, 36112, 2263268, 281249824, 70329901860, 35546752694048.

I computed these numbers by finding representatives of the isomorphism classes of normal digraphs plus the size of each isomorphism class.

I don't know of any enumeration results for general order, even asymptotics.

Richard Stanley asked about normal matrices over $\mathbb{F}_2$ and Martin Rubey gave the first four values in the comments below. The same method works there but is more expensive because the conditions are weaker. Here are the first eight values:

2, 8, 80, 1472, 56192, 3934208, 557649920, 154665746432

  • $\begingroup$ If I'm not mistaken, the first few values for matrices over $\mathbb F_2$ are $2,8,80,1472$. $\endgroup$ – Martin Rubey May 10 '19 at 6:26
  • $\begingroup$ @MartinRubey Interesting. I'm thinking that my computation method (using isomorph-free generation of digraphs) might be able to work for that case too, though probably not as far. Are there operations other than $A\mapsto P^TAP$ for permutation matrix $P$ that preserve normality? $\endgroup$ – Brendan McKay May 10 '19 at 16:18
  • $\begingroup$ For $\mathbb F_2$, the inverse (if it exists) also preserves normality, and is not necessarily conjugation by a permutation matrix. $\endgroup$ – Martin Rubey May 10 '19 at 18:29
  • $\begingroup$ @MartinRubey See my additions. $\endgroup$ – Brendan McKay May 11 '19 at 3:09

I believe this is still open. See here - https://arxiv.org/abs/1711.02842

  • 2
    $\begingroup$ Very interesting paper. But how does one go from the $\pm 1$ case to the 0-1 case? $\endgroup$ – Brendan McKay May 17 '19 at 3:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.