Williamson matrices

A Hadamard matrix of order $n$ is an $(n\times n)$-matrix $H$ with entries $+1$ and $-1$ such that $H{H}^T=H^{T}H=n{I}_n$, where $H^T$ is the transposed matrix of $H$ and $I_n$ is the unit matrix of order $n$. Note that the problem of constructing Hadamard matrices of all orders $n\equiv 0(\mathrm{mod}4)$ is as yet unsolved (1998; the first open case is $n=428$). For a number of methods for constructing Hadamard matrices of concrete orders, see [a1], [a9], [a7]. One of these methods, described below, is due to J. Williamson [a10]. Let $A$, $B$, $C$, and $D$ be pairwise commuting symmetric circulant $(-1,+1)$-matrices of order $m$ such that $A^2+B^2+C^2+D^2=4m{I}_m$ (such matrices are called Williamson matrices). Then the Williamson array

$$W=\left(\begin{array}{cccc}A& B& C& D\\ -B& A& -D& C\\ -C& D& A& -B\\ -D& -C& B& A\end{array}\right)$$

is a Hadamard matrix of order $4m$. The recent achievements about the construction of Hadamard matrices are connected with the construction of orthogonal designs [a4] (cf. also Design with mutually orthogonal resolutions), Baumert–Hall arrays [a2], Goethals–Seidel arrays [a5] and Plotkin arrays [a6], and with the construction of Williamson-type matrices, i.e., of four or eight $(-1,+1)$-matrices $\{A_i{\}}_{i=1}^k$, $k=4,8$, of order $m$ that satisfy the following conditions:

i) $M{N}^T=N{M}^T$, $M,N\in \{A_i{\}}_{i=1}^k$;

ii) $\sum _{i=1}^k{A}_i{A}_i^T=km{I}_m$. Williamson-four matrices have been constructed for all orders $m\le 40$, with the exception of $m=35$, which was eliminated by D.Z. Djokovic [a3], by means of an exhaustive computer search. It is worth mentioning that Williamson-type-four matrices of order $m=35$ are not yet known (1998). Williamson-four and Williamson-type-four matrices are known for many values of $m$. For details, see [a9], Table A1; pp. 543–547. The most recent results can be found in [a11].

There are known Williamson-type-eight matrices of the orders $(p+1)q/2$, where $p\equiv 1(\mathrm{mod}4)$, $q\equiv 1(\mathrm{mod}4)$ are prime numbers [a8].

A set of $(-1,+1)$-matrices $\{A_1,\dots ,A_k\}$ is called a Williamson family, of type $(s_1,\dots ,s_k,B_m)$, if the following conditions are fulfilled:

a) There exists a $(0,1)$-matrix $B_m$ of order $m$ such that for arbitrary $i,j=1,\dots ,k$, $A_i{B}_m{A}_j^T=A_j{B}_m{A}_i^T$;

b) $\sum _{i=1}^k{s}_i{A}_i{A}_i^T=(m\sum _{i=1}^k{s}_i)I_m$. If $s_1=\dots =s_k=s$, then the type $(s,\dots ,s,B_m)$ is denoted by $(s,k,B_m)$.

If $k=4$, $s_1=s_2=s_3=s_4=1$, and $B_m=I_m$, then each Williamson family of type $(1,1,1,1,I_m)=(1,4,I_m)$ coincides with a family of Williamson-type matrices.

If $k=8$, $s_i=1$ for $i=1,\dots ,8$, and $B_m=I_m$, then each Williamson family of type $(1,1,1,1,1,1,1,1,I_m)=(1,8,I_m)$ coincides with a family of Williamson-type-eight matrices.

If $k=4$, $s_1=s_2=s_3=s_4=1$, and $B_m=R$, $R=(r_{i,j}{)}_{i,j=1}^m$,

$$r_{i,j}=\{\begin{array}{ll}1,& \text{ if }i+j=m+1,\\ 0& \text{ otherwise, }\end{array}$$

and $A_i{A}_j=A_j{A}_i$, then each Williamson family of type $(1,1,1,1,R)=(1,4,R)$ coincides with a family of generalized Williamson-type matrices.

An orthogonal design of order $n$ and type $(s_1,\dots ,s_k)$ ($s_i>0$) on commuting variables $x_1,\dots ,x_k$ is an $(n\times n)$-matrix $A$ with entries from $\{0,\pm x_1,\dots ,\pm x_k\}$ such that

$$A{A}^T=A^{T}A=\left(\sum _{i=1}^k{s}_i{x}_i^2\right)I_n.$$

Let $\{A_1,\dots ,A_k\}$ be a Williamson family of type $(s_1,\dots ,s_k,I_m)$ and suppose there exists an orthogonal design of type $(s_1,\dots ,s_k)$ and order $n$ that consists of elements $\pm x_i$, $x_i\ne 0$. Then there exists a Hadamard matrix of order $mn$. In other words, the existence of orthogonal designs and Williamson families implies the existence of Hadamard matrices. For more details and further constructions see [a4], [a9].

References[edit]