gpt 6 astra ultra attempt on Math-342

Hadamard Matrix Conjecture

Definitions and mathematical statement

A Hadamard matrix of order $n$ is a real $n\times n$ matrix $H$ whose entries lie in $\{-1,1\}$ and whose rows are mutually orthogonal. Thus \[ HH^{\mathsf T}=nI_n. \] The existence conjecture asks, for every positive integer $k$, for such a matrix of order $n=4k$. The scalar product condition is exact; it is not an approximate orthogonality requirement. Interchanging or negating rows and columns preserves the condition but is not part of an additional classification task. The assertion quantifies over every multiple of four, not just infinitely many orders or orders supplied by a particular construction.

Formulation and concept references: [S1].

Short English statement

Does a square matrix of plus and minus ones with mutually orthogonal rows exist at every order divisible by four?

Research attempt

Status: UNRESOLVED. The necessary divisibility condition, tensor closure, two finite-field constructions and the equivalence with a symmetric design are proved below. They produce infinite families and exact finite certificates, but do not cover every order divisible by four. No numerical near-orthogonality or modular congruence is used as a substitute for the integer matrix equation.

Source audit and scope.

The publisher page confirms the book and bibliographic information in [S1]. The construction database [E1], also consulted on 27 September 2026, describes many implemented families and audited finite tables. Such a table is a record of constructions within its stated range, not a proof of the universal assertion. Because finite existence records can change, this attempt makes no claim about the current smallest undecided order. The proofs below construct their own matrices and verify them independently of any downloaded matrix payload.

A row or column sign change and a row or column permutation preserve $HH^{\mathsf T}=nI$. These operations let us normalize the first row and the first column to all ones. Since $H$ is square, row orthogonality also implies column orthogonality: $H^{-1}=H^{\mathsf T}/n$, whence $H^{\mathsf T}H=nI$.

1. Necessity of the factor four.

Suppose $n>2$. After normalizing the first row, each other row has equally many $+1$ and $-1$ entries. Thus $n$ is even. Permute columns so that the second row has $n/2$ plus signs followed by $n/2$ minus signs. Let the third row have $a$ plus signs in the first half and $b$ in the second. Its orthogonality to the first row gives $a+b=n/2$. Orthogonality to the second gives \[ (2a-n/2)-(2b-n/2)=0, \] so $a=b=n/4$. Hence $4\mid n$. The exceptional orders one and two have matrices $(1)$ and \[ H_2=\begin{pmatrix}1&1\\1&-1\end{pmatrix}. \] This proves necessity, not sufficiency. In particular, congruence information about possible orders does not construct the required rows.

2. Doubling and tensor products.

If $H$ and $K$ have orders $a$ and $b$, then their Kronecker product has sign entries and \[ (H\otimes K)(H\otimes K)^{\mathsf T} =(HH^{\mathsf T})\otimes(KK^{\mathsf T})=abI_{ab}. \] Taking repeated products with $H_2$ produces every power-of-two order. Equivalently, the doubling step is \[ H\longmapsto\begin{pmatrix}H&H\\H&-H\end{pmatrix}. \] It produces four times any already constructed order as well, but that is not induction from $4k$ to $4(k+1)$. Closure under multiplication cannot be replaced by closure under addition. A block-diagonal sum would have zero off-diagonal blocks and therefore would fail the requirement that every entry be a sign.

3. The quadratic-character correlation identity.

Let $\mathbb F_q$ be a finite field of odd order, and let $\chi$ be its quadratic character, extended by $\chi(0)=0$. We use \[ \sum_{x\in\mathbb F_q}\chi(x)=0,\qquad \sum_{x\in\mathbb F_q}\chi(x-a)\chi(x-b)=-1\quad(a\ne b). \] For completeness, the second identity follows by an affine change of variable from $\sum_u\chi(u(u-1))=-1$. Count pairs $(u,v)$ satisfying $v^2=u(u-1)$. For each $u$ there are $1+\chi(u(u-1))$ possible $v$. On the other hand, \[ (2u-1-2v)(2u-1+2v)=1. \] Each nonzero choice of the first factor determines the second as its inverse and then determines $u,v$ uniquely, since two and four are invertible. There are $q-1$ pairs. Comparing counts gives the identity. This proof applies to all odd prime powers, not just primes.

Index a matrix $Q$ by $\mathbb F_q$, with $Q_{ij}=\chi(i-j)$. The character identities imply \[ Q\mathbf1=0,\qquad QQ^{\mathsf T}=qI-J, \qquad Q^{\mathsf T}=\chi(-1)Q, \] where $J$ is the all-ones matrix. The diagonal entries of $QQ^{\mathsf T}$ are $q-1$ and the off-diagonal entries are $-1$, explaining the sign in $qI-J$.

4. Construction for $q\equiv3\pmod4$.

