betaFeedback

WorksMathematics

From Butson Hadamard switching to graph switching and back

Abstract

Switching is a local operation that preserves specified properties of a combinatorial object. It has been used to derive constructions of inequivalent Hadamard matrices and nonisomorphic cospectral graphs. In this paper we investigate the relation between these constructions for real and Butson Hadamard matrices. We show that, while equivalent matrices have isomorphic associated graphs, the converse can fail for Butson matrices. We prove that a character decomposition determines the graph spectrum from the singular values of entrywise powers. For prime phase, we also observe that the spectrum depends only on the order and phase; for composite phase, a switching preserving the Butson property can change it. We show that Orrick's closed-quadruple and Hall-set switchings correspond to Wang-Qiu-Hu switching, up to graph isomorphism. Going in the other direction, we characterise when the Godsil-McKay and Wang-Qiu-Hu reflections preserve the Butson property and give phase-multiplicity conditions for the corresponding graph switchings. Finally we also relate block switching to cyclic graph switching under a phase-balance condition, automatic at prime phase. These results provide a basis for transferring tools and techniques between matrix switching and graph switching.

2020 Mathematics Subject Classification. Primary 05B20; Secondary 05C50, 15B34.

Introduction

Switching is a local operation that changes a combinatorial object while preserving specified properties. Switching methods have been used to construct inequivalent Hadamard matrices and nonisomorphic cospectral graphs, that is, graphs with the same adjacency spectrum. We study the relation between these constructions. Our aim is to determine when matrix switching induces switching of an associated graph and how graph-switching methods yield operations on matrices.

Butson Hadamard matrices (sometimes called generalised Hadamard matrices) generalise real Hadamard matrices by allowing entries in a fixed finite group of roots of unity [5]; see [6, 9] for background. Orrick [16] introduced two switching operations for real Hadamard matrices, based on closed quadruples and Hall sets. Crnković, Egan and Švob [7] developed a common framework for switching combinatorial objects and extended these operations to Butson and complex Hadamard matrices. Related constructions include Dita’s block method [10], which gives Butson matrices when the input entries and parameters lie in a common finite group of roots of unity. Local deformations also arise from Szöllősi’s paired-column construction [17] and Goyeneche’s extension using pairs of rows or columns whose coordinatewise quotients are ±1\pm1 [13].

In spectral graph theory, Godsil–McKay switching (GM-switching) [12] and Wang–Qiu–Hu switching (WQH-switching) [18] provide methods for constructing cospectral graphs. Abiad and Peters [2] related Orrick’s operations to GM-switching on the Hadamard graphs introduced by McKay [15]. In McKay’s construction, two real Hadamard matrices are equivalent if and only if their associated graphs are isomorphic. This connection motivates extending the graph-switching approach to Butson matrices.

In this paper, we use a graph construction that we call Butson Hadamard graph (see Definition 2.1) to study equivalence, spectra and switching for Butson Hadamard matrices. Each matrix entry is replaced by a cyclic matching between a row fibre and a column fibre, with loops distinguishing the two parts. The construction includes McKay’s real case. We show that equivalent matrices have isomorphic graphs (Proposition 3.1), but the converse need not hold for Butson matrices. Field conjugates have isomorphic graphs (Proposition 3.2), and Example 3.6 gives matrices whose graphs are isomorphic even though the matrices remain inequivalent when field automorphisms and transposition are allowed.

Next we determine the graph spectra by a character decomposition in § 4. The spectrum is expressed in terms of the singular values of the entrywise powers of the matrix. For a fixed matrix order and a fixed prime phase, we prove that all associated graphs are cospectral (Theorem 4.5). A switching in a Butson Hadamard matrix of prime phase therefore preserves the graph spectrum when kk is prime. For composite phase, this conclusion need not hold; indeed, Example 6.4 gives a switching that preserves the Butson property but changes the graph spectrum. Thus the matrix conditions alone do not always suffice to obtain a corresponding graph switching.

We then study when particular switching methods can be transferred between the two settings. For real Hadamard matrices, Orrick’s closed-quadruple and Hall-set switchings correspond, up to graph isomorphism, to WQH-switching (Theorems 5.2 and 5.3). Going the other way around, and with the goal to obtain operations on Butson matrices from graph switching, we apply the reflections underlying GM- and WQH-switching. We characterise when these reflections preserve the Butson property and determine the phase-multiplicity conditions under which they induce the corresponding graph switchings on the specified partitions. For the paired WQH reflection, these graph conditions are automatic for every admissible matrix switching at prime phase (Corollary 6.14). At even phase, the WQH reflection is related to a phased GM reflection by allowed row scalings. The role of phase multiplicities also appears in block switching. Corollary 6.17 shows that the block switching of Proposition 6.1 induces the cyclic graph switching of Theorem 6.16 when each complementary row has uniform phase multiplicities. This condition is automatic at prime phase. These results provide a basis for transferring tools and techniques between matrix switching and graph switching.

This paper is organised as follows. Section 2 introduces the notation, graph construction and switching methods. Section 3 studies matrix equivalence, graph isomorphism and reconstruction. Section 4 determines the spectra of the associated graphs. Section 5 establishes the correspondence between Orrick’s switchings and suitable WQH-switchings. Section 6 studies the GM and WQH reflections for Butson matrices, the corresponding graph switchings, and cyclic switching for balanced blocks. Section 7 discusses further questions.

Preliminaries

Notation and Butson Hadamard matrices

Throughout we write Zk=Z/kZ\mathbb{Z}_k = \mathbb{Z}/k\mathbb{Z}, ζk=e2πi/k\zeta_k = e^{2\pi i/k}, and μk={1,ζk,…,ζkk−1}\mu_k = \{1,\zeta_k,\ldots,\zeta_k^{k-1}\}. An n×nn \times n matrix HH with entries in μk\mu_k such that HH∗=nInHH^* = nI_n is Butson Hadamard of order nn and phase kk, where H∗H^* denotes the complex conjugate transpose of HH. The set of all such matrices is denoted by BH⁡(n,k)\operatorname{BH}(n,k). An element of BH⁡(n,2)\operatorname{BH}(n,2) is a Hadamard matrix, and will sometimes be referred to as a real Hadamard matrix to emphasise this case. A complex Hadamard matrix satisfies the same orthogonality condition and has entries of absolute value one, without the requirement that they are roots of unity. Real Hadamard matrices have order 1, 2, or a multiple of 4. We use kk as a specified phase; it need not always be the least phase containing all entries of HH.

Matrix rows and columns are indexed from 0 to n−1n-1, unless a local block indexing is specified. Indices in Zk\mathbb{Z}_k are always read modulo kk. We write IsI_s, Js,tJ_{s,t} and Os,tO_{s,t} for the identity, all-one and zero matrices of the indicated sizes, and abbreviate Js,sJ_{s,s} and Os,sO_{s,s} to JsJ_s and OsO_s. The vector 1s\mathbf{1}_s is the column vector of ss ones. In a small number of instances, by abuse of notation 1X\mathbf{1}_X will also denote a binary characteristic vector in R∣S∣\mathbb{R}^{|S|} for some subset X⊆SX \subseteq S, and this will be stated or clear from context in those instances. The symbols ⊗\otimes and ⊕\oplus denote the Kronecker product and the direct sum, respectively. The Hadamard product A∘BA \circ B is the entrywise product of matrices of the same size. For a matrix with entries in μk\mu_k, we write

A(ℓ)=(aijℓ)i,j(ℓ∈Z)A^{(\ell)} = (a_{ij}^{\ell})_{i,j}\qquad(\ell\in\mathbb{Z})

for its entrywise ℓ\ellth power. In particular, A(0)A^{(0)} is an all-ones matrix. The parentheses distinguish entrywise powers from ordinary matrix powers. The spectrum spec⁡(A)\operatorname{spec}(A) is the multiset of eigenvalues of AA, counted with algebraic multiplicity. Unions of spectra are understood as multiset unions.

Two matrices H,K∈BH⁡(n,k)H,K \in\operatorname{BH}(n,k) are equivalent if

K=MHN∗K = MHN^*

for monomial matrices M,NM,N whose nonzero entries belong to μk\mu_k. A monomial matrix has exactly one nonzero entry in each row and each column. Thus equivalence allows row and column permutations and multiplication of individual rows and columns by elements of μk\mu_k. We call HH normalised if its first row and first column consist entirely of ones. Every Butson Hadamard matrix is equivalent to a normalised one.

For ℓ\ell coprime to kk, the map ζk↦ζkℓ\zeta_k \mapsto\zeta_k^\ell is a field automorphism of Q(ζk)\mathbb{Q}(\zeta_k) and sends HH to another matrix H(ℓ)∈BH⁡(n,k)H^{(\ell)} \in\operatorname{BH}(n,k). We distinguish this operation, and transposition, from the equivalence relation just defined. When we allow both in addition to monomial equivalence, we refer explicitly to extended equivalence.

Graphs associated with phase matrices

All graphs in this paper are finite and undirected, with no multiple edges. We allow loops when explicitly stated. A loop contributes a diagonal entry 1 to the adjacency matrix and is counted once in the neighbourhood of its vertex. For a graph GG, a vertex vv and a subset S⊆V(G)S \subseteq V(G), we write

NG(v)={u∈V(G):u is adjacent to v},dS(v)=∣NG(v)∩S∣.N_G(v) = \{u \in V(G): u\text{ is adjacent to }v\},\qquad d_S(v) = |N_G(v) \cap S|.

We omit the subscript GG when the graph is clear. The spectrum of a graph is the spectrum of its adjacency matrix. Two graphs are cospectral if their spectra agree, and are cospectral mates if they are also nonisomorphic.

Let PkP_k be the permutation matrix indexed by Zk\mathbb{Z}_k with

(Pk)a,b=1⟺b=a+1.(P_k)_{a,b}=1 \Longleftrightarrow b=a+1.

Thus PkP_k is the circulant permutation matrix with first row (0,1,0,…,0)(0,1,0,\ldots,0). The map

ϕk:μk⟶⟨Pk⟩,ϕk(ζka)=Pka\phi_k:\mu_k\longrightarrow\langle P_k\rangle,\qquad\phi_k(\zeta_k^a)=P_k^a

is the regular permutation representation of μk\mu_k. For a matrix HH with entries in μk\mu_k, we write

ϕk(H)=(ϕk(hij))i,j.\phi_k(H)=(\phi_k(h_{ij}))_{i,j}.

This is a block substitution. We do not regard ϕk\phi_k as an additive map on complex numbers. Where a monomial matrix is involved, we set ϕk(0)=Ok\phi_k(0)=O_k; products with monomial matrices then respect this substitution because each contributing entry is a single product. We often omit the subscript kk when the phase is fixed.

