## Complex Two-Graphs via Equiangular Tight Frames

Thomas R. Hoffman a , James P. Solazzo

a

a Coastal Carolina University, Conway, SC 29528

## Abstract

In 'A survey of two-graphs' [24], J.J. Seidel lays out the connections between simple graphs, two-graphs, equiangular lines and strongly regular graph. It is well known that there is a one-to-one correspondence between regular two-graphs and equiangular tight frames. This article gives a generalization of two-graphs for which these connections can be mimicked using roots of unity beyond ± 1 .

Keywords: equiangular tight frame, two-graph, roots of unity, Seidel adjacency matrix,

2010 MSC:

05C50, 05E30

## 1. Introduction

Two-graphs play a wide and varied role in several areas of mathematics. To quote J.J. Seidel from his well-known paper, A survey of two-graphs [24], 'Twographs provide a good example of combinatorial geometry and group theory.' The study of two-graphs is equivalent to the study of sets of equiangular lines in Euclidean geometry, sets of equidistant point sets in elliptic geometry, binary maps of triples with vanishing co-boundary, and double coverings of complete graphs.

Applications include but are not limited to network theory [1] and coding theory [10]. At the beginning of the 21 st century, R. Holmes and V. Paulsen in [17] and T. Strohmer and R. Heath in [28], discovered the work done by J.J. Seidel and others regarding two-graphs had found another application. In particular, the existence and construction of real equiangular tight frames (ETFs) was expedited by their discovery of the fact that there is a in one-to-one correspondence between real ETFs and regular two-graphs . This one-to-one correspondence is a wellknown fact in the frame theory community [1, 2, 3, 4, 7, 15, 8, 27, 28, 29, 4, 19, 30]. Indeed extending the already lengthy list of applications of two-graphs to now include such areas as signal processing and communication theory.

In this article, we present an alternate yet equivalent definition of a two-graph. This new definition allows us to generalize the definition of a two-graph in a natural and intuitive way to what we refer to as a complex two-graph . Associated to each two-graph is a set of Seidel adjacency matrices , that is, a set of symmetric matrices whose diagonal entries are all zero and off diagonal entries are ± 1 . Similarly, associated to each complex two-graph is a set of complex Seidel adjacency matrices ,that is, a set of self-adjoint matrices whose diagonal entries are all zero and off diagonal entries are m th roots of unity for a fixed m in N . The fact that the off diagonal entries of a 'real' Seidel adjacency matrix are square roots of unity is a trivial yet surprisingly useful observation. This observation coupled with our equivalent definition of a two-graph is the key to this extension. Furthermore, many of the results regarding complex two-graphs mirror the analogous results pertaining to two-graphs .

For example, it is well-known that for a set of equiangular lines in R k to meet the absolute or relative bounds, the associated two-graph must be regular , i.e., the associated Seidel adjacency matrix has precisely two distinct eigenvalues. These results extend naturally to C k . That is, regular complex two-graphs produce sets of equiangular lines that meet either the absolute or relative bounds. Consequently, associated with each regular complex two-graph is a complex ETF.

This article is organized as follows. In Section 2, the motivation underlying the definition of a two-graph is presented. Section 3 discusses the relationship between two-graphs, equiangular lines, and ETFs, comparing the real case to the complex case. Section 4 presents the reader with a careful introduction to complex two-graphs via the cube roots of unity. Section 5 extends the definitions and results from Section 4 to include the m th roots of unity for a fixed m in N .

For the reader familiar with two-graphs this paper is self-contained. For the reader not as familiar with two-graphs many of the definitions and results in this article are accompanied by examples intended to motivate said definitions or results.

## 2. Motivating the Definition of a Two-Graph

In this section we summarize the first four sections of J.J. Seidel's, A Survey of Two-Graphs, [24]. Lemma 2.7 lays the foundation for understanding the generalization of a two-graph presented in Section 4.

A graph is a pair (Ω , E ) where Ω is a set of vertices , and E is a set of unordered pairs of vertices, whose elements are called edges . For the purposes of this paper,

graphs do not have loops or multiple edges. A complete graph on n vertices is a graph with | Ω = | n and E contains every possible unordered pair of vertices.

Denote by A X and V X the adjacency matrix, and the set of vertices of the graph X , respectively. We also use I n for the n × n identity matrix and J n for the n × n matrix of all ones.

Definition 2.1. Given a graph X on n vertices, the Seidel adjacency matrix of X is defined to be the n × n matrix S X := ( s ij ) where s i,j is defined to be -1 when i and j are adjacent vertices, +1 when i and j are not adjacent, and 0 when i = j .

The Seidel adjacency matrix of X is related to the usual adjacency matrix A X by

