betaFeedback

WorksMathematics

On complete morphisms of Butson Hadamard matrices

Abstract

A complete morphism of Butson classes replaces each entry of a matrix in BH(n,k)\mathrm{BH}(n,k) by an m×mm \times m block, uniformly, to produce a matrix in BH(mn,t)\mathrm{BH}(mn,t). We show that every complete morphism is described by a pair (U,Z)(U,Z), where Z∈BH(m,t)Z \in \mathrm{BH}(m,t) and UU is a unitary matrix annihilated by the kthk^{\textrm{th}} cyclotomic polynomial. We deduce from a theorem of Lam and Leung that complete morphisms onto real Hadamard matrices exist precisely when kk is a power of 22. The exponent-reducing morphisms of Östergård–Paavola and Ó Catháin–Swartz achieve the smallest block size the degree bound allows, and we show that there are no other complete morphisms for which UU is monomial. We construct new complete morphisms where UU is not monomial: a complete morphism BH(n,7)→BH(6n,6)\mathrm{BH}(n,7) \rightarrow \mathrm{BH}(6n,6) is given, the first to eliminate a prime from the alphabet.

Introduction

A complex Hadamard matrix is an n×nn \times n matrix MM with entries of modulus 1 which satisfies MM∗=nInMM^{*} = nI_n. Equivalently, while subject to the constraint on the modulus of entries: MM maximises the determinant; and the rows of MM are orthogonal. Let kk be a positive integer, and let ζk=e2π−1k\zeta_k = e^{\frac{2\pi\sqrt{-1}}{k}}. Denote the set of all kthk^{\mathrm{th}} roots of unity by μk\mu_k. A Butson Hadamard (or Butson) matrix is a complex Hadamard matrix with entries in μk\mu_k, and the set of n×nn \times n such matrices is denoted BH(n,k)\mathrm{BH}(n,k). A central topic in the study of complex Hadamard matrices is the question of when BH(n,k)\mathrm{BH}(n,k) is non-empty: the Hadamard conjecture asserts that BH(4n,2)\mathrm{BH}(4n,2) is non-empty for all n∈Nn \in\mathbb{N} and the complex Hadamard conjecture asserts that BH(2n,4)\mathrm{BH}(2n,4) is non-empty for all n∈Nn \in\mathbb{N}.

Several constructions in the literature produce a matrix in BH(mn,t)\mathrm{BH}(mn,t) from a matrix in BH(n,k)\mathrm{BH}(n,k) by replacing each entry with an m×mm \times m block depending only on the entry. The prototypical example is the Kronecker product of complex Hadamard matrices, which is again complex Hadamard by elementary linear algebra: if Mj∈BH(nj,kj)M_j \in\mathrm{BH}(n_j,k_j) then ⨂j∈JMj∈BH(∏j∈Jnj,k)\bigotimes_{j\in J} M_j \in\mathrm{BH}\left(\prod_{j\in J} n_j,k\right), where lcm⁡(kj∣j∈J)∣k\operatorname{lcm}(k_j \mid j \in J) \mid k; it is sometimes the case that ζki⨂j∈JMj\zeta_k^i\bigotimes_{j\in J} M_j lies in a smaller field for suitably chosen scalar factor. Cohn showed that there exists a map from μ4\mu_4 into BH(2,2)\mathrm{BH}(2,2), which may be applied entry-wise to construct a map BH(2n,4)→BH(4n,2)\mathrm{BH}(2n,4) \to\mathrm{BH}(4n,2), [1] cf. [11]. The authors proposed the following:

Definition 1.1. For arbitrary n∈Nn \in\mathbb{N} and fixed k,m,t∈Nk,m,t \in\mathbb{N}, a complete morphism BH(n,k)→BH(mn,t)\mathrm{BH}(n,k) \to\mathrm{BH}(mn,t) is a function ϕ:μk→Mm(μt)\phi:\mu_k \to M_m(\mu_t) such that for every H∈BH(n,k)H \in\mathrm{BH}(n,k), the blockwise image Hϕ=(ϕ(hij))H^\phi= (\phi(h_{ij})) lies in BH(mn,t)\mathrm{BH}(mn,t).

A morphism is called partial if it is not complete: an example was constructed by Compton, Craigen and de Launey with domain the unreal matrices over sixth roots; if H∈BH(n,6)H \in\mathrm{BH}(n,6) has no entries ±1\pm1 then there exists ϕ:{ζ6,ζ62,ζ64,ζ65}→BH(4,2)\phi:\{\zeta_6,\zeta_6^2,\zeta_6^4,\zeta_6^5\} \to\mathrm{BH}(4,2) such that Hϕ∈BH(4n,2)H^\phi\in\mathrm{BH}(4n,2), [2]. Constructions of Gow map matrices in BH(n,p)\mathrm{BH}(n,p), where p=2a+1p = 2^a + 1 is a Fermat prime, with no entry equal to 1, into BH(2an,4)\mathrm{BH}(2^a n,4), [5, 6, 3].