Definition 2.1. Let H=(ζkeij)∈μkn×nH=(\zeta_k^{e_{ij}})\in\mu_k^{n\times n}. The graph GHG_H has vertex set R∪˙C\mathcal{R}\mathbin{\dot\cup}\mathcal{C}, where

R={Ri,a:0≤i<n, a∈Zk},C={Cj,b:0≤j<n, b∈Zk}.\mathcal{R}=\{R_{i,a}:0\le i<n,\ a\in\mathbb{Z}_k\},\qquad \mathcal{C}=\{C_{j,b}:0\le j<n,\ b\in\mathbb{Z}_k\}.

Its edges between the two parts are given by

Ri,a∼Cj,b⟺b−a=eij in Zk.(1)R_{i,a}\sim C_{j,b}\Longleftrightarrow b-a=e_{ij}\text{ in }\mathbb{Z}_k. \tag*{(1)}

Every vertex in R\mathcal{R} has a loop, and there are no other edges. If H∈BH⁡(n,k)H\in\operatorname{BH}(n,k), we call GHG_H the Butson Hadamard graph associated with HH.

We always use the vertex order

R0,0,…,R0,k−1,…,Rn−1,k−1,C0,0,…,C0,k−1,…,Cn−1,k−1.(2)R_{0,0},\ldots,R_{0,k-1},\ldots,R_{n-1,k-1},C_{0,0},\ldots,C_{0,k-1},\ldots,C_{n-1,k-1}. \tag*{(2)}

With this convention, the adjacency matrix is

MH=(Inkϕk(H)ϕk(H)TOnk).(3)\mathcal{M}_H= \begin{pmatrix} I_{nk} & \phi_k(H)\\ \phi_k(H)^{\mathsf{T}} & O_{nk} \end{pmatrix}. \tag*{(3)}

The graph obtained from GHG_H by deleting the loops is bipartite, with parts R\mathcal{R} and C\mathcal{C}. The loops in GHG_H distinguish the row part from the column part under graph isomorphism.

For each row ii and column jj, the sets

Ri={Ri,a:a∈Zk},Cj={Cj,b:b∈Zk}R_i=\{R_{i,a}:a\in\mathbb{Z}_k\},\qquad C_j=\{C_{j,b}:b\in\mathbb{Z}_k\}

are called the row fibres and column fibres. Each pair Ri,CjR_i,C_j induces a perfect matching. The simultaneous translation Ri,a↦Ri,a+cR_{i,a}\mapsto R_{i,a+c}, Cj,b↦Cj,b+cC_{j,b}\mapsto C_{j,b+c} preserves adjacency. If HH is normalised, then R0,a∼Cj,aR_{0,a}\sim C_{j,a} and Ri,a∼C0,aR_{i,a}\sim C_{0,a} for every ii, jj and aa.

When k=2k=2, we recover McKay’s graph [15]: the two copies of row ii are Ri,0R_{i,0} and Ri,1R_{i,1}, the two copies of column jj are Cj,0C_{j,0} and Cj,1C_{j,1}, and a negative entry interchanges the corresponding matching. We use the same vertex notation in the real and complex cases.

Construction of cospectral graphs via GM-switching and WQH-switching

We recall the two graph-switching methods used below. Their usual matrix proofs also apply under our loop convention.

Theorem 2.2 (GM-switching [12]). Let {X1,…,Xt,D}\{X_1,\ldots,X_t,D\} be a partition of V(G)V(G) such that:

(i) for every i,ji,j, the number dXj(v)d_{X_j}(v) is independent of the choice of v∈Xiv\in X_i;

(ii) for every v∈Dv\in D and every ii, the number dXi(v)d_{X_i}(v) belongs to {0,∣Xi∣/2,∣Xi∣}\{0,|X_i|/2,|X_i|\}.

For every v∈Dv\in D with dXi(v)=∣Xi∣/2d_{X_i}(v)=|X_i|/2, reverse all adjacencies between vv and XiX_i. The resulting graph is cospectral with GG.

The orthogonal matrix underlying this operation acts on each XiX_i as the reflection

Qs=2sJs−Is(s=∣Xi∣)(4)Q_s=\frac{2}{s}J_s-I_s \qquad(s=|X_i|) \tag*{(4)}

and as the identity on DD. We have QsT=QsQ_s^{\mathsf{T}}=Q_s, Qs2=IsQ_s^2=I_s and Qs1s=1sQ_s1_s=1_s.

Theorem 2.3 (WQH-switching [18]). Let

{D,X1+,X1−,…,Xt+,Xt−}\{D,X_1^+,X_1^-,\ldots,X_t^+,X_t^-\}

be a partition of V(G)V(G) such that, for every i,ji,j:

(i) ∣Xi+∣=∣Xi−∣|X_i^+|=|X_i^-|;

(ii) there is a constant cijc_{ij} satisfying

