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$
$\endgroup$
6
asked Oct 29, 2014 at 21:46
-
$\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$– StoppleCommented Oct 29, 2014 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 IsraelCommented Oct 29, 2014 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 IsraelCommented Oct 29, 2014 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 SaidCommented Oct 29, 2014 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$– StoppleCommented Oct 30, 2014 at 2:36
|
Show 1 more comment
1 Answer
$\begingroup$
$\endgroup$
0
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.
answered Oct 29, 2014 at 21:56