40.06.05 · combinatorics / design-coding-theory

Hadamard Matrices and the Paley Construction

shipped3 tiersLean: none

Anchor (Master): van Lint-Wilson 2001 *A Course in Combinatorics* 2e Ch. 18-19 (Hadamard matrices and 2-designs, conference matrices, the Paley constructions of types I and II); Hall 1986 *Combinatorial Theory* 2e Ch. 14; Hadamard 1893 *Bull. Sci. Math.* (2) 17 (the determinant inequality); Paley 1933 *J. Math. Phys.* 12 (the quadratic-residue construction); Sylvester 1867 *Phil. Mag.* (4) 34 (the doubling/tessellation construction); Bruck-Ryser-Chowla as the design-theoretic obstruction

Intuition Beginner

Imagine a square grid of cells, each painted black or white. Read black as $+ 1$ and white as $- 1$ , so every row is a string of pluses and minuses. We want the rows to be as different from one another as possible. Two rows of length $n$ "agree" in some columns and "disagree" in the others; the most balanced relationship is when any two distinct rows agree in exactly half their columns and disagree in the other half. A square $\pm 1$ grid whose rows are pairwise balanced in this way is a Hadamard matrix.

Why care about maximal disagreement? If you broadcast each row as a coded message, two rows that agree only half the time are easy to tell apart even when a few entries get corrupted by noise. The same balance makes Hadamard matrices the backbone of error-correcting codes, of efficient ways to weigh objects or run experiments, and of the fast Walsh-Hadamard transform used in signal processing. Maximal balance is maximal usefulness.

There is a beautiful constraint hiding here. You can build such a grid of size $1$ and of size $2$ , but after that the size is always a multiple of $4$ : $4, 8, 12, 16, 20, \dots$ . You cannot make a balanced grid of size $3$ or $6$ . One of the oldest open questions in the subject asks whether a Hadamard matrix exists for every multiple of $4$ — believed yes, still unproven.

Visual Beginner

A Hadamard matrix of order $4$ looks like the grid below, writing $+$ for $+ 1$ and $-$ for $- 1$ . Pick any two different rows and count: they agree in two columns and disagree in two. That fifty-fifty split is the whole idea.

        col1  col2  col3  col4
 row1     +     +     +     +
 row2     +     -     +     -
 row3     +     +     -     -
 row4     +     -     -     +

Compare row 2 and row 3. Column by column the signs are $(+, +), (-, +), (+, -), (-, -)$ : they match in columns 1 and 4, differ in columns 2 and 3 — two and two. Every pair of distinct rows behaves the same way. The doubling trick below grows this $4 \times 4$ block into an $8 \times 8$ one, then $16 \times 16$ , and so on, doubling the size each time.

Worked example Beginner

Let us build a bigger Hadamard matrix from a smaller one by Sylvester's doubling rule. Start from the smallest interesting block, $$ H_2 = \begin{pmatrix} + & + \ + & - \end{pmatrix}. $$

Step 1. Check $H_{2}$ is balanced. Its two rows are $(+, +)$ and $(+, -)$ . They agree in column 1 and disagree in column 2 — one and one, a fifty-fifty split. Good.

Step 2. Apply the doubling rule. Make a $4 \times 4$ grid in four quarters: put a copy of $H_{2}$ in the top-left, top-right, and bottom-left quarters, and a copy with every sign flipped in the bottom-right quarter. Flipping $H_{2}$ gives $(- - - +)$ .

Step 3. Write out the result. $$ H_4 = \begin{pmatrix} + & + & + & + \ + & - & + & - \ + & + & - & - \ + & - & - & + \end{pmatrix}. $$

Step 4. Spot-check the balance. Compare rows 1 and 4: $(+, +, +, +)$ versus $(+, -, -, +)$ . They agree in columns 1 and 4 and disagree in columns 2 and 3 — two and two. Try any other pair and you get the same two-versus-two split.

What this tells us: from one balanced block you manufacture a balanced block of twice the width. Repeating turns size $2$ into $4$ , then $8$ , then $16$ , giving a Hadamard matrix of every size that is a power of $2$ .

Check your understanding Beginner

Exercise (easy, true-false).

True or false: flipping the sign of every entry in one whole column of a Hadamard matrix produces another Hadamard matrix.

Hint

The balance between two rows counts agreements minus disagreements. Negating a single column flips one comparison the same way in every pair of rows.

Answer

True. Negating a column changes the sign of that one coordinate in every row at once, so for any two rows the column still contributes either a shared agreement or a shared disagreement to both — the fifty-fifty count is preserved. Row and column negations (and permutations) are exactly the moves that turn one Hadamard matrix into an equivalent one. Feedback-correct: this is why we may always arrange the first row and first column to be all $+ 1$ . Feedback-wrong: if you said false, recheck a small case like $H_{2}$ with its second column negated.

Formal definition Intermediate+

Throughout, $J$ denotes the all-ones matrix, $I$ the identity, and $1$ the all-ones column vector, of whatever size context demands.

Definition (Hadamard matrix). A Hadamard matrix of order $n$ is a matrix $H \in {+ 1, - 1}^{n \times n}$ satisfying $$ H H^\top = n I_n. $$ Equivalently, distinct rows are orthogonal as vectors in $R^{n}$ ; since each row has squared length $n$ , two distinct rows agree in exactly $n /2$ coordinates. Because $H$ is square and $H H^{⊤} = n I$ , the relation $H^{⊤} H = n I$ holds as well, so the columns are orthogonal too ^{[van Lint-Wilson Ch. 18]}.