{dXj+(v)−dXj−(v)=cij,v∈Xi+,dXj−(v)−dXj+(v)=cij,v∈Xi−;\begin{cases} d_{X_j^+}(v)-d_{X_j^-}(v)=c_{ij}, & v\in X_i^+,\\ d_{X_j^-}(v)-d_{X_j^+}(v)=c_{ij}, & v\in X_i^-; \end{cases}

(iii) every vertex v∈Dv\in D is adjacent to all vertices of one of Xi+,Xi−X_i^+,X_i^- and none of the other, or satisfies dXi+(v)=dXi−(v)d_{X_i^+}(v)=d_{X_i^-}(v).

Whenever a vertex of DD is adjacent to all of one of Xi+,Xi−X_i^+,X_i^- and none of the other, interchange these two neighbourhoods. The resulting graph is cospectral with GG.

Remark 2.4. For t=1t=1, the conditions concern a pair (X+,X−)(X^+,X^-) of equally sized sets. The difference between the number of neighbours in a vertex’s own set and in the other set must be constant on X+∪X−X^+\cup X^-. Every remaining vertex must have either equal numbers of neighbours in the two sets, or all of one set and none of the other. We use this form for closed-quadruple switching. Hall-set switching requires two pairs of sets.

For completeness, the loop convention can be checked directly in the matrix formulation. Put si=∣Xi+∣s_i=|X_i^+| and zi=1Xi+−1Xi−z_i=1_{X_i^+}-1_{X_i^-}, where the latter are characteristic vectors in R∣V(G)∣\mathbb{R}^{|V(G)|}. The WQH conjugating matrix is

W=I−∑i=1t1siziziT.W=I-\sum_{i=1}^{t}\frac{1}{s_i}z_i z_i^{\mathsf{T}}.

The vectors ziz_i have disjoint supports and squared norm 2si2s_i, so WW is orthogonal. Condition (ii) ensures that the adjacency block on the switching sets is fixed by conjugation. Condition (iii) makes the remaining blocks either fixed or switched as prescribed. Thus loops are included by counting their diagonal entries once, just as in the stated neighbourhood conditions.

Construction of unequivalent Hadamard matrices via Closed quadruples and Hall set switching methods

We recall Orrick’s two switching operations [16]. Let hih_i denote row ii of a real Hadamard matrix HH.

Definition 2.5. A Hadamard matrix is 3-normalised on three distinct rows i,j,ℓi,j,\ell if hi∘hj∘hℓ=1nTh_i \circ h_j \circ h_\ell= \mathbf{1}_n^{\mathsf{T}}. A set of four distinct rows is a closed quadruple if their Hadamard product is ±1nT\pm\mathbf{1}_n^{\mathsf{T}}.

After equivalence operations, a Hadamard matrix with a closed quadruple can be written as

H=(1mT−1mT−1mT1mT1mT−1mT1mT−1mT1mT1mT−1mT−1mT1mT1mT1mT1mT),m=n/4.(5)H = \begin{pmatrix} \mathbf{1}_m^{\mathsf{T}} & -\mathbf{1}_m^{\mathsf{T}} & -\mathbf{1}_m^{\mathsf{T}} & \mathbf{1}_m^{\mathsf{T}} \\ \mathbf{1}_m^{\mathsf{T}} & -\mathbf{1}_m^{\mathsf{T}} & \mathbf{1}_m^{\mathsf{T}} & -\mathbf{1}_m^{\mathsf{T}} \\ \mathbf{1}_m^{\mathsf{T}} & \mathbf{1}_m^{\mathsf{T}} & -\mathbf{1}_m^{\mathsf{T}} & -\mathbf{1}_m^{\mathsf{T}} \\ \mathbf{1}_m^{\mathsf{T}} & \mathbf{1}_m^{\mathsf{T}} & \mathbf{1}_m^{\mathsf{T}} & \mathbf{1}_m^{\mathsf{T}} \end{pmatrix}, \qquad m=n/4. \tag*{(5)}

The four sets of mm columns are called fields. Orthogonality implies that every row of each AaA_a has sum zero. Consequently, if n>4n>4, then mm is even and nn is divisible by 8.

Definition 2.6. Switching a closed quadruple means negating the entries in the four selected rows within one field.

Theorem 2.7 (Orrick [16]). Switching a closed quadruple produces a Hadamard matrix. The four choices of field produce equivalent matrices.

For n>4n>4, a Hall set of rows consists of four rows that can be 3-normalised on three of them so that the fourth row has one exceptional sign in each field. Equivalently, their Hadamard product has exactly four entries of one sign and all remaining entries of the other sign. The columns containing these four exceptional entries are the Hall columns. For orders divisible by 8, the Hall columns form a closed quadruple; for orders congruent to 4 modulo 8, they form a Hall set [16]. We use Hall set for the four rows together with their Hall columns in the latter case.

For n=4m+4≥12n=4m+4\geq12, with mm even, a Hadamard matrix containing a Hall set is equivalent to one of the form

H=(S4F1F2F3F4G1A11A12A13A14G2A21A22A23A24G3A31A32A33A34G4A41A42A43A44).(6)H = \begin{pmatrix} S_4 & F_1 & F_2 & F_3 & F_4 \\ G_1 & A_{11} & A_{12} & A_{13} & A_{14} \\ G_2 & A_{21} & A_{22} & A_{23} & A_{24} \\ G_3 & A_{31} & A_{32} & A_{33} & A_{34} \\ G_4 & A_{41} & A_{42} & A_{43} & A_{44} \end{pmatrix}. \tag*{(6)}

Here S4=2I4−J4S_4=2I_4-J_4, Fa=fa1mTF_a=f_a\mathbf{1}_m^{\mathsf{T}}, where

f1=(1111),f2=(1−1−11),f3=(1−11−1),f4=(−1−111),f_1= \begin{pmatrix} 1\\ 1\\ 1\\ 1 \end{pmatrix}, \qquad f_2= \begin{pmatrix} 1\\ -1\\ -1\\ 1 \end{pmatrix}, \qquad f_3= \begin{pmatrix} 1\\ -1\\ 1\\ -1 \end{pmatrix}, \qquad f_4= \begin{pmatrix} -1\\ -1\\ 1\\ 1 \end{pmatrix},

and G1=F1TG_1=F_1^{\mathsf{T}}, Ga=−FaTG_a=-F_a^{\mathsf{T}} for a=2,3,4a=2,3,4. Each AabA_{ab} is an m×mm \times m matrix whose row and column sums are 2 if a=ba=b and 0 otherwise.

Definition 2.8. Switching a Hall set is negating FaF_a and GaG_a for one a∈{1,2,3,4}a\in\{1,2,3,4\} in (6).

Theorem 2.9 (Orrick [16]). Switching a Hall set produces a Hadamard matrix. The four choices of the pair (Fa,Ga)(F_a,G_a) produce equivalent matrices.

Equivalence and reconstruction

We first describe the relation between equivalence of phase matrices and isomorphism of their associated graphs. The graph construction retains monomial equivalence, but it also identifies matrices related by field automorphisms.

Proposition 3.1. If H,K∈BH(n,k)H,K \in\mathrm{BH}(n,k) are equivalent, then GHG_H and GKG_K are isomorphic.

Proof. Write K=MHN∗K = MHN^{*}, where M,NM,N are monomial matrices with nonzero entries in μk\mu_k. Their block substitutions ϕk(M)\phi_k(M) and ϕk(N)\phi_k(N) are permutation matrices, and

ϕk(K)=ϕk(M)ϕk(H)ϕk(N)T.\phi_k(K) = \phi_k(M)\phi_k(H)\phi_k(N)^{\mathsf{T}}.

Consequently,

MK=(ϕk(M)⊕ϕk(N))MH(ϕk(M)⊕ϕk(N))T.\mathcal{M}_K = \left(\phi_k(M) \oplus\phi_k(N)\right)\mathcal{M}_H\left(\phi_k(M) \oplus\phi_k(N)\right)^{\mathsf{T}}.

This permutation similarity gives the required isomorphism.

Proposition 3.2. Let H∈BH(n,k)H \in\mathrm{BH}(n,k) and let ℓ\ell be coprime to kk. Then GHG_H and GH(ℓ)G_{H^{(\ell)}} are isomorphic.

Proof. Relabel every phase index by multiplication by ℓ\ell:

Ri,a⟼Ri,ℓa,Cj,b⟼Cj,ℓb.R_{i,a} \longmapsto R_{i,\ell a}, \qquad C_{j,b} \longmapsto C_{j,\ell b}.

If hij=ζkeijh_{ij} = \zeta_k^{e_{ij}}, then b−a=eijb-a=e_{ij} is equivalent to ℓb−ℓa=ℓeij\ell b-\ell a=\ell e_{ij} in Zk\mathbb{Z}_k. The relabelling therefore preserves adjacency and loops, and gives an isomorphism from GHG_H to GH(ℓ)G_{H^{(\ell)}}.

Deleting the loops also removes the distinction between rows and columns. In fact,

Ri,a⟼Ci,−a,Cj,b⟼Rj,−bR_{i,a} \longmapsto C_{i,-a}, \qquad C_{j,b} \longmapsto R_{j,-b}

is an isomorphism from the graph of HH to the graph of HTH^{\mathsf{T}} with loops removed. With loops retained, an isomorphism must preserve the two parts.

Proposition 3.3. Let H,K∈BH(n,k)H,K \in\mathrm{BH}(n,k). Every permutation matrix PP satisfying PMHPT=MKP\mathcal{M}_H P^{\mathsf{T}}=\mathcal{M}_K has the form P=P⊕QP=P\oplus Q, where P,QP,Q are permutation matrices of order nknk satisfying

Pϕk(H)QT=ϕk(K).P\phi_k(H)Q^{\mathsf{T}}=\phi_k(K).

Proof. The vertices in R\mathcal{R} are precisely the vertices carrying loops, so every isomorphism preserves R\mathcal{R} and C\mathcal{C}. The stated identity follows by comparing the off-diagonal blocks of the adjacency matrices.

Theorem 3.4 (McKay [15]). Two real Hadamard matrices are equivalent if and only if their associated graphs are isomorphic.

Remark 3.5. For real Hadamard matrices, the loopless graphs are isomorphic if and only if the matrices are equivalent after possibly transposing one of them [15]. For general phase, Proposition 3.2 shows that the graph also identifies field conjugates. Moreover, Proposition 3.3 only gives arbitrary permutation matrices P,QP,Q of order nknk; it does not require them to arise from monomial matrices of order nn. Thus graph isomorphism alone does not establish monomial equivalence. This distinction is also relevant in algorithms for testing Butson equivalence; see [11 Section 3].

Example 3.6. We give an example in exponent form. Let H=((ζ4(EH)ij))H = ((\zeta_{4}^{(E_H)_{ij}})) and K=((ζ4(EK)ij))K = ((\zeta_{4}^{(E_K)_{ij}})), where

EH=(000000000000000000222222001223001223001223223001013022013022013022231200021302021302021302203120023210023210023210201032032131032131032131210313),E_H = \begin{pmatrix} 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 2 & 2 & 2 & 2 & 2 & 2 \\ 0 & 0 & 1 & 2 & 2 & 3 & 0 & 0 & 1 & 2 & 2 & 3 \\ 0 & 0 & 1 & 2 & 2 & 3 & 2 & 2 & 3 & 0 & 0 & 1 \\ 0 & 1 & 3 & 0 & 2 & 2 & 0 & 1 & 3 & 0 & 2 & 2 \\ 0 & 1 & 3 & 0 & 2 & 2 & 2 & 3 & 1 & 2 & 0 & 0 \\ 0 & 2 & 1 & 3 & 0 & 2 & 0 & 2 & 1 & 3 & 0 & 2 \\ 0 & 2 & 1 & 3 & 0 & 2 & 2 & 0 & 3 & 1 & 2 & 0 \\ 0 & 2 & 3 & 2 & 1 & 0 & 0 & 2 & 3 & 2 & 1 & 0 \\ 0 & 2 & 3 & 2 & 1 & 0 & 2 & 0 & 1 & 0 & 3 & 2 \\ 0 & 3 & 2 & 1 & 3 & 1 & 0 & 3 & 2 & 1 & 3 & 1 \\ 0 & 3 & 2 & 1 & 3 & 1 & 2 & 1 & 0 & 3 & 1 & 3 \end{pmatrix},
EK=(000000000000000000222222001223001223001223223001013022021032013022203210021302103022021302321200023210013202023210231020032131130231032131312013).E_K = \begin{pmatrix} 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 2 & 2 & 2 & 2 & 2 & 2 \\ 0 & 0 & 1 & 2 & 2 & 3 & 0 & 0 & 1 & 2 & 2 & 3 \\ 0 & 0 & 1 & 2 & 2 & 3 & 2 & 2 & 3 & 0 & 0 & 1 \\ 0 & 1 & 3 & 0 & 2 & 2 & 0 & 2 & 1 & 0 & 3 & 2 \\ 0 & 1 & 3 & 0 & 2 & 2 & 2 & 0 & 3 & 2 & 1 & 0 \\ 0 & 2 & 1 & 3 & 0 & 2 & 1 & 0 & 3 & 0 & 2 & 2 \\ 0 & 2 & 1 & 3 & 0 & 2 & 3 & 2 & 1 & 2 & 0 & 0 \\ 0 & 2 & 3 & 2 & 1 & 0 & 0 & 1 & 3 & 2 & 0 & 2 \\ 0 & 2 & 3 & 2 & 1 & 0 & 2 & 3 & 1 & 0 & 2 & 0 \\ 0 & 3 & 2 & 1 & 3 & 1 & 1 & 3 & 0 & 2 & 3 & 1 \\ 0 & 3 & 2 & 1 & 3 & 1 & 3 & 1 & 2 & 0 & 1 & 3 \end{pmatrix}.

Both matrices belong to BH⁡(12,4)\operatorname{BH}(12,4). Their graphs are isomorphic, although the matrices are inequivalent up to extended equivalence incorporating field automorphisms and transpose.

Recovering a matrix from its graph

The labelled fibres in Definition 2.1 record more information than an unlabelled graph. For prime phase, a common-neighbour condition characterises when a phase matrix recovered from these fibres is Hadamard. We require the following result of Lam and Leung [14].

Lemma 3.7. Let kk be prime and let c0,…,ck−1c_0,\ldots,c_{k-1} be nonnegative integers. Then

∑a=0k−1caζka=0⟺c0=⋯=ck−1.\sum_{a=0}^{k-1} c_a \zeta_k^a = 0 \quad\Longleftrightarrow\quad c_0 = \cdots= c_{k-1}.

Proposition 3.8. Let kk be prime. Let GG have labelled vertex set R∪C\mathcal{R} \cup\mathcal{C} as in Definition 2.1, with loops at all row vertices, no other edges within either part, and the following properties:

(i) each pair Ri,CjR_i,C_j induces a perfect matching;

(ii) the simultaneous translation of all phase indices by 11 preserves adjacency;

(iii) vertices in distinct row fibres have exactly n/kn/k common neighbours.

Then G=GHG = G_H for a unique H∈BH⁡(n,k)H \in\operatorname{BH}(n,k) in the given labelling. Conversely, every graph GHG_H with H∈BH⁡(n,k)H \in\operatorname{BH}(n,k) has these properties.

Proof. By (i) and (ii), the matching between RiR_i and CjC_j is given by a unique shift eij∈Zke_{ij} \in\mathbb{Z}_k. Set hij=ζkeijh_{ij}=\zeta_k^{e_{ij}}. This recovers the adjacency rule (1) and determines HH uniquely.

Fix distinct row indices i,i′i,i'. The number of common neighbours of Ri,aR_{i,a} and Ri′,bR_{i',b} is

#{j:eij−ei′j=b−a}.(7)\#\{j:e_{ij}-e_{i'j}=b-a\}. \tag*{(7)}

