|
%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
|