Definition (equivalence and normalisation). Two Hadamard matrices are equivalent if one is obtained from the other by permuting rows, permuting columns, negating rows, and negating columns. Each such operation preserves $H H^{⊤} = n I$ . A Hadamard matrix is normalised (or in standard form) if its first row and first column consist entirely of $+ 1$ ; every Hadamard matrix is equivalent to a normalised one, obtained by negating each row and column whose leading entry is $- 1$ .

Definition (conference matrix). A conference matrix of order $n$ is a matrix $C \in {0, \pm 1}^{n \times n}$ with zero diagonal, $\pm 1$ off the diagonal, and $$ C C^\top = (n-1) I_n. $$ $C$ is symmetric when $C^{⊤} = C$ and skew when $C^{⊤} = - C$ . Conference matrices are the bridge from quadratic residues to Hadamard matrices.

Definition (quadratic-residue / Jacobsthal matrix). Let $q$ be an odd prime power and $χ : F_{q} \to {0, \pm 1}$ the quadratic-residue character: $χ (0) = 0$ , $χ (x) = + 1$ if $x$ is a nonzero square, $χ (x) = - 1$ otherwise. The Jacobsthal matrix is $Q = (χ (a - b))_{a, b \in F_{q}}$ , a $q \times q$ matrix indexed by field elements. Its construction and properties draw on the structure of $F_{q}$ and the Legendre symbol, applied here rather than re-derived.

Counterexamples to common slips Intermediate+

"Orthogonal rows is enough; the column condition is a separate hypothesis." For a square matrix, $H H^{⊤} = n I$ already forces $H^{⊤} H = n I$ , because $H^{⊤} = n H^{- 1}$ . Row-orthogonality and column-orthogonality are equivalent for Hadamard matrices, not independent assumptions.
"Every order divisible by $4$ is known to occur." The divisibility $4 ∣ n$ (for $n > 2$ ) is necessary, but sufficiency is the open Hadamard conjecture. Necessity is a theorem; sufficiency is not.
"The character $χ$ is multiplicative on all of $F_{q}$ ." It is multiplicative, $χ (x y) = χ (x) χ (y)$ , but only the convention $χ (0) = 0$ makes the key sum $\sum_{c} χ (c) χ (c + a) = - 1$ (for $a \neq = 0$ ) come out correctly; mishandling the zero term corrupts the conference-matrix identity.
"Type I and type II Paley matrices have the same order." For $q \equiv 3 (mod 4)$ the construction yields order $q + 1$ ; for $q \equiv 1 (mod 4)$ the symmetric conference matrix must be doubled, giving order $2 (q + 1)$ . The residue class of $q$ modulo $4$ controls whether $Q$ is skew or symmetric, and hence the order.

Key theorem with proof Intermediate+

The signature result fixes the possible orders. It rests on Hadamard's determinant inequality, whose equality case characterises Hadamard matrices among all $\pm 1$ matrices, and then on a short parity argument.

Theorem (order constraint). If a Hadamard matrix of order $n$ exists, then $n \in {1, 2}$ or $4 ∣ n$ . Moreover, among all matrices $A \in {\pm 1}^{n \times n}$ the determinant satisfies $∣ det A ∣ \leq n^{n /2}$ , with equality if and only if $A$ is a Hadamard matrix ^{[Hadamard 1893]}.

Proof. For the determinant bound, let $A$ have rows $a_{1}, \dots, a_{n} \in R^{n}$ . Hadamard's inequality states $∣ det A ∣ \leq \prod_{i = 1}^{n} ∥ a_{i} ∥_{2}$ , with equality iff the rows are pairwise orthogonal (or some row is zero). A $\pm 1$ row has $∥ a_{i} ∥_{2} = n$ , so $∣ det A ∣ \leq n^{n /2}$ , and equality holds iff the rows are pairwise orthogonal, i.e. $A A^{⊤} = n I$ — exactly the Hadamard condition. This proves the characterisation.

Now suppose $H$ is Hadamard of order $n \geq 3$ . Normalise so the first row is all $+ 1$ . Orthogonality of the first row with any other row $r$ forces $\sum_{j} r_{j} = 0$ , so each subsequent row has equally many $+ 1$ and $- 1$ entries; in particular $n$ is even, $n = 2 k$ .

Take any two rows $r, s$ other than the first. Partition the columns by the sign pattern $(r_{j}, s_{j}) \in {(+, +), (+, -), (-, +), (-, -)}$ and let $a, b, c, d$ be the respective counts. Orthogonality of $r$ with the all- $+ 1$ first row gives $a + b = c + d = k$ (equal numbers of $+ 1$ and $- 1$ in $r$ ); the same for $s$ gives $a + c = b + d = k$ . Orthogonality of $r$ and $s$ gives $⟨ r, s ⟩ = a - b - c + d = 0$ . Combining $a + b = k$ , $a + c = k$ , and $a - b - c + d = 0$ yields $b = c$ and then $a = d$ and $a = b$ ; hence $a = b = c = d = k /2$ . Since $a$ is an integer, $k$ is even, so $n = 2 k$ is divisible by $4$ . The small cases $n = 1$ ( $H = (1)$ ) and $n = 2$ (the matrix $H_{2}$ ) escape the three-row argument. $□$

