login
Number of normal n X n matrices with entries {0,1}.
4

%I #38 May 12 2019 02:26:50

%S 2,8,68,1124,36112,2263268,281249824,70329901860,35546752694048

%N Number of normal n X n matrices with entries {0,1}.

%C A complex matrix M is normal if M^H M = M M^H, where H is conjugate transpose.

%C Let M be an n X n complex matrix with eigenvalues l_1, ..., l_n. The following are equivalent:

%C (a) M is normal;

%C (b) There is a unitary matrix U such that U^H M U is diagonal;

%C (c) Sum_{i,j = 1..n} |M_{i,j}|^2 = |l_1|^2 + ... + |l_n|^2; and

%C (d) M has an orthonormal set of n eigenvectors.

%C If a normal matrix M is split into the symmetric and antisymmetric matrices M=A+S with S=(M+M^H)/2 and A=(M-M^H)/2, M^H the transpose of M, A must be a generalized Tournament matrix. (For Tournament matrices each row and each column sums to zero.) The "generalization" is that zeros (indicating a tie between the players) may occur outside the main matrix diagonal. A is therefore a member of the set of the antisymmetric ternary matrices (elements -1,0,+1) counted in A007081(n), because there is a 1-to-1 mapping of the Tournament matrix onto the labeled edge-oriented Eulerian graphs. - _R. J. Mathar_, Mar 22 2006

%D G. H. Golub and C. F. van Loan, Matrix Computations, Johns Hopkins, 1989, p. 336.

%D R. A. Horn and C. R. Johnson, Matrix Analysis, Cambridge, 1988, Section 2.5.

%D W. H. Press et al., Numerical Recipes, Cambridge, 1986; Chapter 11.

%H R. J. Mathar, <a href="/A055547/a055547.c.txt">C program</a>

%H Georg Muntingh, <a href="/A055547/a055547.txt">Sage code for recursively computing higher entries</a>

%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/NormalMatrix.html">Normal Matrix.</a>

%H <a href="/index/Mat#binmat">Index entries for sequences related to binary matrices</a>

%F a(n) >= 2^[n*(n+1)/2] = A006125(n+1) because all symmetric binary matrices (which have n*(n+1)/2 independent elements) are normal. - _R. J. Mathar_, Mar 22 2006

%t Options[NormalMatrixQ]={ ZeroTest->(#===0&) };

%t Matrices[n_, l_List:{0, 1}] := Partition[ #, n]&/@Flatten[Outer[List, Sequence@@Table[l, {n^2}]], n^2-1]

%t NormalMatrixQ[a_List?MatrixQ, opts___] := Module[ { b=Conjugate@Transpose@a, zerotest=ZeroTest/.{opts}/.Options[NormalMatrixQ] }, (zerotest/@And@@Flatten[a.b-b.a])||Dimensions[a]=={1, 1} ]

%t Table[Count[Matrices[n, {0, 1}], _?NormalMatrixQ], {n, 4}]

%o (PARI) NormaQ(a,n) = { local(aT) ; aT=mattranspose(a) ; if( a*aT == aT*a,1,0) ; } combMat(no,n) = { local(a,noshif) ; a = matrix(n,n) ; noshif=no ; for(co=1,n, for(ro=1,n, if( (noshif %2)== 1,a[ro,co] = 1, a[ro,co] = 0) ; noshif = floor(noshif/2) ; ) ) ; return(a) ; } { for (n = 1, 5, count = 0; a = matrix(n,n) ; for( no=0,2^(n^2)-1, a = combMat(no,n) ; count += NormaQ(a,n) ; ) ; print(count) ; ) } \\ _R. J. Mathar_, Mar 15 2006

%Y Cf. A006125, A055548, A055549.

%K nonn,more,hard

%O 1,1

%A _Eric W. Weisstein_

%E Entry revised by _N. J. A. Sloane_, Jan 15 2004

%E a(5) from _R. J. Mathar_, Mar 15 2006

%E a(6) from _R. J. Mathar_, Mar 22 2006

%E Statement (c) corrected. - _Max Alekseyev_, Oct 18 2008

%E a(7) from _Georg Muntingh_, Feb 03 2014

%E a(8) and a(9) from _Brendan McKay_, May 09 2019