cp's OEIS Frontend

This is a front-end for the Online Encyclopedia of Integer Sequences, made by Christian Perfect. The idea is to provide OEIS entries in non-ancient HTML, and then to think about how they're presented visually. The source code is on GitHub.

Showing 1-4 of 4 results.

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

Original entry on oeis.org

2, 8, 68, 1124, 36112, 2263268, 281249824, 70329901860, 35546752694048
Offset: 1

Views

Author

Eric W. Weisstein

Keywords

Comments

A complex matrix M is normal if M^H M = M M^H, where H is conjugate transpose.
Let M be an n X n complex matrix with eigenvalues l_1, ..., l_n. The following are equivalent:
(a) M is normal;
(b) There is a unitary matrix U such that U^H M U is diagonal;
(c) Sum_{i,j = 1..n} |M_{i,j}|^2 = |l_1|^2 + ... + |l_n|^2; and
(d) M has an orthonormal set of n eigenvectors.
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

References

  • G. H. Golub and C. F. van Loan, Matrix Computations, Johns Hopkins, 1989, p. 336.
  • R. A. Horn and C. R. Johnson, Matrix Analysis, Cambridge, 1988, Section 2.5.
  • W. H. Press et al., Numerical Recipes, Cambridge, 1986; Chapter 11.

Links

Crossrefs

Cf. A006125, A055548, A055549.

Programs

  • Mathematica
    Options[NormalMatrixQ]={ ZeroTest->(#===0&) };
Matrices[n_, l_List:{0, 1}] := Partition[ #, n]&/@Flatten[Outer[List, Sequence@@Table[l, {n^2}]], n^2-1]
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} ]
Table[Count[Matrices[n, {0, 1}], _?NormalMatrixQ], {n, 4}]
  • 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

Formula

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

Extensions

Entry revised by N. J. A. Sloane, Jan 15 2004
a(5) from R. J. Mathar, Mar 15 2006
a(6) from R. J. Mathar, Mar 22 2006
Statement (c) corrected. - Max Alekseyev, Oct 18 2008
a(7) from Georg Muntingh, Feb 03 2014
a(8) and a(9) from Brendan McKay, May 09 2019

A308161 Number of isomorphism classes of Eulerian oriented graphs with n vertices.

Original entry on oeis.org

1, 1, 1, 2, 3, 7, 24, 200, 5479, 439517, 91097868, 48916220147, 68628518786683, 254305521019154638, 2512451288680194070842, 66741359152815902974086530, 4802230893555589082929258033462, 942013815025325986980154281918094498, 506666364226468633163453153303288094604018
Offset: 0

Views

Author

Brendan McKay, May 15 2019

Keywords

Comments

Loops and 2-cycles are not permitted. Eulerian means that each vertex has equal in-degree and out-degree.

Examples

			For n=4, the a(4)=3 solutions are an empty graph, a directed 3-cycle plus an isolated vertex, and a directed 4-cycle.

Crossrefs

A058338 is the same allowing 2-cycles.
A308111 is the same allowing both loops and 2-cycles.
Cf. A007081 (labeled), A308239 (connected).

Extensions

Terms a(12) and beyond from Andrew Howroyd, Apr 10 2020

A358177 Number of Eulerian orientations of a (labeled) 2n-dimensional hypercube graph, Q_2n. Q_2n is also the n-dimensional torus grid graph (C_4)^n.

Original entry on oeis.org

1, 2, 2970, 351135773356461511142023680
Offset: 0

Views

Author

Peter Munn and Zachary DeStefano, Nov 02 2022

Keywords

Comments

An Eulerian orientation of a graph is an orientation of the edges such that every vertex has in-degree equal to out-degree. (C_4)^n denotes the Cartesian product of n cycle graphs on 4 nodes.

Examples

			For n = 1, dimension 2n = 2, there are two Eulerian orientations (the cyclic ones). So a(1) = 2.

Links

Crossrefs

Cf. A007081, A054759, A298119, A307334, A334553.

Formula

a(0) = A007081(2^0) = 1.
a(1) = A334553(1) = 2.
a(2) = A054759(4) = 2970.
Schrijver (1983) provides general bounds on unknown terms of the form (2^(-k) * binomial(2k,k))^(2^(2k)) <= a(k) <= sqrt(binomial(2k,k)^(2^(2k))).
From this we have the specific bounds 2.9*10^25 <= a(3) <= 4.3*10^41 and 1.2*10^164 <= a(4) <= 1.5*10^236.

Extensions

a(3) added by Brendan McKay, Nov 04 2022

A382212 Number of labeled Eulerian oriented graphs with n nodes without isolated vertices.

Original entry on oeis.org

0, 0, 2, 6, 168, 6700, 726360, 202827786
Offset: 1

Views

Author

Bert Dobbelaere, Mar 18 2025

Keywords

Comments

This sequence is similar to A007081 but imposes the restriction that the graphs contain no isolated vertices.
Each graph can be considered to represent a generalized rock-paper-scissors game for which a uniformly random strategy is optimal and no draw can be forced.

Examples

			For n=3, the only solutions are given by the directed cycles (1,2,3) and (1,3,2). Similarly, also n=4 only has directed cycles as solutions.
An example of a solution for n=5 is
  1 -> {5}
  2 -> {5}
  3 -> {4}
  4 -> {1,2}
  5 -> {3,4}
Disconnected solutions exist only for n >= 6.

Links

Crossrefs

Cf. A007081.
Showing 1-4 of 4 results.

Started in 1964 by Neil J. A. Sloane | Maintained by The OEIS Foundation Inc.

Content is available under The OEIS End-User License Agreement.