Bridge. This theorem builds toward every existence construction in the chapter: the determinant characterisation says a Hadamard matrix is the extremal point of the $\pm 1$ determinant problem, so each construction is a recipe for hitting that extremum. The foundational reason the order is divisible by $4$ is the three-row counting identity $a = b = c = d$ , which is exactly the statement that any three rows of a normalised Hadamard matrix induce a balanced incidence pattern — this is the seed of the symmetric design appearing again in the Advanced results, where the rows-minus-first become the blocks of a $2 - (4 m - 1, 2 m - 1, m - 1)$ design. The argument generalises: replacing $\pm 1$ orthogonality by the quadratic-residue character gives the Paley construction, and the bridge is that orthogonality of $\pm 1$ vectors and the character sum $\sum_{c} χ (c) χ (c + a) = - 1$ are the same balancing phenomenon read in two alphabets, ${\pm 1}$ and $F_{q}$ . Putting these together, the order constraint and the constructions are dual faces of one extremal problem.

Exercises Intermediate+

Exercise 3 (medium, symbolic).

Prove that if $H_{1}$ and $H_{2}$ are Hadamard matrices of orders $m$ and $n$ , then the Kronecker product $H_{1} \otimes H_{2}$ is a Hadamard matrix of order $mn$ .

Hint

Use $(A \otimes B) (C \otimes D) = (A C) \otimes (B D)$ and $(A \otimes B)^{⊤} = A^{⊤} \otimes B^{⊤}$ . Entries of a Kronecker product of $\pm 1$ matrices are products of $\pm 1$ entries.

Answer

Each entry of $H_{1} \otimes H_{2}$ is a product $(H_{1})_{ij} (H_{2})_{k l} \in {\pm 1}$ , so $H_{1} \otimes H_{2} \in {\pm 1}^{mn \times mn}$ . Using the mixed-product rule and transpose rule, $$ (H_1 \otimes H_2)(H_1 \otimes H_2)^\top = (H_1 \otimes H_2)(H_1^\top \otimes H_2^\top) = (H_1 H_1^\top) \otimes (H_2 H_2^\top) = (m I_m) \otimes (n I_n) = mn, I_{mn}. $$ Hence $H_{1} \otimes H_{2}$ satisfies the Hadamard relation in order $mn$ . Taking $H_{1} = H_{2} = H_{2}$ (the order- $2$ matrix) recovers Sylvester doubling. Rubric: full credit for the mixed-product identity and the conclusion $mn I$ .

Exercise 4 (medium, symbolic).

Let $χ$ be the quadratic-residue character of $F_{q}$ ( $q$ odd). Prove $\sum_{c \in F_{q}} χ (c) = 0$ and, for $a \neq = 0$ , $\sum_{c \in F_{q}} χ (c) χ (c + a) = - 1$ .

Hint

For the first sum, there are equally many nonzero squares and non-squares. For the second, factor $χ (c) χ (c + a) = χ (c^{2}) χ (1 + a c^{- 1})$ on $c \neq = 0$ using multiplicativity, then substitute $t = a c^{- 1}$ .

Answer

The nonzero elements of $F_{q}$ split into $(q - 1) /2$ squares ( $χ = + 1$ ) and $(q - 1) /2$ non-squares ( $χ = - 1$ ), and $χ (0) = 0$ , so $\sum_{c} χ (c) = 0$ .

For the second sum, the $c = 0$ term vanishes. For $c \neq = 0$ , write $χ (c) χ (c + a) = χ (c (c + a)) = χ (c^{2} (1 + a c^{- 1})) = χ (c^{2}) χ (1 + a c^{- 1}) = χ (1 + a c^{- 1})$ , since $χ (c^{2}) = 1$ . As $c$ ranges over $F_{q}^{\times}$ , the quantity $t = a c^{- 1}$ ranges over $F_{q}^{\times}$ as well, and $1 + t$ ranges over $F_{q} ∖ {1}$ . Thus $$ \sum_{c \neq 0} \chi(c)\chi(c+a) = \sum_{u \neq 1} \chi(u) = \Big(\sum_{u \in \mathbb{F}_q}\chi(u)\Big) - \chi(1) = 0 - 1 = -1. $$ Rubric: full credit for the multiplicativity step, the change of variable, and isolating $χ (1) = 1$ .

Exercise 5 (medium, symbolic).

Using Exercise 4, show the Jacobsthal matrix $Q = (χ (a - b))$ over $F_{q}$ satisfies $Q Q^{⊤} = q I - J$ and $Q J = J Q = 0$ .

Hint

The $(a, b)$ entry of $Q Q^{⊤}$ is $\sum_{c} χ (a - c) χ (b - c)$ . Substitute and split into the diagonal ( $a = b$ ) and off-diagonal ( $a \neq = b$ ) cases. For $Q J$ , use $\sum_{c} χ (c) = 0$ .

Answer

The $(a, b)$ entry of $Q Q^{⊤}$ is $\sum_{c} χ (a - c) χ (b - c)$ . Put $u = a - c$ ; as $c$ runs over $F_{q}$ so does $u$ , and $b - c = u + (b - a)$ . Hence the entry equals $\sum_{u} χ (u) χ (u + (b - a))$ . If $a = b$ this is $\sum_{u} χ (u)^{2} = q - 1$ (every nonzero $u$ contributes $1$ , and $χ (0)^{2} = 0$ ). If $a \neq = b$ , Exercise 4 gives $- 1$ . Therefore $Q Q^{⊤} = (q - 1) I - (J - I) = q I - J$ .

