One of the earliest Hadamard matrix constructions to be discovered is that of Umberto Scarpis.  His construction appeared in

U. Scarpis, Sui determinanti di valore massimo, Rendiconti della R. Istituto Lombardo di Scienze e Lettere 31 (1898) 1441–1446.

Scarpis’s paper followed Hadamard’s by five years. Hadamard in turn had been preceded by Sylvester, who showed that, given a $\{1,-1\}$ matrix $H$ of size $n$ with orthogonal rows, the matrix

$\begin{bmatrix}H & H\\ H & -H\end{bmatrix}=\begin{bmatrix}1 & 1\\ 1 & -1\end{bmatrix}\otimes H$

is  a $\{1,-1\}$ matrix of size 2n with orthogonal rows.  More generally, the Kronecker product $H_1\otimes H_2$ is an mn-by-mn Hadamard matrix for given Hadamard matrices $H_1$ and $H_2$ of sizes $m$ and $n$.  Using the 1-by-1 Hadamard matrix H = [1] as a starting point, Sylvester’s construction produces Hadamard matrices of size $2^k$ for every k ≥ 0.

The results from Hadamard’s paper that pertain to the present discussion are that

• {+1,−1} matrices with orthogonal rows are the only real matrices with elements of unit modulus that attain his determinant bound;
• the size of such a matrix is required to be 1, 2, or a multiple of 4;
• in addition to Sylvester’s examples, such matrices exist of sizes 12 and 20, and hence of sizes that are multiples of powers of 2, 12, and 20.

Scarpis may have been motivated by an examination of the structure of Hadamard’s 12-by-12 example.   As in Sylvester’s construction, Scarpis constructs a larger Hadamard matrix from a smaller Hadamard matrix.  Specifically, if an n-by-n Hadamard matrix can be found, where n−1 is prime, then an n(n−1)-by-n(n−1) Hadamard matrix can be constructed.  Paley later proved that for any n ≡ 0 (mod 4) with n−1 a prime (or more generally, a prime power) an n-by-n Hadamard matrix can indeed be found.  Together, the results of Scarpis and Paley produce Hadamard matrices of sizes 12, 56, 132, 380, 552, and so on.

In this post I will describe Scarpis’s construction in the form in which he originally presented it, with only minor modifications in indexing and notation.

Scarpis proceeds as follows.  The given n-by-n Hadamard matrix, H, is assumed normalized so that its first row and column consist entirely of ones, and columns are assumed to be ordered so that row 2 consists of alternating elements +1, −1, +1, −1, etc.  Let C be the core of H, obtained by removing its first row and column and let $H_2$ be the matrix that results from removing row 2 of H.  Let $p=n-1$, which is prime by assumption.

Scarpis defines row vectors $j$, $a_0$, …, $a_{p-1}$ of length $p$.  Here $j$ is the all-ones vector and $a_i$ is  row $i+1$ of $-C$.

Scarpis then defines p-by-np matrices

$M=H_2\otimes j$

and

$M_r=\begin{bmatrix} a_r & -a_0 & a_r & -a_{2r} & \cdots & a_{(p-2)r} & -a_{(p-1)r}\\ a_r & -a_1 & a_{r+1} & -a_{2r+1} & \cdots & a_{(p-2)r+1} & -a_{(p-1)r+1}\\ \vdots & \vdots & \vdots & \vdots & \ddots & \vdots & \vdots\\ a_r & -a_{p-1} & a_{r+p-1} & -a_{2r+p-1} & \cdots & a_{(p-2)r+p-1} & -a_{(p-1)r+p-1}\end{bmatrix}$

where $r\in\{0,1,\ldots,p-1\}$ and index arithmetic is performed mod p.  Scarpis’s Hadamard matrix is then

$\begin{bmatrix}M\\ M_0\\ M_1\\ \vdots\\ M_{p-1}\end{bmatrix}.$

To verify that the construction works, one must verify (1) that rows of $M$ are orthogonal, (2) that rows of $M_r$ are orthogonal, (3) that rows of $M$ are orthogonal to rows of $M_r$, and (4) that rows of $M_r$ are orthogonal to rows of $M_s$ for $r\ne s$.