The present authors developed a general framework of sound pairs for such constructions, [3]. With Swartz, they constructed a complete morphism BH(n,2s)→BH(22s−1n,2)\mathrm{BH}(n,2^s) \to\mathrm{BH}(2^{2^s-1}n,2) for each s≥2s \ge2, [4]. Östergård and Paavola obtained a more general result, with maps BH(n,pk)→BH(pn,k)\mathrm{BH}(n,p^k) \to\mathrm{BH}(p^n,k) for pp a prime with p∣kp \mid k, [10], cf. [9].

In all prior work, any morphism which eliminates a prime divisor from kk is incomplete, for the morphisms of Compton, Craigen and de Launey, and of Gow mentioned above which map into matrices over μ2s\mu_{2^s} for some ss, the domain restriction is essential. Our first result shows that this is forced, by way of the theorem of Lam and Leung [8] on vanishing sums of roots of unity. We are led to the consideration of matrices with entries in μ6\mu_6, where the Lam-Leung restriction does not hold.

Section 2 describes the structure of complete morphisms, and corollaries to that result limiting the existence of certain morphisms. In particular, this resolves the spectrum of existence for complete morphisms BH(n,k)→BH(mn,2)\mathrm{BH}(n,k) \to\mathrm{BH}(mn,2) for all k∈Nk \in\mathbb{N}. In Section 3 we consider the complete morphisms with the smallest parameters not eliminated by the obstruction, and provide a new example of a complete morphism BH(n,7)→BH(6n,6)\mathrm{BH}(n,7) \to\mathrm{BH}(6n,6). This is the first example of a complete morphism which eliminates a prime divisor of kk from the alphabet.

The structure of complete morphisms

Throughout this paper, Φk\Phi_k is the kkth cyclotomic polynomial. We write rad⁡(k)\operatorname{rad}(k) for the product of the distinct primes dividing kk. We begin with some straightforward but powerful consequences of the definition of a complete morphism.

Lemma 2.1. Suppose that ϕ\phi is a complete morphism BH(n,k)→BH(mn,t)\mathrm{BH}(n,k) \to\mathrm{BH}(mn,t). For ζj∈μk\zeta^j \in\mu_k write Zj=ϕ(ζj)Z_j=\phi(\zeta^j). Let pp be a prime dividing kk and set e=k/pe=k/p. Indices are read modulo kk throughout. Then for every j∈{0,1,…,k−1}j \in\{0,1,\ldots,k-1\}

(1) Zj∈BH(m,t)Z_j \in\mathrm{BH}(m,t);

(2) ∑a=0p−1Zj+ea=0\sum_{a=0}^{p-1} Z_{j+ea}=0;

(3) Zj+aZj∗Z_{j+a}Z_j^* is independent of aa.

Proof. Up to Hadamard equivalence, H∈BH(n,k)H \in\mathrm{BH}(n,k) contains a constant row with all entries equal to ζj\zeta^j. Since Hϕ∈BH(mn,t)H^\phi\in\mathrm{BH}(mn,t), clearly all entries of ZjZ_j are in μt\mu_t and nZjZj∗=mnImnZ_jZ_j^*=mnI_m, and hence Zj∈BH(m,t)Z_j \in\mathrm{BH}(m,t).

Since p∣kp \mid k, the Fourier matrix Fp=(ζij)0≤i,j<pF_p=(\zeta^{ij})_{0\le i,j<p} belongs to BH(p,k)\mathrm{BH}(p,k). Orthogonality of the first two rows of (ζkjFp)ϕ(\zeta_k^jF_p)^\phi requires that

(∑a=0p−1Zj+ea)Zj∗=0m×m.\left(\sum_{a=0}^{p-1} Z_{j+ea}\right)Z_j^*=0_{m\times m}.

Since ZjZ_j is invertible by (1), the claim follows.

For (3), fix aa and let F′F' be obtained from Fk=(ζrc)0≤r,c<kF_k=(\zeta^{rc})_{0\le r,c<k} by multiplying the last column by ζa\zeta^a; scaling a column by a root of unity preserves BH(k,k)\mathrm{BH}(k,k). Orthogonality of block rows 0 and rr of (F′)ϕ(F')^\phi gives

∑c=0k−2ZrcZ0∗+Zr(k−1)+aZa∗=0.\sum_{c=0}^{k-2} Z_{rc}Z_0^*+Z_{r(k-1)+a}Z_a^*=0.

The first summand does not involve aa, so Zr(k−1)+aZa∗Z_{r(k-1)+a}Z_a^* is independent of aa. As rr runs over 1,…,k−11,\ldots,k-1 the residue r(k−1)≡−rr(k-1)\equiv-r runs over all non-zero residues modulo kk; writing jj for −r-r gives the result.

Theorem 2.2. There is a bijection between complete morphisms BH(n,k)→BH(mn,t)\mathrm{BH}(n,k) \to\mathrm{BH}(mn,t) and pairs (U,Z)(U,Z) where Z∈BH(m,t)Z \in\mathrm{BH}(m,t) and UU is unitary with Φk(U)=0\Phi_k(U)=0 such that UjZU^jZ has entries in μt\mu_t for 0≤j<k0 \le j<k.

