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 \pmod 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 } = 4 m I _ { m }$ (such matrices are called Williamson matrices). Then the Williamson array

\begin{equation*} W = \left( \begin{array} { c c c c } { A } & { B } & { C } & { D } \\ { - B } & { A } & { - D } & { C } \\ { - C } & { D } & { A } & { - B } \\ { - D } & { - C } & { B } & { A } \end{array} \right) \end{equation*}

is a Hadamard matrix of order $4 m$. 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 } = k m I _ { m }$. Williamson-four matrices have been constructed for all orders $m \leq 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 \pmod 4 $, $q \equiv 1 \pmod 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 } = \ldots = 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$,

\begin{equation*} r _ { i , j } = \left\{ \begin{array} { l l } { 1 , } & { \text { if } i + j = m + 1, } \\ { 0 } & { \text { otherwise, } } \end{array} \right. \end{equation*}

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 } , \ldots , \pm x _ { k } \}$ such that

\begin{equation*} A A ^ { T } = A ^ { T } A = \left( \sum _ { i = 1 } ^ { k } s _ { i } x _ { i } ^ { 2 } \right) I _ { n }. \end{equation*}

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 } \neq 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]