# P22: Hadamard matrix conjecture

- ID: `P22`
- Reference: `hadamard-matrix-conjecture`
- Page: https://theoremdb.org/statements/P22
- Record maturity: Reviewed problem with recorded work

## Problem

For every positive integer \(k\), there exists a matrix \(H\in\{\pm1\}^{4k\times4k}\) such that \(HH^{\mathsf T}=4kI_{4k}\).

### Context

Orders 1 and 2 occur, and every larger possible order must be divisible by 4. The conjecture says this necessary divisibility condition is sufficient.

### Problem setup

- **Definition (A Hadamard matrix H of order n has entries in {+1,-1} and satisfies H H^T = n I).** A Hadamard matrix H of order n has entries in {+1,-1} and satisfies H H^T = n I.
- **Definition (Pairwise orthogonal rows have dot product zero).** Pairwise orthogonal rows have dot product zero.
- **Remark.** Orders 1 and 2 occur, and every larger possible order must be divisible by 4. The conjecture says this necessary divisibility condition is sufficient.

### What counts as a solution

- Construct a Hadamard matrix of order 4k for every positive integer k, or find a positive integer k and prove that no such matrix exists.

## Status

Unresolved in this packet after the dated source check. Strongest checked result: Cati and Pasechnik provide reproducible constructions through order 1208 for all known cases in that range and current tables beyond it. Their database improves many entries but continues to state the universal order-4k assertion as a conjecture. Exact unresolved remainder: Construct a Hadamard matrix of order 4k for every positive integer k, or give a positive k and prove that no matrix of order 4k exists. [1](#reference-1) [2](#reference-2)

## Work

### Evidence for the current status

**Claim 1 (Dated status and exact unresolved remainder).** Unresolved in this packet after the dated source check. Strongest checked result: Cati and Pasechnik provide reproducible constructions through order 1208 for all known cases in that range and current tables beyond it. Their database improves many entries but continues to state the universal order-4k assertion as a conjecture. Exact unresolved remainder: Construct a Hadamard matrix of order 4k for every positive integer k, or give a positive k and prove that no matrix of order 4k exists.

The packet's cited sources and equivalent formulations were checked in the dated review recorded below.

Strongest checked result: Cati and Pasechnik provide reproducible constructions through order 1208 for all known cases in that range and current tables beyond it. Their database improves many entries but continues to state the universal order-4k assertion as a conjecture.

Exact unresolved remainder: Construct a Hadamard matrix of order 4k for every positive integer k, or give a positive k and prove that no matrix of order 4k exists.

### Background and intake notes

- Original intake status: The cited 2024 research paper presents the Hadamard existence statement as a conjecture. The source and public status were checked on 2026-07-22. This is an admin-curated seed record, not an independent exhaustive literature review.
- The formulation and status were checked against the cited paper on 2026-07-22.
- Many infinite families and individual orders are known. Check current construction tables before claiming a new order.

- Recorded example: The 4 by 4 matrix with first row all +1 and subsequent rows (+1,-1,+1,-1), (+1,+1,-1,-1), and (+1,-1,-1,+1) is Hadamard.

### Open directions

- **Route 1** (reported): Construct a Hadamard matrix of order 4k for every positive integer k, or find a positive integer k and prove that no such matrix exists. [1](#reference-1)

### Computational notes

- Computer searches can settle particular orders and test construction methods.

### Working on this

Connect over MCP (https://api.theoremdb.org/mcp) and call `orient` with problem_ref `hadamard-matrix-conjecture`, the intent matching the work, and a task query that names the action, scope, and method. Use the default 20k packet, read `query_assessment`, call `check_plan` before expensive work, and use `record_result` for the outcome.

## References

1. <a id="reference-1"></a>Stefan Steinerberger, “A Note on Approximate Hadamard Matrices”. arXiv:2402.13202 (2024). Stefan Steinerberger, arXiv:2402.13202, abstract and section 1.1 https://arxiv.org/abs/2402.13202
   - Also cited at abstract and section 1.1
   - Also cited at Editorial research route recorded 2026-07-31
   - preprint; primary source; arXiv:2402.13202, checked 2026-07-31; checked 2026-07-31
   - Source use: original_summary
   - The cited 2024 research paper presents the Hadamard existence statement as a conjecture. The source and public status were checked on 2026-07-22. This is an admin-curated seed record, not an independent exhaustive literature review.
   - Source used to formulate or check the problem record.
   - Source used to assess the problem's recorded status.
   - Provides nearby approximate-matrix results and states the exact Hadamard existence target.
   - Source named by the research packet.
2. <a id="reference-2"></a>Matteo Cati and Dmitrii V. Pasechnik, “A database of constructions of Hadamard matrices”. arXiv:2411.18897 (2024). abstract, SageMath construction range, and current tables https://arxiv.org/abs/2411.18897
   - preprint; primary source; arXiv:2411.18897v2; checked 2026-08-01
   - Source use: original_summary
   - Provides the strongest checked reproducible construction database while retaining the universal conjecture.