Proof. First assume that ϕ\phi is a complete morphism and set Z=Z0Z=Z_0 and let ρ(ζj)=1mZjZj∗\rho(\zeta^j)=\frac{1}{m}Z_jZ_j^*. Then ρ(ζkj)ρ(ζkj)∗=Im\rho(\zeta_k^j)\rho(\zeta_k^j)^*=I_m, and by Lemma 2.1(3), ρ(ζkiζkj)=ρ(ζki)ρ(ζkj)\rho(\zeta_k^i\zeta_k^j)=\rho(\zeta_k^i)\rho(\zeta_k^j), so ζkj↦ρ(ζkj)\zeta_k^j \mapsto\rho(\zeta_k^j) is a homomorphism into the unitary group and Zj=ρ(ζkj)ZZ_j=\rho(\zeta_k^j)Z. Assign U=ρ(ζk)U=\rho(\zeta_k); then Uk=IU^k=I and Lemma 2.1(2) gives ∑i<kUik/p=0m×m\sum_{i<k}U^{ik/p}=0_{m\times m} for every prime p∣kp\mid k, so every eigenvalue of UU is a primitive kkth root of unity, and, UU being unitary, Φk(U)=0\Phi_k(U)=0. Finally UjZ=ZjU^jZ=Z_j has all of its entries in μt\mu_t for every jj, by Lemma 2.1(1). Conversely, given (U,Z)(U,Z), let H∈BH(n,k)H \in\mathrm{BH}(n,k); the entries of HϕH^{\phi} lie in μt\mu_t because those of every UjZU^jZ do. Let r,sr,s be distinct rows of HH with ∑jrjsj‾=0\sum_j r_j\overline{s_j}=0. Write rj=ζkajr_j=\zeta_k^{a_j} and sj=ζkbjs_j=\zeta_k^{b_j}, and set ej=aj−bje_j=a_j-b_j mod kk. The polynomial P(x)=∑jxej∈Z[x]P(x)=\sum_j x^{e_j}\in\mathbb{Z}[x] vanishes at ζk\zeta_k, hence is divisible by Φk\Phi_k, hence P(U)=0P(U)=0. Since ZZ∗=mIZZ^*=mI and Uk=IU^k=I, the inner product of the corresponding block-rows of HϕH^{\phi} is ∑jUajZZ∗U−bj=mP(U)=0\sum_j U^{a_j}ZZ^*U^{-b_j}=mP(U)=0, while each diagonal block of the Gram matrix is mnImmnI_m, so Hϕ∈BH(mn,t)H^{\phi}\in\mathrm{BH}(mn,t).

Remark 2.3. The bijection of Theorem 2.2 is entirely explicit: given a morphism BH(n,k)→BH(mn,t)\mathrm{BH}(n,k)\to\mathrm{BH}(mn,t), recover Z=ϕ(1)Z=\phi(1) and then U=ϕ(ζk)Z∗U=\phi(\zeta_k)Z^*; this inverts (U,Z)↦ϕ(U,Z)\mapsto\phi, since ϕ(ζkj)=UjZ\phi(\zeta_k^j)=U^jZ.

It is natural to give a name to the pairs of matrices (U,Z)(U,Z) satisfying the hypotheses of Theorem 2.2.

Definition 2.4. A pair (U,Z)(U,Z) of m×mm\times m complex matrices is (k,t)(k,t)-flat (or just flat when the parameters (k,t)(k,t) are assumed) if UU is unitary, Φk(U)=0\Phi_k(U)=0, and every UjZU^jZ has all of its entries in μt\mu_t for all 0≤j<k0\leq j<k. A flat pair (U,Z)(U,Z) is a (k,t)(k,t)-amiable pair (or just amiable pair) if moreover ZZ∗=mImZZ^*=mI_m.

Integrality conditions

Proposition 2.5. Let (U,Z)(U,Z) be a (k,t)(k,t)-amiable pair of m×mm\times m matrices. Then mUmU has entries in Z[ζt]\mathbb{Z}[\zeta_t], and d∣md\mid m for d=φ(lcm⁡(k,t))/φ(t)d=\varphi(\operatorname{lcm}(k,t))/\varphi(t).

Proof. Since ZZ∗=mImZZ^*=mI_m we have mU=(UZ)Z∗mU=(UZ)Z^*, and both factors are flat, so the entries of mUmU lie in Z[ζt]\mathbb{Z}[\zeta_t]. Hence the characteristic polynomial of UU lies in Q(ζt)[x]\mathbb{Q}(\zeta_t)[x], and as Φk(U)=0\Phi_k(U)=0 it is a product of irreducible factors of Φk\Phi_k over Q(ζt)\mathbb{Q}(\zeta_t). Those factors correspond to the orbits of G=Gal⁡(Q(ζt)(ζk)/Q(ζt))G=\operatorname{Gal}(\mathbb{Q}(\zeta_t)(\zeta_k)/\mathbb{Q}(\zeta_t)) on the primitive kkth roots of unity, and GG acts freely, so each has degree d=∣G∣=φ(lcm⁡(k,t))/φ(t)d=|G|=\varphi(\operatorname{lcm}(k,t))/\varphi(t); the characteristic polynomial has degree mm, so d∣md\mid m.

