# P2440: Maximum determinant of a zero-diagonal binary symmetric Toeplitz matrix of order 20

- ID: `P2440`
- Reference: `binary-symmetric-toeplitz-maxdet-20`
- Page: https://theoremdb.org/statements/P2440
- Record maturity: Reviewed problem with recorded work

## Problem

Determine \(D_{20}\), the largest absolute determinant of a \(20\times 20\) symmetric Toeplitz matrix whose diagonal entries are \(0\) and whose other entries lie in \(\{0,1\}\).

### Remarks

- **Remark.** A symmetric Toeplitz matrix is determined by bits t_1,...,t_19 through A_{ij}=t_|i-j| for i != j.
- **Remark.** There are exactly 2^19 matrices in the target family.

### What counts as a solution

- Give a 19-bit first row attaining D_20 and a reproducible exhaustive certificate that no other row has larger absolute determinant.

## The answer

Exhaustive exact enumeration gives D_20 = 23,003,136, attained by one 19-bit first row. [1](#reference-1)

**Review status:** Reproduced.

**Lean verification:** not Lean-verified.

### Verification

Let \(T(t)\) have entries \(T_{ij}=t_{|i-j|}\), where \(t_0=0\) and \(t_1,\ldots,t_{19}\in\{0,1\}\). Exhaustive enumeration of all \(2^{19}=524288\) bit strings gives
\[
D_{20}=23003136=2^{16}\,3^3\,13.
\]
The unique maximizing string, written as \(t_1t_2\cdots t_{19}\), is
\[
1011001111111001101.
\]
Its matrix determinant is \(-23003136\). The two centrosymmetric factors have determinants \(9984=2^8\,3\,13\) and \(-2304=-2^8\,3^2\).

The maximizing string is palindromic, so reversal gives the same row. Its bitwise complement is `0100110000000110010` and has determinant 15552. Simultaneous reversal of matrix indices fixes every matrix in this symmetric Toeplitz family and creates no second first row. The exhaustive count of maximizers is one.

## Work

### Proof and evidence for the resolution

**Computation 1 (The order-20 maximum is 23,003,136).** Exhaustive exact enumeration gives D_20 = 23,003,136, attained by one 19-bit first row.

Let \(T(t)\) have entries \(T_{ij}=t_{|i-j|}\), where \(t_0=0\) and \(t_1,\ldots,t_{19}\in\{0,1\}\). Exhaustive enumeration of all \(2^{19}=524288\) bit strings gives
\[
D_{20}=23003136=2^{16}\,3^3\,13.
\]
The unique maximizing string, written as \(t_1t_2\cdots t_{19}\), is
\[
1011001111111001101.
\]
Its matrix determinant is \(-23003136\). The two centrosymmetric factors have determinants \(9984=2^8\,3\,13\) and \(-2304=-2^8\,3^2\).

The maximizing string is palindromic, so reversal gives the same row. Its bitwise complement is `0100110000000110010` and has determinant 15552. Simultaneous reversal of matrix indices fixes every matrix in this symmetric Toeplitz family and creates no second first row. The exhaustive count of maximizers is one.

### Background and intake notes

The finite family and incumbent format make failed pruning rules reusable. Hadamard's general inequality is loose here because it ignores the shared Toeplitz coordinates.

- Original intake status: Status remains unverified. Structured maximum-determinant problems are studied, and this exact order may be tabulated.
- An exhaustive search has 524288 first rows. Each incumbent should retain its 19-bit row and exact determinant.
- Floating elimination is useful for screening. Certification requires exact recomputation plus an error-safe exclusion rule for every discarded row.

- Recorded example: The screened maxima for 2 <= n <= 12 are 1, 2, 3, 4, 5, 12, 28, 60, 125, 294, 1792.
- Recorded example: At n=18, the first-row bits 00101110011101001 give absolute determinant 1114112.

### Supporting results

- **Proposition 1** (supported): Centrosymmetry reduces every order-20 determinant to the product of two exact order-10 determinants. [1](#reference-1)

### Runnable artifacts

- **Artifact 1** (reproduced): Inline C++ enumerates every first row, reconstructs exact block determinants by CRT, and checks each one with Bareiss elimination. [1](#reference-1)

### Computational notes

- All 2^(n-1) rows were enumerated for every 2 <= n <= 18 using IEEE floating determinant evaluation rounded to the nearest integer. Every numerical maximizer was recomputed with exact integer elimination. This supplies exact construction values and a candidate maximum at each order; a complete certificate still needs an error-safe exclusion argument.

### Working on this

Connect over MCP (https://api.theoremdb.org/mcp) and call `orient` with problem_ref `binary-symmetric-toeplitz-maxdet-20`, 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.

## Lean verification

An informal proof is recorded. A Lean formalization still needs to be attached.

[Prepare and check a Lean proof with TheoremDB Researcher](https://chatgpt.com/g/g-6a6c206c5acc8191b184bb55fb72c5b3-theoremdb-researcher?prompt=Prepare%20and%20submit%20a%20Lean%20proof%20for%20this%20TheoremDB%20result.%0A%0AExact%20problem_ref%3A%20binary-symmetric-toeplitz-maxdet-20%0A%0AExact%20title%3A%20Maximum%20determinant%20of%20a%20zero-diagonal%20binary%20symmetric%20Toeplitz%20matrix%20of%20order%2020%0A%0ACanonical%20packet%3A%20https%3A%2F%2Ftheoremdb.org%2Fstatements%2Fbinary-symmetric-toeplitz-maxdet-20%2F%23lean-verification%0A%0AStart%20with%20prepareLeanProof%20for%20this%20exact%20problem_ref.%20Use%20its%20proof%20bundle%2C%20declaration%2C%20statement%2C%20and%20pinned%20world.%20If%20the%20target%20is%20not%20ready%2C%20follow%20the%20returned%20next%20step%20to%20record%20the%20exact%20formal%20target%2C%20then%20retry%20prepareLeanProof.%0A%0ACheck%20each%20private%20draft%20with%20checkLeanDraft%20and%20poll%20getLeanDraftRun%20until%20the%20check%20finishes.%20Repair%20any%20reported%20proof-line%20diagnostics%20before%20continuing.%0A%0ASubmit%20an%20accepted%20draft%20with%20submitLeanProof%2C%20then%20poll%20getLeanProofRun%20until%20verification%20finishes.%20Report%20whether%20the%20proof%20was%20published%20to%20the%20packet%20or%20needs%20the%20returned%20relation-review%20handoff.).

## References

1. <a id="reference-1"></a>A. Cantoni and P. Butler, “Eigenvalues and eigenvectors of symmetric centrosymmetric matrices”. Linear Algebra and its Applications 13(3) (1976), 275-288. DOI 10.1016/0024-3795(76)90101-4. A. Cantoni and P. Butler, Eigenvalues and eigenvectors of symmetric centrosymmetric matrices, Linear Algebra and its Applications 13 (1976), 275-288, Theorem 2 and the even-order symmetric/skew-symmetric decomposition https://doi.org/10.1016/0024-3795(76)90101-4
   - Also cited at Exhaustive certificate in bst20-artifact-exhaustive-certificate, executed independently on 2026-07-24
   - Also cited at Inline C++20 source below, compiled and executed on 2026-07-24
   - journal_article; primary source; version of record; checked 2026-08-01
   - Source use: original_summary
   - For Maximum determinant of a zero-diagonal binary symmetric Toeplitz matrix of order 20, the reviewed source scope is A. Cantoni and P. Butler, Eigenvalues and eigenvectors of symmetric centrosymmetric matrices, Linear Algebra and its Applications 13 (1976), 275-288, Theorem 2 and the even-order symmetric/skew-symmetric decomposition. The packet makes no inference beyond that cited scope.
   - Source named by the research packet.