Chapter 34: The Hadamard Conjecture — Matrices' Perfect Balance

From computation's ultimate question we turn to a problem of perfect orthogonality. The Hadamard Conjecture asks whether maximally orthogonal matrices exist in all dimensions divisible by 4—it is ψ = ψ(ψ) as linear algebra seeking its own extremal configurations, where perfect balance emerges from binary constraints.

34.1 The Thirty-Fourth Movement: Orthogonal Perfection

Continuing through the combinatorial cosmos:

• Previous: Computation questioning its own limits
• Now: Matrices achieving maximal orthogonality
• The quest for perfect combinatorial balance

The Core Question: Does a Hadamard matrix exist for every dimension n ≡ 0 (mod 4)?

34.2 Hadamard Matrices

Definition 34.1 (Hadamard Matrix): An n×n matrix H with entries ±1 such that: $HH^T = nI_n$

Equivalent Conditions:

• All rows mutually orthogonal
• All columns mutually orthogonal
• $|det(H)| = n^\{n/2\}$ (maximal determinant)

Example (n = 2): $H_2 = \begin{pmatrix} 1 & 1 \\ 1 & -1 \end{pmatrix}$

34.3 The Hadamard Conjecture

Conjecture 34.1 (Hadamard, 1893): A Hadamard matrix of order n exists if and only if n = 1, 2, or n ≡ 0 (mod 4).

Known:

• Necessary: n = 1, 2, or n ≡ 0 (mod 4)
• Sufficient: Unknown!

Status: Smallest unknown case is n = 668.

34.4 Hadamard as ψ = ψ(ψ)

Axiom 34.1 (Principle of Binary Balance): $\psi = \psi(\psi) \implies \text{Perfect orthogonality from } \pm 1 \text{ constraints}$

Hadamard matrices embody:

• Maximal structure from minimal alphabet
• Global orthogonality from local constraints
• Perfect balance through binary choices
• This is ψ = ψ(ψ) as discrete optimization

34.5 Construction Methods

Sylvester Construction: $H_{2n} = \begin{pmatrix} H_n & H_n \\ H_n & -H_n \end{pmatrix}$

Gives H₂ₖ for all k.

Paley Construction: For prime p ≡ 3 (mod 4), use quadratic residues: $H_{ij} = \left(\frac{j-i}{p}\right)$

Limitation: These miss many multiples of 4.

34.6 The Orthogonal Design Connection

Definition 34.2 (Orthogonal Design): Matrix with entries 0, ±x₁, ..., ±xₜ where rows are orthogonal for all real xᵢ.

Theorem 34.1 (Seberry): Hadamard matrices relate to orthogonal designs with t = 1.

Generalization: Studying OD(n;t) illuminates Hadamard case.

34.7 Circulant Hadamard Matrices

Definition 34.3 (Circulant Matrix): First row determines all others by cyclic shift.

Theorem 34.2 (Ryser): No circulant Hadamard matrix exists for n > 4.

Proof: Uses finite field character theory.

Lesson: Symmetry constraints can prohibit existence!

34.8 Computational Search

Algorithm 34.1 (Hadamard Search):

def search_hadamard(n):
    # Start with normalized form: first row/column all 1s
    H = ones((n, n))
    
    def backtrack(row, col):
        if row == n:
            return check_orthogonality(H)
        
        # Try both +1 and -1
        for val in [1, -1]:
            H[row, col] = val
            
            # Check partial orthogonality
            if is_feasible(H, row, col):
                if backtrack(next_position(row, col)):
                    return True
        
        return False
    
    return backtrack(1, 1)  # Start from (1,1)

Challenge: Search space is 2^((n-1)²), astronomically large.

34.9 The Conference Matrix Detour

Definition 34.4 (Conference Matrix): Matrix C with 0s on diagonal, ±1 elsewhere, satisfying: $CC^T = (n-1)I$

Connection: If n ≡ 2 (mod 4) and C exists, then H₂ₙ exists.

Application: Another construction method.

34.10 Algebraic Constraints

