Paley's construction of Hadamard matrices from finite fields

This is Paley's 1933 construction of Hadamard matrices from finite fields (the case usually called Paley Construction I).

Let $F$ be a finite field of odd characteristic whose cardinality $q = |F|$ satisfies $q \equiv 3 \pmod 4$. Then there exists a $(q+1)\times(q+1)$ real matrix $M$ with every entry equal to $1$ or $-1$, satisfying the Hadamard orthogonality identity

Construction. Let $\chi$ denote the quadratic residue character of $F$ ($\chi(0)=0$, $\chi(a) = 1$ if $a$ is a nonzero square, $\chi(a) = -1$ otherwise). Form the bordered Jacobsthal matrix $C$, indexed by $\{\infty\} \cup F$, with $C_{\infty,\infty} = 0$, $C_{\infty,x} = 1$, $C_{x,\infty} = -1$, and $C_{x,y} = \chi(y - x)$ for $x, y \in F$. Since $q \equiv 3 \pmod 4$ forces $\chi(-1) = -1$, the matrix $C$ is skew-symmetric, and a direct character-sum computation shows $CC^{\mathsf T} = qI_{q+1}$. The matrix $M = C + I_{q+1}$ then has every entry $\pm1$ and satisfies $MM^{\mathsf T} = (q+1)I_{q+1}$.

Combined with Sylvester's doubling construction (Hadamard matrices of order $2^n$) and the Kronecker-product multiplicativity theorem for Hadamard matrices, this produces Hadamard matrices of many orders not reachable by Sylvester's construction alone — for instance $q = 11, 19, 23, 43$ give orders $12, 20, 24, 44$.

Formalization Note The statement is given in orthogonality form ($MM^{\mathsf T} = NI_N$) rather than the determinant form used elsewhere on the platform; the two are interderivable (see hadamard_det_of_orthogonal used in the Hadamard_Conjecture proof-sketch). The hypothesis ringChar F ≠ 2 (odd characteristic) is listed explicitly alongside Fintype.card F % 4 = 3, even though the latter already implies the former as integers, to keep the statement's Lean hypotheses immediately usable without a separate derivation.