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.

About these ads

Hadamard matrices, maximal determinants

November 17, 2012

2 Comments