ResearchCombinatorial designsGSI-R-0006 · Note · Existence
Circulant good matrices of orders 53 and 55 exist; one explicit set of each is given.
Circulant good matrices of odd order n are circulant ±1 matrices A, B, C, D with A + AT = 2I, B, C, D symmetric, and AAT + BBT + CCT + DDT = 4nI. We give one set for each n ∈ {53, 55}; each yields a skew-Hadamard matrix of order 4n (212, 220) by the Goethals–Seidel array [1].
- Before this work
- Đoković and Kotsireas [1] list good matrices at odd orders ≤ 39 and at 43, 45 and 127, none at 41, 47 and 49; Bright et al. [2] add 57, none at 51, 63 and 69. Neither lists 53 or 55 (read 15 November 2026).
- Evidence
- Independently checked. Each printed set is its own certificate, and 3 programs of ours and a Lean file, written without the search code, also accept it. They share the definition and the sequence encoding; no review outside the lab is recorded.
- What you can check
- All of it. Paste the sequences and the 10-line script below into Python 3 (under a second), then run the published checkers on the same sets (each under 2 seconds; Lean under 15 seconds).
- Not established
- That each order has exactly one inequivalent set (equivalence as in [2]). Our 3 complete computer searches at each order returned only the printed set, none with a public certificate.
- Method
- Not published.
What was known
With the first entries fixed to +1, the four defining rows have 4n−1 possible values at order n [2]. Exhaustive searches had reached order 49 [1]; Bright et al. [2] added the odd multiples of 3 up to 69.
The order-53 near-Williamson matrices of Kharaghani et al. [3] (the same identity with A unrestricted) have ak = an−k for 2 ≤ k ≤ n−2, so A is not skew. The order-53 difference families of Abuzin et al. [4] have 2 equal blocks, neither symmetric nor skew. Neither gives a good set.
Đoković [5] (16 November 2024) writes that the known good matrices have orders at most 127. We found no good matrices of order 53 or 55 in any reference below (the survey [6] was searched for the term only); to our knowledge these are the first.
Skew-Hadamard matrices of orders 212 and 220 were already known: Table 3 of [7] lists n = 53 under Paley’s first construction and n = 55 under complementary difference sets. New here is the good-matrix structure.
The result
Each sequence is a first row x0, …, xn−1, with + for 1 and - for −1; a0 = 1, an−i = −ai, and xn−i = xi for x = b, c, d. The matrix identity is equivalent to Σx Σi xixi+s = 0 for s ≠ 0 and 4n for s = 0, over x = a, b, c, d with indices mod n.
A53 = "++-+--+--++-+-----++-+-++++----+-+--+++++-+--++-++-+-"
B53 = "+++++-+++-++--++----+--+-++++-+--+----++--++-+++-++++"
C53 = "+---++++-++++-+++---+-+++----+++-+---+++-++++-++++---"
D53 = "+-++----+++-++--+---+-+-+----+-+-+---+--++-+++----++-"
A55 = "+-+---+++-+-+----+++-++-++++----+--+---++++-+-+---+++-+"
B55 = "++---+--+--+++---+-+++++-++++++-+++++-+---+++--+--+---+"
C55 = "+-++-+--++--------++-+-+---++---+-+-++--------++--+-++-"
D55 = "+---++-++-+-+---+--+--+++++--+++++--+--+---+-+-++-++---"Theorem 1 of [2] (Wallis, 1970) is stated for pairwise amicable matrices (XYT symmetric); Bright et al. reach them from good matrices by reversing the rows of B, C, D. With R the reversal matrix, H below is the Goethals–Seidel array [1]; it is skew-Hadamard if its entries are ±1, HHT = 4nI and H + HT = 2I.
H = [ A BR CR DR ]
[ -BR A DR -CR ]
[ -CR -DR A BR ]
[ -DR CR -BR A ]How to check it
1. Append this script to the sequences above.
def paf(x, s): return sum(x[i] * x[(i + s) % len(x)] for i in range(len(x)))
def word(x): return sum(1 << (i - 1) for i in range(1, len(x) // 2 + 1) if x[i] == -1)
for n, rows in ((53, (A53, B53, C53, D53)), (55, (A55, B55, C55, D55))):
A, B, C, D = [[1 if c == "+" else -1 for c in r] for r in rows]
assert all(len(X) == n for X in (A, B, C, D)) and A[0] == 1 and all(A[n - i] == -A[i] for i in range(1, n))
assert all(X[n - i] == X[i] for X in (B, C, D) for i in range(1, n))
sums = [sum(paf(X, s) for X in (A, B, C, D)) for s in range(n)]
assert sums[0] == 4 * n and not any(sums[1:])
print(n, "row sums", [sum(X) for X in (A, B, C, D)], "autocorrelation total", sums[0])
print("hex", *[format(word(X), "x") for X in (A, B, C, D)])2. From one folder holding the 5 files listed below (ck_good.py, vgood.py and mutants.py need NumPy, ck_good2.c a C compiler):
python3 ck_good.py 53 29f4da b79910 3171087 3576479
python3 ck_good.py 55 48f51d 82e36e 3a9fe69 41b7527
cc -O2 -o ck_good2 ck_good2.c
./ck_good2 53 29f4da b79910 3171087 3576479
./ck_good2 55 48f51d 82e36e 3a9fe69 41b7527
python3 vgood.py
python3 mutants.py
lean Good5355.lean{'n': 53, 'paf_ok': True, 'paf0': 212, 'pm1': True, 'hadamard': True, 'skew': True, 'rowsums': [1, 9, 9, -7], 'PASS': True}
{'n': 55, 'paf_ok': True, 'paf0': 220, 'pm1': True, 'hadamard': True, 'skew': True, 'rowsums': [1, 7, -13, -1], 'PASS': True}
n=53 poly_identity=1 hadamard=1 skew=1
n=55 poly_identity=1 hadamard=1 skew=1
witness n=53 ok=True [] rowsums=[1, 9, 9, -7]
witness n=55 ok=True [] rowsums=[1, 7, -13, -1]
53 single-bit mutants 104 accepted 0 | junk high bit rejected | A<->B swap accepted False
55 single-bit mutants 108 accepted 0 | junk high bit rejected | A<->B swap accepted FalseA pass establishes that the printed sequences meet the defining conditions and that H is skew-Hadamard at both orders. The Lean proof covers the defining conditions in autocorrelation form only, not H or the Goethals–Seidel theorem. The script shares no code with the files. A failed condition would refute the claim.
What it changes
Of the 6 odd orders up to 69 without a listed status in [1] and [2] (53, 55, 59, 61, 65, 67), we give an explicit set at 53 and at 55.
Limits
- Uniqueness. We do not claim that each order has exactly one inequivalent set (equivalence as in [2]). At each order, 3 complete computer searches run in the lab returned only the printed set, none with a public certificate. A public certificate or a search outside the lab would close it.
- Priority. That these are the first sets of orders 53 and 55 holds only against [1]–[7] as read on 15 November 2026; an earlier publication or an unpublished computation would change it.
Files
- ck_good.pyPython checker (NumPy): autocorrelations, structure, order-4n array; input n and four hex words
- ck_good2.cC checker: polynomial identity and the array built entry by entry, with the reversal that fixes index 0 in place of R
- vgood.pyThird checker (NumPy); checks both sets with no arguments
- mutants.pyAll one-bit changes of the hex words, all rejected; needs ck_good.py in the same folder
- Good5355.leanLean 4: the defining conditions for both sets by decide +kernel, and one changed set proved not good
References
- [1]D. Ž. Đoković, I. S. Kotsireas, Goethals–Seidel difference families with symmetric or skew base blocks, Math. Comput. Sci. 12 (2018) 373–388, arXiv:1802.00556v1 (2 February 2018): display (1) and the Introduction. Link
- [2]C. Bright, D. Ž. Đoković, I. Kotsireas, V. Ganesh, A SAT+CAS approach to finding good matrices: new examples and counterexamples, AAAI 2019, doi:10.1609/aaai.v33i01.33011435, arXiv:1811.05094v1 (13 November 2018): Definition 1, Theorem 1 and Section 2. Link
- [3]H. Kharaghani, A. Mohammadian, B. Tayfeh-Rezaie, V. Zaitsev, A search for Hadamard matrices of near-Williamson type, arXiv:2605.08661v2 (6 September 2026), Sections 2.2 and 2.3 and Table 4. Version 1 (9 May 2026) has 3 authors, without Zaitsev, and the title A search for Hadamard matrices of Williamson type. Link
- [4]L. V. Abuzin, N. A. Balonin, D. Ž. Đoković, I. S. Kotsireas, Hadamard matrices from Goethals–Seidel difference families with a repeated block, Informatsionno-upravliaiushchie sistemy [Information and Control Systems] 2019, no. 5, 2–9, doi:10.31799/1684-8853-2019-5-2-9: the section on v = 53. Link
- [5]D. Ž. Đoković, Two classes of Hadamard matrices of Goethals–Seidel type, arXiv:2404.14375v3 (16 November 2024): Section 3. Link
- [6]R. Egan, I. S. Kotsireas, S. London, P. Ó Catháin, Recent progress in the construction of Hadamard matrices, arXiv:2610.27175v2 (3 November 2026). Link
- [7]M. Cati, D. V. Pasechnik, A database of constructions of Hadamard matrices, arXiv:2411.18897v2 (30 August 2025): Table 3. Link