Character Theory: For group G of order n: $\sum_{g \in G} \chi(g) = \begin{cases} n & \text{if } \chi = 1 \\ 0 & \text{otherwise} \end{cases}$

Application: Group-based constructions use character orthogonality.

Limitation: Not all Hadamard matrices have group structure.

34.11 The Determinant Bound

Theorem 34.3 (Hadamard's Inequality): For any real matrix A = (aᵢⱼ): $|det(A)| \leq \prod_{i=1}^n \|a_i\|$

Equality: Achieved iff rows orthogonal.

For ±1 matrices: Maximum is n^(n/2), achieved by Hadamard matrices.

34.12 Weighing Matrices Generalization

Definition 34.5 (Weighing Matrix): W(n,k) has entries 0, ±1 with k non-zeros per row/column, orthogonal rows.

Special Case: W(n,n) = Hadamard matrix.

Theory: Richer existence results for k < n.

34.13 Applications

Error-Correcting Codes:

• Hadamard codes from matrix rows
• Maximum distance separable
• Used in deep space communication

Signal Processing:

• Walsh-Hadamard transform
• Fast algorithm via recursion
• Compression and filtering

Quantum Computing:

• Hadamard gate fundamental
• Creates superposition states

34.14 The Asymptotic Question

Theorem 34.4 (Seberry): Hadamard matrices exist for all: $n = 2^a \prod_{i} p_i^{b_i}$ where each pᵢ = 4k + 3 is prime.

Coverage: Infinitely many n, but gaps remain.

Density: Unknown if "most" multiples of 4 have Hadamard matrices.

34.15 Complex Hadamard Matrices

Generalization: Entries from {1, -1, i, -i}.

Definition 34.6 (Complex Hadamard): $HH^* = nI$

Result: Exist for all n, not just n ≡ 0 (mod 4)!

Mystery: Why does complex case differ?

34.16 The Cocyclic Approach

Definition 34.7 (Cocyclic Matrix): Constructed from group cocycle: $H_{ij} = \psi(g_i, g_j)$

Theorem 34.5 (de Launey-Horadam): Many Hadamard matrices are cocyclic.

Open: Are all Hadamard matrices cocyclic?

34.17 Automorphism Groups

Question: What symmetries can Hadamard matrices have?

Known Groups:

• Trivial (most matrices)
• Cyclic (from cyclic difference sets)
• Large groups (from algebraic constructions)

Open: Classification of possible automorphism groups.

34.18 The Williamson Method

Construction: Build H₄ₙ from four symmetric ±1 matrices A,B,C,D of order n: $H = \begin{pmatrix} A & B & C & D \\ -B & A & -D & C \\ -C & D & A & -B \\ -D & -C & B & A \end{pmatrix}$

Requirement: A² + B² + C² + D² = 4nI

Success: Many new Hadamard matrices found.

34.19 Why Hadamard Matters

Central to:

1. Combinatorics: Extremal set theory
2. Coding Theory: Optimal codes
3. Statistics: Optimal experimental design
4. Physics: Quantum gates and measurements

The conjecture touches many fields.

34.20 The Thirty-Fourth Echo

The Hadamard Conjecture presents perfect balance from binary constraints:

• Maximal orthogonality from minimal alphabet
• Global structure from local choices
• The mystery of why n ≡ 0 (mod 4) matters
• Discrete perfection resisting general construction

This is ψ = ψ(ψ) as matrix theory seeking its extremal configurations—the attempt to achieve perfect orthogonal balance using only ±1 entries. The conjecture claims such perfection is possible precisely when the dimension permits quaternionic structure.

The variety of construction methods—Sylvester, Paley, Williamson, cocyclic—each revealing different aspects of the problem, shows how Hadamard matrices sit at the intersection of algebra, combinatorics, and design theory, yet resist a unified approach.

The Hadamard matrix whispers: "I am perfect balance achieved through binary choice, maximal determinant from minimal entries, ψ = ψ(ψ) as orthogonality emerging from constraint. In my ±1 patterns lies the secret of how discrete choices can achieve continuous perfection—if only the dimension aligns with the hidden quaternionic order."