16
$\begingroup$

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.

Improve this question
$\endgroup$
7
  • 15
    $\begingroup$ OEIS $\endgroup$
    – Wojowu
    May 4, 2019 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, 2019 at 17:42
  • 9
    $\begingroup$ @Dirk That's why it's a comment and not an answer. $\endgroup$
    – Wojowu
    May 4, 2019 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, 2019 at 17:50
  • 6
    $\begingroup$ What about normal matrices over $\mathbb{F}_2$? Is this known? $\endgroup$
    – Richard Stanley
    May 4, 2019 at 23:48

2 Answers 2

Reset to default
6
$\begingroup$

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

Improve this answer
$\endgroup$
4
  • $\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, 2019 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, 2019 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, 2019 at 18:29
  • $\begingroup$ @MartinRubey See my additions. $\endgroup$
    – Brendan McKay
    May 11, 2019 at 3:09
1
$\begingroup$

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

Improve this answer
$\endgroup$
1
  • 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, 2019 at 3:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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