Necessary conditions for existence of complete morphisms

Corollary 2.6. Suppose there exists a complete morphism BH(n,k)→BH(mn,t)\mathrm{BH}(n,k)\to\mathrm{BH}(mn,t). Then every prime divisor of kk is a non-negative integer combination of the prime divisors of tt.

Proof. Let p∣kp\mid k and set e=k/pe=k/p. By Lemma 2.1(2), ∑a=0p−1Zea=0m×m\sum_{a=0}^{p-1}Z_{ea}=0_{m\times m}. The entries of each ZeaZ_{ea} are elements of μt\mu_t; hence any component of the matrix equation yields a vanishing sum of exactly pp elements of μt\mu_t.

By a well-known theorem of Lam and Leung, if there exists a vanishing sum with elements in μt\mu_t then the number of summands is in the set Np1+⋯+Npr\mathbb{N}p_1+\cdots+\mathbb{N}p_r where p1,…,prp_1,\ldots,p_r are the primes dividing tt, [8].

Combinations of a single prime are especially restrictive:

Corollary 2.7. Let t=qbt=q^b be a prime power. A complete morphism BH(n,k)→BH(mn,qb)\mathrm{BH}(n,k)\to\mathrm{BH}(mn,q^b) exists if and only if kk is a power of qq. In particular, complete morphisms BH(n,k)→BH(mn,2)\mathrm{BH}(n,k)\to\mathrm{BH}(mn,2) exist if and only if k=2αk=2^\alpha.

Proof. Every non-negative combination of the single prime qq is a multiple of qq, so Corollary 2.6 forces rad⁡(k)=q\operatorname{rad}(k)=q. Conversely, for k=qak=q^a with a≤ba\leq b the inclusion μk⊆μt\mu_k\subseteq\mu_t gives a morphism with m=1m=1, and for a>ba>b the Östergård–Paavola and Ó Catháin–Swartz constructions [10, 9] gives one with m=qa−bm=q^{a-b}, which is optimal: by Proposition 2.5, mm is divisible by d=φ(qa)/φ(qb)=qa−bd=\varphi(q^a)/\varphi(q^b)=q^{a-b}.

For real targets this settles the question raised at the end of [3]: the complete morphisms BH(n,k)→BH(mn,2)\mathrm{BH}(n,k)\to\mathrm{BH}(mn,2) are exactly those with k=2αk=2^\alpha, realised with the minimal multiplier m=2α−1m=2^{\alpha-1} by [10, 9], and every morphism from an alphabet containing an odd prime onto real Hadamard matrices is necessarily partial.

The complete morphisms constructed to date by the authors and Swartz and by Östergård–Paavola correspond to pairs (U,Z)(U,Z) where UU is monomial; as a result flatness of the powers UjZU^jZ is automatic there, [9, 10].

Proposition 2.8. Fix kk and tt. There is a (k,t)(k,t)-amiable pair (U,Z)(U,Z) with UU monomial if and only if rad⁡(k)∣t\operatorname{rad}(k) \mid t.

Proof. If rad⁡(k)∣t\operatorname{rad}(k) \mid t, the matrices of [9] are monomial. Conversely, let (U,Z)(U,Z) be amiable with UU monomial: its phases lie in μt\mu_t, being quotients of entries of UZUZ and of ZZ. Suppose pa∥kp^a \mathrel{\Vert} k with p∤tp \nmid t. Then W=Uk/paW=U^{k/p^a} is again monomial with entries in μt\mu_t, and every eigenvalue of WW is a primitive pap^ath root of unity. The eigenvalues of WW arising from a cc-cycle of its permutation part with phase product δ∈μt\delta\in\mu_t form the full solution set of ωc=δ\omega^c=\delta. Each solution lies in μpa\mu_{p^a}, so δ=ωc∈μpa∩μt={1}\delta=\omega^c \in\mu_{p^a}\cap\mu_t=\{1\}; but then ω=1\omega=1 is among the solutions, and 11 is not a primitive pap^ath root of unity. □

Corollary 2.7 and Proposition 2.8 together establish the limits of all previous constructions of complete morphisms. We observe that these results generalise to partial morphisms: the domain of the Compton-Craigen-de Launey partial morphism is maximal, as adding another root of unity to the domain would give a vanishing sum of length 3 in {±1}\{\pm1\}; and similarly for the unreal matrices constructed from matrices of Gow. In the preparation of this note, the authors became aware of a minor inaccuracy in previous work, which is recorded below for the sake of correcting the record; no results of the previous paper are affected.

Remark 2.9 (Erratum to [3]). The proof of Theorem 10 of [3], which realises Gow’s matrices Mp′M'_p for a Fermat prime p=2a+1p=2^a+1, states that the trace of 2−aMp′2^{-a}M'_p is −p-p. The correct value is −(p−1)=−2a-(p-1)=-2^a, and the conclusion of the theorem is unaffected.

