A263626 Number of inequivalent self-complementary Seidel matrices of order n.

1, 1, 0, 1, 1, 4, 0, 19, 10, 360, 0, 25112, 720, 6975976, 0, 7030565576, 703760, 25473667704064, 0, 333377175390634880, 9168331776, 15881995583375102901824, 0, 2775171714758797872451279104, 1601371799340544, 1790676527377592615808645709379328, 0, 4291738728096066980970104665682237420544, 3837878966366932639744, 38401679870039848205115101680007123726281532416, 0

Offset: 1

Author

N. J. A. Sloane, Oct 24 2015

Keywords

• nonn

Comments

From Petros Hadjicostas, Mar 01 2021: (Start)

On p. 9 of their arxiv paper, Greaves et al. (2014-2015) state that "The number of self-complementary Seidel matrices is known explicitly" and refer to Sozański (1980). The authors apparently refer to formula (20) in Theorem 2 (p. 139) in Sozański (1980). (See also p. 218 in Greaves et al. (2016).)

The so-called "Seidel matrix" of a graph G was apparently introduced by the Dutch mathematician Johan Jacob Seidel (1967, 1968, and with van Lint in 1966). They are not related to the so-called Euler-Seidel (or just Seidel) matrices named after Leonhard Euler and Philipp Ludwig von Seidel.

A Seidel matrix S = S(G) of a simple labeled graph G with vertex set V = {v_1, ..., v_n} is an n x n symmetric matrix with rows and columns corresponding to the n vertices such that S(i,j) is defined in the following way: S(i,j) = 0 iff i = j; S(i,j) = -1 iff vertex v_i is connected to vertex v_j (i <> j), and S(i,j) = 1 iff vertex v_i is not connected to vertex v_j (i <> j). Thus, S(G) = J - I - 2*A(G), where J is an n x n matrix of 1's, I is the n x n identity matrix, and A(G) is the adjancecy matrix of the labeled graph G.

Two Seidel matrices S1 and S2 are said to be equivalent if S1 can be obtained from S2 by a sequence of simultaneous row i to j and column i to j permutations or by a simultaneous multiplication of a row i and a column i by -1.

Thus, Seidel matrices S1 and S2 are equivalent iff there is a symmetric signed permutation matrix P such that S1 = P*S2*P^T.

A Seidel matrix S is called "self-complementary" if S is equivalent to -S. Thus, S is self-complementary iff there is a symmetric signed permutation matrix P such that S = -P*S*P^T. The sequence a(n) counts equivalence classes of self-complementary n x n Seidel matrices.

In terms of a labeled graph G with Seidel matrix S and vertex set V, a simultaneous row i to j and column i to j permutation of S corresponds to exchanging labels between vertices v_i and v_j. On the other hand, a simultaneous multiplication of row i and column i by -1 corresponds to what Mallows and Sloane (1975) call "switching at node" v_i: if A(i) is the set of vertices in V to which v_i is connected and B(i) is the set of vertices in V to which v_i is not connected, "switching at node v_i" means switching the sets A(i) and B(i) (the vertices connected with the vertices non-connected to v_i). Of course, either A(i) or B(i) may be empty.

Mallows and Sloane (1975) proved that the number of equivalence classes of Seidel matrices of order n is equal to the number of unlabeled even graphs (known colloquially as unlabeled "Euler graphs"). See sequence A002854.

The equivalence class of graphs corresponding to a self-complementary Seidel matrix is closed under complementation.

For simplicity, in the examples below that illustrate equivalence classes Seidel matrices, we only include unlabeled graphs on n = 3 or n = 4 nodes rather than labeled ones. (End)

Examples

			From _Petros Hadjicostas_, Mar 01 2021: (Start)
For n = 3, we have the following A000088(3) = 4 unlabeled graphs on 3 nodes:
(1) o     (2)  o      (3)  o      (4)  o
              / \         /           / \
  o   o      o   o       o   o       o-- o
Graphs (1) and (2) form one equivalence class and graphs (3) and (4) form another equivalence class (under the Seidel-Mallows-Sloane "switching" equivalence relation). The complement of (1) is (4) and the complement of (2) is (3), so there are no self-complementary classes; i.e., a(3) = 0. (Here, the number of equivalence classes is A002854(3) = 2.)
For n = 4, the A000088(4) = 11 unlabeled graphs are listed in Mallows and Sloane (1975). There are A002854(4) = 3 equivalence classes, only one of which is self-complementary:
(1) o  o   (2) o -- o   (3) o--o   (4) o  o   (5) o--o
    |          |            |          | /|       | /|
    o  o       o    o       o--o       o--o       o--o
Thus, a(4) = 1. (End)
		

