Fix $n$ a natural number. Consider the set of all $2n \times 2n$ matrices with entries from {0,1}. This is clearly a finite set. I would like to count the number of such normal matrices for fixed $n$, call this number $N(n)$. What are the asymptotics for $N(n)$? It is easy to see that if the matrix is symmetric, then it is normal so we can get a lower bound on $N(n)$. Does anyone have any ideas on an upper bound besides the trivial one.

  • $\begingroup$ You can re-interpret the criteria $AA^t=A^tA$ as $4n^2$ equations in $4n^2$ variables over the field with two elements. Each equation defines a hypersurface; you're interested in the cardinality of the intersection of these hypersurfaces, which is an algebraic variety. Bounds on the number of solutions are of interest to algebraic geometers; you might want to add a tag. $\endgroup$ – Stopple Oct 29 '14 at 22:04
  • 1
    $\begingroup$ See OEIS sequence A055547 for the first few entries of the sequence. Why $2n \times 2n$ rather than $n \times n$? $\endgroup$ – Robert Israel Oct 29 '14 at 22:45
  • 1
    $\begingroup$ @Stopple: As I read the question, we're not doing this over $\mathbb F_2$: the matrix entries happen to be in $\{0,1\}$ but the arithmetic is done in $\mathbb Z$. $\endgroup$ – Robert Israel Oct 29 '14 at 22:48
  • $\begingroup$ @RobertIsrael $2n$ is chosen instead of $n$ because in the problem I am working on, the matrix is actually a block matrix with $4$ $n \times n$ blocks. $\endgroup$ – Mustafa Said Oct 29 '14 at 23:10
  • $\begingroup$ @RobertIsrael: The problem is unclear; I took 'Boolean' to mean the same as $\mathbb F_2$ and would have said '$0-1$ matrices' otherwise. $\endgroup$ – Stopple Oct 30 '14 at 2:36

Since the dimension of the variety of normal matrices is the same as that of the variety of symmetric matrices (for $n\times n$ complex normal matrices, the real dimension of the variety is $n^2+n,$ see this discussion: structure of the variety of normal matrices) I expect that the lower bound whereof you speak is asymptotically sharp.


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.