Here $Q^{\mathsf T}=-Q$. Form the $(q+1)$-square matrix \[ H=\begin{pmatrix}1&\mathbf1^{\mathsf T}\\ -\mathbf1&I+Q\end{pmatrix}. \] Its entries are signs: $I+Q$ has diagonal one and off-diagonal $\pm1$. Its top row has squared length $q+1$. The scalar product of the top row with a lower row is $-1+1+0=0$. The lower-row Gram matrix is \[ J+(I+Q)(I+Q)^{\mathsf T} =J+I+Q+Q^{\mathsf T}+QQ^{\mathsf T}=(q+1)I. \] Thus it is a Hadamard matrix of order $q+1$. Multiplying every lower row by $-1$ normalizes the first column if desired. The construction gives, for example, orders $4,8,12,20,24$ from primes $3,7,11,19,23$.

5. Construction for $q\equiv1\pmod4$.

Now $Q$ is symmetric. Define the symmetric conference matrix \[ C=\begin{pmatrix}0&\mathbf1^{\mathsf T}\\ \mathbf1&Q\end{pmatrix},\qquad C^2=qI_{q+1}. \] The identity follows from $Q\mathbf1=0$ and $Q^2=qI-J$. Its diagonal is zero and all off-diagonal entries are signs. Put \[ H=\begin{pmatrix}C+I&C-I\\ C-I&-C-I\end{pmatrix}. \] Every entry of $H$ is again a sign. Since $C-I$ and $C+I$ commute and are symmetric, each diagonal block of $HH^{\mathsf T}$ is \[ (C+I)^2+(C-I)^2=2(q+1)I, \] and each off-diagonal block vanishes. The order is $2(q+1)$, a multiple of four. This includes orders $12,28,36$ from primes $5,13,17$.

The two constructions and tensor closure provide many overlapping families. To settle the conjecture by these tools alone, one would need a number-theoretic coverage theorem saying every $4k$ factors into available orders. No such theorem is established here. Failure of one parameterization to represent an order would show a limitation of that parameterization, not nonexistence of a Hadamard matrix.

6. An equivalent incidence-matrix problem.

Write $n=4t$ and normalize $H$. Delete its first row and column to obtain a $(4t-1)$-square sign matrix $B$. Orthogonality with the first row gives $B\mathbf1=-\mathbf1$, and lower-row orthogonality gives \[ BB^{\mathsf T}=4tI-J. \] Set $A=(J+B)/2$. It is a zero-one matrix with constant row sum $2t-1$. A direct expansion, using $BJ=JB^{\mathsf T}=-J$, gives \[ AA^{\mathsf T}=tI+(t-1)J. \] Thus each row contains $2t-1$ ones and any two distinct rows meet in $t-1$ ones. Column sums are also $2t-1$, either from the normalized column orthogonality of $H$ or directly from invertibility and the displayed Gram equation. This is the incidence structure usually called a symmetric Hadamard design, with parameters $(4t-1,2t-1,t-1)$.

Conversely, suppose a square zero-one matrix $A$ of size $4t-1$ has those row sums and Gram matrix. Define $B=2A-J$ and border it with a first row and column of ones. Then $B\mathbf1=-\mathbf1$ and $BB^{\mathsf T}=4tI-J$, so the bordered sign matrix has Gram matrix $4tI$. This proves the equivalence without assuming a general existence theorem for designs.

The design parameters satisfy the necessary counting identities, but numerical feasibility of parameters is not construction of a design. Rephrasing the conjecture this way is useful because it gives exact intersection constraints, not because it removes the existence problem.

7. Determinants, approximation and a precise diagnostic.

Gram--Schmidt bounds the absolute determinant of any sign matrix by the product of its row lengths, namely $n^{n/2}$. Equality holds exactly when each row is orthogonal to the span of its predecessors, hence when all rows are mutually orthogonal. Consequently the conjecture is equivalent to attaining this determinant bound at every order $4t$.

A large determinant short of that value does not prove equality. Nor does a modular identity $HH^{\mathsf T}\equiv nI\pmod M$ imply the integer identity: an off-diagonal dot product might be a nonzero multiple of $M$. If one additionally has $M>n$, the integer bound $|\langle H_i,H_j\rangle|\le n$ forces such a multiple to be zero, but without a modulus exceeding this range that inference is unavailable. Likewise, a floating Gram computation requires a justified error bound below the relevant integer separation before it becomes an exact certificate.

The offline script uses exact integers to build the two character families over prime fields for odd primes at most 43, and selected tensor products. For every output it checks all signs and every entry of $HH^{\mathsf T}$, then normalizes it and verifies the associated design row sums and pair intersections. The character-correlation sums are checked separately. This tests the construction formulas and signs over a stated finite range; the all-prime-power proofs are the algebraic arguments above. It provides no matrix for a generic prescribed $4k$, and the universal existence assertion remains unresolved here.

Sources

• S1 K. J. Horadam, Hadamard Matrices and Their Applications, Princeton Univ. Press, 2007. https://press.princeton.edu/books/hardcover/9780691119212/hadamard-matrices-and-their-applications. Formulation source.
• E1 Matteo Cati and Dmitrii V. Pasechnik, A database of constructions of Hadamard matrices, arXiv:2411.18897. https://arxiv.org/abs/2411.18897. Primary construction-database reference; finite coverage is not universal existence.