Generating Hadamard matrices with transformers

Geordie Williamson; Oded Yacobi; Paul Zinn-Justin

math.COApr 13, 2026

Generating Hadamard matrices with transformers

Authors: Geordie Williamson, Oded Yacobi, Paul Zinn-Justin

Abstract

We present a new method for constructing Hadamard matrices that combines transformer neural networks with local search in the PatternBoost framework. Our approach is designed for extremely sparse combinatorial search problems and is particularly effective for Hadamard matrices of Goethals--Seidel type, where Fourier methods permit fast scoring and optimisation. For orders between 100 and 200, it produces large numbers of inequivalent Hadamard matrices, and for larger orders, it succeeds where local search from random initialisation fails. The largest example found by our method has order 252. In addition to these new constructions, our experiments reveal that the transformer can discover and exploit useful hidden symmetry in the search space.

Figures & tables

Figure 1. A GS type Hadamard matrix of order $244$ . Coloured entries are $+1$ , black entries are $-1$ .

Panel of Figure 2 — Figure 2. Number of GS type Hadamard matrices for small $n$ .

Panel of Figure 3 — Figure 3. Loss, average score and ratio of Hadamard matrices in a typical $n=140$ run .

Panel of Figure 4 — Figure 4. Loss, average score and ratio of Hadamard matrices in a typical $n=212$ run .

Figure 5. Influence of stacking on ratio of produced Hadamard matrices and on computation time.

Panel of Figure 6 — Figure 6. A typical $n=140$ run with alternate Ansatz ( 5 ).

		(5,7,7,7)	(1,5,5,11)
False	1	0	1
False	270	1 009	1 087
True	14	17	26
True	305	1 196	1 437

Table 1. Influence of transformer_uses_score (rows) and segment_sums (columns) on the generation of

n=172

Hadamard matrices: top/bottom number is pre/post improvement total number of Hadamard matrices after 30 generations.

Combinatorial Optimization

Combinatorial optimization finds the best feasible choices among discrete alternatives in routing, scheduling, graph problems, and resource allocation.

See all 382 papers

Manifold-based Algorithms for the Hadamard Decomposition
May 27, 2026Nicolas Gillis, Subhayan Saha, Stefano Sicilia +1Low-Rank Matrix Decomposition Low-Rank Approximation
Department of Mathematics and Operational Research, University of Mons, Mons, Belgium. · SS is a member of the Gruppo Nazionale Calcolo Scientifico-Istituto Nazionale di Alta Matematica (GNCS-INdAM).
AdaHOP: Fast and Accurate Low-Precision Training via Outlier-Pattern-Aware Rotation
Apr 2, 2026Seonggon Kim, Alireza Khodamoradi, Pranathi Vasireddy +2Walsh-Hadamard Transform Low-Precision Training
Advanced Micro Devices, Inc. · POSTECH
HORST: Composing Optimizer Geometries for Sparse Transformer Training
May 20, 2026Tom Jacobs, Rohan Jain, Rebekka BurkholzDeep Learning Optimization Transformer
CISPA Helmholtz Center for Information Security

May 27, 2026J/K move · Enter open · S save

Manifold-based Algorithms for the Hadamard Decomposition

Nicolas Gillis, Subhayan Saha, Stefano Sicilia, Arnaud Vandaele

Department of Mathematics and Operational Research, University of Mons, Mons, Belgium. · SS is a member of the Gruppo Nazionale Calcolo Scientifico-Istituto Nazionale di Alta Matematica (GNCS-INdAM).

Low-Rank Matrix Decomposition Low-Rank Approximation Matrix Optimization Matrix Factorization

Open paper AskPDF arXiv

Given a matrix

X

, and two ranks

r_1

and

r_2

, the Hadamard decomposition (HD) looks for two low-rank matrices,

X_1

of rank

r_1

and

X_2

of rank

r_2

, both of the same size as

X

, such that

X\approx X_1\circ X_2

, where

\circ

is the Hadamard (element-wise) product. In most cases, HD is more expressive than standard low-rank approximations such as the truncated singular value decomposition (TSVD), as it can represent higher-rank matrices with the same number of parameters; this is because the rank of

X_1 \circ X_2

is generically equal to

r_1 r_2

. In this paper, we first present some theoretical insights for HD, in particular a useful reformulation

X\approx WH^\top

where

W

and

H

have

r_1 r_2

columns and belong to certain manifolds. These allow us to develop three new algorithms for computing HD. The first one uses the representation

X\approx X_1\circ X_2

and relies on the Manopt toolbox. The other two rely on the reformulation

X\approx WH^\top

: one is a block projected gradient method, and the other is a manifold-based gradient descent algorithm that does not require projection onto the feasible set. The last two algorithms are particularly effective for handling large sparse data. We also propose new initializations that allow us to improve the accuracy of the HD. We compare our algorithms and initialization strategies with the TSVD and with the state of the art. Numerical results show that the new methods are efficient and competitive on both synthetic and real data.

Abstract

Combinatorial Optimization

Explore similar work

Manifold-based Algorithms for the Hadamard Decomposition

AdaHOP: Fast and Accurate Low-Precision Training via Outlier-Pattern-Aware Rotation

HORST: Composing Optimizer Geometries for Sparse Transformer Training