Hadamard Graph

A Hadamard graph of index is a graph on vertices defined in terms of a Hadamard matrix as follows. Define symbols , , , and , where stands for "row" and stands for "column," and take these as the vertices of the graph. Then construct two edges for each matrix element such that and for each matrix element such that (Brouwer et al. 1989, p. 19).

An -Hadamard graph therefore exists for each value of for which a corresponding Hadamard matrix exists, which includes , 2, and every positive integer multiple of 4 below 2000. Epoch AI (2026) reported constructions for the twelve previously unresolved orders in this range, including 668. Existence for every positive integer multiple of 4 remains conjectural. Multiple distinct Hadamard matrices may exist of a given order, but their corresponding Hadamard graphs are not necessarily distinct. While the numbers of different Hadamard matrices of orders 4, 8, 12, ... are 1, 1, 1, 5, 3, 60, 487, ..., the corresponding numbers of nonisomorphic Hadamard graphs are 1, 1, 1, 4, 3, 36, 294, ....

Note that there are two variants in the definition of Hadamard graphs. In particular, Wallis (1988, p. 165) requires that half the vertices of a Hadamard graph (those corresponding to rows) be given self-loops while the rest of the vertices (corresponding to columns) should not. In contrast, the definition of Brouwer et al. (1989, p. 19), which is the one adopted here, omits such self-loops. Note that while Hadamard graphs with self-loops can be used as a tool for determining equivalence of Hadamard matrices, those without cannot (L. Baird, pers. comm., Nov. 2008).

For , an -Hadamard graph is distance-regular with intersection array (Brouwer et al. 1989, p. 19). An -Hadamard graph is distance-transitive if is a power of 2 or if (Brouwer et al. 1989, pp. 227-228).

Special cases are summarized in the following table.

	-Hadamard graph
1	2-ladder rung graph
2	cycle graph
4	tesseract graph