Morphisms of Butson classes
Ronan Egan Padraig Ó Catháin
math.CO 05B20, 05B30, 05C50

empty
Theory and particle tracking simulations of a resonant radiofrequency deflection cavity in TM_110 mode for ultrafast electron microscopy
    [
    December 30, 2023
========================================================================================================================================




We introduce the concept of a morphism from the set of Butson Hadamard matrices over k roots of unity to the set of Butson matrices over ℓ roots of unity.  As concrete examples of such morphisms, we describe tensor-product-like maps which reduce the order of the roots of unity appearing in a Butson matrix at the cost of increasing the dimension. Such maps can be constructed from Butson matrices with eigenvalues satisfying certain natural conditions.  Our work unifies and generalises Turyn's construction of real Hadamard matrices from Butson matrices over the 4 roots and the work of Compton, Craigen and de Launey on `unreal' Butson matrices over the 6 roots.  As a case study, we classify all morphisms from the set of n × n Butson matrices over k roots of unity to the set of 2n× 2n Butson matrices over ℓ roots of unity where ℓ < k.
[2010 Mathematics Subject Classification: 05B20, 05B30, 05C50][Keywords: Butson Hadamard matrix, morphism, eigenvalues]






§ INTRODUCTION


Let M be an n × n matrix with entries in the complex numbers ℂ. If every entry m_ij of M has modulus bounded by 1,
then Hadamard's theorem states that |(M)| ≤ n^n/2. Hadamard himself observed that a matrix M meets this bound with equality if and
only if every entry in M has modulus 1, and every pair of distinct rows of M are orthogonal (with respect to the usual Hermitian inner product) <cit.>. While Hadamard's name has become associated with real matrices meeting the bound, his original paper is not restricted to this case.

It is well known that a real Hadamard matrix of order n (i.e. a matrix with entries in {± 1 } meeting the Hadamard bound) can exist only if n = 1, 2 or n ≡ 0  4.
The Hadamard conjecture states that these necessary conditions are also sufficient. Since the discovery in 2005 of a real Hadamard matrix of order 428, the smallest
open case is n = 668 <cit.>. Asymptotic existence results are also available in the real case: building on pioneering work of Seberry, Craigen has shown that
for any odd integer m, there exists a Hadamard matrix of order 2^αlog_2(m) + 2m where α < 1 is a constant <cit.>.
Despite the existence of many constructions for Hadamard matrices, the density of integers n for which it is known that there exists a Hadamard matrix of order n is essentially
given by the density of the Paley matrices (i.e. the density of the primes, all other constructions contribute a higher order correction term) <cit.>.

There is an analogue of the Hadamard conjecture for any number field: the usual Hadamard conjecture concerns the existence of Hadamard matrices over ℚ.
Examples of matrices are known in which the entries are described as roots of modulus 1 of certain polynomial equations, see matrix A_8^(0) of the database <cit.> for example. We will be exclusively interested in matrices whose entries are roots of unity in this paper. We write M^∗ for the Hermitian transpose of M.


A matrix H of order n with entries in ⟨ζ_k⟩ is Butson Hadamard if HH^∗ = n I_n.
We write (n,k) for the set of such matrices.


There exists a large literature on real Hadamard matrices, which have close ties to symmetric designs, certain binary codes and difference sets <cit.>.
The Butson classes (n,4) and (n,6) have received some attention in the literature, due to applications in signal processing and connections
to real Hadamard matrices <cit.>. In fact, if (n,4) is non-empty, then (2n,2) is necessarily non-empty. This motivates the
complex Hadamard conjecture: that there exists a Hadamard matrix of order n with entries in {± 1, ± i} whenever n is even.

More generally, de Launey and Winterhof have described necessary conditions for the existence of Hadamard matrices whose entries are roots of unity <cit.>. A typical application of these results shows that (n, 3^a) is empty whenever the square-free part
of n is divisible by a prime p ≡ 5  6. In contrast to (n,2) and (n,4), there does not appear to be any consensus in the
literature on sufficient conditions for (n,k) to be non-empty for general values of k. Apart from the obvious examples of character tables of
abelian groups, relatively few constructions for matrices in (n,k) are known. An early result of Butson shows that for all primes p, the set (n,p)
is empty unless n ≡ 0  p, and that (2p,p) is non-empty <cit.>. Further constructions and a survey of known results are given by Agaian <cit.>.




§ MORPHISMS OF BUTSON MATRICES


We define a (complete) morphism of Butson matrices to be a function (n,k) →(r,ℓ).
The Kronecker product is perhaps the best-known example of a morphism: if M ∈(m,d) and
H is any matrix in (n,k) then H ⊗ M ∈(mn, ℓ) where ℓ is the least common
multiple of k and d. To be explicit, the map - ⊗ M: (n,k) →(mn,ℓ)
is a Butson morphism.

We will restrict our attention to morphisms which come from embeddings of matrix algebras (as the tensor product does),
such morphisms can be considered generalised plug-in constructions. In this case, we say a morphism (n,k) →(mn,ℓ) is of degree m.  We will be particularly interested in the construction
of morphisms where k does not divide ℓ. We will also relax our conditions to allow partial morphisms,
where the domain is a proper subset of (n,k); typically we impose a restriction on matrix entries of H.
We introduce the concept of a sound pair to collect necessary and sufficient conditions for our main existence theorem.

We define ζ_k = e^2π i/k, and set G_k = ⟨ζ_k⟩.  We define H^ϕ to be the entrywise application of ϕ to H whenever ϕ is a function defined on the entries of H, and we write H^(r) for the function which replaces each entry of H by its r power.

 
Let X,Y ⊆ G_k be fixed.
Suppose that H ∈(n,k) such that every entry of H is contained in X,
and that M ∈(m,ℓ) such that every eigenvalue of √(m)^-1M is contained in Y.

Then the pair (H, M) is (X,Y)-sound if


  * For each ζ_k^i∈ X, we have √(m)^1-i M^i∈(m, ℓ).

  * For each ζ_k^j∈ Y, we have H^(j)∈(n,k).

We will often say that (H,M) is a sound pair if there exist sets X and Y for which (H, M) is (X, Y)-sound.



Often the first condition of a sound pair is satisfied only when i is odd: this occurs
in particular when ℚ[ζ_k] contains no elements of absolute value √(m).
But there do exist matrices satisfying this condition where m is not a perfect square:
one example is given by the square of the matrix

    M_24 = [ [  1  1;  i -i ]] ,    √(2)^-1M_24^2 =  [ [   ζ_8 ζ_8^7;   ζ_8 ζ_8^3 ]]

which belongs to (2,8). This example also shows that one should distinguish carefully between ℓ and the
degree of the cyclotomic field generated by the entries of M in Definition <ref>. A natural question arises
about the smallest field containing the entries of √(m)^1-iM^i for all i. Since we are interested exclusively
in Butson matrices, this will be the largest cyclotomic field contained in ℚ[ζ_ℓ, √(m)], which is at
most a quadratic extension of ℚ[ζ_ℓ], so its torsion units will be at most 2ℓ roots of unity if
ℓ is even and 4ℓ roots of unity if ℓ is odd.

Before we prove our main theorem, we recall that for an n× n matrix A, and an
m × m matrix B, the Kronecker products A ⊗ B and B ⊗ A are similar matrices.
There exists a permutation matrix P_mn such that P_mn (A⊗ B) P_mn^-1 = B ⊗ A.
We call this matrix the Kronecker shuffle. The locations of the non-zero entries in P_mn can be precisely described.

 
For any m,n ∈ℕ, the nm × nm Kronecker shuffle matrix P_mn is

    P_mn = [ δ^im - ⌊(i-1)/n⌋(mn-1)_j + m - 1]_1≤ i, j ≤ mn .

If M is an mn × mn matrix consisting of n× n diagonal blocks,
then P_mnM P_mn^-1 has m× m blocks down the diagonal and is zero elsewhere.


We now show that the conditions of a sound pair are sufficient to guarantee that a plug-in construction
gives a Hadamard matrix.


Let H ∈(n,k) and M ∈(m,ℓ) be Hadamard matrices.
Define a map ϕ: ζ_k^i↦√(m)^1-i M^i, and write
H^ϕ for the entrywise application of ϕ to H.
If (H, M) is a sound pair then H^ϕ∈(mn,ℓ).



Fix sets X,Y ⊆ G_k such that (H, M) is (X, Y)-sound.
By the first property of a sound pair, for every ζ_k^i∈ X,
the image ϕ(ζ_k^i) = √(m)^1-i M^i∈(m, ℓ). Hence
every entry in H^ϕ is in ⟨ζ_ℓ⟩. To show that H^ϕ is a Hadamard matrix, it will suffice
to show that every eigenvalue of H^ϕ has absolute value √(mn).

Every Hadamard matrix is diagonalisable. Write A for a matrix
such that AMA^-1 is diagonal, and define
ψ(ζ_k^i) = √(m)^1-i AM^iA^-1.
Observe that if ζ_k^α is the t
diagonal entry of AMA^-1, then
ψ(ζ_k^i)_t,t = ζ_k^iα, where by hypothesis ζ_k^α∈ Y.
Writing H^ψ for the entrywise application of ψ to H, it follows easily that

    H^ψ = (I_n⊗ A) H^ϕ (I_n⊗ A^-1) .

Now, H^ψ is an mn × mn block matrix in which each m× m
block is diagonal. Applying Proposition <ref>, we obtain a block diagonal matrix,

    P_mn H^ψ P_mn^-1 = diag [ B_1, B_2, …, B_k]  .


To conclude, observe that B_t[i,j] = √(m)ψ(h_i,j)_t,t = √(m)h_i,j^α with the notation chosen above.
So B_t = √(m)H^(α), and by the second property of a sound pair, each eigenvalue of B_t has absolute value √(mn).
This argument holds for each block B_t, so since P_mnH^ψP_mn^-1 and H^ϕ are similar, we have H^ϕ∈(mn,ℓ) as required.


In the special case that every eigenvalue of M is a primitive k root of unity, the second condition of Definition <ref> is vacuous:
raising each entry to its α power for α coprime to k is a field automorphism. Such an operation preserves both the modulus of entries of H and the orthogonality of rows.
These are examples of global equivalence operations as considered by de Launey and Flannery <cit.>.
The first condition of Definition <ref> still places restrictions on the entries of H: it can never contain 1, for example;
since the image of ζ_k^0 = 1 in H^ϕ never has entries of modulus 1. Next we identify some sound pairs of
special interest, since they correspond to complete morphisms.


Suppose that M ∈(m,ℓ),
that all eigenvalues of M are primitive
k roots of unity,
and that √(m)^1-i M^i is
Hadamard for all i coprime to k.
Let d = ∏_i=1^r p_i^α_i such that p_i^α_i+1| k
for 1 ≤ i ≤ r. Then there exists a complete Butson morphism (n,d) →(mn,ℓ).



Under the hypotheses, the primitive k roots of unity contain a translate of the d roots of unity.
If H ∈(n,d) then every entry of ζ_kH is a primitive k root. The conditions of
Definition <ref> are satisfied with X and Y both taken to be the
primitive k roots of unity. The claim follows from Theorem <ref>.



The following construction of Turyn illustrates Corollary <ref>.

[Turyn, <cit.>]

Let M_8 be the matrix

    M_8 = [ [  1  1; -1  1 ]] .

It is easily verified that the eigenvalues of M_8 are √(2)ζ_8
and √(2)ζ_8^7. Likewise, it can be verified that

    1/2 M_8^3 =  [ [ -1  1; -1 -1 ]]

that 2^-2M_8^5 = -M_8 and that 2^-3M_8^7 = -M_8^3. (In fact M_8^8 = 16I_2.)
Thus M_8 satisfies all the conditions of Corollary <ref> with m = 2 and ℓ = 8.
So for any H ∈(n,4), the pair (ζ_8 H, M_8) is sound. We recover Turyn's famous
morphism: (n,4) →(2n,2).


Next, we illustrate the full generality of Theorem <ref>.

[Compton, Craigen, de Launey <cit.>]

Let M_6 be the following matrix (which is in fact similar to the matrix given by Compton, Craigen and de Launey):

    M_6 = [ [  1  1  1  1; -1  1 -1  1; -1  1  1 -1; -1 -1  1  1 ]] .

One computes that the eigenvalues of 2^-1M_6 are the primitive sixth roots of unity, each with multiplicity 2.
Likewise, one can check that 2^-1M_6^2 is Hadamard and that M_6^3 = -8I_4. As a result, 2^-3M_6^4 and 2^-4M_6^5 are Hadamard.

In the definition of a sound pair, we can take
X = {ζ_6, ζ_6^2, ζ_6^4, ζ_6^5} and
Y = {ζ_6, ζ_6^5}. Since raising each entry to its first power is the identity map on
⟨ζ_6⟩ and raising an entry to its 5 power is complex conjugation,
the restrictions placed on H by Y are vacuous. Since M_6^3 is a scalar matrix,
we cannot allow -1 as an entry in H. Compton, Craigen and de Launey call a matrix in (n,6) with
entries in X unreal. We have constructed a partial morphism: (n,6) →(4n,2)
with domain the unreal matrices.


We conclude this section with a question which we feel should have a positive answer.


If the eigenvalues of M ∈(m, ℓ) are all primitive k roots of unity, is it true that √(m)^1-iM^i ∈(m, ℓ) for all i coprime to k?





§ CONSTRUCTION OF BUTSON MORPHISMS
 




 §.§ Partial morphisms


We begin by describing a relationship between certain sets of mutually unbiased bases and partial morphisms of Hadamard matrices.


Let V be an n-dimensional vector space over ℂ carrying the usual Hermitian inner product.
Two orthonormal bases B_1 and B_2 of V are unbiased if |⟨ u,v ⟩| = n^-1/2
for all u ∈ B_1 and v ∈ B_2. A set of bases is mutually unbiased if each pair is
unbiased.


We refer to sets of mutually unbiased bases as MUBs. Such objects are of substantial interest in quantum physics,
and are well studied in the literature. Normalising so that B_0 is the standard normal basis, every other B_i
is necessarily represented by a Hadamard matrix. Being mutually unbiased means that B_iB_j^∗ is again Hadamard
for all i ≠ j. The largest possible number of MUBs in ℂ^d is d+1. Maximal sets of MUBs are known to exist in
every prime power dimension, and in no other dimensions. It is believed that the maximal number of MUBs in dimension 6 is three,
but this is an outstanding open problem <cit.>.

To construct sound pairs, we require a Hadamard matrix M for which a specified set of its powers are Hadamard. Since M^i (M^j)^∗ = M^i-j,
a subset ℬ of the powers of M is a set of MUBs if and only if M^i-j is Hadamard for all M^i, M^j∈ℬ.
A remarkable construction of Gow yields Butson matrices with the property that every power is either Hadamard or scalar.
The construction uses the representation theory of extra-special p-groups of exponent p over ℂ for odd p, these are the so-called discrete Heisenberg groups. (For p = 2, Gow uses generalised quaternion groups.)


Let q = 2^a such that q+1 is prime.
There exists M_q∈(q, 4) and M'_q∈(q^2, 2)
such that M_q has only primitive (q+1)^st roots of unity
as eigenvalues.



Since M'_q∈(q^2, 2), every eigenvalue of q^-1M'_q
is a complex number of modulus 1. Since q+1 is prime, the eigenvalues
are even (q+1)^st roots of unity (though not necessarily all primitive).
Gow proves that the trace of q^-1M'_q is -q. Together with the irreducibility of the
cyclotomic polynomials over ℚ, this shows that every eigenvalue of q^-1M'_q
is a primitive (q+1)^st root of unity.

The proof is similar in the complex case: again, the matrix √(q)^-1M_q is of multiplicative order q+1.
So the eigenvalues are (q+1)^st roots of unity, and the minimal polynomial divides the cyclotomic polynomial
Φ_q+1(x). Factoring q+1 over the Gaussian integers and applying a generalisation of Eisenstein's criterion,
shows that Φ_q+1(x) remains irreducible over ℚ[i], so every eigenvalue of √(q)^-1M_q is again a
(q+1)^st root of unity.


The smallest example of Gow's theorem is in dimension 2, where Gow gives the matrix

    2^-1/2ζ_8M = 1+i/2[ [ -1  i;  1  i ]]  .

Some care is necessary in interpreting the matrices of Theorem <ref> as partial morphisms, however.
While Gow's unitary matrix is defined over ℚ[i] and has order 3, the corresponding Hadamard matrix
(denoted M above) has order 24. In fact, if there exists M ∈(2, ℓ) such that 2^-3/2M^3 = I_2
then 8 |ℓ. Interestingly, applying the Turyn morphism to ζ^5_8M yields a matrix in (4, 2) which is
similar to the Compton-Craigen-de Launey matrix of Example <ref>. For a Fermat prime p > 3, it is well known that p-1
is a perfect square, and we do not need to pass to a larger field.


Suppose that p = 2^a + 1 is a Fermat prime, p> 3. Then there exists M_p∈(2^a, 4) and M'_p∈(2^2a, 2) with only primitive p roots as eigenvalues.
Hence, for any H ∈(n,p) with no entries equal to 1, the pairs (H, M_p) and (H, M'_p) are sound.


Gow has also constructed large sets of MUBs as powers of a single matrix in odd prime power dimensions. But when q+1 is not prime, the conditions imposed by Definition
 <ref> on H may be impossible to satisfy. Gow's 5 × 5 matrix has eigenvalues {-1, ±ω, ±ω^2},
 which require that H^(2) and H^(3) both be Hadamard. But this implies that H is generalised Hadamard over
 the cyclic group of order 6: generalised Hadamard matrices have been constructed only over p-groups, and it has been conjectured
that no such matrices exist over groups of composite order. (See Section 2.10 of <cit.> for the definition of generalised Hadamard matrices, and
<cit.> for some non-existence results.)


It seems rather difficult to realise Gow's work as an explicit construction for partial morphisms.
We constructed several examples computationally. The follows matrix has as eigenvalues the primitive fifth roots of unity.

    M_5 = [ [ -1 -1 -1 -1;  1 -1  1 -1;  i  i -i -i;  i -i -i  i ]] .

Equivalently, M_5 induces a partial morphism (n, 5)→(4n, 4) where the domain consists of matrices have no entries
equal to 1. Allowing negations, we obtain a map (n, 10) →(4n, 4) with domain the unreal matrices (i.e. those containing no real entries).


These morphisms generalise the Compton-Craigen-de Launey result which is the case a = 1 of Corollary <ref>.




 §.§ New morphisms from old


Suppose that there is a complete morphism (n,d) →(nm,ℓ) where M, d and k are defined as in Corollary <ref>.
The next result allows us to construct new morphisms over larger roots of unity.


If (ζ_kH,M) is (X,Y)-sound for all H ∈(n,d) where Y consists only of primitive k roots of unity, then (ζ_ktH, ζ_tM) is sound for any t coprime to k.



The eigenvalues of ζ_tM are primitive kt roots of unity.
Let T ⊂{1,…,k-1} be the set of all i such that √(m)^1-iM^i ∈(m, ℓ).
By hypothesis, M induces a complete morphism (n,d) →(nm,ℓ);
so T contains an arithmetic progression of length d, say D ⊆ T.

Furthermore, √(m)^1-kt(ζ_tM)^kt = I_m, and √(m)^1-a(ζ_tM)^a ∈(m, ℓ t) whenever a ≡ i  k and i ∈ T.
Let T' be the set of all a such that √(m)^1-a(ζ_tM)^a ∈(m, ℓ t). Define D' ⊆ T' to be the set exponents such that a  t is in D.
Then D' is an arithmetic progression of length dt.  Thus (ζ_ktH, ζ_tM) is (X',Y')-sound for all H ∈(n,d), where X' = {ζ_kt^i  :   i ∈ T'} and Y' is the set of primitive kt roots of unity.



If there exists a complete morphism (n,d) →(nm,ℓ), there exists a complete morphism (n,dt) →(nm,(t,ℓ)).


As an illustration of Theorem <ref> we generalise Turyn's morphism.


Let M_8 be the matrix of Example <ref>. The eigenvalues of ζ_3M_8 are primitive 24 roots of unity, and √(2)^1-i(ζ_3M_8)^i
is Hadamard for all odd i. So for any H ∈(n,12), the pair (ζ_24H,ζ_3M_8) is sound, and thus there is a complete morphism (n,12) →(2n,6).


We can also generalize to partial morphisms.  For example, the matrix

    M_12 = 2^-1[ [  1  1  1  1;  1 -1 -1  1;  1  1 -1 -1; -1  1 -1  1 ]]

is of order 12, has primitive 12 roots as its eigenvalues, and 2^-iM_12^i is Hadamard for all i ∈ T = {1,2,4, 5,7,8,10,11}.
Then 2^1-i(ζ_5M_12)^i is Hadamard for all i ∈ T' = {1,…,60-1}∖{3,6,…,57}, and the eigenvalues of ζ_52^-1M_12 are primitive 60 roots of unity.  So T' contains two arithmetic progressions of length 20.  Thus, with the appropriate choice of X and Y, (ζ_60H,ζ_5M_12) is sound for any H ∈(n,20), and (K,ζ_5M_12) is sound for any K ∈(n,60) such that no entry in K is a 20 roots of unity.  So there is a complete morphism (n,20) →(4n,10) and a partial morphism (n,60) →(4n,10).




 §.§ Construction of complete morphisms


The construction of large sets of MUBs is a challenging open problem, even without the added restriction that all of the bases arise as powers of a single matrix.
As a result, we do not expect in general to find subgroups of ⟨ m^-1/2 M ⟩ which contain many Hadamard matrices. On the other hand, there seem to
be few restrictions on cosets containing many Hadamard powers. This is precisely the intuition behind Corollary <ref>.

It seems natural (though not strictly necessary) to study matrices M such that M ∈(m, ℓ) and the unitary matrix m^-1/2M has as eigenvalues only primitive k roots of unity. The characteristic polynomial of m^-1/2M is a divisor of a power of the cyclotomic polynomial Φ_k(x). So the possible characteristic polynomials then depend on the factorisation of Φ_k(x) in ℚ[ζ_ℓ, √(m)]. The following Proposition gives an easy construction of larger complete morphisms from small ones.


Suppose that 4 | k and that the eigenvalues of M ∈(m, ℓ) are primitive k roots of unity. If H ∈(n, ℓ) is Hermitian, then the eigenvalues of H ⊗ M ∈(mn, ℓ) are all primitive k roots of unity.



The eigenvalues of H are real, and so all lie in {±√(n)}. The eigenvalues of a tensor product are the products of the eigenvalues
of the component matrices, and by hypothesis, ζ_k^i is primitive if and only if ζ_k^i + n/2 is.


The first interesting examples of complete morphisms occur when M is real and its eigenvalues are primitive 8 roots of unity. The matrix M_8 in Example <ref> is one such. It is somewhat unusual in that the size of the matrix is smaller than the degree of Φ_8(x); in fact its characteristic polynomial comes from an exceptional factorisation of cyclotomic polynomials related to Sophie Germain's identity. Larger examples of complete morphisms can be constructed from the Turyn example via tensor products. We combine Proposition <ref> and Example <ref>: since real symmetric Hadamard matrices are easily constructed at orders 1, 2 and 4t for all t ≤ 10, we will focus on the cases n ≡ 4  8. The classification of (10, 4) and (14, 4) has been completed up to Hadamard equivalence by Lampio, Szöllősi and Östergård: Hermitian matrices exist at both orders <cit.>. We have not yet managed to construct a real Hadamard matrix of order 36
with eigenvalues in the set {6ζ_8, 6ζ_8^3, 6ζ_8^5, 6ζ_8^7}.


There exists a complete morphism (n, 4) →(2mn,2) whenever there exists a Hermitian matrix in (m, 4).
In particular, there exist such morphisms for m = 1 and for all even m ≤ 8.


It seems more challenging to construct complete morphisms (n,k) →(mn, ℓ) for which k and ℓ are coprime.


What is the smallest m for which there is a complete morphism (n,3) →(mn,2)?


If M yields a complete morphism as in the question, then the eigenvalues of M are primitive 9k^th roots of unity for some k ∈ℕ. If k = 4, the characteristic polynomial of (12t)^-1/2M is necessarily (x^12 - x^6 + 1)^t, where M is a matrix of order 12t. The characteristic polynomial of M can be obtained from that of the unitary matrix via the substitution x^k↦ (12t)^(n-k)/2x^k.




 §.§ Eigenvalues of (2,ℓ)


In this section we classify all M ∈(2,ℓ) for which the corresponding unitary matrix has finite multiplicative order, and study morphisms derived
from these matrices. We begin with a lemma on roots of unity which will constrain the eigenvalues of M.

 
Suppose that α and λ are roots of unity such that (α) = √(2)(λ). Then up to negation and complex conjugation, [α, λ] is one of [i, i], [1,ζ_8], [ζ_8, ζ_6].



Recall that (ζ) = 1/2(ζ + ζ^-1). So we require the solutions of the identity

    α + α^-1/λ + λ^-1 = √(2) .

Expanding as a quadratic in α and solving, we have that

    √(2)α = -(λ + λ^-1) ±√(λ^2 + λ^-2) .

Applying field automorphisms, we may assume that λ = ζ_k for some suitable integer k.
Suppose that k ≥ 8, then λ + λ^-1 = 2(λ) ≥√(2), while |√(λ^2 + λ^-2)| ≤√(2).
Since k ≥ 8, we have that (λ^2) > 0, hence the right hand side of the equation is real and negative. The unique solution of
absolute value √(2) occurs when k = 8. The solutions with k < 8 can be found by inspection.




Suppose that M ∈(2, ℓ) such that 2^-1/2M has finite multiplicative order.
Then λ_1λ_2^-1∈{-1, ± i, ±ζ_3}.



For an arbitrary 2 × 2 Butson matrix

    M = [ [ α β; γ δ ]] ∈(2, ℓ),

we observe that (α^-1/2δ^-1/2) M has real trace, and hence its eigenvalues are
conjugate. Furthermore, the ratio of the eigenvalues of H is preserved by scalar multiplication.
Orthogonality of rows forces β = -γ^∗. In fact, different choices of β yield similar matrices.
So to compute the ratio of the eigenvalues of M, it suffices to consider matrices of the form

    M_α = [ [    α    α; -α^*  α^* ]] .

We compute the eigenvalues explicitly:

    λ = (α) + i √( 2 - (α)^2),    λ^∗ = (α) - i √( 2 - (α)^2) .

Since clearly (α) ≤ 1, the second term is always purely imaginary and we have (α) = (λ).
The matrix 2^-1/2M_α has finite order if and only if its eigenvalues are roots of unity. Setting 2^-1/2λ = λ', we require the classification of  the pairs of roots of unity (α, λ') for which (α) = √(2)(λ'). Now apply Proposition <ref>.


Corollary <ref> reduces the analysis of the 2 × 2 Butson matrices to three cases. We deal with the traceless matrices
separately, since the proof is short, and we never obtain morphisms for which k ≥ℓ.


Suppose that M ∈(2, ℓ) such that 2^-1/2M has finite multiplicative order with k root of unity eigenvalues.
Then if λ_1 = -λ_2, k ≤ℓ.



Let a = m_11, and so m_22 = -a. Orthogonality of the rows of M implies that m_12 = ab and
m_21 = ab^∗ for arbitrary b of modulus 1. It is easily verified that different choices of b produce similar
matrices and that the eigenvalues of M are ±√(2) a. Hence k ≤ℓ.


Now we turn our attention to the remaining cases of Corollary <ref>. We will restrict attention to matrices M in (2, ℓ) for
which the eigenvalues of 2^-1/2M are primitive k roots. From this information, we easily obtain a classification of all complete morphisms of order 2.


Suppose that M ∈(2, ℓ), and that the eigenvalues of M are both primitive k
roots of unity for some k > ℓ. Then M is one of the following, where a,b are ℓ roots of unity.


  * M_1 = ( [     a    ab; -ab^∗     a ]), and ℓ = 2^αt where t is odd. Then k > ℓ when α≤ 2, and both eigenvalues have the same order when α≠ 3.


  * M_2 = ( [      a     ab; -iab^∗     ia ]), and ℓ = 2^α3^βt where t is coprime to 6. Then k > ℓ when β≤ 1 or α≤ 3, and both eigenvalues have the same order when β≠ 1 and α≠ 3.




Throughout we write λ_1,λ_2 for the eigenvalues of M, and m_ij for the entry in row i and column j.
By Corollary <ref> and Lemma <ref>, we may assume that (up to relabelling of eigenvalues and negation of M) that
λ_1λ_2^-1∈{i, ζ_3}.


1: Suppose λ_1 = iλ_2. Then writing λ_1 = √(2)ω for some ω∈ℂ of modulus 1,
we have that m_11 + m_22 = 2ζ_8ω, where ζ_8ω.
By the triangle inequality, a := m_11 = m_22.  Enforcing the orthogonality of the rows of M,
we find that m_12 = ab and m_21 = -ab^∗ for arbitrary b of modulus 1.  Thus under the assumption that M ∈(2, ℓ),
we have that M = M_1. It is easily verified that different choices of b produce similar matrices,
and the eigenvalues of M_1 are √(2)ζ_8a and √(2)ζ_8^7 a.

For convenience, we write M_1(a) for the unitary matrix with 2^-1/2a on the diagonal,
and up to similarity we can take b = 1. The group generated by M_1(a) is finite and cyclic,
and so a direct product of a cyclic 2-group and group of odd order.
Since M_1(a)^4 = -a^4I_2 a maximal subgroup of odd order is scalar.
Squaring is an automorphism on the roots of unity of odd order, hence there
exists some root of unity of odd order ζ∈⟨ζ_ℓ⟩
such that M_1(a) = ζ M_1(a'), where a' is a root of unity of order 2^α.

It is easily verified that when a' ∈{± 1, ± i} that the eigenvalues of M_1(a') are
primitive 8 roots of unity. But when a' is a primitive 8 root, then one eigenvalue
of M_1(a') is real while the other is purely imaginary. Finally, a' is a primitive root of unity
of order 2^α for α≥ 3, then both eigenvalues of M_1(a') are again of order 2^α.

We write ℚ[ζ_ℓ] for the coefficient field of √(2)M_1(a), where ℓ = 2^αt and t is odd.
Orthogonality of the rows of M_1(a) implies that α≥ 1. When α∈{1, 2}, the eigenvalues of M_1(a)
are both primitive roots of unity of order 8t, and so k > ℓ. When α = 3
the eigenvalues have different orders, and in all cases, M_1(a)^4t = I_2, while when α≥ 4 we always have k ≤ℓ.


2: Suppose that λ_1 = ζ_3λ_2.
Then the sum of the eigenvalues has modulus √(2), from which we conclude that a := m_11 = im_22.
As before, we can solve for the off diagonal entries in terms of a single unknown, obtaining m_12 = ab and m_21 = -iab^∗.
Thus under the assumption that M ∈(2, ℓ), we have that M = M_2. The eigenvalues of M_2 are λ_1 = √(2)ζ_24^7a
and λ_2 = √(2)ζ_24^23a.

For convenience, we write M_2(a) for the unitary matrix with 2^-1/2a and 2^-1/2ia on the diagonal, again up to similarity we can take b = 1.  The group generated by M_2(a) is finite and cyclic when a is a root of unity, and contains a scalar subgroup of index 3 generated by (2^-3/2a^3(2-2i))I_2.

Suppose now that a is a primitive ℓ root of unity where ℓ = 2^α3^βt, with (t, 6) = 1.
For each choice of α, β, t, it is routine to compute the orders of the eigenvalues, though there are a large number of
cases to consider. Since -ia is an entry of √(2)M_2(a), we can assume that α≥ 2. Next we will show that the eigenvalues of
M_2(a) have distinct orders if and only if β = 1 or α = 3.

Suppose that β = 1: then the eigenvalues of M_2(a) are ζ_24ℓ^24i + 7ℓ and ζ_24ℓ^24i + 23ℓ where i ≡ 1, 2  3 and ℓ≡ 3, 6  9 (since a is a primitive ℓ root). Suppose that i ≡ 1  3 and ℓ≡ 3  9, then 24i + 7 ℓ≡ 0  9 while 24 i + 23 ℓ≡ 3  9. But since 9 | 24 ℓ, the eigenvalues do not have the same order. The remaining three cases are similar; in no case do the eigenvalues of M have the same order. When a is a primitive 8 root, M_2(a) has order 3, 6 or 12 (depending on the choice of primitive root). When ℓ = 2^3t with (t, 6) = 1 we obtain matrices of orders 3t, 6t, 12t. And by a similar argument, when ℓ = 2^3 3^β t with β≥ 2 we obtain matrices of order 3^βt, 2 · 3^βt,4 · 3^βt.

It remains to examine the cases α = 2 and β≠ 1, and α≥ 4 with β≠ 1. In the first case, when α = 2 and β = 0, we have that a = ζ_24^jζ_t for j ∈{6, 18}. So the eigenvalues of M(a) are ζ_24^j+7ζ_t and ζ_24^j -1ζ_t. For each choice of j, one finds that both exponents are coprime to 24, and hence the eigenvalues have multiplicative order 24t = 6ℓ. The remaining computations are all similar, in each case one finds that both eigenvalues are primitive roots of order (24, ℓ).


Suppose that M = M_1 where a, b are chosen to be 2t roots of unity for odd t. Then the eigenvalues of M_1 are Y = {ζ_8a, ζ_8^7a}
and √(2)^1-iM^i∈(2, 2t) whenever i is odd. Hence the pair (H, M) is sound whenever the entries of H lie in X = {ζ_8t^2i+1| i ∈ℕ}.
We have recovered the generalisation of Turyn's morphism described in Theorem <ref>. When α≥ 3, then k ≤ℓ, and we never obtain an interesting morphism. When α = 2, we obtain a partial morphism with the same domain as when α = 1; but the image lies over a larger field. These are the only non-trivial morphisms obtained from M_1.

We can also examine the morphisms obtained from M_2: an interesting case occurs when a = b = 1, denote this matrix by M_24. Its entries are fourth roots,
and its eigenvalues are primitive 24 roots. It is easily verified that X = {ζ_24^3i+j| i ∈ℕ, j = 1, 2} and
Y = {ζ_24^7, ζ_24^23}. The set X consists of all 24 roots which are not 8 roots.
We obtain the obvious partial morphism (n, 24)→(n, 4). Since X contains an arithmetic progression of length 8,
we have that the pair (ζ_24H, M_24) is sound for any H ∈(n, 8). Hence we obtain a complete morphism (n, 8) →(2n, 4)
which does not seem to have appeared previously in the literature.





 §.§ Acknowledgements


The first author has been fully supported by Croatian Science Foundation under the project 1637.
The argument for Proposition <ref> was provided by Richard Stanley in response to a question posted on MathOverflow.


abbrv