For $Q J$ : the $(a, \cdot)$ row-sum is $\sum_{b} χ (a - b) = \sum_{u} χ (u) = 0$ , so $Q J = 0$ ; symmetrically $J Q = 0$ . Rubric: full credit for the substitution and both cases of the character sum.

Exercise 7 (hard, symbolic).

Paley type I: for $q \equiv 3 (mod 4)$ , set $H = I_{q + 1} + S$ where $S$ is the $(q + 1) \times (q + 1)$ matrix $$ S = \begin{pmatrix} 0 & \mathbf{1}^\top \ -\mathbf{1} & Q \end{pmatrix}, $$ with $Q$ the Jacobsthal matrix. Prove $H$ is a Hadamard matrix of order $q + 1$ .

Hint

For $q \equiv 3 (mod 4)$ , $Q$ is skew, so $S^{⊤} = - S$ . Compute $S S^{⊤} = - S^{2}$ using $Q Q^{⊤} = q I - J$ , $Q J = 0$ , and $Q 1 = 0$ . Then $H H^{⊤} = (I + S) (I - S) = I - S^{2}$ .

Answer

Entries of $H = I + S$ are $\pm 1$ : the diagonal is $+ 1$ , the first row/column off-diagonal entries are $\pm 1$ , and the $Q$ -block has $\pm 1$ off its diagonal with $+ 1$ on the diagonal from the added $I$ . Since $q \equiv 3 (mod 4)$ , $χ (- 1) = - 1$ so $Q^{⊤} = - Q$ , hence $S^{⊤} = - S$ (the corner is $0$ , and the off-diagonal $\pm 1$ blocks swap sign under transpose). Then $$ HH^\top = (I + S)(I + S)^\top = (I+S)(I - S) = I - S^2 = I + S S^\top. $$ Compute $S S^{⊤}$ blockwise. The top-left entry is $1^{⊤} 1 = q$ . The top-right is $1^{⊤} Q^{⊤} = (Q 1)^{⊤} = 0$ since each row of $Q$ sums to $0$ . The bottom-left is likewise $0$ . The bottom-right is $1 1^{⊤} + Q Q^{⊤} = J + (q I - J) = q I$ . Hence $S S^{⊤} = q I_{q + 1}$ , and $H H^{⊤} = I + q I = (q + 1) I$ . So $H$ is Hadamard of order $q + 1$ . Rubric: full credit for the skew property, the block computation of $S S^{⊤}$ , and the conclusion.

Exercise 8 (hard, symbolic).

Let $H$ be a normalised Hadamard matrix of order $4 m$ . Delete its first row and first column, replace $+ 1$ by $0$ and $- 1$ by $1$ in the remaining $(4 m - 1) \times (4 m - 1)$ matrix, and call the result $N$ . Prove that $N$ is the incidence matrix of a symmetric $2 - (4 m - 1, 2 m - 1, m - 1)$ design.

Hint

After normalising, each non-first row has $2 m$ entries $+ 1$ and $2 m$ entries $- 1$ , one of which (the first column) is removed. Two non-first rows agree in $2 m$ columns. Translate "agree/disagree" between $\pm 1$ rows into "common $1$ 's" of the $0/1$ rows of $N$ .

Answer

Normalisation makes the first column all $+ 1$ . A non-first row $r$ is orthogonal to the all- $+ 1$ first row, so it has exactly $2 m$ entries $+ 1$ and $2 m$ entries $- 1$ ; removing the first-column $+ 1$ leaves $2 m - 1$ entries $+ 1$ and $2 m$ entries $- 1$ among the remaining $4 m - 1$ columns. Under $+ 1 \mapsto 0$ , $- 1 \mapsto 1$ , each row of $N$ has exactly $2 m$ ones, but we instead read blocks as the $1$ -positions: each of the $4 m - 1$ rows of $N$ has $2 m - 1$ zeros becoming... more cleanly, set $b_{r} = {j : H_{r j} = - 1, j \neq = 1}$ , so $∣ b_{r} ∣ = 2 m$ ; this is the standard convention giving block size $k = 2 m - 1$ after the symmetric complement. Two distinct non-first rows $r, s$ are orthogonal, so among the $4 m$ columns they agree in $2 m$ and disagree in $2 m$ ; restricting to the $4 m - 1$ non-first columns and counting positions where both are $- 1$ gives $m - 1$ (from $a = b = c = d = m$ in the three-row identity, minus the first-column contribution). Hence any two blocks meet in $λ = m - 1$ points, every block has $k = 2 m - 1$ points, and there are $v = 4 m - 1$ points and blocks: a symmetric $2 - (4 m - 1, 2 m - 1, m - 1)$ design. Rubric: full credit for the row-balance count, the pairwise-intersection count $λ = m - 1$ , and identifying the symmetric design parameters.

Advanced results Master

The order theorem and the two constructions situate Hadamard matrices inside design theory, coding theory, and an unresolved existence problem. The results below trace those threads.

Theorem 1 (Sylvester-Kronecker family). The map $H \mapsto H \otimes H_{2}$ , equivalently $H \mapsto \begin{psmallmatrix} H & H \\ H & -H \end{psmallmatrix}$ , sends a Hadamard matrix of order $n$ to one of order $2 n$ . Iterated from the seed $H_{1} = (1)$ it produces a Hadamard matrix $H_{2^{k}}$ of every order $2^{k}$ ; the rows of $H_{2^{k}}$ , indexed by ${0, 1}^{k}$ , are the Walsh functions $w_{x} (y) = (- 1)^{⟨ x, y ⟩}$ , and the linear map they define is the Walsh-Hadamard transform ^{[Sylvester 1867]}.

