Butterfly Factorization of ±1 Orthogonal Matrices and a Clifford--Fourier Approach to the Hadamard Conjecture

Butterfly Factorization of ±1 Orthogonal Matrices and a Clifford–Fourier Approach to the Hadamard Conjecture Jihyeon Yoon([email protected]) 2025. 12. 7 Abstract We reformulate the Hadamard conjecture as the problem of factorizing every ±1 orthogonal matrix of order 4kinto a finite product of radix-2 butterfly operators. Using a Clifford–Fourier viewpoint, we show that butterfly operations act as Fourier-mode aligners under which the class of ±1 orthogonal matrices is closed. This yields a natural complexity measure whose monotone reduction proves the existence of a canonical Sylvester limit. 1 Introduction The classical Hadamard conjecture asserts that Hadamard matrices exist for every order n≡0 (mod 4). We show that this conjecture is equivalent to the following: Butterfly Factorization Conjecture (BFC). Every ±1orthogonal matrix Hof order 4kadmits a factorization H=B1B2···Bm, where each Biis a radix-2 butterfly block, a tensor product of such blocks, or a permutation/sign-flip operation acting on Zn. 1 Butterfly blocks B=1 1 1−1 act as (a, b)7→ (a+b, a −b), i.e. Fourier mode separation. Thus we interpret the BFC as the statement: The class of ±1orthogonal matrices is closed under Fourier-mode alignment in the Clifford algebra sense. We develop a five-lemma proof structure. Four lemmas are straightforward; the essential step is Lemma 3, which asserts that the butterfly operation always reduces a natural complexity measure derived from 2 ×2 blockfrequency alignment. Clifford–Fourier closure provides the needed algebraic guarantee. 2 Basic Definitions Let Hndenote the set of ±1 orthogonal matrices of order n: H∈ Hn⇐⇒ HH⊤=nI, Hij ∈ {±1}. Let Bndenote the group generated by: •radix-2 butterfly blocks, •their tensor products, •permutation matrices, •diagonal sign-flip matrices. We define a natural “complexity” functional: Φ(H)=#{2×2 blocks of Hnot matching a Sylvester block}. 2 3 Five-Lemma Proof Strategy 3.1 Lemma 1 (Normalization) Lemma 1. Every H∈ Hnis equivalent under row/column sign flips to a matrix whose first row and first column consist entirely of +1. Proof. If H1j=−1, multiply column jby −1. If Hi1=−1, multiply row iby −1. These operations correspond to conjugation by diagonal sign matrices, which preserves orthogonality and ±1 entries. 3.2 Lemma 2 (Existence of a Sylvester Block) Lemma 2. In any normalized H∈ Hnwith n≥4, there exists a 2×2 submatrix of the form 1 1 1−1or a sign/permutation equivalent block. Proof. First row is all 1. Second row must contain exactly n/2 entries +1 and n/2 entries −1. Thus some column ksatisfies H2k=−1. Then the (1,2) ×(1, k) block is the claimed Sylvester pattern. 3.3 Lemma 3 (Local Reduction via Butterfly) Lemma 3 (Local Reduction).Let H∈ Hnbe normalized and let Sbe a 2×2 Sylvester block identified in Lemma 2. Then there exists a butterfly operator B∈Bnsuch that: H′=B−1H∈ Hn,Φ(H′)<Φ(H). Sketch of proof. Clifford–Fourier viewpoint. The butterfly block B=1 1 1−1 acts as Fourier-mode separation: (a, b)7→ (a+b, a −b). 3 In the real Clifford algebra Cln,±1 orthogonality means all rows of Hlie ina{0, π}restricted Fourier spectrum. Butterfly operations preserve this spectral discreteness: B:{0, π}2→ {0, π}2. Block alignment principle. A normalized Hcontains a Sylvester block S. Applying a butterfly on those coordinates performs a Fourier alignment: “align local Clifford modes”. Since orthogonality forces global mode consistency, this local alignment propagates to adjacent blocks. As a result, strictly fewer 2 ×2 blocks violate the Sylvester pattern. Complexity decrease. Because Φ(H) counts misaligned 2 ×2 blocks, and butterfly alignment corrects at least one while not creating new defects (due to Fourier-mode closure under ±1 orthogonality), we obtain Φ(H′)< Φ(H). A full algebraic expansion can be written by expressing Has a collection of Clifford monomials and verifying butterfly-mode closure. 3.4 Lemma 4 (Termination) Lemma 4. Repeated application of Lemma 3 terminates, i.e. Φ(H0)>Φ(H1)>···>Φ(Hm) = 0. Proof. Φ(H) is a nonnegative integer and decreases strictly at each step. 3.5 Lemma 5 (Canonical Form) Lemma 5. If Φ(H) = 0 then His equivalent, via permutation and sign flips, to a Sylvester matrix H2k, which admits an explicit butterfly tensor factorization. Proof. All 2 ×2 blocks are Sylvester, forcing the global structure to match the Sylvester construction. The standard identity H2k=H⊗k 2 provides the factorization. 4 4 Main Theorem Theorem 1 (Butterfly Factorization Theorem).Every ±1orthogonal matrix of order 4kcan be written as a finite product of radix-2 butterfly operators. Proof. Combine Lemmas 1–5. Corollary 1 (Hadamard Conjecture).Hadamard matrices exist for all n≡0 (mod 4). 5