Links

• G. Greaves, J. H. Koolen, A. Munemasa, and F. Szöllősi, Equiangular lines in Euclidean spaces, arXiv:1403.2155 [math.CO], 2014-2015.
• G. Greaves, J. H. Koolen, A. Munemasa, and F. Szöllősi, Equiangular lines in Euclidean spaces, Journal of Combinatorial Theory, Series A, 138 (2016), 208-235.
• C. L. Mallows and N. J. A. Sloane, Two-graphs, switching classes and Euler graphs are equal in number, SIAM J. Appl. Math., 28 (1975), 876-880. (copy at N. J. A. Sloane's home page)
• Johan Jacob Seidel, Strongly regular graphs on L2-type and of triangular type, Nederl. Akad. Wet., Proc., Ser. A, 70 (1967), 188-196. (Zentralblatt 161 #20802)
• Johan Jacob Seidel, Strongly regular graphs with (-1,1,0) adjacency matrix having eigenvalue 3, Linear Algebra and its Applications, 1(2) (1968), 281-298. (Zentralblatt 159 #25403)
• Tadeusz Sozański, Enumeration of weak isomorphism classes of signed graphs, J. Graph Theory 4 (1980), no. 2, 127-144. (Zentralblatt 434 #05059)
• Jacobus Hendricus van Lint and Johan Jacob Seidel, Equilateral point sets in elliptic geometryNederl. Akad. Wetensch. Proc. Ser. A, 69 (= Indag. Math., 28) (1966), 335-348. (Zentralblatt 138 #41702)
• Wikipedia, Seidel adjacency matrix.

Crossrefs

Cf. A000088, A000171, A002854, A085618 (same ?), A341941.

Programs

PARI

a(n)={local(p=vector(n));
my(S=0, J() = sum(j=0, floor((n-1)/2), p[2*j+1]),
    I1() = sum(i=1, n, p[i]) - if(J() == 0, 0, 1),
    I2() = (sum(i=1, n, sum(j=1, n, p[i]*p[j]*gcd(i,j))) - J())/2,
    M2() = sum(i=1, n, if(1 == (i%2), p[i], 0))*(abs((p[1]-1)*(p[1]-2)) + sum(j=2, n, if(0!=(j%4), p[j], 0))),
    M() = I2() - I1(),
inc()=!forstep(i=n, 1, -1, p[i]n, p[i]=n); next(2))); t==n && S+=if(M2() == 0, 2^M()/prod(i=1, n, i^p[i]*p[i]!), 0)); S} \\ This is a modification of M. F. Hasler's PARI program from A002854. - Petros Hadjicostas, Mar 02 2021

Formula

From Petros Hadjicostas, Mar 01 2021: (Start)

a(n) = 0 for 3 == n mod 4 (see the references).

Conjecture (due to Peter Luschny): a(n) = Sum_{k=0}^{n*(n-1)/2} (-1)^k*A341941(n,k) = [o.g.f. of n-th row of A341941](x=-1).

a(n) = Sum_{p in M2(n)} 2^(I2(p) - I1(p))/f(p), where

p = (p[1], ..., p[n]) is a partition of n written in frequency or multiplicity notation with p[i] >= 0 for i = 1..n and Sum_{i=1..n} i*p[i] = n;

M2(n) is the set of all partitions p of n with either (a) p[i] = 0 for all odd i or (b) p[1] = 1 or 2, and p[i] = 0 for i >= 2 with 0 <> (i mod 4);

f(p) = Product_{i=1..n} p[i]!*i^p[i];

J(p) = Sum_{j=1..floor((n-1)/2)} p[2*j+1];

I1(p) = Sum_{i=1..n} p[i] - if(J(p) == 0, 0, 1); and

I2(p) = (Sum_{1 <= i, j <= n} p[i]*p[j]*gcd(i,j) - J(p))/2.

(This is modification of formula (20) in Theorem 2 (p. 139) in Sozański (1980).)

Note that, if we take sum over all partitions of n, rather than just over M2(n), then we get A002854(n).

If, on the other hand, we consider Sum_{p in M1(n)} 2^I2(p)/f(p), where M1(n) is the set of all partitions p of n with p[1] in {0,1} and p[i] = 0 for i >= 2 with 0 <> (i mod 4), then we get A000171(n).

Finally, if we consider Sum_{p} 2^I2(p)/f(p) over all partitions p of n, then we get A000088(n). (End)

Extensions

Terms a(13) to a(21) copied from Table I (p. 140) in Sozański (1980). - Petros Hadjicostas, Feb 27 2021

Name edited by and terms a(22) to a(31) from Petros Hadjicostas, Mar 01 2021