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 [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 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 , , and . An matrix with entries in such that is Butson Hadamard of order and phase , where denotes the complex conjugate transpose of . The set of all such matrices is denoted by . An element of 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 as a specified phase; it need not always be the least phase containing all entries of .
Matrix rows and columns are indexed from 0 to , unless a local block indexing is specified. Indices in are always read modulo . We write , and for the identity, all-one and zero matrices of the indicated sizes, and abbreviate and to and . The vector is the column vector of ones. In a small number of instances, by abuse of notation will also denote a binary characteristic vector in for some subset , and this will be stated or clear from context in those instances. The symbols and denote the Kronecker product and the direct sum, respectively. The Hadamard product is the entrywise product of matrices of the same size. For a matrix with entries in , we write
for its entrywise th power. In particular, is an all-ones matrix. The parentheses distinguish entrywise powers from ordinary matrix powers. The spectrum is the multiset of eigenvalues of , counted with algebraic multiplicity. Unions of spectra are understood as multiset unions.
Two matrices are equivalent if
for monomial matrices whose nonzero entries belong to . 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 . We call normalised if its first row and first column consist entirely of ones. Every Butson Hadamard matrix is equivalent to a normalised one.
For coprime to , the map is a field automorphism of and sends to another matrix . 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 , a vertex and a subset , we write
We omit the subscript 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 be the permutation matrix indexed by with
Thus is the circulant permutation matrix with first row . The map
is the regular permutation representation of . For a matrix with entries in , we write
This is a block substitution. We do not regard as an additive map on complex numbers. Where a monomial matrix is involved, we set ; products with monomial matrices then respect this substitution because each contributing entry is a single product. We often omit the subscript when the phase is fixed.
Definition 2.1. Let . The graph has vertex set , where
Its edges between the two parts are given by
Every vertex in has a loop, and there are no other edges. If , we call the Butson Hadamard graph associated with .
We always use the vertex order
With this convention, the adjacency matrix is
The graph obtained from by deleting the loops is bipartite, with parts and . The loops in distinguish the row part from the column part under graph isomorphism.
For each row and column , the sets
are called the row fibres and column fibres. Each pair induces a perfect matching. The simultaneous translation , preserves adjacency. If is normalised, then and for every , and .
When , we recover McKay’s graph [15]: the two copies of row are and , the two copies of column are and , 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 be a partition of such that:
(i) for every , the number is independent of the choice of ;
(ii) for every and every , the number belongs to .
For every with , reverse all adjacencies between and . The resulting graph is cospectral with .
The orthogonal matrix underlying this operation acts on each as the reflection
and as the identity on . We have , and .
Theorem 2.3 (WQH-switching [18]). Let
be a partition of such that, for every :
(i) ;
(ii) there is a constant satisfying
(iii) every vertex is adjacent to all vertices of one of and none of the other, or satisfies .
Whenever a vertex of is adjacent to all of one of and none of the other, interchange these two neighbourhoods. The resulting graph is cospectral with .
Remark 2.4. For , the conditions concern a pair 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 . 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 and , where the latter are characteristic vectors in . The WQH conjugating matrix is
The vectors have disjoint supports and squared norm , so 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 denote row of a real Hadamard matrix .
Definition 2.5. A Hadamard matrix is 3-normalised on three distinct rows if . A set of four distinct rows is a closed quadruple if their Hadamard product is .
After equivalence operations, a Hadamard matrix with a closed quadruple can be written as
The four sets of columns are called fields. Orthogonality implies that every row of each has sum zero. Consequently, if , then is even and 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 , 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 , with even, a Hadamard matrix containing a Hall set is equivalent to one of the form
Here , , where
and , for . Each is an matrix whose row and column sums are 2 if and 0 otherwise.
Definition 2.8. Switching a Hall set is negating and for one in (6).
Theorem 2.9 (Orrick [16]). Switching a Hall set produces a Hadamard matrix. The four choices of the pair 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 are equivalent, then and are isomorphic.
Proof. Write , where are monomial matrices with nonzero entries in . Their block substitutions and are permutation matrices, and
Consequently,
This permutation similarity gives the required isomorphism.
Proposition 3.2. Let and let be coprime to . Then and are isomorphic.
Proof. Relabel every phase index by multiplication by :
If , then is equivalent to in . The relabelling therefore preserves adjacency and loops, and gives an isomorphism from to .
Deleting the loops also removes the distinction between rows and columns. In fact,
is an isomorphism from the graph of to the graph of with loops removed. With loops retained, an isomorphism must preserve the two parts.
Proposition 3.3. Let . Every permutation matrix satisfying has the form , where are permutation matrices of order satisfying
Proof. The vertices in are precisely the vertices carrying loops, so every isomorphism preserves and . 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 of order ; it does not require them to arise from monomial matrices of order . 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 and , where
Both matrices belong to . 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 be prime and let be nonnegative integers. Then
Proposition 3.8. Let be prime. Let have labelled vertex set as in Definition 2.1, with loops at all row vertices, no other edges within either part, and the following properties:
(i) each pair induces a perfect matching;
(ii) the simultaneous translation of all phase indices by preserves adjacency;
(iii) vertices in distinct row fibres have exactly common neighbours.
Then for a unique in the given labelling. Conversely, every graph with has these properties.
Proof. By (i) and (ii), the matching between and is given by a unique shift . Set . This recovers the adjacency rule (1) and determines uniquely.
Fix distinct row indices . The number of common neighbours of and is
Condition (iii) says that every phase occurs times among the ratios . Their sum is therefore zero. Hence distinct rows are orthogonal and .
Conversely, (i) and (ii) follow from the construction. If is Hadamard, orthogonality and Lemma 3.7 show that every ratio occurs times. Equation (7) then gives (iii).
Spectra of Butson Hadamard graphs
We now determine the spectrum of . The key observation is that the regular representation separates into the characters of , so the relevant matrices are the entrywise powers of . Denote the Fourier matrix by .
Proposition 4.1. For every , the matrix is unitarily similar to
In particular,
Proof. The unitary Fourier matrix diagonalises [8]:
Conjugating by replaces its block by . Reordering the coordinates by character gives (8).
Corollary 4.2. Let . If
then and are cospectral. If is prime, it is sufficient that and are cospectral for some .
Proof. The first assertion follows from Proposition 4.1. For the second, equality of the spectra gives equality of the characteristic polynomials over . Applying each field automorphism gives equality of the characteristic polynomials of and . Since multiplication by permutes the nonzero residues modulo the prime , taking the multiset union proves the claim.
The spectrum of depends on the singular values of , rather than on its eigenvalues. The unitary form of Proposition 4.1 makes this distinction explicit.
Proposition 4.3. For , the multiset of squared singular values of is
If is prime, these values are once, with multiplicity , and with multiplicity .
Proof. Unitary similarity in Proposition 4.1 preserves singular values, giving (9). The block for is . If is prime, each nonzero gives a field automorphism, so .
Proposition 4.4. Let be the singular values of , with multiplicities. Then the eigenvalues of are
The eigenvalues of the graph without loops are and for the same indices.
Proof. Take a real singular value decomposition . Conjugation by changes (3) into
After reordering coordinates, this is the direct sum of the matrices , whose characteristic polynomials are . Deleting the loops replaces the diagonal entry by and gives eigenvalues .
Theorem 4.5. Let be prime and let . The spectrum of is given in Table 1. In particular, all graphs associated with matrices in are cospectral.
| Eigenvalue | 0 | 1 | ||||
| Multiplicity | 1 | 1 |
Table 1. Spectrum of for with prime.
Proof. Combine Propositions 4.3 and 4.4.
For composite , the blocks with still equal in (9), but the remaining blocks need not do so. Thus and have multiplicity at least , the two values occur at least once each, and each have multiplicity at least , where 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 be the Sylvester Hadamard matrix of order 16, indexed by , with . Write for the first two standard basis vectors. The sets
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 . Before switching, and 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 be a Hadamard matrix of order with a closed quadruple, and let be obtained by switching that quadruple. Then is isomorphic to a graph obtained from by WQH-switching.
Proof. By Theorems 2.7 and 3.4, it suffices to take in the form (5) and negate its initial block, where . Let
These are equally sized independent sets, with no edges between them. For , put . Every vertex of is adjacent to all of and none of ; every vertex of has the reverse neighbourhood.
Every row of in (5) has sum zero, so every other row vertex has neighbours in each of and . 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 column fibres. By (1), this negates the initial block and gives .
Switching a Hall set
Theorem 5.3. Let be a Hadamard matrix of order , with , containing a Hall set. If is obtained by switching that Hall set, then is isomorphic to a graph obtained from by WQH-switching.
Proof. Use the normal form (6), with . By Theorems 2.9 and 3.4, it suffices to negate and . Define
and let consist of the remaining vertices. The four sets above have size .
We check condition (ii) of Theorem 2.3 for the two pairs and . 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 and .
::: Since every row and column of has sum 2, each contains positive entries and negative entries. Hence the two cross-difference constants are .
For , put
The all-one blocks imply that is complete to and anticomplete to , while has the reverse neighbourhood. Similarly, is complete to and anticomplete to , and has the reverse neighbourhood. These vertices have no neighbours in the other pair of switching sets.
All other vertices of are balanced on each pair. Indeed, the relevant off-diagonal blocks and have row and column sums zero, giving 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 and , and between and . These changes negate and , so the resulting graph is .
Switching methods for Butson matrices and their graphs
Theorem 4.5 shows that a switching which stays within automatically preserves the associated graph spectrum when 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 , put , and let have its first rows equal to
Multiplying any one of the blocks in these rows by an element of produces another matrix in .
Example 6.2. Let . Consider the following matrices in :
The first three rows of are , and is obtained by multiplying their middle block by . Proposition 6.1 therefore applies. We can computationally check that and 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 , let , and let have the form
where is circulant and has order . Choose an index . Multiply the block in the first rows and columns by . Simultaneously multiply the block in the corresponding rows and first columns by . The resulting matrix belongs to .
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], , where
It belongs to . Let be obtained by multiplying the initial all-one block by and the corresponding block by . By Theorem 6.3, . Computationally we verify that and are not cospectral.
The GM reflection on Butson matrices
We now use the GM reflection from (4) as a matrix-switching operation. Orthogonality is preserved automatically. The first question is therefore when the transformed entries remain in . 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 ,
Lemma 6.5. Let . Then if and only if at least one of the following conditions holds:
(a) all entries of are equal;
(b) is even, and contains two distinct roots, each occurring times;
(c) is even and .
In these cases, fixes , interchanges its two values, or negates , respectively. The descriptions agree when the conditions overlap.
Proof. Sufficiency follows directly from (11). For necessity, put . If , then , and holds precisely when , or equivalently when is even.
Suppose . Every entry of must satisfy . The two circles with centres and and radius have at most two intersection points. Thus contains at most two distinct values. If it is constant, (a) holds. Otherwise, let its values be , with occurring a proportion of the time. Then . The identity gives
Hence , proving (b).
Theorem 6.6. Let , and let be pairwise disjoint nonempty sets of row indices. Write , and let act as on the coordinates indexed by and as the identity on the remaining coordinates. Set , so
Then if and only if every restricted column 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, is a direct sum of the matrices and an identity matrix. Hence and . Therefore
The remaining requirement is that all entries of lie in , which is exactly the condition of Lemma 6.5. Finally, .
Remark 6.7. The same construction can be applied after multiplying the rows by prescribed phases. If , with , satisfies the required entry conditions for , then undoing the phases gives
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 , and let be disjoint row sets of even sizes . Suppose that every column restricted to is constant or contains two distinct roots, each occurring times. Define as in Theorem 6.6 and set . Then and is obtained from by GM-switching with cells
and remainder . 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,
The column hypothesis makes this number , , or , 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 in Lemma 6.5, so the resulting graph is .
Conversely, fix , , and vary in (15). The counts are the phase multiplicities in the restricted column and sum to . If every count lies in , either one phase occurs times or two phases occur times each. ▢
In the fixed vertex order (2), the conjugating matrix is particularly simple. Put and . Then
These identities follow blockwise from the constant or equally split two-value condition. In particular, and are cospectral for every phase covered by the theorem, including odd and composite phases.
Example 6.9. Let , and consider
Then . On the first four rows, each restricted column contains two distinct phases twice each. Taking , we obtain
By Theorem 6.8, the graph is obtained from by GM-switching on the three cells
This operation interchanges phases within each restricted column and applies at odd phase. This does not assert that and 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 , put and define
This is the one-pair WQH matrix from § 2.3. Since and , we have , and . For , its action is
Lemma 6.10. Let . Then if and only if at least one of the following conditions holds:
(a) ;
(b) both and are constant, possibly with different values;
(c) is even, and the signed vector contains two distinct roots, each occurring 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 , then and the signed values are replaced by , respectively. These descriptions agree when the conditions overlap. In particular, for odd , conditions (a) and (b) are the only possibilities.
Proof. Sufficiency follows from (18). For necessity, the case is (a). Suppose , and write . Every entry of satisfies . The two circles have distinct centres, so has at most two distinct values. If is constant, (b) holds. Otherwise, let its two values be , with occurring a proportion of the time. Since
the equality gives
Thus each value occurs times. If is even, all entries of lie in , giving (c). If is odd, the sets and are disjoint. The entries of lie in the first set and those of in the second. With only two values available, each half must therefore be constant, giving (b).
Theorem 6.11. Let , and let be pairwise disjoint nonempty row sets with . In , put
where is the difference of characteristic vectors. Equivalently, with
the entries of are
Then if and only if every column restricted to each ordered pair satisfies Lemma 6.10. Whenever this holds, the operation is an involution on the same row sets.
Proof. The vectors have disjoint supports and squared norms . Hence and , and
The remaining requirement is entry preservation, which is precisely Lemma 6.10 on each pair. The identity proves involutivity. □
Remark 6.12. The relation with the preceding construction is
For even , 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 , the signs in 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 , the paired row sets and be as in Theorem 6.11. Suppose that for every pair and every column either
(a) each element of occurs equally often on and ; or
(b) the column is constant on each of and , possibly with different values.
Then , and is obtained from by WQH-switching with paired cells
and remainder 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 . Within their union, every vertex has only its own loop, so the difference constants in Theorem 2.3(ii) are for a pair with itself and for distinct pairs. Remaining row vertices have no neighbours in the cells. For a column vertex, the neighbourhood counts are
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 .
Conversely, fix , , and let be the multiplicity of on . Varying in (22), the WQH condition requires, for every , either or
If any pair of counts differs, one half is constant. Since the multiplicities in each half sum to , 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 and . Under the hypotheses of Theorem 6.13, we have
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 as additive on complex numbers. The second identity proves cospectrality for every phase covered by the lifting criterion.
Corollary 6.14. Let be prime, and let be as in Theorem 6.11. If , 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 , Lemma 6.10 allows only equal sums or constant halves. For , its case (c) also has equal sums, since the two distinct signed values are and . It therefore remains to consider equal sums. Write for the phase multiplicities of the two halves and put
We have . Since is prime and , the minimal polynomial of gives for some rational . The two halves have equal size, so , whence . 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 , take and . The reflection fixes columns and negates column , so it preserves the Butson property. However, in column the two halves are and . Their sums agree but their phase multiplicities do not, and has respectively and neighbours in and . 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 be the matrix in Example 6.9, and take and . Its first two columns are constant on each half, with values and , respectively. In each of the other four columns, the two halves have identical phase multisets.
Thus gives
Only the first two columns on the four selected rows change. Theorem 6.13 realises this operation as WQH-switching on the three pairs
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 instead rotates phase classes. We make this observation precise in a graph-switching construction.
Theorem 6.16. Let be a graph with disjoint vertex sets of the same size , where . Suppose that their union is independent and has no loops. For every vertex , suppose that either
(i) for some ; or
(ii) .
For each vertex in case (i), replace its neighbourhood by , with indices modulo . Leave all other adjacencies unchanged. The resulting graph is cospectral with .
Proof. Order the vertices of by the classes , and put
Since and are orthogonal projections and is orthogonal, . Let be the row of incidences from a vertex outside to . If its blocks have equal sums, then . If is all ones in block and zero elsewhere, multiplication by moves that all-one block to .
Write the adjacency matrix with the vertices outside first. Conjugating by preserves the zero block on , preserves the adjacency block outside , and changes the off-diagonal blocks exactly as stated. It therefore produces the adjacency matrix of the switched graph. Orthogonal similarity proves cospectrality.
When , this is the one-pair WQH operation for independent switching sets. No divisibility condition on is required by the graph theorem.
We next apply the theorem to Proposition 6.1. After scaling the first rows, we may assume that the selected block is . Let be the submatrix formed by the remaining rows and those same columns. The proof of Proposition 6.1 gives zero row sums for . To obtain the graph switching, we require the stronger condition: that each element of occurs equally often in every row of . If has no rows, this condition is vacuous. Otherwise it implies . For prime , 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 occurs equally often in the submatrix completing the columns of the selected block, normalised to . Let be obtained by multiplying that block by . Then is obtained from by the cyclic switching of Theorem 6.16. In particular, and are cospectral. The balance hypothesis is automatic when is prime.
Proof. Assume the selected columns are and put
Their union is independent. Every selected row vertex , with , is adjacent to all of and none of the other classes. By Lemma 3.7, every other row vertex has neighbours in each ; other column vertices have none. The graph theorem therefore applies. Its cyclic change replaces the matching for an entry in the selected block by the matching for , giving .
We can also express this correspondence directly in the original vertex order. Put and define the complex unitary matrix
and the real orthogonal matrix
The first matrix multiplies a constant row by and fixes a row with sum zero. The second rotates the constant phase-class components and fixes their orthogonal complement. We define explicitly, since has no additive extension to complex numbers that would justify writing it as .
Under the balance condition,
For the second identity, each row-block sum of is , which annihilates on the right. Hence, with ,
Writing gives
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, has sum zero in but contains neither of the phases , and . 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]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]A. Abiad and L. Peters. Switching graphs and Hadamard matrices. The Art of Discrete and Applied Mathematics, 2025.arxiv.org/abs/2410.10638
- [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]W. Bosma, J. Cannon, and C. Playoust. The Magma algebra system. I. the user language. J. of Symbolic Comput., 24:235–265, 1997.
- [5]A. T. Butson. Generalized Hadamard matrices. Proc. Amer. Math. Soc., 13:894–898, 1962.DOI
- [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]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]P. J. Davis. Circulant matrices. John Wiley & Sons, New York-Chichester-Brisbane, 1979.
- [9]W. de Launey and D. Flannery. Algebraic Design Theory. Mathematical Surveys and Monographs, vol. 175. American Mathematical Society, Providence, RI, 2011.
- [10]P. Diță. Some results on the parametrization of complex Hadamard matrices. J. Phys. A: Math. Gen., 37(20):5355–5374, 2004.DOI
- [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]C. D. Godsil and B. McKay. Constructing cospectral graphs. Aequationes Math., 25(1):257–268, 1982.DOI
- [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]T. Y. Lam and K. H. Leung. On vanishing sums of roots of unity. J. Algebra, 224(1):91–109, 2000.DOI
- [15]B. D. McKay. Hadamard equivalence via graph isomorphism. Discrete Mathematics, 27:213–214, 1979.DOI
- [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]F. Szöllősi. Parametrizing complex Hadamard matrices. European J. Combin., 29(5):1219–1234, 2008.arxiv.org/abs/math/0610297
- [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