The existence of a complete morphism BH(nn, 7) →\to BH(6nn, 6)

In this section we exhibit a (7,6)(7,6)-amiable pair (U,Z)(U,Z) with m=6m=6, which is the smallest block size Proposition 2.5 permits, since d=φ(42)/φ(6)=6d=\varphi(42)/\varphi(6)=6. The search that produced it enumerates flat orbits rather than matrices UU, and is described in §3.2.

Theorem 3.1. There is a complete morphism BH⁡(n,7)→BH⁡(6n,6)\operatorname{BH}(n,7)\to\operatorname{BH}(6n,6).

The matrices displayed below prove the theorem, and the enumeration of §3.2 shows that up to monomial equivalence exactly four matrices UU occur in a (7,6)(7,6)-amiable pair at block size m=6m=6, falling into two families of two, the classes within each family interchanged by U↦UaU\mapsto U^a for aa a non-residue modulo 7. A single ZZ serves for both: put Z=(ζ3zij)Z=(\zeta_3^{z_{ij}}),

2U1=(0000021ζ621ζ650001ζ62ζ6510ζ63ζ630ζ64ζ60ζ64ζ62ζ620ζ640ζ6401ζ610),3U2=(111ζ642ζ6ζ64ζ62ζ62ζ65111ζ62ζ62ζ62ζ631112ζ631ζ64ζ64ζ642ζ6311ζ64ζ64ζ64ζ62ζ62ζ62112ζ63),(zij)=(000000001122010212021201022110012021).2U_1= \begin{pmatrix} 0&0&0&0&0&2\\ 1&\zeta_6^2&1&\zeta_6^5&0&0\\ 0&1&\zeta_6^2&\zeta_6^5&1&0\\ \zeta_6^3&\zeta_6^3&0&\zeta_6^4&\zeta_6&0\\ \zeta_6^4&\zeta_6^2&\zeta_6^2&0&\zeta_6^4&0\\ \zeta_6^4&0&1&\zeta_6&1&0 \end{pmatrix}, \qquad 3U_2= \begin{pmatrix} 1&1&1&\zeta_6^4&2\zeta_6&\zeta_6^4\\ \zeta_6^2&\zeta_6^2&\zeta_6^5&1&1&1\\ \zeta_6^2&\zeta_6^2&\zeta_6^2&\zeta_6^3&1&1\\ 1&2\zeta_6^3&1&\zeta_6^4&\zeta_6^4&\zeta_6^4\\ 2\zeta_6^3&1&1&\zeta_6^4&\zeta_6^4&\zeta_6^4\\ \zeta_6^2&\zeta_6^2&\zeta_6^2&1&1&2\zeta_6^3 \end{pmatrix}, \qquad (z_{ij})= \begin{pmatrix} 0&0&0&0&0&0\\ 0&0&1&1&2&2\\ 0&1&0&2&1&2\\ 0&2&1&2&0&1\\ 0&2&2&1&1&0\\ 0&1&2&0&2&1 \end{pmatrix}.

Then U1U_1 and U2U_2 are unitary; Φ7(Ui)=0\Phi_7(U_i)=0; Z∈BH⁡(6,6)Z\in\operatorname{BH}(6,6); and UijZ∈BH⁡(6,6)U_i^jZ\in\operatorname{BH}(6,6) for 0≤j<70\le j<7. By Theorem 2.2 each assignment ϕi(ζ7j)=UijZ\phi_i(\zeta_7^j)=U_i^jZ is a complete morphism BH⁡(n,7)→BH⁡(6n,6)\operatorname{BH}(n,7)\to\operatorname{BH}(6n,6).

Let (U,Z)(U,Z) be (k,t)(k,t)-amiable and let P,QP,Q be monomial over μt\mu_t. Then (PUP−1,PZQ)(PUP^{-1},PZQ) is amiable too, since PP and QQ are unitary and (PUP−1)jPZQ=P(UjZ)Q(PUP^{-1})^jPZQ=P(U^jZ)Q. The right factor QQ acts on ZZ without touching UU, and it is this freedom that allows a single ZZ to serve both pairs above.

Flat orbits

Let pp be prime and let (U,Z)(U,Z) be a (p,t)(p,t)-amiable pair with p∤tp \nmid t. Each column cc of ZZ generates the sequence cj=Ujcc_j=U^jc, 0≤j≤p−10\le j\le p-1; these are columns of the matrices UjZU^jZ and so lie in μtm\mu_t^m. Call such a sequence a flat orbit and cc a flat orbit generator. We will show that flat orbits are characterised without reference to UU.

Lemma 3.2. Let c0,…,cp−1∈μtmc_0,\ldots,c_{p-1}\in\mu_t^m with m≤p−1m\le p-1, and suppose c0,…,cm−1c_0,\ldots,c_{m-1} are linearly independent. Then there is a unitary m×mm\times m matrix UU with Ujc0=cjU^jc_0=c_j for all jj, Up=IU^p=I and Φp(U)=0\Phi_p(U)=0, if and only if

