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.

$\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$ May 4, 2019 at 23:48

2 Answers 2

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

$\endgroup$
4
  • $\begingroup$ If I'm not mistaken, the first few values for matrices over $\mathbb F_2$ are $2,8,80,1472$. $\endgroup$ 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$ 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$ May 10, 2019 at 18:29
  • $\begingroup$ @MartinRubey See my additions. $\endgroup$ May 11, 2019 at 3:09
1
$\begingroup$

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

$\endgroup$
1
  • 2
    $\begingroup$ Very interesting paper. But how does one go from the $\pm 1$ case to the 0-1 case? $\endgroup$ May 17, 2019 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.