Theorem 2 (Paley constructions). Let $q$ be an odd prime power and $Q$ the Jacobsthal matrix over $F_{q}$ , with $Q Q^{⊤} = q I - J$ , $Q J = 0$ , $Q^{⊤} = χ (- 1) Q$ ^{[Paley 1933]}.

Type I ( $q \equiv 3 (mod 4)$ , so $Q$ skew): $H = I_{q + 1} + (0 - 1 1^{⊤} Q)$ is a Hadamard matrix of order $q + 1$ .
Type II ( $q \equiv 1 (mod 4)$ , so $Q$ symmetric): the bordered matrix $C = (01 1^{⊤} Q)$ is a symmetric conference matrix of order $q + 1$ with $C C^{⊤} = q I$ ; substituting $(11 1 - 1)$ for each $+ 1$ , $(- 1 1 11)$ for each $- 1$ , and $(1001)$ -type blocks for the zero diagonal yields a Hadamard matrix of order $2 (q + 1)$ .

Together the Sylvester and Paley families realise every order $4 m \leq 100$ except $4 m = 92$ (first settled by Baumert-Golomb-Hall 1962 via a Williamson search), and infinitely many others.

Theorem 3 (Hadamard matrices $\leftrightarrow$ symmetric designs). Normalised Hadamard matrices of order $4 m$ are in bijection (up to equivalence) with symmetric $2 - (4 m - 1, 2 m - 1, m - 1)$ designs, the Hadamard designs: deleting the first row and column and sending $+ 1 \mapsto 0$ , $- 1 \mapsto 1$ gives the incidence matrix of such a design, and the construction reverses. The complementary parameters $2 - (4 m - 1, 2 m, m)$ arise from the opposite sign convention ^{[Hall Ch. 14]}.

Theorem 4 (Hadamard 3-design). From a Hadamard matrix $H$ of order $n = 4 m$ , take the $2 n$ vectors $\pm (rows of H)$ ; the supports of agreement partition the columns so that the $n$ columns, with the blocks ${j : (row r)_{j} = (row s)_{j}}$ , form a $3 - (4 m, 2 m, m - 1)$ design. Hadamard matrices are thus a source of $3$ -designs, rare among elementary constructions, and the only $3$ -designs with $λ$ this small for general $m$ .

Theorem 5 (the Hadamard code). The rows of an order- $n$ Hadamard matrix and their negatives form a binary code of length $n$ with $2 n$ codewords, every two distinct codewords at Hamming distance $n /2$ (or $n$ for a word and its negative): a $[n, lo g_{2} (2 n), n /2]$ code meeting the Plotkin bound. The order- $32$ Paley-Hadamard code was used by the Mariner 9 spacecraft (1971) to transmit images of Mars, correcting up to $7$ bit errors per $32$ -bit word. The first-order Reed-Muller code $RM (1, k)$ is exactly the Sylvester-Hadamard code of length $2^{k}$ ^{[van Lint-Wilson Ch. 18]}.

Theorem 6 (the Hadamard conjecture and asymptotics). It is conjectured that a Hadamard matrix exists for every order $n \equiv 0 (mod 4)$ . The smallest order in doubt has steadily fallen; as of the 2000s every multiple of $4$ below $668$ is realised. Asymptotically, de Launey and Gérard-Levavasseur-type results, and the Seberry construction, show a Hadamard matrix of order $n$ exists whenever $n$ is a multiple of $2^{t}$ with $t$ growing like $lo g_{2} n$ ; combined with Paley orders $q + 1$ this gives density- $1$ realisation. The Bruck-Ryser-Chowla theorem supplies the only known nonexistence obstruction at the level of symmetric designs, and it never rules out a genuine multiple of $4$ — consistent with the conjecture.

Synthesis. Putting these threads together, the Hadamard matrix is the foundational reason three subjects share one combinatorial core: the orthogonality $H H^{⊤} = n I$ is exactly the extremal condition of Hadamard's determinant problem, is exactly the balanced-incidence condition of a symmetric $2 - (4 m - 1, 2 m - 1, m - 1)$ design, and is exactly the equidistant condition of a code meeting the Plotkin bound. This is the central insight of the design-coding-graph triangle: a single $\pm 1$ array, depending on which structure one reads off its rows, becomes an extremal determinant, a symmetric design with its strongly regular point graph, or an optimal code. The Paley construction generalises the elementary Sylvester doubling by trading the alphabet ${\pm 1}$ for the field $F_{q}$ , where the character identity $\sum_{c} χ (c) χ (c + a) = - 1$ plays the role orthogonality played for $\pm 1$ rows; the two are dual realisations of one balancing law. The bridge from the order theorem to existence is the Hadamard conjecture, which asserts that the necessary divisibility $4 ∣ n$ is also sufficient — that the extremal determinant is always attained — and which the Sylvester, Paley, and Williamson families establish for an asymptotic density of orders without yet closing the gap.

Full proof set Master