$$S _ { X } = J _ { n } - I _ { n } - 2 A _ {$$

Definition 2.2. Let X be a graph and τ ⊆ V X . Now define the graph X τ to be the graph arising from X by changing all of the edges between τ and V X -τ to nonedges and all the nonedges between τ and V X -τ to edges. This operation is called switching on the subset τ , see [10].

The operation of switching is an equivalence relation on the collection of graphs on n vertices. This can be seen by observing if τ ⊆ V X , then switching on τ is equivalent to conjugating S X by the diagonal matrix D with D ii = -1 when i ∈ τ and 1 otherwise. The switching class of X , denoted [ X ] , is the collection of graphs obtained from X by switching on every subset of V X .

Example 2.3. The graph in Figure 1 will be denoted as X S . This graph will be referred to frequently throughout the paper.

Figure 1: Star graph on 6 vertices

![image](https://ac.marcodsn.me/arxiv-markdown-images/1408.0334v1-figure-e16dfc0b-1d00-4598-8ab1-2be8db78359c.jpg)

The graph in Figure 2 can be obtained by switching X S on the set τ = { 2 3 , } .

![image](https://ac.marcodsn.me/arxiv-markdown-images/1408.0334v1-figure-d5377d4d-2d41-4d95-97c0-b3bfdd27f646.jpg)

4

Figure 2: X S switched on { 2 3 , } .

As stated above, switching on τ is equivalent to conjugating S X by the diagonal matrix D with D ii = -1 when i ∈ τ and 1 otherwise. This is demonstrated in Example 2.4.

Example 2.4. The Seidel matrix for X S is

$$S _ { X _ { S } } = \begin{pmatrix} 0 & 1 & -$$

The diagonal matrix D corresponding to switching on the set τ = { 2 3 , } is

$$D = \begin{pmatrix} 1 & 0 & 0 & 0 & 0 \\ 0 & -$$

The result of this conjugation is Seidel matrix for the graph in Figure 2.

$$D S _ { X s } D = \begin{pmatrix} 0 & - 1 & 1$$

Definition 2.5. The graphs X and Y on n vertices are called switching equivalent if Y is isomorphic to X τ for some τ ⊂ V X , see [10].

Switching equivalent defines a second yet coarser equivalence relation on the collection of graphs on n vertices. The switching equivalent class of X , denoted [[ X ]] , is the collection of graphs obtained from X by conjugating S X by a signed permutation matrix, i.e. the product of a permutation matrix and a diagonal matrix of ± 1 ′ s . Thus, the spectrum of the Seidel adjacency matrices of switching equivalent graphs are identical. Note that [ X ] is a subset of [[ X ]] for any graph. For the complete graph and empty graph on n vertices, their switching classes are equal to their switching equivalent classes.

Corollary 2.6 (Corollary 3.5 in [24]) . Switching does not change the parity of the number of adjacencies among any 3 vertices of a graph.

/negationslash

Proof. On 3 vertices there are 4 non-isomorphic graphs, 2 distinct switching classes of graphs, and 2 distinct switching equivalent classes of graphs. The 4 non-isomorphic graphs X 1 , X 2 , X 3 , and X 4 are given in Figure 3. Clearly, [ X 1 ] = [[ X 1 ]] = [ X 2 ] and [ X 3 ] = [[ X 3 ]] = [ X 4 ] but [ X 1 ] = [ X 3 ] .

Figure 3: Nonisomorphic graphs on 3 vertices.

![image](https://ac.marcodsn.me/arxiv-markdown-images/1408.0334v1-figure-5e62f802-8f2b-4592-9ff7-38f7397282d4.jpg)

Lemma 2.7 (Lemma 3.8 in [24]) . For any graph on 4 vertices the number of subgraphs on 3 vertices, having an odd number of edges, is even.

Proof. On 4 vertices there are 11 non-isomorphic graphs, 8 distinct switching classes of graphs, and 3 distinct switching equivalent classes of graphs. The 11 non-isomorphic graphs are X , ..., X 1 6 , shown in Figure 4, and their complements X , ..., X 6 11 . The distinct switching classes are [ X 1 ] , [ X 2 ] , [ X 4 ] , and each 1 -edge graph contributes a distinct switching class. The distinct switching equivalent classes are [[ X 1 ]] the empty graph, [[ X 2 ]] the 1 -edge graph, and [[ X 4 ]] the complete graph.

Figure 4: Nonisomorphic graphs on 4 vertices.

![image](https://ac.marcodsn.me/arxiv-markdown-images/1408.0334v1-figure-ff845fda-f358-4df6-b637-1cf350ba2226.jpg)

Lemma 2.7 is the motivation behind the definition of a two-graph . Let Ω be a finite set and ∆ a set of triples of elements from Ω .

Definition 2.8. A two-graph (Ω ∆) , is a pair of a vertex set Ω and a triple set ∆ ⊂ Ω 3 , such that each set of four element subset from Ω contains an even number of triples of ∆ .

Lemma 2.9 is necessary to prove Theorem 2.10 below which states there is one-to-one correspondence between two-graphs and the switching classes of graphs on n vertices.

Lemma 2.9 (Lemma 3.9 in [24]) . The graphs (Ω , E ) and (Ω , E ′ ) are switching equivalent if the parity of the number of edges among each triple of vertices is the same for both graphs.

Proof. Let v be any vertex in Ω and S the set of vertices in Ω which have different adjacency with v in (Ω , E ) and (Ω , E ′ ) . Switching (Ω , E ′ ) on the set S gives a new graph (Ω , E ′′ ) such that the adjacencies of v with every other vertex are the same in (Ω , E ) and (Ω , E ′′ ) . Consider a pair of vertices { u, w } from Ω for which neither is equal to v . By hypothesis, the triangles { v, u, w } in (Ω , E ) and (Ω , E ′ ) have the same parity of edges. Switching on S preserves the parity of these triangles, so the triangles { v, u, w } in (Ω , E ) and (Ω , E ′′ ) have the same parity of edges and the adjacencies between v and u , and v and w are equal. Thus, the adjacency between u and w must also be the same for (Ω , E ) and (Ω , E ′′ ) . Therefor, these two graphs are isomorphic and the original two are switching equivalent.

Theorem 2.10 (Theorem 4.2 in [24]) . Given n , there is a one-to-one correspondence between the two-graphs and the switching classes of graphs on n vertices.

The following is Seidel's proof and is included for later reference.

Proof. Let (Ω , E ) be any graph. Define ∆ as the triples of Ω which correspond to triangles containing an odd number of edges. By Corollary 2.6, ∆ is invariant under switching. Lemma 2.7 proves (Ω ∆) , is a two-graph.

Conversely, let (Ω ∆) , be a two-graph, satisfying Definition 2.8. Select any ω in Ω and partition Ω \ { ω } into any 2 disjoint sets Ω 1 and Ω 2 . Let E consist of the following pairs:

$$\begin{array} {$$

Thus, we associate to (Ω ∆) , a class of graphs (Ω , E ) . By construction, ∆ is the set of triangles in (Ω , E ) which have an odd number of edges. So, by Lemma 2.9, the class of graphs constructed from (Ω ∆) , is a switching class and distinct switching classes yield distinct two-graphs. This proves the theorem.

Table 1 provides partial data on the number of non-isomorphic graphs, switching classes (two-graphs), and switching equivalent classes (non-isomorphic twographs) on n vertices up to n = 12 [21]. Indeed for Ω = { 1 2 3 , , } there are 2 two-graphs which are non-isomorphic. For Ω = { 1 2 3 4 , , , } there are 8 twographs but only 3 non-isomorphic two-graphs. Two of the three aforementioned non-isomorphic two-graphs correspond to the empty and complete graphs on 4 vertices and the third non-isomorphic two-graph corresponds to any one of the six 1-edge graphs on 4 vertices. This is precisely Lemma 2.7.

Table 1: Class Sizes

| n   | non-isomophic    | switching classes    | switching equivalent classes   |
|-----|------------------|----------------------|--------------------------------|
| 3   | 4                | 2                    | 2                              |
| 4   | 11               | 8                    | 3                              |
| 5   | 34               | 64                   | 7                              |
| 6   | 156              | 1024                 | 16                             |
| 7   | 1044             | 32,768               | 54                             |
| 8   | 12,346           | 2 21                 | 243                            |
| 9   | 274,668          | 2 28                 | 2038                           |
| 10  | 12,005,168       | 2 36                 | 33,120                         |
| n   | no known formula | 2 ( n - 1)( n - 2) 2 | See Proposition Appendix A.2   |

## 3. Equiangular Lines in R k and C k

This section reviews the process which takes a two-graph to a set of equiangular lines and vice versa. This process provides both the insight and the underlying motivation for our generalization of the definition of a Seidel matrix to allow m th -roots of unity in the off diagonal entries as well as our generalization of the definition of a two-graph.

## 3.1. Equiangular Lines in R k to a Two-Graph

Given a set Γ = { x , ..., x 1 n } of vectors in R k , let U be the k × n matrix with the elements of Γ as its columns. Then

$$G \coloneqq U ^ { T } U$$

is the Gram matrix of the vectors in Γ .

If Γ is set of unit vectors representing a set of equiangular lines in R k with x x T i j = ± α , then the n × n Gram matrix associated with Γ has the form

$$G = I + \alpha S$$

where S is an n × n Seidel adjacency matrix. Let X be the graph associated to the matrix S . If Ω := { 1 2 3 , , , ..., n } and ∆ is the set of all triples of vertices of X whose induced subgraph on three vertices has either 1 or 3 edges, the ordered pair (Ω ∆) , is a two-graph by Lemma 2.7.

Thus, every set of n -equiangular lines in R k yields a two-graph using the previously described process. It is worth noting there are 2 n -1 distinct Seidel adjacency matrices associated with a given set of n -equiangular lines. However, this set of Seidel adjacency matrices belong to the same switching class.

## 3.2. A Two-Graph to Equiangular Lines in R k

Constructing a graph (Ω , E ) from a two-graph (Ω ∆) , is not a well-defined process. Indeed there is a one to many correspondence. Fortunately the many are in the same switching class. The proof of Theorem 2.10 includes a process of how to build a graph (Ω , E ) given a two-graph (Ω ∆) , . We review this process below as well as include an example.

Pick v in Ω and a subset Ω 1 of Ω \ { v } . Define Ω 2 as the complement of Ω 1 in Ω \ { v } .

- · Start with E = {} .

- · For each ω in Ω 1 , add { v, ω } into E .
- · For each pair { ω, ω ′ } of elements in Ω 1 , if { v, ω, ω ′ } is in ∆ , add { ω, ω ′ } into E .
- · For each pair { ω, ω ′ } with ω in Ω 1 and ω ′ in Ω 2 , if { v, ω, ω ′ } is not in ∆ , add { ω, ω ′ } into E .
- · For each pair { ω, ω ′ } of elements in Ω 2 , if { v, ω, ω ′ } is in ∆ , add { ω, ω ′ } into E .

The resulting set E is the edge set for a graph (Ω , E ) . Example 3.1 illustrates this process.

## Example 3.1. Consider the two-graph

$$( \{ 1, 2, 3, 4, 5, 6 \}, \{ \{ 1, 2, 3 \}, \{ 1, 2, 6 \}, \{ 1, 3, 4 \}, \{ 1, 4, 5 \}, \{ 1, 5, 6 \}, \\ \{ 2, 3, 5 \}, \{ 2, 4, 5 \}, \{ 2, 4, 6 \}, \{ 3, 4, 6 \}, \{ 3, 5, 6 \} \} ).$$

Let v = 2 and Ω = 1 { 5 6 , } , so Ω = 2 { 1 3 4 , , } .

- · Start with E = {} .
- · Add { 2 5 , } and { 2 6 , } into E .
- · Since { 1 2 5 , , } and { 2 3 6 , , } are not in ∆ , we include { 1 5 , } and { 3 6 , } in E .
- · Since { 1 2 3 , , } is in ∆ , we include { 1 3 , } in E .

The resulting graph is

$$( \{ 1, 2, 3, 4, 5, 6 \}, \{ \{ 2, 5 \}, \{ 2, 6 \}, \{ 1, 5 \}, \{ 3, 6 \}, \{ 1, 3 \} \} ),$$

## or as in Figure 5.

One should notice the choice of v , Ω 1 and Ω 2 will possibly result in different graphs, but they will be in the same switching class. Applying a permutation from S | Ω | to the labels in the triple sets of ∆ will result in a graph switching equivalent to X S .

Figure 5: Graph resulting from two-graph construction, X S .

![image](https://ac.marcodsn.me/arxiv-markdown-images/1408.0334v1-figure-65894d0d-bbc9-473a-9e6b-3a3fbc99418e.jpg)

/negationslash

Given a two-graph (Ω ∆) , construct a graph, say X , on n vertices using this process. Again any graph constructed using this process must be in the same switching class as any other graph constructed via the given two-graph (Ω ∆) , . Consequently, the spectrum of the associated Seidel matrix denoted, S X , of any such graph X , remains constant. Since trS X = 0 and S X = 0 , the least eigenvalue of S X is negative. It follows that

$$G \coloneqq I + \frac { 1 } { \alpha } S _ { X }$$

is a positive semi-definite matrix where -α denotes the least eigenvalue of S X . Thus if the G has rank k , then there is a k × n matrix U such that G = U U T , where the n columns of this matrix U are the vectors in Γ which generate the n -equiangular lines in R k . Once again G is the Gram matrix associated with Γ .

## 3.3. Equiangular Lines in C k and Complex Seidel Adjacency Matrices

Now consider a set of equiangular lines in C k . If Λ = { z , ..., z 1 n } is a set of vectors representing this set of equiangular lines in C k with | z z ∗ i j | = α , then the n × n Gram matrix associated with Λ has the form

$$G = I + \alpha Q$$

where Q is a Hermitian matrix with all diagonal entries zero and all off-diagonal entries have modulus 1 . In [17], Holmes and Paulsen call such a matrix Q a signature matrix . However, some authors refer to this matrix as a Seidel matrix due to the connection to two-graphs. For the remainder of this paper we define a complex Seidel adjacency matrix as follows.

/negationslash

Definition 3.2. An n × n Hermitian matrix S such that s ii = 0 and | s ij | = 1 for all i = j is called a complex Seidel adjacency matrix .

Thus, there is a one-to-one correspondence between sets of n -equiangular lines in C k and complex Seidel adjacency matrices. In Sections 4 and 5 we prove a given complex Seidel adjacency matrix which has only roots of unity for its nonzero entries gives a natural way to generalize the definition of a two-graph to what we refer to as a complex two-graph . Moreover, we show complex regular two-graphs are precisely the complex two-graphs for which the relative or absolute bounds are met for the associated set of equiangular lines.

## 3.4. Relative, Absolute, and Welch Bounds

The maximal number of equiangular lines in either R k and C k occurs precisely when the associated Seidel adjacency matrix has exactly two distinct eigenvalues, e.g., [17, 10, 24]. In addition, the vectors associated with the maximal set of equiangular lines span the ambient space. This is a particularly valuable fact in frame theory since it guarantees this set of vectors, with a slight modification to their length, will be an ETF in either R k or C k .

It is well known that the maximal number of equiangular lines is k k ( +1) 2 in R k and k 2 in C k . One way to prove this in R k is to show the projections corresponding to the equiangular lines form a linearly independent set inside the vector space of symmetric k × k matrices which has dimension k k ( +1) 2 . One difference in the complex setting is that the Hermitian k × k matrices do not form a vector space over C . However, the Hermitian k × k matrices do form a vector space over R with dimension equal to k 2 . In Proposition 3.3, we derive the known upper bound, k 2 , for the number of equiangular lines in C k using this idea.

We begin by noting if z is a unit vector in C k , then Z = zz ∗ is a Hermitian k × k matrix and Z 2 = Z . It is also worth noting replacing z by e iθ z does not change the matrix Z . To compare with the real case, for a line through the origin in R k there are two distinct unit vectors which can be used to represent the given line. However, in the complex case, for a line through the origin in C k there are infinitely many unit vectors one can choose to represent the given line.

Now if W is also a unit vector in C k and W = ww ∗ , then

$$Z W = z z ^ { * } w w ^ { * } = ( z ^ { * } w ) z w ^ { * },$$

and so

$$\text{tr} ( Z W ) = | \langle z, w \rangle | ^ { 2 }.$$

Proposition 3.3 and it's proof closely resemble Theorem 11.2.1 in [10]. For the remainder of this section Γ = { z , ..., z 1 n } will denote a set of unit vectors associated with a set of equiangular lines in C k , and Z , ..., Z 1 n will denote the projections onto this set of equiangular lines, i.e., Z i = z z i ∗ i for each i = 1 , ..., n .

Proposition 3.3. (The Absolute Bound) Let Z , ..., Z 1 n be the projections onto a set of equiangular lines in C k . Then these matrices form a linearly independent set in the vector space of Hermitian matrices over the R , and consequently n ≤ k 2 .

/negationslash

$$\ r r o o { J. \text{ Leu} } & \alpha = \left | \langle z _ { i }, z _ { j } \rangle \right | \text{ for } t \neq \\ \text{lines.} & \text{If } W = \sum _ { i = 1 } ^ { n } c _ { i } Z _ { i }, \text{then} \\ & \quad \vdots \left | \mathcal { m } { V } ^ { 2 } \right | \cdot \sum _ { i = 1 } ^ { n } \Sigma$$

Proof. Let α = |〈 z , z i j 〉| for i = j , the cosine of the smaller angle between the

/negationslash

$$c _ { i } ^ { 2 }.$$

$$\overline { i = 1 } ^ { \quad } & \\ & \text{tr} ( W ^ { 2 } ) & = \sum _ { i, j } c _ { i } c _ { j } \text{tr} ( Z _ { i } Z _ { j } ) \\ & = \sum _ { i } c _ { i } ^ { 2 } + \sum _ { i, j \colon i \neq j } c _ { i } c _ { j } \alpha ^ { 2 } \\ & = \alpha ^ { 2 } \left ( \sum _ { i } c _ { i } \right ) ^ { 2 } + ( 1 - \alpha ^ { 2 } ) \sum _ { i } c _ { i } ^ { 2 }. \\ \\ \cdot \quad \cdot \quad \stackrel { \sim } { \vec { \sim } \cdot \vec { \sim } \cdot \vec { \sim } \cdot \vec { \sim } \cdot \vec { \sim } \cdot \vec { \sim } } \cdot \cdot \cdot \cdot \cdot \cdot$$

It follows that the tr( W 2 ) = 0 if and only if c i = 0 for all i . So, the Z i are linearly independent. The space of Hermitian k × k matrices over R has dimension k 2 , and the result follows.

The following two propositions are Lemmas 11.3.1 and 11.4.1 in [10]. The proofs of these propositions are not included since they are identical to the proofs given in [10] and the idea is similar to the proof of Proposition 3.3.

Proposition 3.4. (Lemma 11.3.1 [10]) Suppose Z , ..., Z 1 n are the projections onto a set of equiangular lines in C k and |〈 z , z i j 〉| = α . If I = ∑ i c Z i i , then c i = k/n for all i and

$$n = \frac { d - d \alpha ^ { 2 } } { 1 - d \alpha ^ { 2 } }.$$

The Seidel matrix determined by any set of n unit vectors spanning these lines has eigenvalues

$$- \frac { 1 } { \alpha }, \underset { \dots } { \frac { n - k } { k \alpha } }$$

with multiplicities n -k and k , respectively.

Proposition 3.5. (Lemma 11.4.1 [10]) Suppose { z , ..., z 1 n } is a set of n equiangular lines in C k and |〈 z , z i j 〉| = α . If α -2 &gt; k , then

$$n \leq \frac { k - k \alpha ^ { 2 } } { 1 - k \alpha ^ { 2 } }.$$

If Z , ..., Z 1 n are the projections onto these lines, then equality holds if and only if ∑ i Z i = ( k/n I ) . Corollary 3.6. (Welch bound) Given a set { z , ..., z 1 n } of n vectors in C k or R k set

$$\alpha \coloneqq \max _ { i \neq j } | \langle z _ { i }, z _ { j } \rangle |.$$

/negationslash

Then

$$\alpha & \geq \left ( \frac { n - k } { k ( n - 1 ) } \right ) ^ { \frac { 1 } { 2 } }. \\ \dots & e \dots \dots \dots \ddots \ddots.$$

To summarize, given a set of equiangular lines in either C k or R k this set of lines spans the given space if and only if equality holds in Proposition 3.5. In addition, this set of equiangular lines is maximal in the space. The Welch bound plays an equivalent role in frame theory, that is, a given set of frame vectors it is necessary for equality to hold in the Welch bound for the frame vectors to be an equiangular tight frame.

## 4. Cube Root Two-Graphs

In [3], to simplify the search for complex ETFs the authors restrict the off diagonal entries of a Seidel adjacency matrix to the cube roots of unity. The fact that the Seidel adjacency matrix must have two distinct eigenvalues coupled with this restriction to the cube roots of unity introduced new constraints that must be satisfied for the frame associated with the Seidel adjacency matrix to be an ETF. These new constraints along with the fact that these 'cube root Seidel adjacency matrices' corresponded to strongly regular graphs allowed the authors to discover new complex ETFs.

Like the authors in [3], J.A. Tropp in [30] simplifies the search for complex ETFs but this time by restricting the entries of the frame vectors to m th roots of unity. D. Kalra developed a technique in [19] which similarly restricts the entries in the frame vectors. Neither Tropp's nor Kalra's techniques lead to Seidel matrices whose nonzero entries are all roots of unity. Tropp poses several open questions at the end of [30], one of which is 'Are complex ETFs equivalent to some type of graph or combinatorial object?'.

In this section, we use the techniques from [3] to extend the definition of a two-graph and answer the above question posed in [30].

Recall that associated to each Seidel adjacency matrix there is a two-graph and to each two-graph there is an associated switching class of Seidel matrices. In this

section, all nonzero entries of the 'Seidel adjacency matrix' will be restricted to the cube roots of unity. That is, ω := e 2 π/ 3 , ω 2 := e 4 π/ 3 , and 1 . Such a matrix will be called a cube root Seidel matrix . The graph associated with an n × n cube root Seidel matrix will be a complete graph on n vertices with edges weighted by 1 , ω , and ω 2 . Such graphs will be referred to as cube root edge weighted graphs or CREWgraphs . Figure 6 gives an example of such a graph.

![image](https://ac.marcodsn.me/arxiv-markdown-images/1408.0334v1-figure-d9c4924b-b756-47c2-89de-c0ecafb85f57.jpg)

ω

Figure 6: CREW graph on 3 vertices

Unlike the real-case, there is a choice as to which matrix will correspond to the graph given in Figure 6. For the purposes of this article, the weight of the edge { i, j } with i &lt; j will be the ( i, j ) th entry in the corresponding cube root Seidel matrix, which means the ( j, i ) th entry will be the complex conjugate of the ( i, j ) th entry. The cube root Seidel matrix corresponding to Figure 6 is

$$\begin{pmatrix} 0 & 1 & \omega \\ 1 & 0 & \omega ^ { 2 } \\ \omega ^ { 2 } & \omega & 0 \end{pmatrix}.$$

Recall from Section 2, switching a graph X on a subset τ ⊆ V X is equivalent to conjugating S X by the diagonal matrix D with D ii = -1 when i ∈ τ and 1 otherwise.

## Definition 4.1. Let X be a CREW graph and define

D 3 := { D is a diagonal matrix : D ii is a cube root of unity } .

Given D in D 3 , the graph associated with the cube root Seidel matrix D S ∗ X D is called a switch on D . The switching class of X , denoted [ X ] , is the collection of graphs obtained by switching X by every element of D 3 .

The following is an example of a switch on the graph in Figure 6 with the resulting graph.

![image](https://ac.marcodsn.me/arxiv-markdown-images/1408.0334v1-figure-3b28c841-1a53-4507-982b-87882083e006.jpg)

$$\begin{pmatrix} 1 & 0 & 0 \\ 0 & \omega ^ { 2 } & 0 \\ 0 & 0 & \omega \end{pmatrix} \begin{pmatrix} 0 & 1 & \omega \\ 1 & 0 & \omega ^ { 2 } \\ \omega ^ { 2 } & \omega & 0 \end{pmatrix} \begin{pmatrix} 1 & 0 & 0 \\ 0 & \omega & 0 \\ 0 & 0 & \omega ^ { 2 } \end{pmatrix} = \begin{pmatrix} 0 & \omega & 1 \\ \omega ^ { 2 } & 0 & 1 \\ 1 & 1 & 0 \end{pmatrix}$$

Figure 7: A switch of Figure 6.

In the real case, we switched on a vertex or a set of vertices of a graph. Working with weighted graphs changes this approach. In this case, we say switching the i th vertex by weight ω is the result of conjugating by the diagonal matrix which has 1 ′ s on the diagonal with the exception that ω is in the i th position. Careful consideration of the example above suggests Proposition 4.2.

Proposition 4.2. Let G be a CREW graph. Switching G on vertex v i by ω results in a graph G ′ where edges not incident to v i are not effected and edges incident to v i have their weight multiplied by ω if there other vertex is v j with i &lt; j and their weight is multiplied by ω when j &lt; i .

Proof. Let S be the Seidel matrix for G and D the diagonal matrix corresponding to this switch. The resulting matrix G ′ has Seidel matrix DSD -1 . Since we weight our graphs using the upper half of the Seidel matrix, we see the entries in DSD -1 above the diagonal in the i th row ( i &lt; j ) are multiplied by ω and in the i th column ( j &lt; i ) are multiplied by ω .

The proof of Proposition 4.2 does not rely on cube roots of unity and extends to all complex numbers of modulus 1 .

A Seidel matrix whose nonzero entries in the first row and column are all 1 ′ s is said to be in standard form . Each Seidel matrix, with real or complex entries, can be switched to be in standard form. The three graphs in Figure 8 are representatives for distinct switching classes of CREW graphs on 3 vertices.

Proposition 4.3. There are three distinct switching classes for the CREW graphs with 3 vertices. In fact, the three graphs in Figure 8 are the unique representatives in standard form from each switching class.

Figure 8: Representatives for switching classes.

![image](https://ac.marcodsn.me/arxiv-markdown-images/1408.0334v1-figure-8ecc6532-bd10-4316-9c30-b1ac60edb400.jpg)

Proof. Given any CREW graph on 3 vertices the associated Seidel adjacency matrix in standard form must be associated with one of the three graphs in Figure 8. Now suppose there is a switch from one of the representatives in Figure 8 to another. This means there is a D in D 3 such that

$$\begin{pmatrix} a & 0 & 0 \\ 0 & b & 0 \\ 0 & 0 & c \end{pmatrix} \begin{pmatrix} 0 & 1 & 1 \\ 1 & 0 & \omega _ { 1 } \\ 1 & \overline { \omega } _ { 1 } & 0 \end{pmatrix} \begin{pmatrix} \overline { a } & 0 & 0 \\ 0 & \overline { b } & 0 \\ 0 & 0 & \overline { c } \end{pmatrix} = \begin{pmatrix} 0 & 1 & 1 \\ 1 & 0 & \omega _ { 2 } \\ 1 & \overline { \omega ^ { 2 } } & 0 \end{pmatrix} \\ \text{where} \, \omega _ { 1 }, \omega _ { 2 }, a, b, \text{ and } c \text{ are cube roots of unity.} \text{ This forces } a = b = c = 1 \text{ while}$$

where ω 1 , ω 2 , a b , , and c are cube roots of unity. This forces a = b = c = 1 which in return forces ω 1 = ω 2 .

Thus far, switching on a CREW graph, X , has been accomplished by conjugating the associated cube root Seidel adjacency matrix, S X , by a diagonal matrix D in D 3 . Proposition 4.4 extends switching on CREW graphs in a manner similar to Definition 2.2.

Proposition 4.4. Let G be a CREW graph with vertices labeled { 1 2 , , ..., n } . Switching vertex i of G by weight ω will change the weight of edges { i, j } by a factor of ω 2 if i &lt; j and by a factor of ω if j &lt; i . Edge weights for edges not incident to i will not change.

Proof. Let S be the Seidel matrix corresponding to G . Switching the vertex i by ω on the matrix becomes multiplying the i th row by ω and the i th column by ω 2 . Considering the graph corresponding to this new matrix gives the desired result since the edge weights come from the upper half of the matrix.

Proposition 4.5. Let S be an n × n cube root Seidel matrix. There are 3 n -1 elements in the switching class of S . Furthermore, there are 3 ( n -1)( n -2) 2 switching classes of n × n cube root Seidel matrices.

Proof. Let S be a n × n cube root Seidel matrix. Switches of S are the result of conjugating S by diagonal matrices D in D 3 . If ω is a cube root of unity, then

( ωD S ωD ) ( ) -1 = DSD -1 . Thus, there are 3 n -1 elements in the switching class of S . To count the number of classes, divide the number of n × n cube root Seidel matrices, which is 3 n n ( -1) 2 , by the number of elements in each class. This yields the stated result.

As in the real case, when classifying CREW graphs up to isomorphism and switching, some switching classes collapse together. Allowing for both switching and isomorphism, the new classes are called switching equivalent classes . Let X be a CREW graph, then conjugating the associated cube root Seidel adjacency matrix, S X , by the product of a diagonal matrix D in D 3 and a permutation matrix P results in a cube root Seidel matrix, PDS X ( PD ) -1 , which is switching equivalent to X . The switching equivalent class of X , denoted [[ X ]] , is the collection of all such conjugations.

While Proposition 4.5 gives the number of switching classes of CREW graphs, there is not a known formula for the number of switching equivalent classes. The sequence 2 , 4 , 14 , 120 , 3222 does not occur in the Online Encyclopedia of Integer Sequences, see [23], so the number of switching equivalence classes of CREW graphs does not match with any known sequence. However, [12] contains a formula for the number of non-isomorphic CREW graphs on n vertices which is repeated in Appendix A.4. To compare with the real case, recall that Mallows and Sloan, [22], provide a formula for the number of switching equivalent classes but the number of non-isomorphic graphs is the ever elusive graph isomorphism problem. Table 2 summarizes the data we have collected thus far.

Table 2: Cube Root Class Sizes

| n   | non-isomorphic CREW graphs   | switching classes                 | switching equivalent classes   |
|-----|------------------------------|-----------------------------------|--------------------------------|
| 3   | 7                            | 3                                 | 2                              |
| 4   | 42                           | 27                                | 4                              |
| 5   | 582                          | 729                               | 14                             |
| 6   | 21,480                       | 59,049                            | 120                            |
| 7   | 2,142,288                    | 14,348,907                        | 3222                           |
| n   | See Appendix A.4             | 3 ( n - 1)( n - 2) 2 by Prop. 4.5 | no known formula               |

Recall in the real case, on four vertices there are 11 non-isomorphic graphs, 8 switching classes (or equivalently 8 two-graphs), 3 switching equivalent classes (or equivalently 3 non-isomorphic two-graphs). Using Table 2 and terminology in

Section 4.3 we have on four vertices there are 42 non-isomorphic CREW graphs, 27 cube root two-graphs, and 4 non-isomorphic cube root two-graphs.

## 4.1. Complex Two-Graphs with Cube Roots of Unity

Before defining a complex two-graph with cube roots of unity a further exploration of two-graphs (in the real setting) will be useful. The following 'new' yet equivalent definition of a two-graph plays a crucial role in adapting the definition of a two-graph to include not only CREW graphs but p th root edge weighted graphs as well.

Definition 4.6. A two-graph (Ω ∆ , 1 , ∆ ) 2 is a triple of a vertex set Ω and triple sets ∆ 1 and ∆ 2 such that ∆ 1 ∪ ∆ = Ω 2 3 and each set of four elements from Ω contains an even number of elements of ∆ 1 and ∆ 2 as subsets.

Comparing Definitions 4.6 and 2.8 leads to the following proposition.

Proposition 4.7. Definitions 2.8 and 4.6 are equivalent.

Proof. Let (Ω ∆) , be a two-graph according to Definition 2.8. Clearly (Ω ∆ ∆) , , ¯ satisfies Definition 4.6.

Let (Ω ∆ , 1 , ∆ ) 2 be a two-graph according to Definition 4.6. By Lemma 2.7, (Ω ∆ ) , 1 satisfies Definition 2.8.

Example 4.8 gives the two graph for Figure 1 following Definitions 2.8 and 4.6.

Example 4.8. Recall the star graph from Example 2.3, repeated in Figure 9. If Ω = { 1 2 3 4 5 6 , , , , , } and let ∆ be the set of triples of vertices of this graph whose induced subgraph on three vertices has either 1 or 3 edges. By Lemma 2.7, (Ω ∆) , is a two-graph where

$$\Delta = \{ \{ 1, 2, 3 \}, \{ 1, 2, 6 \}, \{ 1, 3, 4 \}, \{ 1, 4, 5 \}, \{ 1, 5, 6 \}, \{ 2, 3, 5 \}, \\ \{ 2, 4, 5 \}, \{ 2, 4, 6 \}, \{ 3, 4, 6 \}, \{ 3, 5, 6 \} \}.$$

Using Definition 4.6, (Ω ∆ , 1 , ∆ ) 2 is a two-graph where ∆ = ∆ 1 and

$$\Delta _ { 2 } = \{ \{ 1, 2, 4 \}, \{ 1$$

Figure 9: Star graph on 6 vertices

![image](https://ac.marcodsn.me/arxiv-markdown-images/1408.0334v1-figure-de872d77-da3c-44b8-901e-b59f6cfd133c.jpg)

Theorem 2.10 connected two-graphs and switching classes of simple graphs. Restating Theorem 2.10 using Definition 4.6 requires replacing simple graphs with complete graphs whose edges are weighted by ± 1 , i.e., square root edge weighted graphs . This trivial replacement is the key to understanding the extension of the definition of a two-graph to include cube roots of unity in this section and the m th roots of unity in Section 5.

Theorem 4.9 (Theorem 2.10 restated using Definition 4.6) . Given n , there is a one-to-one correspondence between the two-graphs (Definition 4.6) and the switching classes of ± 1 edge weighted complete graphs on n vertices.

Proof. Let (Ω , E ) be a complete graph on n vertices with the edges in E weighted by -1 and the rest of the edges weighted by 1 . Define ∆ 1 as the set of triangles containing an odd number of edges weighted by -1 , i.e., the switching class of the triangle with three -1 weighted edges, and ∆ 2 the rest of the triangles, i.e., the switching class of the triangle with three 1 weighted edges. Since ∆ 1 and ∆ 2 are invariant under switching, Lemma 2.7 proves (Ω ∆ , 1 , ∆ ) 2 is a two-graph.

Conversely, let (Ω ∆ , 1 , ∆ ) 2 be a two-graph, satisfying Definition 4.6. Select any ω in Ω and partition Ω \ { ω } into any 2 disjoint sets Ω 1 and Ω 2 . Define E 1 and E -1 as the edges weighted by 1 and -1 respectively. For all ω 1 ∈ Ω 1 , the pair { ω, ω 1 } is in E -1 and for all ω 1 ∈ Ω 2 , the pair { ω, ω 2 } is in E 1 . Lastly, if { ω, ω , ω 1 2 } is in ∆ 1 , then { ω , ω 1 2 } is in E 1 , otherwise { ω , ω 1 2 } is in E -1 .

Thus, we associate to (Ω ∆ , 1 , ∆ ) 2 a class of ± 1 complete graphs (Ω , E 1 , E -1 ) . By construction, ∆ 1 is the set of triangles in (Ω , E 1 , E -1 ) which have an odd number of edges weighted by -1 . So, by Lemma 2.9, the class of graphs constructed from (Ω ∆ , 1 , ∆ ) 2 is a switching class and distinct switching classes yield distinct two-graphs. This proves the theorem.

The existence, and hence the definition, of two-graphs comes from Lemma 3.8 in [24]. Before defining cube root two-graphs, we extend this lemma.

Lemma 4.10 (Extension of Lemma 3.8 in [24]) . For any CREW graph on 4 vertices the number of induced CREW subgraphs on 3 vertices, having an odd number of edges weighted w ∈ { 1 , ω, ω 2 } , is even.

Proof. Let G be a CREW graph on 4 vertices and let G ′ be the graph obtained from G by removing edges with weight not w . By Lemma 2.7, there are an even number of induced subgraphs of G ′ on three vertices with an odd number of edges. These subgraphs correspond to the induced subgraphs of G which have an odd number of edges weighted with w .

Using Definition 4.6 as a model, we now define cube root two-graphs.

Definition 4.11. A cube root two-graph (Ω ∆ , 1 , ∆ 2 , ∆ ) 3 is a quadruple of a vertex set Ω and triple sets ∆ 1 , ∆ 2 and ∆ 3 such that ∆ 1 ∪ ∆ 2 ∪ ∆ = Ω 3 3 and each set of four element subset of Ω contains an even number of triples of ∆ 1 , ∆ 2 , or ∆ 3 .

Proving a version of Theorem 2.10 for cube root two-graphs requires extending Lemma 2.9. The idea behind the proof for Lemma 2.9 works equally as well in the cube root case, but some rewriting needs to be done since the parity of edges no longer makes sense.

Lemma 4.12 (Extension of Lemma 3.9 in [24]) . The CREW graphs (Ω , E ) and (Ω , E ′ ) are switching equivalent if the parity of the number of edges weighted by w among each triple of vertices is the same for both graphs with w ∈ { 1 , ω, ω 2 } .

Proof. Let v be any vertex in Ω . Define S 1 as the set of vertices u in Ω such that the edge weight of { v, u } in (Ω , E ′ ) is ω times the edge weight in (Ω , E ) . Similarly, define S 2 as the set of vertices u in Ω such that the edge weight of { v, u } in (Ω , E ′ ) is ω 2 times the edge weight in (Ω , E ) . Switching (Ω , E ′ ) by ω on the set S 1 and by ω 2 on S 2 results in a new graph (Ω , E ′′ ) such that the adjacencies of v with every other vertex are the same in (Ω , E ) and (Ω , E ′′ ) . Consider a pair of vertices { u, w } from Ω for which neither is equal to v . By hypothesis, the triangles { v, u, w } in (Ω , E ) and (Ω , E ′ ) have the same parity of each possible edge weight. Switching on S preserves the parity of these triangles, so the triangles { v, u, w } in (Ω , E ) and (Ω , E ′′ ) have the same parity of edge weights and the weights of the edges { v, u } , and { v, w } are equal. Thus, the edge weight of { u, w } must also be the same for (Ω , E ) and (Ω , E ′′ ) . Therefor, these two graphs are isomorphic and the original two are switching equivalent.

Theorem 4.13 (Extension of Theorem 2.10) . Given n , there is a one-to-one correspondence between the cube root two-graphs and the switching classes of CREW graphs on n vertices.

Proof. Let (Ω , E ) be a complete graph on n vertices with the edges weighted by cube roots of unity. Define ∆ 1 , ∆ 2 and ∆ 3 to be the sets of triples of vertices whose induced subgraphs are in the switching classes of the corresponding graphs given in Figure 8. Since ∆ 1 , ∆ 2 , and ∆ 3 are invariant under switching, Lemma 4.10 proves (Ω ∆ , 1 , ∆ 2 , ∆ ) 3 is a cube root two-graph.

Conversely, let (Ω ∆ , 1 , ∆ 2 , ∆ ) 3 be a cube root two-graph. Select any v in Ω and partition Ω \ { v } into any 3 disjoint sets Ω 1 , Ω 2 , and Ω 3 . For simplicity, we assume Ω = { 1 , ..., n } , v = 1 and for each i ∈ Ω 1 , j ∈ Ω 2 and k ∈ Ω 3 , i &lt; j &lt; k . Changing any choices of v and Ω 1 , Ω 2 , and Ω 3 to fit this description is a permutation of Ω which simplifies the following construction but does not restrict the generality of the proof.

From the partition, build a CREW graph G as follows:

Let E 1 , E 2 and E 3 be a partition of the edges of G such that an edge in E i has weight ω i . As an abuse of notation, we consider indices for E i to be modulo 3 , so E 1 = E 4 and E 2 = E 5 .

- · For every u in Ω i , put { v, u } in E i .
- · For every pair u and w in Ω i , if { 1 , u, w } is in ∆ j , put { u, w } in E j .
- · For every u in Ω 1 and w in Ω 2 , if { 1 , u, w } is in ∆ j , put { u, w } in E j +1 .
- · For every u in Ω 2 and w in Ω 3 , if { 1 , u, w } is in ∆ j , put { u, w } in E j +1 .
- · For every u in Ω 1 and w in Ω 3 , if { 1 , u, w } is in ∆ j , put { u, w } in E j +2 .

Thus, associated to (Ω ∆ , 1 , ∆ 2 , ∆ ) 3 is a class of CREW graphs of the form (Ω , E 1 , E 2 , E 3 ) . By construction, ∆ i is the set of triangles in (Ω , E 1 , E 2 , E 3 ) which have an odd number of edges weighted by ω i . So, by Lemma 4.12, the class of graphs constructed from (Ω ∆ , 1 , ∆ 2 , ∆ ) 3 is a switching class and distinct switching classes yield distinct two-graphs. This proves the theorem.

The use of a permutation in the proof of Theorem 4.13 is justified since to get around this complicates the decision process for putting edges into the E i . For example, if we don't assume v = 1 and the Ω i 's are ordered, we get for every u in

Ω 1 and w in Ω 2 , put { u, w } in E k where

$$k = \begin{cases} j + 1 & \text{if $v<u<w$$$

 Writing out all of the cases in this format will lead to the same result and is not useful for understanding the proof or constructing CREW graphs from cube root two-graphs.

The following example describes a cube root two-graph.

Example 4.14. Following the proof of Theorem 4.13, the graph with cube root Seidel matrix

corresponds to the cube root two-graph with Ω = { 1 , . . . , 8 } ,

$$\begin{array} {$$

```
<_SQL_>
```

and

$$\Delta _ { 3 } = \{ \{ 1, 2, 3 \}, \{ 1$$

A regular two-graph is a two-graph such that any, and consequently all, of the associated Seidel adjacency matrices have two distinct eigenvalues. There is an intimate relationship between regular two-graphs and strongly regular graphs which is captured in Theorem 4.15.

Let Φ be a two-graph and X an associated graph. A vertex of X can be isolated by switching and removed, resulting in a graph with one fewer vertex, called a neighborhood of Φ .

Theorem 4.15 (Theorem 11 6 1 . . in [10]) . Let Φ be a nontrivial two-graph on n +1 vertices. Then the following are equivalent:

- 1. Φ is a regular two-graph.
- 2. All the neighborhoods of Φ are regular graphs.
- 3. All the neighborhoods of Φ are ( n, k, a, c ) strongly regular graphs with k = 2 c .
- 4. One neighborhood of Φ is an ( n, k, a, c ) strongly regular graph with k = 2 c .

Theorem 4.15 explains the motivation behind calling a two-graph with exactly two-eigenvalues a regular two-graph. Furthermore the strongly regular graphs have been actively studied and many of these results can be used to build regular two-graphs. Regular two-graphs are important because they are the only nontrivial two-graphs for which the corresponding set of equiangular lines meet the absolute bound or the relative bound. Thus, the set of vectors determined by choosing a unit vector to represent each line spans the ambient space. In frame theory this guarantees this set of vectors with adjusted lengths will form an equiangular tight frame.

The proof of Theorem 4.15 uses terminology such as equitable and quotient matrix which are specific to graphs as well as powerful tools. While this terminology does not apply directly to the cube root setting, the underlying linear algebra results do hold, and gives us Theorem 4.16.

Similar to two-graphs, we call a cube root two-graph regular if any, and hence all, associated CREW graph has two eigenvalues. In [3], they show if a cube root Seidel adjacency matrix with two eigenvalues, λ 1 and λ 2 , is in standard form, then all rows after the first have a constant sum. The row sum being constant is the key to proving Theorem 4.16.

Theorem 4.16. Let Φ be a nontrivial cube root two-graph on n +1 vertices. Then the following are equivalent:

- 1. Φ is a regular cube root two-graph.
- 2. All the neighborhoods of Φ are CREW graphs with vertex sums µ and eigenvalues µ λ , 1 , and λ 2 . The multiplicity of µ is 1 .
- 3. One neighborhood of Φ is a CREW graph with vertex sum µ and eigenvalues µ λ , 1 , and λ 2 . The multiplicity of µ is 1 .

Proof. 1 → 2: Let x be a vertex of Φ and S a Seidel matrix whose first row and column correspond to x . Without loss of generality, assume S is in standard form, which corresponds to x being isolated. By [3], S has two eigenvalues, λ 1 and λ 2 . Let A be the ( n -1) × ( n -1) matrix obtained from S by removing the first row and column. By the interlacing theorem, n -2 of the eigenvalues of A are λ 1 or λ 2 . By [3], the rows of A have a constant sum equal to µ , so this is an eigenvalue for A as well.

2 → 3:

Obvious.

3 → 1: Let A be a matrix corresponding to a cube root Seidel graph with vertex sum µ and eigenvalues µ λ , 1 , and λ 2 . By the Spectral Theorem, eigenvectors for λ 1 and λ 2 can be chosen to be orthogonal to 1 , the eigenvector corresponding to µ . Let S be the matrix

$$\begin{pmatrix} \text{to } \mu. \text{ Let } S \text{ be the matrix } & \begin{pmatrix} 0 & 1 ^ { t } \\ 1 & A \end{pmatrix} \\ \text{then the vectors } & \begin{pmatrix} 0 \\ v \end{pmatrix} \\ \text{where } v \text{ is an eigenvector for } A, \text{ are eigenvectors for } \end{pmatrix}$$

where v is an eigenvector for A , are eigenvectors for S , corresponding to eigenvalues λ 1 or λ 2 .

Let and

$$P = \begin{pmatrix} 1 & 0 \\ 0 & 1 \\ \vdots & \vdots \\ 0 & 1 \end{pmatrix} \\ \Gamma \quad \int 0 \quad n - 1 \, \zeta$$

$$B = \begin{pmatrix} 0 & n - 1 \\ 1 & \mu \end{pmatrix} \\ \text{is-never-for $B$ then $P$}$$

then SP = PB . If v is an eigenvector for B , then Pv is an eigenvector for S for the same eigenvalue. The characteristic polynomial for B is x 2 -µx -( n -1) , so its eigenvalues are λ 1 and λ 2 . Since the first component of Pv is nonzero, these eigenvectors are not any of the previously known eigenvectors of S , so S has just the two eigenvalues. Thus, S is a Seidel matrix which corresponds to a regular cube root two-graph.

## 4.2. Constructions for (9,6) ETF

The article [3] contains an example of a (9 , 6) -equiangular tight frame or equivalently 9 equiangular lines in C 6 . Their construction starts with the known directed strongly regular graph on 8 vertices in Figure 10.

Figure 10: Directed strongly regular graph on 8 vertices.

![image](https://ac.marcodsn.me/arxiv-markdown-images/1408.0334v1-figure-c920cb45-2d8c-4c11-b1ca-b67823c17bb6.jpg)

/negationslash

A Seidel matrix can be constructed from this graph by letting the ij th entry, with i = j , be

$$\begin{cases} \omega & \text{if there is an edge from $i$ to $j$} \\ \omega ^ { 2 } & \text{if there is an edge from $j$ to $i$} \\ 1 & \text{otherwise} \end{cases}$$

and setting the diagonal entries to 0 . Adding a first row and column of ones, with zero on the diagonal entry, completes the construction. This new Seidel matrix has two eigenvalues, and will be switching equivalent to the matrix

```
    envalues, and will be switching equivalent to the matrix
```

where ω is a primitive cube root of unity. This construction is an application of proof of Theorem 4.16.

While this construction seems to connect cube root two-graphs to directed strongly regular graphs with no undirected edges, the development of cube root two-graphs describe above can be extended to m th roots of unity. Along with this development, the authors have constructed nontrivial complex two-graphs and regular complex two-graphs for many roots of unity which do not obviously connect with generalizations of strongly regular graphs, see [7, 15].

## 5. Complex Two-Graphs with m th Roots of Unity

Using the obvious definitions for m th root Seidel matrices and m th root edge weighted graphs, we reconsider the results of Section 4. Let D m be the collection of diagonal matrices whose nonzero entries are m th roots of unity, then the definitions of switching classes and switching equivalent classes make sense. With these definitions, most of the results from Section 4 are true for m th roots of unity without modification because their proofs do not depend on cube roots of unity.

Recall the representatives of switching classes for 3 vertices in Figure 8. The extension is representatives have a single edge weighted by 1 , ω ,..., ω m -1 , with ω a primitive m th root of unity, and the other two edges both weighted by 1 . Proposition 4.4 changes as follows, but the proof from Section 4 holds with the modification of the matrix entries being m th roots of unity.

Proposition 5.1 (Extension of Proposition 4.4) . There are m distinct switching classes of m th root edge weighted graphs on three vertices.

With the goal of defining m th root two-graphs, Lemmas 4.10 and 4.12 require special attention. Fortunately, the proof of Lemma 4.10 is an application of Lemma 2.7 and can be extended to any number of weights. The proof of Lemma 4.12 is extended to m th roots of unity by replacing ω 2 by ω . With these lemmas in place, we define m th root two-graphs as follows.

Definition 5.2. An m th root two-graph (Ω ∆ , 1 , . . . , ∆ ) m is a m + 1 -tuple of a vertex set Ω and triple sets ∆ 1 , ∆ 2 ,..., ∆ m such that ⋃ ∆ = Ω i 3 and each set of four element subset of Ω contains an even number of triples of ∆ i , for 1 ≤ i ≤ m .

As expected, the m th root two-graph are in one-to-one correspondence with the switching classes of m th root edge weighted graphs.

Theorem 5.3 (Extension of Theorem 4.13) . Given n , there is a one-to-one correspondence between the m th root two-graphs and the switching classes of m th root edge weighted graphs on n vertices.

The proof of this theorem follows from modifying the proof of Theorem 4.13 to use edge sets E 1 ,..., E m and extending the cases for all possible pairs of vertices. Fortunately, the edge weights are determined by the ∆ i 's, and the proof follows.

For regular m th root two-graphs, we need constant row sums in our m th root Seidel matrices. While, in [3], the authors focus only on cube roots of unity, their result that the standard form of a cube root Seidel matrix with two eigenvalues has constant row sum for every row after the first does not depend on cube roots of unity, only on the standard form and two eigenvalues, and hence, is true for m th root Seidel matrices. This gives us the Theorem 4.16.

Theorem 5.4 (Extension of Theorem 4.16) . Let Φ be a nontrivial m th root twograph on n +1 vertices. Then the following are equivalent:

- 1. Φ is a regular m th root two-graph.
- 2. All the neighborhoods of Φ are m th root edge weighted graphs with vertex sums µ and eigenvalues µ λ , 1 , and λ 2 , the multiplicity of µ is 1 .
- 3. One neighborhood of Φ is an m th root edge weighted graph with vertex sum µ and eigenvalues µ λ , 1 , and λ 2 , the multiplicity of µ is 1 .

The proof of Theorem 4.16 does not depend on cube roots of unity, only on the relationship between the row sums and the eigenvalues of the matrices corresponding to the cube root two-graph. So, replacing the cube roots by m th roots does not effect the proof and the result holds.

## Appendix A. Known Formulas for Counting Switching Equivalence Classes and Cube Root Edge Weighted Graphs

In Tables 1 and 2, formulas are used which were derived combinatorially. The techniques and terminology are different enough from the rest of this article that they deserve attention.

Suppose j is a positive integer and ( j ) denotes a partition of j . Define j k to be the number of times k appears in ( j ) , so ∑ j k =1 k ∗ j k = j . Several of the following formulas involve summations over all partitions of j which will be denoted as ∑ ( j ) .

In [22], the following formula for the number of Euler graphs on n vertices is attributed to R. W. Robinson.

Theorem Appendix A.1 (Eulerian Graphs) . The number of Euler graphs on n vertices is where

and

The central result of [22] is Appendix A.2. Seidel had proved Appendix A.2 for odd n by finding Euler graphs as representatives of switching equivalent classes. Mallows and Sloan proved the even case without making an obvious connection between Euler graphs and switching equivalent classes or two-graphs.

$$\text{eorem Appendix } A. 1 \text{ (Eulerian Graphs).  The number of Euler graphs on} \\ \text{rtices is} \\ \sum _ { ( j ) } \frac { 2 ^ { v ( j ) - \lambda ( j ) } } { \prod _ { i } i ^ { j i } j _ { i }! }, \\ \text{ere} \\ v ( j ) = \sum _ { i < k } j _ { i } j _ { k } \gcd ( i, j ) + \sum _ { i } i \left ( j _ { 2 i } + j _ { 2 i + 1 } + \binom { j } { 2 } \right ), \\ d \\ \lambda ( j ) = \sum _ { i } j _ { i } - \text{sgn} \left ( \sum _ { i } j _ { 2 i + 1 } \right ). \\ \text{ The central result of [22] is Appendix } A. 2. \text{ Seidel had proved Appendix } A \\ \text{ odd } n \text{ by finding Euler graphs as representatives of switching equivalent class}$$

Proposition Appendix A.2 (Theorem 1 in [22]) . The number of two-graphs on n vertices is equal to the number of Euler graphs on n vertices.

We do not include the proof of Appendix A.2 as it is most of [22]. However, it is a nice arguement and we recommend any interested person should read it.

Harary and Palmer define a complete directed graph as a directed graph such that for any pair of vertices there is either a directed edge or two directed edges connecting them. With this definition comes the question of how many such graphs are there on n vertices. In [12], this question is answered and [13] contains a refinement of the formula. We include the refined formula.

Theorem Appendix A.3 (Page 133 of [13]) . The number of complete directed graphs on n vertices is where

$$c _ { n } = \frac { 1 } { n! } \sum _ { ( n ) } \frac { n! } { \prod k ^ { n _ { k } } n _ { k }! } 3 ^ { a ( n ) }$$

$$a ( n ) & = \sum _ { k = 1 } ^ { n } \left ( \left \lfloor \frac { k - 1 } { 2 } \right \rfloor n _ { k } + k \binom { n _ { k } } { 2 } \right ) + \sum _ { 1 \leq r < s \leq n } \gcd ( r, s ) n _ { r } n _ { s }. \\ \intertext { a n d v } \underbrace { \lambda \ 2 \, \text{bold} d \, \text{int} \, \text{int} } \underbrace { \lambda \ 2 \, \text{bold} d \, \text{int} \, \text{int} \, \text{int} \, \text{int} \, \text{int} \, \text{int} \, \text{int} \, \text{int} \, \text{int} \, \text{int} \, \text{int} \, \text{int} \, \text{int} \, \text{int} \, \text{int} \, \text{int} \, \text{int} \, \text{int} \, \text{int} \, \text{int} \, \text{int} \, \text{int} \, \text{int} \, \text{int} \, \text{int} \, \text{int} \, \text{int} \, \text{int} \, \text{int} \, \colon }$$

Appendix A.3 holds interest for this article because of Appendix A.4.

Proposition Appendix A.4. There is a one to one correspondence between cube root edge weighted graphs on n vertices and complete directed graphs on n vertices.

Proof. Given a complete directed graph G , label the vertices from 1 to n and define CRG to be a complete graph on n vertices. For any pair of vertices v and u , if two edges connect them in G , then weight the edge { v, u } of CRG with a 1 . For any pair { v, u } with a single directed edge going from v to u , weight it by ω if v &lt; u and ω 2 if u &lt; v . The graph with CRG with these weights is a cube root edge weighted graph. The choice of labeling does not effect the outcome of the weights, so this assignment is one to one and clearly invertible.

## References

- [1] B.G. Bodmann and H.J. Elwood, Complex equiangular Parseval frames and Seidel matrices containing pth roots of unity. Proc. Amer. Math. Soc. 138 (2010), no. 12, 43874404.
- [2] B.G. Bodmann and V.I. Paulsen, Frames, graphs and erasures, Linear Algebra Appl. 404 (2005), 118-146.
- [3] B.G. Bodmann, V.I. Paulsen, and M. Tomforde, Equiangular Tight Frames from Complex Seidel Matrices Containing Cube Roots of Unity, Linear Algebra Appl. 430 (2009), 396-417.
- [4] L. Bos, and S. Waldron, Some Remarks on Heisenberg Frames and Sets of Equiangular Lines, New Zealand Journal of Mathematics 36 (2007), 113137.

| [5]   | P.G. Casazza and J. Kova ˘ c evi´, c Uniform Tight Frames with Erasures, Ad- vances in Computational Mathematics 18 (2003), 387-430.                |
|-------|-----------------------------------------------------------------------------------------------------------------------------------------------------|
| [6]   | J. Clark and D.A. Holton, A first look at graph theory, World Scientific Pub- lishing Co. Inc., Teaneck NJ, 1991.                                   |
| [7]   | D.M. Duncan, T.R. Hoffman, and J.P. Solazzo, Equiangular tight frames and fourth root Seidel matrices, Linear Algebra Appl. 4 32 (2010), 2816-2823. |
| [8]   | M. Fickus, D.G. Mixon, and J.C. Tremain, Steiner equiangular tight frames. Linear Algebra Appl. 436 (2012), no. 5, 10141027.                        |
| [9]   | The GAP Group, GAP - Groups, Algo- rithms, and Programming, Version 4.7.5 ; 2014 (\protect\vrule width0pt\protect\href{http://www.gap-system.org}{h |
| [10]  | C.D. Godsil and G. Royle, Algebraic Graph Theory, Springer New York, 2001.                                                                          |
| [11]  | R.L. Graham, B.L. Rothschild, and J.H. Spencer, Ramsey Theory, Second Ed. John Wiley &Sons Inc. New York, 1990.                                     |
| [12]  | F. Harary and E. Palmer, Enumeration of Mixed Graphs, Proceedings of the American Mathematical Society 1 7 (1966), 682-687.                         |
| [13]  | F. Harary and E. Palmer, Graphical Enumeration, Academic Press, New York-London, 1973.                                                              |
| [14]  | K. Hoffman and R. Kunze, Linear Algebra, Prentice-Hall Inc. Englewood Cliffs, N.J., Second edition, 1971.                                           |
| [15]  | T.R. Hoffman and J.P. Solazzo, Complex equiangular tight frames and era- sures. Linear Algebra Appl. 437 (2012), no. 2, 549558.                     |
| [16]  | R.B. Holmes, Optimal Frames, PhD Thesis, University of Houston, 2003.                                                                               |
| [17]  | R.B. Holmes and V.I. Paulsen, Optimal frames for erasures, Linear Algebra and its Applications 377 (2004), 31-51.                                   |
| [18]  | J. Jasper, D.G. Mixon, and M. Fickus, Kirkman equiangular tight frames and codes. IEEE Trans. Inform. Theory 60 (2014), no. 1, 170181.              |

| [19]   | D. Kalra, Complex equiangular cyclic frames and erasures, Linear Algebra and its Applications 419 (2006), 373-399.                                                                                               |
|--------|------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------|
| [20]   | J. Kova ˘ c evi´ c and A. Chebira, Life beyond bases: The advent of frames (Part I), IEEE SP Mag., vol. 24, no. 4 , Jul. 2007, pp. 86-104. Feature article.                                                      |
| [21]   | B. McKay, Isomorph-Free Exhaustive Generation, Journal of Algorithms, 26 (1998), 306-324.                                                                                                                        |
| [22]   | C. Mallows and N. Sloane, Two-graphs, switching classes and Euler graphs are equal in number, SIAM Journal on Applied Mathematics, 28 (1975), 876-880.                                                           |
| [23]   | OEIS Foundation Inc. (2011), The On-Line Encyclopedia of Integer Se- quences, http://oeis.org.                                                                                                                   |
| [24]   | J.J. Seidel, Asurvey of two-graphs, in: colloquio Internazionale sulle Teorie Combinatorie (Rome, 1973), Tomo I, in: Atti dei Convegni Lincei, Vol 17, Accad. Naz. Lincei, Rome, 1976, pp. 481-511.              |
| [25]   | J.J. Seidel, Geometry and combinatorics, in: Selected works of J. J. Seidel, Edited and with a preface by D. G. Corneil and R. Mathon, Academic Press, Boston, 1991.                                             |
| [26]   | J.J. Seidel and D.E. Taylor, Two-graphs, a second survey. Algebraic methods in graph theory, Vol. I, II (Szeged, 1978), pp. 689711, Colloq. Math. Soc. Jnos Bolyai, 25, North-Holland, Amsterdam-New York, 1981. |
| [27]   | F. Sz¨ll˝si, o o Complex Hadamard matrices and equianguar l tight frames. Lin- ear Algebra Appl. 438 (2013), no. 4, 1962-1967.                                                                                   |
| [28]   | T. Strohmer and R. Heath, Grassmannian frames with applications to coding and communications, Appl. Comp. Harm. Anal., 14 (2003), 257-275.                                                                       |
| [29]   | M.A. Sustik, J.A. Tropp, I.S. Dhillon, and R.W. Heath, Jr., On the existence of equiangular tight frames, Linear Algebra Appl., 426 , (2007), 619-635.                                                           |
| [30]   | J.A. Tropp, Complex equiangular tight frames, In Proc. SPIE Wavelets XI, pp. 590412.01-11, San Diego, Aug. 2005.                                                                                                 |
| [31]   | J.H. van Lint and J.J. Seidel, Equilateral point sets in elliptic geometry, Ned- erl. Akad. Wetensch. Proc. Ser. A 69=Indag. Math., 28 , (1966), 335-348.                                                        |
Thomas Hoffman James Solazzo
Complex Two-Graphs via Equiangular Tight Frames
In `A survey of two-graphs' \cite{Sei}, J.J. Seidel lays out the connections
between simple graphs, two-graphs, equiangular lines and strongly regular
graph. It is well known that there is a one-to-one correspondence between
regular two-graphs and equiangular tight frames. This article gives a
generalization of two-graphs for which these connections can be mimicked using
roots of unity beyond $\pm 1$.