1. Orthogonality of rows of $M$ follows from orthogonality of rows of $H_2$.
2. Orthogonality of rows of $M_r$ is a consequence of the relations $a_r\cdot a_r=p$ and $a_s\cdot a_t=-1$ for $s\ne t$.
3. Note that the alternation of signs in the columns of $M_r$ matches that of row 2 of $H$, which is the row omitted in the definition of $H_2$.  Hence row 2 of $H$ is orthogonal to all rows of $H_2$.  Since $j\cdot a_s=1$ for all $s$, orthogonality of any row of $M$ with any row of $M_r$ follows.
4. The inner product of row $u$ of $M_r$ with row $v$ of $M_s,$ where $r,s,u,v\in\{0,1,\ldots,p-1\}$, $r\ne s,$ is $a_r\cdot a_s+\sum_{i=0}^{p-1}a_{ir+u}\cdot a_{is+v}$.  In the summation over $i$, there is a unique $i$ for which $ir+u=is+v\pmod{p}$, namely $i=(v-u)/(r-s),$ where arithmetic is performed in $\mathbf{F}_p.$  (This is the only place where primality of $p$ is used.)  Hence the expression for the inner product contains $p$ terms equal to −1 and one term equal to $p$, yielding inner product 0.

In Paley’s famous paper on the construction of Hadamard matrices using quadratic residues in finite fields, he remarks (see Lemma 5) that an 1892-by-1892 Hadamard matrix can be constructed by applying Scarpis’s construction to the 44-by-44 Hadamard matrix obtained using Paley’s first construction, and that size 1892 (which is 44×43) cannot be obtained using the methods of Sylvester and Paley alone.  See

R. E. A. C. Paley, On orthogonal matrices, J. Mathematics and Physics 12 (1933) 311–320.

I will make one remark about Scarpis’s construction.  The matrix $M$ consists of $n$ p-by-p rank-1 submatrices.  Furthermore, the first p columns of each of the $M_r$ form a p-by-p rank-1 submatrix.  These rank-1 blocks are, in some sense, as big as rank-1 blocks in Hadamard matrices are allowed to get.  The proposition that follows contains the precise statement.

Proposition: Let

$H=\begin{bmatrix}J_{ab} & X\\Y & Z\end{bmatrix}$

be an n-by-n Hadamard matrix containing an a-by-b all-ones block $J_{ab}$.  Then $ab\le n$, and equality is equivalent to either of the following conditions.

• Every column sum of $X$ is zero.
• Every row sum of $Y$ is zero.

If a is odd and a > 1, then $(a+1)b\le n$ with equality if and only if the column sums of $X$ all equal ±1.
Proof: Let $x_1,\ldots,x_{n-b}$ denote the column sums of $X$.  Evaluate $j_a^THH^Tj_a$ in two different ways:

\begin{aligned}j_a^THH^Tj_a&=\left\lvert\begin{bmatrix}a & \ldots a & x_1 & \ldots & x_{n-b}\end{bmatrix}\right\rvert^2=ba^2+x_1^2+\ldots+x_{n-b}^2\\ &=j_a^TnIj_a=na.\end{aligned}

Hence $ba^2\le na,$ or $ab\le n,$ with equality if and only if the column sums of $X$ are all zero.   A similar analysis of the transposed matrix $H^T$ establishes equivalence with the condition on the column sums of $Y$.

If $a$ is odd, then the column sums of $X$ have magnitude at least 1, so the inequality can be strengthened to
$ba^2+(n-b)\le na$, which implies that $(a+1)b\le n$ when $a> 1$.  Equality is equivalent to $x_j^2=1$ for all $1\le j\le n-b$.

If we restrict our attention to square (k-by-k) submatrices of Hadamard matrices of size n(n−1), where n ≡ 0 (mod 4), then k may not exceed n − 1.  Hence Scarpis’s construction contains maximal square rank-1 blocks.  Hadamard matrices containing large rank-1 blocks appear to be useful in constructing large-determinant matrices of size congruent to 1 (mod 4), and Scarpis’s Hadamard matrix of size 56 can, in fact, can be used to construct the current record-determinant matrix of size 57.  This record was first constructed by Jean-Charles Meyrignac by improving a matrix found by Bertram Felgenhauer during Lars Backstrom’s programming  contest.  Felgenhauer’s construction method is described in a post to the contest message board.