Proposition 1 (Hadamard's determinant inequality and its equality case). For $A \in R^{n \times n}$ with rows $a_{1}, \dots, a_{n}$ , $∣ det A ∣ \leq \prod_{i = 1}^{n} ∥ a_{i} ∥_{2}$ , with equality iff the rows are pairwise orthogonal or some $a_{i} = 0$ . Consequently $∣ det A ∣ \leq n^{n /2}$ for $A \in {\pm 1}^{n \times n}$ , with equality iff $A$ is Hadamard.

Proof. If some $a_{i} = 0$ both sides vanish. Otherwise apply Gram-Schmidt to $a_{1}, \dots, a_{n}$ , obtaining orthogonal $b_{1}, \dots, b_{n}$ with $a_{i} = b_{i} + \sum_{j < i} c_{ij} b_{j}$ ; the change of basis is unipotent upper-triangular, so $det A = det B = \prod_{i} ∥ b_{i} ∥$ (taking $B$ the matrix of rows $b_{i}$ , orthogonal hence $∣ det B ∣ = \prod ∥ b_{i} ∥$ ). Since $b_{i}$ is the component of $a_{i}$ orthogonal to $span (a_{1}, \dots, a_{i - 1})$ , $∥ b_{i} ∥ \leq ∥ a_{i} ∥$ , with equality iff $a_{i} ⊥ a_{j}$ for all $j < i$ . Multiplying, $∣ det A ∣ = \prod ∥ b_{i} ∥ \leq \prod ∥ a_{i} ∥$ , equality iff all rows are pairwise orthogonal. For $\pm 1$ entries $∥ a_{i} ∥ = n$ , giving $n^{n /2}$ , attained iff $A A^{⊤} = n I$ . $□$

Proposition 2 (order divisibility). A Hadamard matrix of order $n > 2$ has $4 ∣ n$ .

Proof. Normalise the first row to all $+ 1$ . Orthogonality with row $i \neq = 1$ forces the row sum to vanish, so $n$ is even, $n = 2 k$ . Take rows $r, s \neq = 1$ and let $a, b, c, d$ count columns with sign patterns $(+, +), (+, -), (-, +), (-, -)$ . From row sums: $a + b = c + d$ and $a + c = b + d$ , each equal to $k$ . From $⟨ r, s ⟩ = 0$ : $a - b - c + d = 0$ . Solving, $b = c$ , $a = d$ , and $a + b = k$ together with $a - b - c + d = 2 a - 2 b = 0$ give $a = b$ , hence $a = b = c = d = k /2$ . As $a \in Z$ , $k$ is even and $4 ∣ n$ . $□$

Proposition 3 (Paley type I gives order $q + 1$ ). For an odd prime power $q \equiv 3 (mod 4)$ , the matrix $H = I_{q + 1} + (0 - 1 1^{⊤} Q)$ is Hadamard.

Proof. By the character sums, $Q Q^{⊤} = q I - J$ , $Q 1 = 0$ , $1^{⊤} Q = 0$ , and $Q^{⊤} = χ (- 1) Q = - Q$ since $χ (- 1) = (- 1)^{(q - 1) /2} = - 1$ for $q \equiv 3 (mod 4)$ . Write $S = (0 - 1 1^{⊤} Q)$ ; then $S^{⊤} = (01 - 1^{⊤} Q^{⊤}) = (01 - 1^{⊤} - Q) = - S$ , so $S$ is skew and $H = I + S$ has $\pm 1$ entries (diagonal $+ 1$ ; off-diagonal $\pm 1$ ). Then $$ SS^\top = \begin{pmatrix} \mathbf 1^\top \mathbf 1 & \mathbf 1^\top Q^\top \ Q^\top{}^\top!!\cdots \end{pmatrix} $$ computed blockwise: top-left $1^{⊤} 1 = q$ ; top-right $1^{⊤} Q^{⊤} = (Q 1)^{⊤} = 0$ ; bottom-left $- 1 (0) + Q (- 1)^{⊤}$ ... directly, the bottom-right block is $(- 1) (- 1)^{⊤} + Q Q^{⊤} = J + (q I - J) = q I$ , and the cross blocks vanish because $Q 1 = 0$ . Hence $S S^{⊤} = q I_{q + 1}$ . Finally $H H^{⊤} = (I + S) (I - S) = I - S^{2} = I + S S^{⊤} = (q + 1) I$ . $□$

Proposition 4 (Paley conference matrix, type II). For $q \equiv 1 (mod 4)$ , $C = (01 1^{⊤} Q)$ is a symmetric conference matrix: $C^{⊤} = C$ and $C C^{⊤} = q I_{q + 1}$ .

Proof. Here $χ (- 1) = + 1$ , so $Q^{⊤} = Q$ and $C^{⊤} = C$ . The diagonal of $C$ is $0$ (the corner, and $Q$ 's diagonal $χ (0) = 0$ ), off-diagonal entries are $\pm 1$ . Blockwise $C C^{⊤} = C^{2} = (1^{⊤} 1 Q 1 1^{⊤} Q 1 1^{⊤} + Q^{2})$ . Now $1^{⊤} 1 = q$ , $1^{⊤} Q = 0$ and $Q 1 = 0$ by the row/column sums, and $1 1^{⊤} + Q^{2} = J + Q Q^{⊤} = J + (q I - J) = q I$ . Hence $C C^{⊤} = q I_{q + 1}$ , a symmetric conference matrix. Replacing entries $0, + 1, - 1$ of $C$ by the $2 \times 2$ blocks of Theorem 2 produces $H$ with $H H^{⊤} = 2 (q + 1) I$ , a Hadamard matrix of order $2 (q + 1)$ ; the block substitution is exactly the Kronecker tensoring of $C$ against $H_{2}$ adjusted on the diagonal, and the verification is the order- $2$ analogue of Proposition 3. $□$

Proposition 5 (Hadamard matrix yields a symmetric $2$ -design). A normalised Hadamard matrix of order $4 m$ produces a symmetric $2 - (4 m - 1, 2 m - 1, m - 1)$ design.

Proof. Delete the first row and column; in the remaining $(4 m - 1) \times (4 m - 1)$ matrix $M$ each row has, by Proposition 2's count restricted to non-first columns, exactly $2 m - 1$ entries equal to $- 1$ (taking $- 1$ as incidence). Any two rows agree in $2 m$ of the $4 m$ columns; removing the first column (where both are $+ 1$ ) leaves agreement in $2 m - 1$ columns, of which the number where both equal $- 1$ is, from $a = b = c = d = m$ in the three-row identity, exactly $m - 1$ . Thus the $- 1$ -supports form blocks of size $k = 2 m - 1$ on $v = 4 m - 1$ points, any two blocks meeting in $λ = m - 1$ points; dually any two points lie in $m - 1$ common blocks. This is a symmetric $2 - (4 m - 1, 2 m - 1, m - 1)$ design. The reverse map sends such a design's incidence matrix $N$ to the bordered $\pm 1$ matrix $(1^{⊤} 1 J - 2 N)$ , which is Hadamard, establishing the bijection. $□$

Connections Master

Finite fields $F_{q}$ and their squares 21.02.01. The Paley construction is an application of the structure of $F_{q}^{\times}$ as a cyclic group of even order: the quadratic-residue character $χ$ is the unique order- $2$ multiplicative character, and the count of nonzero squares as $(q - 1) /2$ is precisely the input that makes $\sum_{c} χ (c) = 0$ and the Jacobsthal identity $Q Q^{⊤} = q I - J$ hold. The foundational reason Paley orders $q + 1$ exist is that finite fields supply, for free, a set of size $q$ with a perfectly balanced quadratic character — the field's arithmetic is what manufactures the combinatorial balance.
Quadratic residues and the Legendre symbol 21.01.06. The character $χ$ is the Legendre symbol $(\frac{\cdot}{p})$ when $q = p$ is prime, and its value $χ (- 1) = (- 1)^{(q - 1) /2}$ — a consequence of quadratic reciprocity's supplementary law — is exactly what decides whether the Jacobsthal matrix is skew ( $q \equiv 3$ ) or symmetric ( $q \equiv 1$ ), and hence whether the Paley construction is type I (order $q + 1$ ) or type II (order $2 (q + 1)$ ). The residue class of $q$ modulo $4$ , a number-theoretic datum, dictates the combinatorial output.
Balanced incomplete block designs and symmetric 2-designs 40.06.01. Hadamard matrices of order $4 m$ are the same data as symmetric $2 - (4 m - 1, 2 m - 1, m - 1)$ designs (Proposition 5), the densest family of symmetric BIBDs; the Bruck-Ryser-Chowla nonexistence test for symmetric designs is the design-theoretic shadow of the Hadamard order constraint, and the point graph of a Hadamard design is strongly regular, tying this unit to the design-coding-graph triangle developed alongside.
Linear codes and the Singleton/Plotkin bounds 40.06.06. The Hadamard code — rows and their negatives — is the canonical code meeting the Plotkin bound, and the Sylvester-Hadamard code of length $2^{k}$ is literally the first-order Reed-Muller code $RM (1, k)$ ; the orthogonality $H H^{⊤} = n I$ is the equidistance that the coding-theoretic bound extremises, so the same matrix that solves the determinant problem also solves the optimal-distance problem.

Historical & philosophical context Master

The determinant inequality came first. In 1893 Jacques Hadamard ^{[Hadamard 1893]} asked how large the determinant of a matrix with bounded entries can be and proved $∣ det A ∣ \leq \prod_{i} ∥ a_{i} ∥$ , observing that for $\pm 1$ entries the bound $n^{n /2}$ is met exactly when the rows are orthogonal — the matrices that now bear his name. The orthogonal $\pm 1$ arrays themselves were older: James Joseph Sylvester had introduced the doubling construction in 1867 ^{[Sylvester 1867]}, under the heading of "tessellated pavements" and "sign-successions," producing the order- $2^{k}$ family and noting their use in what would become signal analysis.

The decisive generalisation is due to Raymond Paley, whose 1933 paper On orthogonal matrices ^{[Paley 1933]} built Hadamard matrices from the quadratic-residue character of a finite field, splitting into the type I and type II constructions according to $q mod 4$ and realising many orders beyond the powers of $2$ . Paley conjectured that a Hadamard matrix exists for every order divisible by $4$ ; he died in an avalanche later that year at age $26$ , and the conjecture remains open. The design-theoretic equivalence was systematised by Marshall Hall and others ^{[Hall Ch. 14]}, linking Hadamard matrices to symmetric $2$ -designs and thereby to the Bruck-Ryser-Chowla obstruction, while the modern existence record rests on the Williamson construction and the Baumert-Golomb-Hall settlement of order $92$ in 1962. The textbook consolidation followed by van Lint and Wilson places the whole theory in the combinatorics of designs and codes ^{[van Lint-Wilson Ch. 18]}.

Bibliography Master

@article{hadamard1893determinants,
  author  = {Hadamard, Jacques},
  title   = {R\'{e}solution d'une question relative aux d\'{e}terminants},
  journal = {Bulletin des Sciences Math\'{e}matiques (2)},
  volume  = {17},
  pages   = {240--246},
  year    = {1893}
}

@article{sylvester1867tessellated,
  author  = {Sylvester, James Joseph},
  title   = {Thoughts on inverse orthogonal matrices, simultaneous sign-successions, and tessellated pavements in two or more colours},
  journal = {Philosophical Magazine (4)},
  volume  = {34},
  pages   = {461--475},
  year    = {1867}
}

@article{paley1933orthogonal,
  author  = {Paley, Raymond E. A. C.},
  title   = {On orthogonal matrices},
  journal = {Journal of Mathematics and Physics},
  volume  = {12},
  pages   = {311--320},
  year    = {1933}
}

@article{williamson1944hadamard,
  author  = {Williamson, John},
  title   = {Hadamard's determinant theorem and the sum of four squares},
  journal = {Duke Mathematical Journal},
  volume  = {11},
  pages   = {65--81},
  year    = {1944}
}

@article{baumert1962discovery,
  author  = {Baumert, Leonard and Golomb, Solomon W. and Hall, Marshall},
  title   = {Discovery of an Hadamard matrix of order 92},
  journal = {Bulletin of the American Mathematical Society},
  volume  = {68},
  pages   = {237--238},
  year    = {1962}
}

@book{vanlintwilson2001course,
  author    = {van Lint, J. H. and Wilson, R. M.},
  title     = {A Course in Combinatorics},
  edition   = {2},
  publisher = {Cambridge University Press},
  year      = {2001}
}

@book{hall1986combinatorial,
  author    = {Hall, Marshall},
  title     = {Combinatorial Theory},
  edition   = {2},
  publisher = {Wiley},
  year      = {1986}
}

@book{agayan1985hadamard,
  author    = {Agaian, Sos S.},
  title     = {Hadamard Matrices and Their Applications},
  series    = {Lecture Notes in Mathematics},
  volume    = {1168},
  publisher = {Springer},
  year      = {1985}
}

Prerequisites

none — this is a leaf unit

Tier anchors

beginner: van Lint-Wilson 2001 *A Course in Combinatorics* 2e (Cambridge) Ch. 18 (orthogonal ±1 matrices, the Sylvester doubling construction by hand); 3Blue1Brown / Mathologer style 'why ±1 vectors that disagree half the time' for the orthogonality picture
intermediate: van Lint-Wilson 2001 *A Course in Combinatorics* 2e (Cambridge) Ch. 18 (Hadamard matrices, the order constraint, normalisation, the Paley construction from quadratic residues); Hall 1986 *Combinatorial Theory* 2e (Wiley) Ch. 14
master: van Lint-Wilson 2001 *A Course in Combinatorics* 2e Ch. 18-19 (Hadamard matrices and 2-designs, conference matrices, the Paley constructions of types I and II); Hall 1986 *Combinatorial Theory* 2e Ch. 14; Hadamard 1893 *Bull. Sci. Math.* (2) 17 (the determinant inequality); Paley 1933 *J. Math. Phys.* 12 (the quadratic-residue construction); Sylvester 1867 *Phil. Mag.* (4) 34 (the doubling/tessellation construction); Bruck-Ryser-Chowla as the design-theoretic obstruction

References

van Lint, J. H. & Wilson, R. M. — A Course in Combinatorics · Cambridge University Press, 2nd edition (2001). Chapter 18 develops Hadamard matrices: the defining relation $HH^\top = nI$, Hadamard's determinant inequality and its equality case, the order divisibility ($n = 1, 2$, or $4 \mid n$), equivalence and normalisation, the Kronecker/Sylvester product giving orders $2^k$, the Paley construction from the quadratic-residue character over $\mathbb{F}_q$ (type I for $q \equiv 3 \pmod 4$, type II via conference matrices for $q \equiv 1 \pmod 4$), and the equivalence with Hadamard 2-designs / symmetric $2\text{-}(4m-1, 2m-1, m-1)$ designs.
Hadamard, J. — Résolution d'une question relative aux déterminants · *Bulletin des Sciences Mathématiques* (2) 17 (1893), 240-246. The inequality $|\det A| \leq \prod_i \|a_i\|$ for a real matrix with rows $a_i$, with equality iff the rows are mutually orthogonal; specialised to $\pm 1$ entries it gives $|\det H| \leq n^{n/2}$ with equality exactly for Hadamard matrices.
Paley, R. E. A. C. — On orthogonal matrices · *Journal of Mathematics and Physics* 12 (1933), 311-320. The construction of Hadamard matrices from the Legendre/quadratic-residue character $\chi$ of a finite field $\mathbb{F}_q$: the Jacobsthal matrix $Q = (\chi(a-b))_{a,b}$, the conference matrix it builds, and the resulting Hadamard matrices of order $q+1$ ($q \equiv 3 \bmod 4$) and $2(q+1)$ ($q \equiv 1 \bmod 4$).
Sylvester, J. J. — Thoughts on inverse orthogonal matrices, simultaneous sign-successions, and tessellated pavements · *Philosophical Magazine* (4) 34 (1867), 461-475. The doubling construction $H \mapsto \begin{psmallmatrix} H & H \\ H & -H \end{psmallmatrix}$ producing Hadamard matrices of every order $2^k$ from the $1 \times 1$ seed.
Hall, M. — Combinatorial Theory · Wiley, 2nd edition (1986). Chapter 14 treats Hadamard matrices, their normalisation and equivalence, the connection to symmetric 2-designs and the Hadamard 3-designs, and the Paley and Williamson constructions.

Estimated time

beginner: 18m
intermediate: 45m
master: 85m