G. Butbaia

J. Tan

P. Vipulanandan

X. Huang

T. Saunders-A'Court

L. Fagan

D. Passaro

M. Tarquini

S. Gukov

Binary matrices achieving record-highest determinants are computed by employing reinforcement learning as a combinatorial optimisation tool.

The Hadamard maximal determinant problem, conceived in 1893, seeks binary matrices attaining the highest possible determinant. For orders n~3 (mod 4), we reformulate the problem as a sequence reconstruction problem and use reinforcement learning to circumvent arithmetic obstructions to sequence completion. We set new records in six orders, demonstrating the utility of learned search in extremal sparse-reward problems.

The Hadamard maximal determinant problem seeks an n×n matrix X with entries in {±1}, which maximizes the determinant |detX| for a given order n∈ℕ. We report matrices attaining new record determinants for orders n≡3(mod4) between 103 and 119, as well as n=51. We provide a proof of optimality within a specific family of circulant--block constructions for X. For these orders, we recast the Hadamard problem as a sequence reconstruction problem from a pair of periodic autocorrelation functions, subject to certain arithmetic conditions. We describe several learning--based strategies for reconstruction and provide a comparison with classical simulated annealing--style approaches as a benchmark.

New records for the Hadamard maximal determinant problem