Condition (iii) says that every phase occurs n/kn/k times among the ratios hijhi′j‾h_{ij}\overline{h_{i'j}}. Their sum is therefore zero. Hence distinct rows are orthogonal and HH∗=nInHH^*=nI_n.

Conversely, (i) and (ii) follow from the construction. If HH is Hadamard, orthogonality and Lemma 3.7 show that every ratio occurs n/kn/k times. Equation (7) then gives (iii).

Spectra of Butson Hadamard graphs

We now determine the spectrum of GHG_H. The key observation is that the regular representation separates into the characters of μk\mu_k, so the relevant matrices are the entrywise powers of HH. Denote the k×kk \times k Fourier matrix by Fk=(ζkab)a,b∈ZkF_k=(\zeta_k^{ab})_{a,b\in\mathbb{Z}_k}.

Proposition 4.1. For every H∈μkn×nH\in\mu_k^{n\times n}, the matrix ϕk(H)\phi_k(H) is unitarily similar to

⨁ℓ=0k−1H(ℓ)=Jn⊕H⊕⋯⊕H(k−1).(8)\bigoplus_{\ell=0}^{k-1}H^{(\ell)}=J_n\oplus H\oplus\cdots\oplus H^{(k-1)}. \tag*{(8)}

In particular,

spec⁡(ϕk(H))=⋃ ⁣+ℓ=0k−1spec⁡(H(ℓ)).\operatorname{spec}(\phi_k(H))=\mathop{\bigcup\nolimits^{\mkern-5mu+}}_{\ell=0}^{k-1}\operatorname{spec}(H^{(\ell)}).

Proof. The unitary Fourier matrix k−1/2Fkk^{-1/2}F_k diagonalises PkP_k [8]:

1kFk∗PkFk=diag⁡(1,ζk,…,ζkk−1).\frac{1}{k}F_k^*P_kF_k=\operatorname{diag}(1,\zeta_k,\ldots,\zeta_k^{k-1}).

Conjugating ϕk(H)\phi_k(H) by In⊗(k−1/2Fk)I_n\otimes(k^{-1/2}F_k) replaces its (i,j)(i,j) block by diag⁡(1,hij,…,hijk−1)\operatorname{diag}(1,h_{ij},\ldots,h_{ij}^{k-1}). Reordering the coordinates by character gives (8).

Corollary 4.2. Let H,K∈BH⁡(n,k)H,K\in\operatorname{BH}(n,k). If

⋃ ⁣+ℓ=1k−1spec⁡(H(ℓ))=⋃ ⁣+ℓ=1k−1spec⁡(K(ℓ)),\mathop{\bigcup\nolimits^{\mkern-5mu+}}_{\ell=1}^{k-1}\operatorname{spec}(H^{(\ell)})=\mathop{\bigcup\nolimits^{\mkern-5mu+}}_{\ell=1}^{k-1}\operatorname{spec}(K^{(\ell)}),

then ϕk(H)\phi_k(H) and ϕk(K)\phi_k(K) are cospectral. If kk is prime, it is sufficient that HH and K(r)K^{(r)} are cospectral for some 1≤r<k1\le r<k.

Proof. The first assertion follows from Proposition 4.1. For the second, equality of the spectra gives equality of the characteristic polynomials over Q(ζk)\mathbb{Q}(\zeta_k). Applying each field automorphism ζk↦ζkℓ\zeta_k\mapsto\zeta_k^\ell gives equality of the characteristic polynomials of H(ℓ)H^{(\ell)} and K(rℓ)K^{(r\ell)}. Since multiplication by rr permutes the nonzero residues modulo the prime kk, taking the multiset union proves the claim.

The spectrum of MHM_H depends on the singular values of ϕk(H)\phi_k(H), rather than on its eigenvalues. The unitary form of Proposition 4.1 makes this distinction explicit.

Proposition 4.3. For H∈BH(n,k)H \in\mathrm{BH}(n,k), the multiset of squared singular values of ϕk(H)\phi_k(H) is

⨄ℓ=0k−1spec⁡(H(ℓ)(H(ℓ))∗).(9)\biguplus_{\ell=0}^{k-1}\operatorname{spec}\left(H^{(\ell)}\left(H^{(\ell)}\right)^{*}\right). \tag*{(9)}

If kk is prime, these values are n2n^2 once, 00 with multiplicity n−1n-1, and nn with multiplicity n(k−1)n(k-1).

Proof. Unitary similarity in Proposition 4.1 preserves singular values, giving (9). The block for ℓ=0\ell=0 is JnJnT=nJnJ_nJ_n^{\mathsf{T}}=nJ_n. If kk is prime, each nonzero ℓ\ell gives a field automorphism, so H(ℓ)(H(ℓ))∗=nInH^{(\ell)}(H^{(\ell)})^*=nI_n.

Proposition 4.4. Let σ1,…,σnk\sigma_1,\ldots,\sigma_{nk} be the singular values of ϕk(H)\phi_k(H), with multiplicities. Then the eigenvalues of MH\mathcal{M}_H are

1+1+4σj22,1−1+4σj22(1≤j≤nk).(10)\frac{1+\sqrt{1+4\sigma_j^2}}{2},\qquad\frac{1-\sqrt{1+4\sigma_j^2}}{2}\qquad(1\leq j\leq nk). \tag*{(10)}

The eigenvalues of the graph without loops are σj\sigma_j and −σj-\sigma_j for the same indices.

Proof. Take a real singular value decomposition UTϕk(H)V=ΣU^{\mathsf{T}}\phi_k(H)V=\Sigma. Conjugation by U⊕VU\oplus V changes (3) into

(InkΣΣOnk)\begin{pmatrix} I_{nk} & \Sigma\\ \Sigma& O_{nk} \end{pmatrix}

After reordering coordinates, this is the direct sum of the matrices (1σjσj0)\begin{pmatrix}1&\sigma_j\\\sigma_j&0\end{pmatrix}, whose characteristic polynomials are x2−x−σj2x^2-x-\sigma_j^2. Deleting the loops replaces the diagonal entry 11 by 00 and gives eigenvalues ±σj\pm\sigma_j.

Theorem 4.5. Let kk be prime and let H∈BH(n,k)H\in\mathrm{BH}(n,k). The spectrum of GHG_H is given in Table 1. In particular, all graphs associated with matrices in BH(n,k)\mathrm{BH}(n,k) are cospectral.

Eigenvalue011+1+4n22\frac{1+\sqrt{1+4n^2}}{2}1−1+4n22\frac{1-\sqrt{1+4n^2}}{2}1+1+4n2\frac{1+\sqrt{1+4n}}{2}1−1+4n2\frac{1-\sqrt{1+4n}}{2}
Multiplicityn−1n-1n−1n-111n(k−1)n(k-1)n(k−1)n(k-1)

Table 1. Spectrum of GHG_H for H∈BH(n,k)H\in\mathrm{BH}(n,k) with kk prime.

Proof. Combine Propositions 4.3 and 4.4.

For composite kk, the blocks with gcd⁡(ℓ,k)=1\gcd(\ell,k)=1 still equal nInnI_n in (9), but the remaining blocks need not do so. Thus 00 and 11 have multiplicity at least n−1n-1, the two values (1±1+4n2)/2(1\pm\sqrt{1+4n^2})/2 occur at least once each, and (1±1+4n)/2(1\pm\sqrt{1+4n})/2 each have multiplicity at least nφ(k)n\varphi(k), where φ\varphi is Euler’s totient function. These contributions are added if values coincide. The nonunit exponents determine any additional contributions. Example 6.4 shows that the spectrum can then change under a switching that preserves the Butson property.

WQH-switching and Orrick’s Hadamard switchings

We now show that the two switching operations to construct Hadamard matrices in Section 2.4 can be realised by WQH-switching on the associated Hadamard graphs. The switching sets are chosen from the phase copies of the fields in the relevant normal forms.

Switching a closed quadruple

An arbitrary graph switching need not preserve the class of Hadamard graphs. The following example explains why a suitable switching partition is essential.

Example 5.1. Let HH be the Sylvester Hadamard matrix of order 16, indexed by x,y∈F2x,y \in\mathbb{F}_2, with hx,y=(−1)x⋅yh_{x,y}=(-1)^{x\cdot y}. Write e1,e2e_1,e_2 for the first two standard basis vectors. The sets

X+={R0,0,Re1,0},X−={Re2,1,Re1+e2,1}X^+ = \{R_{0,0},R_{e_1,0}\}, \qquad X^- = \{R_{e_2,1},R_{e_1+e_2,1}\}

satisfy the one-pair WQH conditions: they contain only their own loops, and a column vertex has either one neighbour in each set or two in one set and none in the other.

The all-or-none case occurs precisely for the four columns with y1=y2=0y_1=y_2=0. Before switching, R0,0R_{0,0} and Re2,0R_{e_2,0} have eight common neighbours. The switching removes four of these and adds no new common neighbours to this pair. They therefore have four common neighbours in the switched graph. In a Hadamard graph of order 16, distinct looped vertices have either zero common neighbours, if they belong to the same row fibre, or eight, if they belong to different fibres. Hence the switched graph is not isomorphic to any Hadamard graph of order 16.

Theorem 5.2. Let HH be a Hadamard matrix of order n>4n>4 with a closed quadruple, and let H′H' be obtained by switching that quadruple. Then GH′G_{H'} is isomorphic to a graph obtained from GHG_H by WQH-switching.

Proof. By Theorems 2.7 and 3.4, it suffices to take HH in the form (5) and negate its initial 4×m4 \times m block, where m=n/4m=n/4. Let

X+={Cj,0:0≤j<m},X−={Cj,1:0≤j<m}.X^+ = \{C_{j,0}:0 \leq j < m\}, \qquad X^- = \{C_{j,1}:0 \leq j < m\}.

These are equally sized independent sets, with no edges between them. For a∈Z2a \in\mathbb{Z}_2, put Ua={Ri,a:0≤i<4}U^a=\{R_{i,a}:0 \leq i < 4\}. Every vertex of U0U^0 is adjacent to all of X+X^+ and none of X−X^-; every vertex of U1U^1 has the reverse neighbourhood.

Every row of A1A_1 in (5) has sum zero, so every other row vertex has m/2m/2 neighbours in each of X+X^+ and X−X^-. The remaining column vertices have no neighbours in either set. The one-pair WQH conditions therefore hold. Switching interchanges exactly the matchings between the first four row fibres and the first mm column fibres. By (1), this negates the initial 4×m4 \times m block and gives GH′G_{H'}.

Switching a Hall set

Theorem 5.3. Let HH be a Hadamard matrix of order n≥12n \geq12, with n≡4(mod8)n \equiv4 \pmod{8}, containing a Hall set. If H′H' is obtained by switching that Hall set, then GH′G_{H'} is isomorphic to a graph obtained from GHG_H by WQH-switching.

Proof. Use the normal form (6), with m=(n−4)/4m=(n-4)/4. By Theorems 2.9 and 3.4, it suffices to negate F1F_1 and G1G_1. Define

X1+={Cj,0:4≤j<m+4},X1−={Cj,1:4≤j<m+4},X_1^+ = \{C_{j,0}:4 \leq j < m+4\}, \qquad X_1^- = \{C_{j,1}:4 \leq j < m+4\},
X2+={Ri,0:4≤i<m+4},X2−={Ri,1:4≤i<m+4},X_2^+ = \{R_{i,0}:4 \leq i < m+4\}, \qquad X_2^- = \{R_{i,1}:4 \leq i < m+4\},

and let DD consist of the remaining vertices. The four sets above have size mm.

We check condition (ii) of Theorem 2.3 for the two pairs (X1+,X1−)(X_1^+,X_1^-) and (X2+,X2−)(X_2^+,X_2^-). There are no edges within the column part, while every row vertex has its own loop and no other row neighbour. The corresponding difference constants are therefore c11=0c_{11}=0 and c22=1c_{22}=1.

::: Since every row and column of A11A_{11} has sum 2, each contains m/2+1m/2+1 positive entries and m/2−1m/2-1 negative entries. Hence the two cross-difference constants are c12=c21=2c_{12}=c_{21}=2.

For a∈Z2a\in\mathbb{Z}_2, put

Ua={Ri,a:0≤i<4},Va={Cj,a:0≤j<4}.U^a=\{R_{i,a}:0\le i<4\},\qquad V^a=\{C_{j,a}:0\le j<4\}.

The all-one blocks F1,G1F_1,G_1 imply that U0U^0 is complete to X1+X_1^+ and anticomplete to X1−X_1^-, while U1U^1 has the reverse neighbourhood. Similarly, V0V^0 is complete to X2+X_2^+ and anticomplete to X2−X_2^-, and V1V^1 has the reverse neighbourhood. These vertices have no neighbours in the other pair of switching sets.

All other vertices of DD are balanced on each pair. Indeed, the relevant off-diagonal blocks Aa1A_{a1} and A1aA_{1a} have row and column sums zero, giving m/2m/2 neighbours in each set of the appropriate pair; the counts for the other pair are both zero. Thus all WQH conditions hold.

The switching changes exactly the adjacencies between U0∪U1U^0\cup U^1 and X1+∪X1−X_1^+\cup X_1^-, and between V0∪V1V^0\cup V^1 and X2+∪X2−X_2^+\cup X_2^-. These changes negate F1F_1 and G1G_1, so the resulting graph is GH′G_{H'}.

Switching methods for Butson matrices and their graphs

Theorem 4.5 shows that a switching which stays within BH(n,k)\mathrm{BH}(n,k) automatically preserves the associated graph spectrum when kk is prime. For composite phase, this conclusion requires further hypotheses. In this section we first recall two matrix switchings from [7], then characterise the GM and WQH reflections on Butson matrices and give graph realisations of these operations and of balanced block switching.

Block switching and composite-phase examples

The following form of block switching uses separate parameters for the number of selected rows and the phase. Its short proof also explains the balance condition needed later.

Proposition 6.1 (Block switching; cf. [7 Proposition 5.1]). Let q,m≥1q,m\ge1, put n=qmn=qm, and let H∈BH(n,k)H\in\mathrm{BH}(n,k) have its first qq rows equal to

K0⊗1mT,K0∈BH(q,k).K_0\otimes\mathbf{1}_m^{\mathsf{T}},\qquad K_0\in\mathrm{BH}(q,k).

Multiplying any one of the q×mq\times m blocks in these rows by an element of μk\mu_k produces another matrix in BH(n,k)\mathrm{BH}(n,k).

Example 6.2. Let ω=ζ3\omega=\zeta_3. Consider the following matrices in BH(6,6)\mathrm{BH}(6,6):

H1=(11111111ωωω2ω211ω2ω2ωω1−1−111−11−1−ωωω2−ω21−1−ω2ω2ω−ω),H2=(11ωω1111ω2ω2ω2ω21111ωω1−1−111−11−1−ωωω2−ω21−1−ω2ω2ω−ω).H_1= \begin{pmatrix} 1&1&1&1&1&1\\ 1&1&\omega&\omega&\omega^2&\omega^2\\ 1&1&\omega^2&\omega^2&\omega&\omega\\ 1&-1&-1&1&1&-1\\ 1&-1&-\omega&\omega&\omega^2&-\omega^2\\ 1&-1&-\omega^2&\omega^2&\omega&-\omega \end{pmatrix}, \qquad H_2= \begin{pmatrix} 1&1&\omega&\omega&1&1\\ 1&1&\omega^2&\omega^2&\omega^2&\omega^2\\ 1&1&1&1&\omega&\omega\\ 1&-1&-1&1&1&-1\\ 1&-1&-\omega&\omega&\omega^2&-\omega^2\\ 1&-1&-\omega^2&\omega^2&\omega&-\omega \end{pmatrix}.

The first three rows of H1H_1 are F3⊗12TF_3\otimes\mathbf{1}_2^{\mathsf{T}}, and H2H_2 is obtained by multiplying their middle 3×23\times2 block by ω\omega. Proposition 6.1 therefore applies. We can computationally check that GH1G_{H_1} and GH2G_{H_2} are non-isomorphic cospectral mates.

The next result extends the block pattern underlying Hall-set switching.

Theorem 6.3 ([7 Theorem 5.3 and Corollary 5.4]). Let m≥1m \ge1, let n=k(m+1)n = k(m+1), and let H∈BH(n,k)H \in\mathrm{BH}(n,k) have the form

H=(SFk⊗1mTFk∗⊗1mA),H = \begin{pmatrix} S & \mathcal{F}_k \otimes\mathbf{1}_m^{\mathsf{T}} \\ \mathcal{F}_k^{*} \otimes\mathbf{1}_m & A \end{pmatrix},

where S∈BH(k,k)S \in\mathrm{BH}(k,k) is circulant and AA has order kmkm. Choose an index a∈{0,…,k−1}a \in\{0,\ldots,k-1\}. Multiply the k×mk \times m block in the first kk rows and columns k+am,…,k+(a+1)m−1k+am,\ldots,k+(a+1)m-1 by α∈μk\alpha\in\mu_k. Simultaneously multiply the m×km \times k block in the corresponding rows and first kk columns by α‾\overline{\alpha}. The resulting matrix belongs to BH(n,k)\mathrm{BH}(n,k).

For composite phase, this operation can change the spectrum of the associated graph.

Example 6.4. We use the matrix from [7 Example 5.8], H=(ζ4eij)H=(\zeta_4^{e_{ij}}), where

E=(012100000000101200112233210100220022121000332211000011020202000011202020032102220220032120222002020202203302020220023320012302022022012320200222).E = \left( \begin{array}{cccc|cc|cc|cc|cc} 0&1&2&1&0&0&0&0&0&0&0&0\\ 1&0&1&2&0&0&1&1&2&2&3&3\\ 2&1&0&1&0&0&2&2&0&0&2&2\\ 1&2&1&0&0&0&3&3&2&2&1&1\\ \hline 0&0&0&0&1&1&0&2&0&2&0&2\\ 0&0&0&0&1&1&2&0&2&0&2&0\\ \hline 0&3&2&1&0&2&2&2&0&2&2&0\\ 0&3&2&1&2&0&2&2&2&0&0&2\\ \hline 0&2&0&2&0&2&2&0&3&3&0&2\\ 0&2&0&2&2&0&0&2&3&3&2&0\\ \hline 0&1&2&3&0&2&0&2&2&0&2&2\\ 0&1&2&3&2&0&2&0&0&2&2&2 \end{array} \right).

It belongs to BH(12,4)\mathrm{BH}(12,4). Let KK be obtained by multiplying the initial all-one 4×24 \times2 block by ζ4\zeta_4 and the corresponding 2×42 \times4 block by −ζ4-\zeta_4. By Theorem 6.3, K∈BH(12,4)K \in\mathrm{BH}(12,4). Computationally we verify that GHG_H and GKG_K are not cospectral.

The GM reflection on Butson matrices

We now use the GM reflection QmQ_m from (4) as a matrix-switching operation. Orthogonality is preserved automatically. The first question is therefore when the transformed entries remain in μk\mu_k. Related extensions of GM-switching to complex unit gain graphs appear in [3]; here we work with Butson matrices and their associated unweighted graphs.

For x∈Cmx \in\mathbb{C}^m,

Qmx=2m(∑r=0m−1xr)1m−x.(11)Q_m x = \frac{2}{m}\left(\sum_{r=0}^{m-1}x_r\right)\mathbf{1}_m-x. \tag*{(11)}

Lemma 6.5. Let x∈μkmx \in\mu_k^m. Then Qmx∈μkmQ_mx \in\mu_k^m if and only if at least one of the following conditions holds:

(a) all entries of xx are equal;

(b) mm is even, and xx contains two distinct roots, each occurring m/2m/2 times;

(c) kk is even and ∑rxr=0\sum_r x_r=0.

In these cases, QmQ_m fixes xx, interchanges its two values, or negates xx, respectively. The descriptions agree when the conditions overlap.

Proof. Sufficiency follows directly from (11). For necessity, put z=(2/m)∑rxrz=(2/m)\sum_r x_r. If z=0z=0, then Qmx=−xQ_mx=-x, and −xr∈μk-x_r\in\mu_k holds precisely when −1∈μk-1\in\mu_k, or equivalently when kk is even.

Suppose z≠0z\ne0. Every entry α\alpha of xx must satisfy ∣α∣=∣z−α∣=1|\alpha|=|z-\alpha|=1. The two circles with centres 00 and zz and radius 11 have at most two intersection points. Thus xx contains at most two distinct values. If it is constant, (a) holds. Otherwise, let its values be α≠β\alpha\ne\beta, with α\alpha occurring a proportion pp of the time. Then z=2(pα+(1−p)β)z=2(p\alpha+(1-p)\beta). The identity ∣z−α∣2=∣z−β∣2|z-\alpha|^2=|z-\beta|^2 gives

(2p−1)∣α−β∣2=0.(2p-1)|\alpha-\beta|^2=0.

Hence p=1/2p=1/2, proving (b).

Theorem 6.6. Let H∈BH(n,k)H\in\mathrm{BH}(n,k), and let S1,…,StS_1,\ldots,S_t be pairwise disjoint nonempty sets of row indices. Write sℓ=∣Sℓ∣s_\ell=|S_\ell|, and let UU act as QsℓQ_{s_\ell} on the coordinates indexed by SℓS_\ell and as the identity on the remaining coordinates. Set K=UHK=UH, so

kij={2sℓ∑r∈Sℓhrj−hij,i∈Sℓ,hij,i∉⋃ℓ=1tSℓ.(12)k_{ij}= \begin{cases} \frac{2}{s_\ell}\sum_{r\in S_\ell}h_{rj}-h_{ij}, & i\in S_\ell,\\ h_{ij}, & i\notin\bigcup_{\ell=1}^{t}S_\ell. \end{cases} \tag*{(12)}

Then K∈BH(n,k)K\in\mathrm{BH}(n,k) if and only if every restricted column (hij)i∈Sℓ(h_{ij})_{i\in S_\ell} satisfies a condition of Lemma 6.5. Whenever this holds, the operation is an involution on the same row sets.

Proof. After reordering the row coordinates, UU is a direct sum of the matrices QsℓQ_{s_\ell} and an identity matrix. Hence U=U∗U=U^* and U2=InU^2=I_n. Therefore

KK∗=UHH∗U∗=nIn.KK^*=UHH^*U^*=nI_n.

The remaining requirement is that all entries of KK lie in μk\mu_k, which is exactly the condition of Lemma 6.5. Finally, UK=HUK=H.

Remark 6.7. The same construction can be applied after multiplying the rows by prescribed phases. If T=diag⁡(d0,…,dn−1)T=\operatorname{diag}(d_0,\ldots,d_{n-1}), with di∈μkd_i\in\mu_k, satisfies the required entry conditions for THTH, then undoing the phases gives

K=T∗UTH∈BH(n,k).(13)K=T^*UTH\in\mathrm{BH}(n,k). \tag*{(13)}

Column versions follow by transposition.

The constant and equally split two-value cases have a direct GM interpretation on the associated graph. The zero-sum condition alone does not give the same graph partition.

Theorem 6.8. Let H∈BH(n,k)H\in\mathrm{BH}(n,k), and let S1,…,StS_1,\ldots,S_t be disjoint row sets of even sizes sℓ≥2s_\ell\ge2. Suppose that every column restricted to SℓS_\ell is constant or contains two distinct roots, each occurring sℓ/2s_\ell/2 times. Define UU as in Theorem 6.6 and set K=UHK=UH. Then K∈BH(n,k)K\in\mathrm{BH}(n,k) and GKG_K is obtained from GHG_H by GM-switching with cells

Xℓ,a={Ri,a:i∈Sℓ},1≤ℓ≤t,a∈Zk,(14)X_{\ell,a}=\{R_{i,a}:i\in S_\ell\},\qquad1\le\ell\le t,\quad a\in\mathbb{Z}_k, \tag*{(14)}

and remainder D=V(GH)∖⋃ℓ,aXℓ,aD=V(G_H)\setminus\bigcup_{\ell,a}X_{\ell,a}. Conversely, the GM conditions for these cells force each restricted column to have one of the two stated forms.

Proof. The matrix assertion follows from Theorem 6.6. The cells consist of row vertices, so every vertex has just its own loop within its cell and no neighbours in any other cell. This gives condition (i) of Theorem 2.2. Remaining row vertices have no neighbours in the switching cells. For a column vertex,

dXℓ,a(Cj,b)=#{i∈Sℓ:hij=ζkb−a}.(15)d_{X_{\ell,a}}(C_{j,b})=\#\{i\in S_{\ell}:h_{ij}=\zeta_k^{b-a}\}. \tag*{(15)}

The column hypothesis makes this number 00, sℓ/2s_{\ell}/2, or sℓs_{\ell}, giving condition (ii). A constant restricted column is unchanged. If two roots occur equally often, the switching complements the two half-neighbourhoods and interchanges their positions. This is exactly the action of QsℓQ_{s_{\ell}} in Lemma 6.5, so the resulting graph is GKG_K.

Conversely, fix ℓ\ell, jj, bb and vary aa in (15). The counts are the phase multiplicities in the restricted column and sum to sℓs_{\ell}. If every count lies in {0,sℓ/2,sℓ}\{0,s_{\ell}/2,s_{\ell}\}, either one phase occurs sℓs_{\ell} times or two phases occur sℓ/2s_{\ell}/2 times each. ▢

In the fixed vertex order (2), the conjugating matrix is particularly simple. Put U^=U⊗Ik\widehat{U}=U\otimes I_k and Q=U^⊕InkQ=\widehat{U}\oplus I_{nk}. Then

ϕk(K)=U^ϕk(H),MK=QMHQT.(16)\phi_k(K)=\widehat{U}\phi_k(H),\qquad\mathcal{M}_K=Q\mathcal{M}_H Q^{\mathsf{T}}. \tag*{(16)}

These identities follow blockwise from the constant or equally split two-value condition. In particular, GHG_H and GKG_K are cospectral for every phase kk covered by the theorem, including odd and composite phases.

Example 6.9. Let ω=ζ3\omega=\zeta_3, and consider

H=(11111111ωωω2ω2ωω2ω11ω2ωω21ωω211ω2ω2ω1ω1ω2ωω2ω1).H=\begin{pmatrix} 1&1&1&1&1&1\\ 1&1&\omega&\omega&\omega^2&\omega^2\\ \omega&\omega^2&\omega&1&1&\omega^2\\ \omega&\omega^2&1&\omega&\omega^2&1\\ 1&\omega^2&\omega^2&\omega&1&\omega\\ 1&\omega^2&\omega&\omega^2&\omega&1 \end{pmatrix}.

Then H∈BH(6,3)H\in\mathrm{BH}(6,3). On the first four rows, each restricted column contains two distinct phases twice each. Taking U=Q4⊕I2U=Q_4\oplus I_2, we obtain

K=UH=(ωω2ωωω2ω2ωω21111111ωω2111ω11ω21ω2ω2ω1ω1ω2ωω2ω1)∈BH(6,3).K=UH=\begin{pmatrix} \omega&\omega^2&\omega&\omega&\omega^2&\omega^2\\ \omega&\omega^2&1&1&1&1\\ 1&1&1&\omega&\omega^2&1\\ 1&1&\omega&1&1&\omega^2\\ 1&\omega^2&\omega^2&\omega&1&\omega\\ 1&\omega^2&\omega&\omega^2&\omega&1 \end{pmatrix}\in\mathrm{BH}(6,3).

By Theorem 6.8, the graph GKG_K is obtained from GHG_H by GM-switching on the three cells

Xa={R0,a,R1,a,R2,a,R3,a},a∈Z3.X_a=\{R_{0,a},R_{1,a},R_{2,a},R_{3,a}\},\qquad a\in\mathbb{Z}_3.

This operation interchanges phases within each restricted column and applies at odd phase. This does not assert that HH and KK are inequivalent.

The WQH reflection on Butson matrices

We next apply the paired reflection underlying WQH-switching to Butson matrices. Extensions of WQH-switching to complex unit and general gain graphs appear in [1, 3]. We distinguish the condition that this reflection preserves the allowed matrix entries from the stronger phase-multiplicity condition that gives WQH-switching on the associated unweighted graphs.

For s≥1s \ge1, put z=(1sT,−1sT)Tz=(\mathbf{1}_s^{\mathsf{T}},-\mathbf{1}_s^{\mathsf{T}})^{\mathsf{T}} and define

Ws=I2s−1szzT=(Is−1sJs1sJs1sJsIs−1sJs).(17)W_s=I_{2s}-\frac{1}{s}zz^{\mathsf{T}}= \begin{pmatrix} I_s-\frac{1}{s}J_s & \frac{1}{s}J_s\\ \frac{1}{s}J_s & I_s-\frac{1}{s}J_s \end{pmatrix}. \tag*{(17)}

This is the one-pair WQH matrix from § 2.3. Since zTz=2sz^{\mathsf{T}}z=2s and zT12s=0z^{\mathsf{T}}\mathbf{1}_{2s}=0, we have WsT=WsW_s^{\mathsf{T}}=W_s, Ws2=I2sW_s^2=I_{2s} and Ws12s=12sW_s\mathbf{1}_{2s}=\mathbf{1}_{2s}. For u,v∈Csu,v\in\mathbb{C}^s, its action is

Ws(uv)=(u−δ1sv+δ1s),δ=1s(∑r=0s−1ur−∑r=0s−1vr).(18)W_s\begin{pmatrix}u\\v\end{pmatrix} = \begin{pmatrix}u-\delta\mathbf{1}_s\\v+\delta\mathbf{1}_s\end{pmatrix}, \qquad \delta=\frac{1}{s}\left(\sum_{r=0}^{s-1}u_r-\sum_{r=0}^{s-1}v_r\right). \tag*{(18)}

Lemma 6.10. Let u,v∈μksu,v\in\mu_k^s. Then Ws(uT,vT)T∈μk2sW_s(u^{\mathsf{T}},v^{\mathsf{T}})^{\mathsf{T}}\in\mu_k^{2s} if and only if at least one of the following conditions holds:

(a) ∑rur=∑rvr\sum_r u_r=\sum_r v_r;

(b) both uu and vv are constant, possibly with different values;

(c) kk is even, and the signed vector (uT,−vT)T(u^{\mathsf{T}},-v^{\mathsf{T}})^{\mathsf{T}} contains two distinct roots, each occurring ss times.

In case (a), the reflection fixes the column. In case (b), it interchanges the two constant values. In case (c), if the two signed values are α,β\alpha,\beta, then δ=α+β\delta=\alpha+\beta and the signed values are replaced by −β,−α-\beta,-\alpha, respectively. These descriptions agree when the conditions overlap. In particular, for odd kk, conditions (a) and (b) are the only possibilities.

Proof. Sufficiency follows from (18). For necessity, the case δ=0\delta=0 is (a). Suppose δ≠0\delta\ne0, and write y=(uT,−vT)Ty=(u^{\mathsf{T}},-v^{\mathsf{T}})^{\mathsf{T}}. Every entry γ\gamma of yy satisfies ∣γ∣=∣δ−γ∣=1|\gamma|=|\delta-\gamma|=1. The two circles have distinct centres, so yy has at most two distinct values. If yy is constant, (b) holds. Otherwise, let its two values be α≠β\alpha\ne\beta, with α\alpha occurring a proportion pp of the time. Since

δ=1s∑ryr=2(pα+(1−p)β),\delta=\frac{1}{s}\sum_r y_r=2(p\alpha+(1-p)\beta),

the equality ∣δ−α∣2=∣δ−β∣2|\delta-\alpha|^2=|\delta-\beta|^2 gives

(2p−1)∣α−β∣2=0.(2p-1)|\alpha-\beta|^2=0.

Thus each value occurs ss times. If kk is even, all entries of yy lie in μk\mu_k, giving (c). If kk is odd, the sets μk\mu_k and −μk-\mu_k are disjoint. The entries of uu lie in the first set and those of −v-v in the second. With only two values available, each half must therefore be constant, giving (b). □\square

Theorem 6.11. Let H∈BH(n,k)H\in\mathrm{BH}(n,k), and let S1+,S1−,…,St+,St−S_1^+,S_1^-,\ldots,S_t^+,S_t^- be pairwise disjoint nonempty row sets with ∣Sℓ+∣=∣Sℓ−∣=sℓ|S_\ell^+|=|S_\ell^-|=s_\ell. In Rn\mathbb{R}^n, put

zℓ=1Sℓ+−1Sℓ−,V=In−∑ℓ=1t1sℓzℓzℓT,K=VHz_\ell=\mathbf{1}_{S_\ell^+}-\mathbf{1}_{S_\ell^-}, \qquad V=I_n-\sum_{\ell=1}^{t}\frac{1}{s_\ell}z_\ell z_\ell^{\mathsf{T}}, \qquad K=VH

where zℓz_\ell is the difference of characteristic vectors. Equivalently, with

δℓj=1sℓ(∑r∈Sℓ+hrj−∑r∈Sℓ−hrj),\delta_{\ell j}=\frac{1}{s_\ell}\left(\sum_{r\in S_\ell^+}h_{rj}-\sum_{r\in S_\ell^-}h_{rj}\right),

the entries of KK are

kij={hij−δℓj,i∈Sℓ+,hij+δℓj,i∈Sℓ−,hij,i∉⋃ℓ=1t(Sℓ+∪Sℓ−).(19)k_{ij}= \begin{cases} h_{ij}-\delta_{\ell j}, & i\in S_\ell^+,\\ h_{ij}+\delta_{\ell j}, & i\in S_\ell^-,\\ h_{ij}, & i\notin\bigcup_{\ell=1}^{t}(S_\ell^+\cup S_\ell^-). \end{cases} \tag*{(19)}

Then K∈BH(n,k)K\in\mathrm{BH}(n,k) if and only if every column restricted to each ordered pair (Sℓ+,Sℓ−)(S_\ell^+,S_\ell^-) satisfies Lemma 6.10. Whenever this holds, the operation is an involution on the same row sets.

Proof. The vectors zℓz_\ell have disjoint supports and squared norms 2sℓ2s_\ell. Hence VT=VV^\mathsf{T}=V and V2=InV^2=I_n, and

KK∗=VHH∗VT=nIn.KK^*=VHH^*V^\mathsf{T}=nI_n.

The remaining requirement is entry preservation, which is precisely Lemma 6.10 on each pair. The identity VK=HVK=H proves involutivity. □

Remark 6.12. The relation with the preceding construction is

Ws=−DsQ2sDs,Ds=diag⁡(Is,−Is).(20)W_s=-D_sQ_{2s}D_s,\qquad D_s=\operatorname{diag}(I_s,-I_s). \tag*{(20)}

For even kk, these row signs are allowed phase scalings, so the WQH reflection is related to the phased GM reflection of Remark 6.7 by such scalings. The paired graph partition below gives its direct WQH interpretation. For odd kk, the signs in DsD_s do not preserve the specified phase group. The entry criterion may also be applied after prescribed row phase scalings, as in Remark 6.7, to obtain phased versions. Transposition gives column versions.

Equality of the two column sums suffices to fix a column in the matrix operation. To fix all corresponding graph incidences, we require equality of the individual phase multiplicities.

Theorem 6.13. Let HH, the paired row sets and VV be as in Theorem 6.11. Suppose that for every pair and every column either

  • (a) each element of μk\mu_k occurs equally often on Sℓ+S_\ell^+ and Sℓ−S_\ell^-; or

  • (b) the column is constant on each of Sℓ+S_\ell^+ and Sℓ−S_\ell^-, possibly with different values.

Then K=VH∈BH(n,k)K=VH\in\mathrm{BH}(n,k), and GKG_K is obtained from GHG_H by WQH-switching with paired cells

Xℓ,a±={Ri,a:i∈Sℓ±},1≤ℓ≤t,a∈Zk,(21)X_{\ell,a}^{\pm}=\{R_{i,a}:i\in S_\ell^\pm\},\qquad1\leq\ell\leq t,\quad a\in\mathbb{Z}_k, \tag*{(21)}

and remainder DD consisting of all other vertices. Conversely, the WQH conditions for these paired cells force each restricted column to have one of the two stated forms.

Proof. The matrix assertion follows from Lemma 6.10 and Theorem 6.11. Each cell has size sℓs_\ell. Within their union, every vertex has only its own loop, so the difference constants in Theorem 2.3(ii) are 11 for a pair with itself and 00 for distinct pairs. Remaining row vertices have no neighbours in the cells. For a column vertex, the neighbourhood counts are

dXℓ,a±(Cj,b)=#{i∈Sℓ±:hij=ζkb−a}.(22)d_{X_{\ell,a}^{\pm}}(C_{j,b})=\#\{i\in S_\ell^\pm:h_{ij}=\zeta_k^{b-a}\}. \tag*{(22)}

In case (a), these counts agree for the two cells, and all incidences are fixed. In case (b), equal constant values also give equal counts. Distinct constant values give, for the two relevant phases, all of one cell and none of the other. WQH-switching interchanges these neighbourhoods, exactly interchanging the two constant values in (18). Thus the switched graph is GKG_K.

Conversely, fix ℓ\ell, jj, and let mr±m_r^{\pm} be the multiplicity of ζkr\zeta_k^r on Sℓ±S_\ell^{\pm}. Varying aa in (22), the WQH condition requires, for every rr, either mr+=mr−m_r^+=m_r^- or

(mr+,mr−)∈{(sℓ,0),(0,sℓ)}.(m_r^+,m_r^-)\in\{(s_\ell,0),(0,s_\ell)\}.

If any pair of counts differs, one half is constant. Since the multiplicities in each half sum to sℓs_\ell, applying the same condition to all other phases forces the other half to be constant too. Otherwise all phase multiplicities agree.

In the fixed vertex order (2), put V^=V⊗Ik\widehat V=V\otimes I_k and W=V^⊕Ink\mathcal W=\widehat V\oplus I_{nk}. Under the hypotheses of Theorem 6.13, we have

ϕk(K)=V^ϕk(H),MK=WMHWT.(23)\phi_k(K)=\widehat V\phi_k(H),\qquad\mathcal M_K=\mathcal W\mathcal M_H\mathcal W^{\mathsf T}. \tag*{(23)}

Indeed, equal phase multiplicities give equal sums of the permutation blocks on the two halves, while constant halves have their permutation blocks interchanged. This verifies the first identity directly, without treating ϕk\phi_k as additive on complex numbers. The second identity proves cospectrality for every phase covered by the lifting criterion.

Corollary 6.14. Let kk be prime, and let H,VH,V be as in Theorem 6.11. If VH∈BH(n,k)VH\in\mathrm{BH}(n,k), then the hypotheses of Theorem 6.13 hold. Thus every admissible paired reflection at prime phase has the stated WQH realisation on the associated graph.

Proof. For odd kk, Lemma 6.10 allows only equal sums or constant halves. For k=2k=2, its case (c) also has equal sums, since the two distinct signed values are 11 and −1-1. It therefore remains to consider equal sums. Write mr±m_r^{\pm} for the phase multiplicities of the two halves and put

f(x)=∑r=0k−1(mr+−mr−)xr.f(x)=\sum_{r=0}^{k-1}(m_r^+-m_r^-)x^r.

We have f(ζk)=0f(\zeta_k)=0. Since kk is prime and deg⁡f≤k−1\deg f\le k-1, the minimal polynomial of ζk\zeta_k gives f=c(1+x+⋯+xk−1)f=c(1+x+\cdots+x^{k-1}) for some rational cc. The two halves have equal size, so f(1)=0f(1)=0, whence c=0c=0. All phase multiplicities therefore agree.

The corollary identifies a specific graph switching, in addition to the cospectrality already guaranteed by Theorem 4.5. For composite phase, the distinction between sums and phase multiplicities must be retained. For example, in H=(ζ4ij)0≤i,j<4∈BH(4,4)H=(\zeta_4^{ij})_{0\le i,j<4}\in\mathrm{BH}(4,4), take S+={0,2}S^+=\{0,2\} and S−={1,3}S^-=\{1,3\}. The reflection fixes columns 0,1,30,1,3 and negates column 22, so it preserves the Butson property. However, in column 11 the two halves are (1,−1)T(1,-1)^{\mathsf T} and (ζ4,−ζ4)T(\zeta_4,-\zeta_4)^{\mathsf T}. Their sums agree but their phase multiplicities do not, and C1,0C_{1,0} has respectively 11 and 00 neighbours in X1,0+X^+_{1,0} and X1,0−X^-_{1,0}. These cells fail the WQH conditions. In this example the matrices are column-equivalent; the obstruction concerns this particular graph partition.

Example 6.15. Let H∈BH(6,3)H\in\mathrm{BH}(6,3) be the matrix in Example 6.9, and take S+={0,1}S^+=\{0,1\} and S−={2,3}S^-=\{2,3\}. Its first two columns are constant on each half, with values (1,ω)(1,\omega) and (1,ω2)(1,\omega^2), respectively. In each of the other four columns, the two halves have identical phase multisets.

Thus V=W2⊕I2V = W_2 \oplus I_2 gives

K=VH=(ωω21111ωω2ωωω2ω211ω11ω2111ωω211ω2ω2ω1ω1ω2ωω2ω1)∈BH(6,3).K = VH = \begin{pmatrix} \omega& \omega^2 & 1 & 1 & 1 & 1 \\ \omega& \omega^2 & \omega& \omega& \omega^2 & \omega^2 \\ 1 & 1 & \omega& 1 & 1 & \omega^2 \\ 1 & 1 & 1 & \omega& \omega^2 & 1 \\ 1 & \omega^2 & \omega^2 & \omega& 1 & \omega\\ 1 & \omega^2 & \omega& \omega^2 & \omega& 1 \end{pmatrix} \in\mathrm{BH}(6,3).

Only the first two columns on the four selected rows change. Theorem 6.13 realises this operation as WQH-switching on the three pairs

Xa+={R0,a,R1,a},Xa−={R2,a,R3,a},a∈Z3.X_a^+ = \{R_{0,a}, R_{1,a}\}, \qquad X_a^- = \{R_{2,a}, R_{3,a}\}, \qquad a \in\mathbb{Z}_3.

As in Example 6.9, no inequivalence or graph nonisomorphism is asserted.

Cyclic graph switching

For real matrices, negating a switched block interchanges the two phase classes of the associated graph. Multiplying a Butson block by ζk\zeta_k instead rotates kk phase classes. We make this observation precise in a graph-switching construction.

Theorem 6.16. Let GG be a graph with disjoint vertex sets X0,…,Xk−1X_0, \ldots, X_{k-1} of the same size m≥1m \ge1, where k≥2k \ge2. Suppose that their union XX is independent and has no loops. For every vertex v∉Xv \notin X, suppose that either

(i) N(v)∩X=XaN(v) \cap X = X_a for some a∈Zka \in\mathbb{Z}_k; or

(ii) dX0(v)=⋯=dXk−1(v)d_{X_0}(v) = \cdots= d_{X_{k-1}}(v).

For each vertex in case (i), replace its neighbourhood XaX_a by Xa+1X_{a+1}, with indices modulo kk. Leave all other adjacencies unchanged. The resulting graph is cospectral with GG.

Proof. Order the vertices of XX by the classes X0,…,Xk−1X_0, \ldots, X_{k-1}, and put

E=1mJm,Q=Ik⊗(Im−E)+Pk⊗E.E = \frac{1}{m}J_m, \qquad Q = I_k \otimes(I_m - E) + P_k \otimes E.

Since EE and Im−EI_m - E are orthogonal projections and PkP_k is orthogonal, QQT=IkmQQ^{\mathsf{T}} = I_{km}. Let bb be the row of incidences from a vertex outside XX to XX. If its kk blocks have equal sums, then bQ=bbQ = b. If bb is all ones in block aa and zero elsewhere, multiplication by QQ moves that all-one block to a+1a+1.

Write the adjacency matrix with the vertices outside XX first. Conjugating by I∣V(G)∖X∣⊕QI_{\lvert V(G)\setminus X\rvert} \oplus Q preserves the zero block on XX, preserves the adjacency block outside XX, and changes the off-diagonal blocks exactly as stated. It therefore produces the adjacency matrix of the switched graph. Orthogonal similarity proves cospectrality.

When k=2k = 2, this is the one-pair WQH operation for independent switching sets. No divisibility condition on mm is required by the graph theorem.

We next apply the theorem to Proposition 6.1. After scaling the first qq rows, we may assume that the selected q×mq \times m block is Jq,mJ_{q,m}. Let AA be the submatrix formed by the remaining rows and those same mm columns. The proof of Proposition 6.1 gives zero row sums for AA. To obtain the graph switching, we require the stronger condition: that each element of μk\mu_k occurs equally often in every row of AA. If AA has no rows, this condition is vacuous. Otherwise it implies k∣mk \mid m. For prime kk, it follows from the zero row sums by Lemma 3.7.

Corollary 6.17. Under the hypotheses of Proposition 6.1, assume that each element of μk\mu_k occurs equally often in the submatrix AA completing the columns of the selected block, normalised to Jq,mJ_{q,m}. Let KK be obtained by multiplying that block by ζk\zeta_k. Then GKG_K is obtained from GHG_H by the cyclic switching of Theorem 6.16. In particular, GHG_H and GKG_K are cospectral. The balance hypothesis is automatic when kk is prime.

Proof. Assume the selected columns are 0,…,m−10,\ldots,m-1 and put

Xa={Cj,a:0≤j<m}(a∈Zk).X_a = \{C_{j,a}: 0 \le j < m\}\quad(a \in\mathbb{Z}_k).

Their union is independent. Every selected row vertex Ri,aR_{i,a}, with 0≤i<q0 \le i < q, is adjacent to all of XaX_a and none of the other classes. By Lemma 3.7, every other row vertex has m/km/k neighbours in each XaX_a; other column vertices have none. The graph theorem therefore applies. Its cyclic change replaces the matching for an entry 11 in the selected block by the matching for ζk\zeta_k, giving GKG_K.

We can also express this correspondence directly in the original vertex order. Put E=Jm/mE = J_m/m and define the complex unitary matrix

L=Im+(ζk−1)EL = I_m + (\zeta_k - 1)E

and the real orthogonal matrix

L^=(Im−E)⊗Ik+E⊗Pk=Imk+E⊗(Pk−Ik).(24)\widehat{L} = (I_m - E) \otimes I_k + E \otimes P_k = I_{mk} + E \otimes(P_k - I_k). \tag*{(24)}

The first matrix multiplies a constant row by ζk\zeta_k and fixes a row with sum zero. The second rotates the constant phase-class components and fixes their orthogonal complement. We define L^\widehat{L} explicitly, since ϕk\phi_k has no additive extension to complex numbers that would justify writing it as ϕk(L)\phi_k(L).

Under the balance condition,

ϕk(Jq,m)L^=ϕk(ζkJq,m),(25)\phi_k(J_{q,m})\widehat{L} = \phi_k(\zeta_k J_{q,m}), \tag*{(25)}
ϕk(A)L^=ϕk(A).(26)\phi_k(A)\widehat{L} = \phi_k(A). \tag*{(26)}

For the second identity, each row-block sum of ϕk(A)\phi_k(A) is (m/k)Jk(m/k)J_k, which annihilates Pk−IkP_k-I_k on the right. Hence, with n=qmn=qm,

ϕk(K)=ϕk(H)(L^⊕I(n−m)k).\phi_k(K) = \phi_k(H)\bigl(\widehat{L} \oplus I_{(n-m)k}\bigr).

Writing L=Ink⊕L^⊕I(n−m)k\mathcal{L} = I_{nk} \oplus\widehat{L} \oplus I_{(n-m)k} gives

MK=LTMHL.\mathcal{M}_K = \mathcal{L}^{\mathsf{T}}\mathcal{M}_H\mathcal{L}.

This proves the graph correspondence by an explicit real orthogonal similarity. For composite phase, zero row sums alone do not imply the condition of Lemma 3.7; for example, (1,1,−1,−1)(1,1,-1,-1) has sum zero in μ4\mu_4 but contains neither of the phases ζ4\zeta_4, and −ζ4-\zeta_4. The balance hypothesis must therefore be retained in the graph lifting statement.

Concluding remarks

Our results provide a basis for transferring tools between matrix switching and graph switching. The correspondences in Sections 5 and 6 show how suitable matrix operations lead to graph switchings and how graph-switching methods yield operations on Butson matrices. The spectral analysis in Section 4 also explains a limitation of this transfer: for fixed order and phase, preserving the Butson property guarantees cospectral associated graphs at prime phase, but need not do so at composite phase.

A natural next step is to characterise the graph-switching partitions that preserve the class of Butson Hadamard graphs. Together with structural criteria for spectral preservation at composite phase, such a characterisation could guide the search for inequivalent matrices and nonisomorphic cospectral graphs.

The computational work in this paper, such as graph isomorphism and Hadamard equivalence checking, was carried out with Magma [4].

Acknowledgements

Aida Abiad acknowledges support from the Dutch Research Council (NWO), Vidi grant VI.Vidi.213.085 (grant ID https://doi.org/10.61686/CSWNV56135). This work was done in part while the first author was visiting the Simons Institute for the Theory of Computing at UC Berkeley.

Declaration of AI use

ChatGPT (OpenAI, accessed October 2026) assisted with literature checking, proofreading and revision of the exposition. The authors are responsible for the mathematical content and the final manuscript.

References

  1. [1]A. Abiad, F. Belardo, and A. P. Khramova. A switching method for constructing cospectral gain graphs. Discrete Mathematics, 347(4):113838, 2024.arxiv.org/abs/2304.03555
  2. [2]A. Abiad and L. Peters. Switching graphs and Hadamard matrices. The Art of Discrete and Applied Mathematics, 2025.arxiv.org/abs/2410.10638
  3. [3]F. Belardo, M. Brunetti, M. Cavalleri, and A. Donno. Godsil-McKay switching for mixed and gain graphs over the circle group. Linear Algebra Appl., 614:256–269, 2021.DOI
  4. [4]W. Bosma, J. Cannon, and C. Playoust. The Magma algebra system. I. the user language. J. of Symbolic Comput., 24:235–265, 1997.
  5. [5]A. T. Butson. Generalized Hadamard matrices. Proc. Amer. Math. Soc., 13:894–898, 1962.DOI
  6. [6]R. Craigen and H. Kharaghani. Hadamard matrices and Hadamard designs. In Handbook of Combinatorial Designs, pages 299–305. Chapman and Hall/CRC, 2006.DOI
  7. [7]D. Crnković, R. Egan, and A. Švob. A universal theory of switching for combinatorial objects, and applications to complex Hadamard matrices. J. Algebr. Comb., 63:64, 2026.
  8. [8]P. J. Davis. Circulant matrices. John Wiley & Sons, New York-Chichester-Brisbane, 1979.
  9. [9]W. de Launey and D. Flannery. Algebraic Design Theory. Mathematical Surveys and Monographs, vol. 175. American Mathematical Society, Providence, RI, 2011.
  10. [10]P. Diță. Some results on the parametrization of complex Hadamard matrices. J. Phys. A: Math. Gen., 37(20):5355–5374, 2004.DOI
  11. [11]R. Egan, D. Flannery, and P. Ó Catháin. Classifying cocyclic Butson Hadamard matrices. Algebraic design theory and Hadamard matrices. in Springer Proc. Math. Stat., 133:93–106, 2015.
  12. [12]C. D. Godsil and B. McKay. Constructing cospectral graphs. Aequationes Math., 25(1):257–268, 1982.DOI
  13. [13]D. Goyeneche. A new method to construct families of complex Hadamard matrices in even dimensions. J. Math. Phys., 54(3):032201, 2013.DOI
  14. [14]T. Y. Lam and K. H. Leung. On vanishing sums of roots of unity. J. Algebra, 224(1):91–109, 2000.DOI
  15. [15]B. D. McKay. Hadamard equivalence via graph isomorphism. Discrete Mathematics, 27:213–214, 1979.DOI
  16. [16]W.P. Orrick. Switching operations for Hadamard matrices. SIAM Journal on Discrete Mathematics, 22(1):31–50, 2008.arxiv.org/abs/math/0507515
  17. [17]F. Szöllősi. Parametrizing complex Hadamard matrices. European J. Combin., 29(5):1219–1234, 2008.arxiv.org/abs/math/0610297
  18. [18]W. Wang, L. Qiu, and Y. Hu. Cospectral graphs, GM-switching and regular rational orthogonal matrices of level p. Linear Algebra Appl., 563:154–177, 2019.DOI

Paper details

vlnc:W_2uhdjkj8
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC0-1.0
Usage

views · 0

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Mathematics

ChatGPT

View statement
Looking for related papers…
Contents