(1) ⟨ci,cj⟩\langle c_i,c_j\rangle depends only on j−ij-i modulo pp, and

(2) ∑jcj=0\sum_j c_j=0.

Proof. Suppose the matrix UU with the stated properties exists. Then ⟨ci,cj⟩=⟨Uic,Ujc⟩=⟨c,Uj−ic⟩\langle c_i,c_j\rangle=\langle U^ic,U^jc\rangle=\langle c,U^{j-i}c\rangle as UU is unitary, implying part (1). That ∑jUj=0\sum_jU^j=0 follows because Φp(x)=∑j<pxj\Phi_p(x)=\sum_{j<p}x^j for pp prime and by assumption, Φp(U)=0\Phi_p(U)=0. Hence ∑jcj=(∑jUj)c0=0\sum_jc_j=(\sum_jU^j)c_0=0, implying part (2).

Conversely, assume claims (1) and (2) hold and write γr=⟨c0,cr⟩\gamma_r=\langle c_0,c_r\rangle, so that by (1) any mm consecutive cjc_j have Gram matrix Γ=(γj−i)0≤i,j<m\Gamma=(\gamma_{j-i})_{0\le i,j<m}. Let M1M_1 and M2M_2 be the matrices with columns (c0,…,cm−1)(c_0,\ldots,c_{m-1}) and (c1,…,cm)(c_1,\ldots,c_m); both have Gram matrix Γ\Gamma, and M1M_1 is invertible by hypothesis, so Γ\Gamma is too. Let U=M2M1−1U=M_2M_1^{-1}, the unique linear map with Ucj=cj+1Uc_j=c_{j+1} for 0≤j<m0\le j<m. Then

M1∗U∗UM1=(UM1)∗(UM1)=M2∗M2=Γ=M1∗M1,M_1^*U^*UM_1=(UM_1)^*(UM_1)=M_2^*M_2=\Gamma=M_1^*M_1,

so U∗U=IU^*U=I and UU is unitary.

We claim that Ucl=cl+1Uc_l=c_{l+1} for every l<p−1l<p-1. Write Wl=[cl−m+1∣⋯∣cl]W_l=[c_{l-m+1}\mid\cdots\mid c_l], so that Wm−1=M1W_{m-1}=M_1 and Wm=M2W_m=M_2, and induct on l≥ml\ge m. If Ucj=cj+1Uc_j=c_{j+1} for all j<lj<l then UWl−1=WlUW_{l-1}=W_l, whence Wl∗Wl=Wl−1∗Wl−1=ΓW_l^*W_l=W_{l-1}^*W_{l-1}=\Gamma and WlW_l is invertible. For l−m<i≤ll-m<i\le l,

⟨ci,Ucl⟩=⟨Uci−1,Ucl⟩=⟨ci−1,cl⟩=γl−i+1=⟨ci,cl+1⟩,\langle c_i,Uc_l\rangle=\langle Uc_{i-1},Uc_l\rangle=\langle c_{i-1},c_l\rangle=\gamma_{l-i+1}=\langle c_i,c_{l+1}\rangle,

that is Wl∗(Ucl)=Wl∗cl+1W_l^*(Uc_l)=W_l^*c_{l+1}, and Ucl=cl+1Uc_l=c_{l+1} follows.

By claim (2),

Ucp−1=U(−∑j<p−1cj)=−∑j<p−1cj+1=−∑1≤j≤p−1cj=c0,Uc_{p-1}=U\left(-\sum_{j<p-1}c_j\right)=-\sum_{j<p-1}c_{j+1}=-\sum_{1\le j\le p-1}c_j=c_0,

so UU permutes the cjc_j in a pp-cycle and Up=IU^p=I. Finally (∑jUj)c0=∑jcj=0(\sum_jU^j)c_0=\sum_jc_j=0; the kernel of ∑jUj\sum_jU^j is UU-invariant and contains c0c_0, hence contains span⁡{Ujc0}=Cm\operatorname{span}\{U^jc_0\}=\mathbb{C}^m. So ∑jUj=0\sum_jU^j=0, that is Φp(U)=0\Phi_p(U)=0. □

Remark 3.3. The matrix UU of Lemma 3.2 is unique and determined explicitly from c0,…,cmc_0,\ldots,c_m by

U=M2M1−1,(1)U=M_2M_1^{-1}, \tag*{(1)}

where M1M_1 is invertible by the assumption of linear independence of {c0,…,cm−1}\{c_0,\ldots,c_{m-1}\}.

Lemma 3.4. Let (U,Z)(U,Z) be a (p,t)(p,t)-amiable pair where p∤tp\nmid t with m=p−1m=p-1, and let cc be any column of ZZ. Then {c,Uc,…,Up−2c}\{c,Uc,\ldots,U^{p-2}c\} is linearly independent.

