# Counting Boolean Normal Matrices of size $2n \times 2n$

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.

• 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. – Stopple Oct 29 '14 at 22:04
• See OEIS sequence A055547 for the first few entries of the sequence. Why $2n \times 2n$ rather than $n \times n$? – Robert Israel Oct 29 '14 at 22:45
• @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$. – Robert Israel Oct 29 '14 at 22:48
• @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. – Mustafa Said Oct 29 '14 at 23:10
• @RobertIsrael: The problem is unclear; I took 'Boolean' to mean the same as $\mathbb F_2$ and would have said '$0-1$ matrices' otherwise. – 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.