Proof. Put K=Q(ζt)K=\mathbb{Q}(\zeta_t) and L=K(ζp)L=K(\zeta_p), and let G=Gal⁡(L/K)G=\operatorname{Gal}(L/K), which is cyclic and acts simply transitively on the primitive pthp^{\text{th}} roots of unity, since [L:K]=φ(pt)/φ(t)=p−1[L:K]=\varphi(pt)/\varphi(t)=p-1 for p∤tp\nmid t. The entries of UU lie in KK, because mU=(UZ)Z∗mU=(UZ)Z^* has entries in Z[ζt]\mathbb{Z}[\zeta_t], and c∈μtm⊂Kmc\in\mu_t^m\subset K^m.

The characteristic polynomial of UU lies in K[x]K[x], and its roots are primitive pthp^{\text{th}} roots of unity because Φp(U)=0\Phi_p(U)=0. Its multiset of roots is therefore stable under GG, hence a union of GG-orbits; each orbit is the full set of p−1p-1 primitive pthp^{\text{th}} roots, and the degree is m=p−1m=p-1, so each occurs exactly once. Choose xλx_\lambda from each of the p−1p-1 distinct 11-dimensional λ\lambda-eigenspaces EλE_\lambda so that c=∑λxλc=\sum_\lambda x_\lambda.

For σ∈G\sigma\in G, applying σ\sigma entrywise to (U−λ)xλ=0(U-\lambda)x_\lambda=0 and using σ(U)=U\sigma(U)=U gives σ(xλ)∈Eσ(λ)\sigma(x_\lambda)\in E_{\sigma(\lambda)}; since σ(c)=c\sigma(c)=c, uniqueness of the decomposition yields xσ(λ)=σ(xλ)x_{\sigma(\lambda)}=\sigma(x_\lambda). Hence the xλx_\lambda vanish either all together or not at all, and c≠0c\ne0 forces all of them to be non-zero. So the cyclic subspace generated by cc is all of Cm\mathbb{C}^m, and its spanning set {c,Uc,…,Um−1c}\{c,Uc,\ldots,U^{m-1}c\} is a basis.

The search for a complete morphism

The classification is by exhaustive enumeration of flat orbits, in two stages.

Stage 1: enumerating flat orbits. Fix p=7p=7, t=6t=6, m=6m=6. An amiable pair (U,Z)(U,Z) may be replaced by (PUP−1,PZ)(PUP^{-1},PZ) for any monomial PP over μ6\mu_6, so a chosen column orbit may be normalised: taking P=diag⁡(c0‾)P=\operatorname{diag}(\overline{c_0}) makes c0=1c_0=1, the column of all ones, and the residual freedom is the symmetric group permuting the six coordinates, which fixes c0c_0. This allows us to restrict to columns c1c_1 with non-decreasing exponents in the entries, hence there are (115)=462\binom{11}{5}=462 candidates for c1c_1. Every amiable pair is therefore reached: normalising the orbit of the first column of ZZ in this way gives a sequence satisfying Lemma 3.2(1) and (2), so it is enumerated, and its first six terms are independent by Lemma 3.4, so (1) returns the conjugated UU.

Lemma 3.2(1) requires that ⟨ci,cj⟩=γj−i\langle c_i,c_j\rangle=\gamma_{j-i} depends only on j−ij-i; hence each additional column added to a flat orbit imposes a linear constraint on subsequent columns. Since γ−r=γr‾\gamma_{-r}=\overline{\gamma_r}, all inner products are determined once c1,c2,c3c_1,c_2,c_3 are chosen; the last column is not searched, being forced as c6=−∑j<6cjc_6=-\sum_{j<6}c_j by Lemma 3.2(2) and retained only if it is flat. The enumeration yields 30,728 flat orbits in seconds.

Each flat orbit determines UU uniquely via equation (1). The flat orbit is retained if and only if 6U∈M6(Z[ζ6])6U\in M_6(\mathbb{Z}[\zeta_6]), which is necessary by Proposition 2.5. Of these, 3,560 yield an integral 6U6U.

Stage 2: constructing ZZ from UU. Whether a column generates a flat orbit of UU depends on that column alone, so the flat orbit generators of a fixed UU are found by one sweep of the 666^6 elements of μ66\mu_6^6. A matrix ZZ completing UU to an amiable pair is exactly a set of six pairwise orthogonal such columns, each of norm 6\sqrt{6}; so Stage 2 is a search for 6-cliques in the orthogonality graph on the flat orbit generators of UU. It is run for every UU retained at Stage 1, and the resulting amiable pairs are reduced by monomial equivalence, leaving four classes.

Remark 3.5 (Cost of the search). A complete morphism BH(n,k)→BH(mn,t)\mathrm{BH}(n,k)\to\mathrm{BH}(mn,t) exists for some mm if and only if, for each prime p∣kp\mid k with p∤tp\nmid t, a complete morphism BH(n,p)→BH(mpn,t)\mathrm{BH}(n,p)\to\mathrm{BH}(m_pn,t) exists for some mpm_p. By Proposition 2.5, (p−1)∣mp(p-1)\mid m_p; the search treats mp=p−1m_p=p-1, the only case in which a single flat orbit determines UU.

In Stage 1 each partial orbit (c1,…,cj−1)(c_1,\ldots,c_{j-1}) is expanded by scanning the v∈μtp−1v\in\mu_t^{p-1} with ⟨cj−1,v⟩=γ1\langle c_{j-1},v\rangle=\gamma_1, each tested against at most pp inner products. There are at most tp−1t^{p-1} such vv and, since ⟨1,v⟩\langle1,v\rangle takes at most (p+t−2p−1)\binom{p+t-2}{p-1} values, at least tp−1/(p+t−2p−1)t^{p-1}/\binom{p+t-2}{p-1} for some choice of c1c_1. Up to factors polynomial in pp, Stage 1 therefore costs between t2(p−1)t^{2(p-1)} (expanding depth 2) and t(p−1)(p−3)t^{(p-1)(p-3)} (the full tree) operations. Stage 2 multiplies each vector of μtp−1\mu_t^{p-1} by UU a total of p−1p-1 times, at a cost of O(p3tp−1)O(p^3t^{p-1}) operations per UU.

We ran the search in a NumPy implementation on a laptop; the table gives the number of nodes in the Stage 1 tree and of candidates scanned. Both are exact for (5,6)(5,6) and (7,6)(7,6). Elsewhere they are estimated by Knuth’s random-probe method [7], which reproduces both counts at (7,6)(7,6) to within one standard error. Times are projected at about 3×1073\times10^7 candidates per second, which is the rate measured at (7,6)(7,6).

(p,t)(p,t)mmnodescandidatesStage 1 time
(5,6)(5,6)443513511.5×1041.5\times10^40.2 s0.2\ \mathrm{s}
(7,6)(7,6)661.1×1061.1\times10^61.3×1091.3\times10^938 s38\ \mathrm{s}
(7,12)(7,12)666.3×1076.3\times10^75.7×10115.7\times10^{11}5 h5\ \mathrm{h}
(11,6)(11,6)10105×1055\times10^5>1.3×1015>1.3\times10^{15}>1 year>1\ \mathrm{year}

Table 1.

At (5,6)(5,6) there is no flat orbit at all, so no complete morphism BH(n,5)→BH(4n,6)\mathrm{BH}(n,5) \to\mathrm{BH}(4n,6) exists. Stage 2 took about 30 ms per UU at (7,6)(7,6), under two minutes for all 3,560 matrices. and its sweep of 6106^{10} vectors at (11,6)(11,6) would take minutes per UU; asymptotically, Stage 1 dominates the running time.

Statement of AI Use

The authors used Anthropic’s Claude Fable and Claude Opus 3.5 to generate Python scripts to search for morphisms. Initial versions of some proofs were also generated with Claude. All proofs were rederived and rewritten by the authors; and computational results were checked and verified in MAGMA.

References

  1. [1]J. H. E. Cohn. Hadamard matrices and some generalisations. The American Mathematical Monthly, 72(5):515–518, 1965.DOI
  2. [2]B. Compton, R. Craigen, and W. de Launey. Unreal BH(n, 6)’s and Hadamard matrices. Des. Codes Cryptogr., 79(2):219–229, 2016.DOI
  3. [3]R. Egan and P. Ó Catháin. Morphisms of Butson classes. Linear Algebra Appl., 577:78–93, 2019.DOI
  4. [4]R. Egan, P. Ó Catháin, and E. Swartz. Spectra of Hadamard matrices. Australas. J. Combin., 73:501–512, 2019.arxiv.org/abs/1807.04238
  5. [5]R. Gow. Generation of mutually unbiased bases as powers of a unitary matrix in 2-power dimensions. ArXiv preprint, math/070333v2, 2007.arxiv.org/abs/math/0703333
  6. [6]R. Gow. Generation of real mutually unbiased bases as powers of a real orthogonal matrix of odd finite order. ArXiv preprint, math/1410.4059v1, 2014.
  7. [7]D. E. Knuth. Estimating the efficiency of backtrack programs. Math. Comp., 29(129):121–136, 1975.
  8. [8]T. Y. Lam and K. H. Leung. On vanishing sums of roots of unity. J. Algebra, 224(1):91–109, 2000.DOI
  9. [9]P. Ó Catháin and E. Swartz. Homomorphisms of matrix algebras and constructions of Butson–Hadamard matrices. Disc. Math., 342(12):111606, 2019.DOI
  10. [10]P. R. J. Östergaard and W. T. Paavola. Mappings of Butson-type Hadamard matrices. Discrete Math., 341(9):2387–2397, 2018.
  11. [11]R. J. Turyn. Complex Hadamard matrices. In Combinatorial Structures and their Applications (Proc. Calgary Internat. Conf., Calgary, Alta., 1969), pages 435–437. Gordon and Breach, New York, 1970.

Paper details

vlnc:W_zqjw27cu
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 0

downloads · 0

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

  • Mathematics

Not recorded for this paper

View statement
Looking for related papers…
Contents