Namespaces
Variants
Actions

Difference between revisions of "Williamson matrices"

From Encyclopedia of Mathematics
Jump to: navigation, search
(Importing text file)
 
(details)
 
(6 intermediate revisions by 3 users not shown)
Line 1: Line 1:
A [[Hadamard matrix|Hadamard matrix]] of order <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/w/w120/w120210/w1202101.png" /> is an <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/w/w120/w120210/w1202102.png" />-matrix <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/w/w120/w120210/w1202103.png" /> with as entries <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/w/w120/w120210/w1202104.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/w/w120/w120210/w1202105.png" /> such that <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/w/w120/w120210/w1202106.png" />, where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/w/w120/w120210/w1202107.png" /> is the transposed matrix of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/w/w120/w120210/w1202108.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/w/w120/w120210/w1202109.png" /> is the unit matrix of order <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/w/w120/w120210/w12021010.png" />. Note that the problem of constructing Hadamard matrices of all orders <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/w/w120/w120210/w12021011.png" /> is as yet unsolved (1998; the first open case is <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/w/w120/w120210/w12021012.png" />). For a number of methods for constructing Hadamard matrices of concrete orders, see [[#References|[a1]]], [[#References|[a9]]], [[#References|[a7]]]. One of these methods, described below, is due to J. Williamson [[#References|[a10]]]. Let <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/w/w120/w120210/w12021013.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/w/w120/w120210/w12021014.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/w/w120/w120210/w12021015.png" />, and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/w/w120/w120210/w12021016.png" /> be pairwise commuting symmetric circulant <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/w/w120/w120210/w12021017.png" />-matrices of order <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/w/w120/w120210/w12021018.png" /> such that <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/w/w120/w120210/w12021019.png" /> (such matrices are called Williamson matrices). Then the Williamson array
+
<!--This article has been texified automatically. Since there was no Nroff source code for this article,
 +
the semi-automatic procedure described at https://encyclopediaofmath.org/wiki/User:Maximilian_Janisch/latexlist
 +
was used.
 +
If the TeX and formula formatting is correct and if all png images have been replaced by TeX code, please remove this message and the {{TEX|semi-auto}} category.
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/w/w120/w120210/w12021020.png" /></td> </tr></table>
+
Out of 80 formulas, 79 were replaced by TEX code.-->
  
is a Hadamard matrix of order <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/w/w120/w120210/w12021021.png" />. The recent achievements about the construction of Hadamard matrices are connected with the construction of orthogonal designs [[#References|[a4]]] (cf. also [[Design with mutually orthogonal resolutions|Design with mutually orthogonal resolutions]]), Baumert–Hall arrays [[#References|[a2]]], Goethals–Seidel arrays [[#References|[a5]]] and Plotkin arrays [[#References|[a6]]], and with the construction of Williamson-type matrices, i.e., of four or eight <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/w/w120/w120210/w12021022.png" />-matrices <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/w/w120/w120210/w12021023.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/w/w120/w120210/w12021024.png" />, of order <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/w/w120/w120210/w12021025.png" /> that satisfy the following conditions:
+
{{TEX|semi-auto}}{{TEX|part}}
 +
A [[Hadamard matrix|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 [[#References|[a1]]], [[#References|[a9]]], [[#References|[a7]]]. One of these methods, described below, is due to J. Williamson [[#References|[a10]]]. Let $A$, $B$, $C$, and $D$ be pairwise commuting symmetric [[Circulant matrix|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
  
i) <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/w/w120/w120210/w12021026.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/w/w120/w120210/w12021027.png" />;
+
\begin{equation*} W = \left( \begin{array} { c c c c } { A } &amp; { B } &amp; { C } &amp; { D } \\ { - B } &amp; { A } &amp; { - D } &amp; { C } \\ { - C } &amp; { D } &amp; { A } &amp; { - B } \\ { - D } &amp; { - C } &amp; { B } &amp; { A } \end{array} \right) \end{equation*}
  
ii) <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/w/w120/w120210/w12021028.png" />. Williamson-four matrices have been constructed for all orders <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/w/w120/w120210/w12021029.png" />, with the exception of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/w/w120/w120210/w12021030.png" />, which was eliminated by D.Z. Djokovic [[#References|[a3]]], by means of an exhaustive computer search. It is worth mentioning that Williamson-type-four matrices of order <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/w/w120/w120210/w12021031.png" /> are not yet known (1998). Williamson-four and Williamson-type-four matrices are known for many values of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/w/w120/w120210/w12021032.png" />. For details, see [[#References|[a9]]], Table A1; pp. 543–547. The most recent results can be found in [[#References|[a11]]].
+
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 [[#References|[a4]]] (cf. also [[Design with mutually orthogonal resolutions|Design with mutually orthogonal resolutions]]), Baumert–Hall arrays [[#References|[a2]]], Goethals–Seidel arrays [[#References|[a5]]] and Plotkin arrays [[#References|[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:
  
There are known Williamson-type-eight matrices of the orders <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/w/w120/w120210/w12021033.png" />, where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/w/w120/w120210/w12021034.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/w/w120/w120210/w12021035.png" /> are prime numbers [[#References|[a8]]].
+
i) $M N ^ { T } = N M ^ { T }$, $M , N \in \{ A_i \} _ { i = 1 } ^ { k }$;
  
A set of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/w/w120/w120210/w12021036.png" />-matrices <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/w/w120/w120210/w12021037.png" /> is called a Williamson family, of type <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/w/w120/w120210/w12021038.png" />, if the following conditions are fulfilled:
+
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 [[#References|[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 [[#References|[a9]]], Table A1; pp. 543–547. The most recent results can be found in [[#References|[a11]]].
  
a) There exists a <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/w/w120/w120210/w12021039.png" />-matrix <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/w/w120/w120210/w12021040.png" /> of order <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/w/w120/w120210/w12021041.png" /> such that for arbitrary <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/w/w120/w120210/w12021042.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/w/w120/w120210/w12021043.png" />;
+
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 [[#References|[a8]]].
  
b) <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/w/w120/w120210/w12021044.png" />. If <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/w/w120/w120210/w12021045.png" />, then the type <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/w/w120/w120210/w12021046.png" /> is denoted by <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/w/w120/w120210/w12021047.png" />.
+
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:
  
If <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/w/w120/w120210/w12021048.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/w/w120/w120210/w12021049.png" />, and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/w/w120/w120210/w12021050.png" />, then each Williamson family of type <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/w/w120/w120210/w12021051.png" /> coincides with a family of Williamson-type matrices.
+
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 }$;
  
If <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/w/w120/w120210/w12021052.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/w/w120/w120210/w12021053.png" /> for <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/w/w120/w120210/w12021054.png" />, and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/w/w120/w120210/w12021055.png" />, then each Williamson family of type <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/w/w120/w120210/w12021056.png" /> coincides with a family of Williamson-type-eight matrices.
+
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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/w/w120/w120210/w12021057.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/w/w120/w120210/w12021058.png" />, and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/w/w120/w120210/w12021059.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/w/w120/w120210/w12021060.png" />,
+
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.
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/w/w120/w120210/w12021061.png" /></td> </tr></table>
+
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.
  
and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/w/w120/w120210/w12021062.png" />, then each Williamson family of type <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/w/w120/w120210/w12021063.png" /> coincides with a family of generalized Williamson-type 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$,
  
An orthogonal design of order <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/w/w120/w120210/w12021064.png" /> and type <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/w/w120/w120210/w12021065.png" /> (<img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/w/w120/w120210/w12021066.png" />) on commuting variables <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/w/w120/w120210/w12021067.png" /> is an <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/w/w120/w120210/w12021068.png" />-matrix <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/w/w120/w120210/w12021069.png" /> with entries from <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/w/w120/w120210/w12021070.png" /> such that
+
\begin{equation*} r _ { i , j } = \left\{ \begin{array} { l l } { 1 , } &amp; { \text { if } i + j = m + 1, } \\ { 0 } &amp; { \text { otherwise, } } \end{array} \right. \end{equation*}
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/w/w120/w120210/w12021071.png" /></td> </tr></table>
+
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.
  
Let <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/w/w120/w120210/w12021072.png" /> be a Williamson family of type <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/w/w120/w120210/w12021073.png" /> and suppose there exists an orthogonal design of type <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/w/w120/w120210/w12021074.png" /> and order <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/w/w120/w120210/w12021075.png" /> that consists of elements <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/w/w120/w120210/w12021076.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/w/w120/w120210/w12021077.png" />. Then there exists a Hadamard matrix of order <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/w/w120/w120210/w12021078.png" />. In other words, the existence of orthogonal designs and Williamson families implies the existence of Hadamard matrices. For more details and further constructions see [[#References|[a4]]], [[#References|[a9]]].
+
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 [[#References|[a4]]], [[#References|[a9]]].
  
 
====References====
 
====References====
<table><TR><TD valign="top">[a1]</TD> <TD valign="top"> S.S. Agaian,   "Hadamard matrices and their applications" , ''Lecture Notes Math.'' , '''1168''' , Springer (1985)</TD></TR><TR><TD valign="top">[a2]</TD> <TD valign="top"> L.D. Baumert,   M. Hall Jr.,   "A new construction for Hadamard matrices" ''Bull. Amer. Math. Soc.'' , '''71''' (1965) pp. 169–170</TD></TR><TR><TD valign="top">[a3]</TD> <TD valign="top"> D.Z. Djokovic,   "Williamson matrices of order <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/w/w120/w120210/w12021079.png" /> for <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/w/w120/w120210/w12021080.png" />"  ''Discrete Math.'' , '''115''' (1993) pp. 267–271</TD></TR><TR><TD valign="top">[a4]</TD> <TD valign="top"> A.V. Geramita,   J. Seberry,   "Orthogonal designs: Quadratic forms and Hadamard matrices" , M. Dekker (1979)</TD></TR><TR><TD valign="top">[a5]</TD> <TD valign="top"> J.M. Goethals,   J.J. Seidel,   "A skew–Hadamard matrix of order 36" ''J. Austral. Math. Soc. A'' , '''11''' (1970) pp. 343–344</TD></TR><TR><TD valign="top">[a6]</TD> <TD valign="top"> M. Plotkin,   "Decomposition of Hadamard matrices" ''J. Combin. Th. A'' , '''2''' (1972) pp. 127–130</TD></TR><TR><TD valign="top">[a7]</TD> <TD valign="top"> W.D. Wallis,   A.P. Street,   J.S. Wallis,   "Combinatorics: Room squares, sum-free sets and Hadamard matrices" , ''Lecture Notes Math.'' , '''292''' , Springer (1972)</TD></TR><TR><TD valign="top">[a8]</TD> <TD valign="top"> J.S. Wallis,   "Construction of Williamson type matrices" ''Linear and Multilinear Algebra'' , '''3''' (1975) pp. 197–207</TD></TR><TR><TD valign="top">[a9]</TD> <TD valign="top"> J. Seberry,   M. Yamada,   "Hadamard matrices, sequences and block designs" J.H. Dinitz (ed.) D.R. Stinson (ed.) , ''Contemporary Design Theory: A Collection of Surveys'' , Wiley (1992) pp. 431–560</TD></TR><TR><TD valign="top">[a10]</TD> <TD valign="top"> J. Williamson,   "Hadamard's determinant theorem and the sum of four squares" ''Duke Math. J.'' , '''11''' (1944) pp. 65–81</TD></TR><TR><TD valign="top">[a11]</TD> <TD valign="top"> M.Y. Xia,   "An infinite class of supplementary difference sets and Williamson matrices" ''J. Combin. Th. A'' , '''58''' (1991) pp. 310–317</TD></TR></table>
+
<table>
 +
<tr><td valign="top">[a1]</td> <td valign="top"> S.S. Agaian, "Hadamard matrices and their applications" , ''Lecture Notes Math.'' , '''1168''' , Springer (1985) {{MR|0818740}} {{ZBL|}} </td></tr>
 +
<tr><td valign="top">[a2]</td> <td valign="top"> L.D. Baumert, M. Hall Jr., "A new construction for Hadamard matrices" ''Bull. Amer. Math. Soc.'' , '''71''' (1965) pp. 169–170 {{MR|0169860}} {{ZBL|0156.02803}} </td></tr>
 +
<tr><td valign="top">[a3]</td> <td valign="top"> D.Z. Djokovic, "Williamson matrices of order $4 n$ for $n = 33,35,39$" ''Discrete Math.'' , '''115''' (1993) pp. 267–271 {{MR|}} {{ZBL|0771.05024}} </td></tr>
 +
<tr><td valign="top">[a4]</td> <td valign="top"> A.V. Geramita, J. Seberry, "Orthogonal designs: Quadratic forms and Hadamard matrices" , M. Dekker (1979) {{MR|}} {{ZBL|0411.05023}} </td></tr>
 +
<tr><td valign="top">[a5]</td> <td valign="top"> J.M. Goethals, J.J. Seidel, "A skew–Hadamard matrix of order 36" ''J. Austral. Math. Soc. A'' , '''11''' (1970) pp. 343–344 {{MR|0269527}} {{ZBL|0226.05015}} </td></tr>
 +
<tr><td valign="top">[a6]</td> <td valign="top"> M. Plotkin, "Decomposition of Hadamard matrices" ''J. Combin. Th. A'' , '''2''' (1972) pp. 127–130 {{MR|0300914}} {{ZBL|0241.05016}} </td></tr>
 +
<tr><td valign="top">[a7]</td> <td valign="top"> W.D. Wallis, A.P. Street, J.S. Wallis, "Combinatorics: Room squares, sum-free sets and Hadamard matrices" , ''Lecture Notes Math.'' , '''292''' , Springer (1972) {{MR|0392580}} {{ZBL|}} </td></tr>
 +
<tr><td valign="top">[a8]</td> <td valign="top"> J.S. Wallis, "Construction of Williamson type matrices" ''Linear and Multilinear Algebra'' , '''3''' (1975) pp. 197–207 {{MR|0396299}} {{ZBL|0321.05021}} </td></tr>
 +
<tr><td valign="top">[a9]</td> <td valign="top"> J. Seberry, M. Yamada, "Hadamard matrices, sequences and block designs" J.H. Dinitz (ed.) D.R. Stinson (ed.) , ''Contemporary Design Theory: A Collection of Surveys'' , Wiley (1992) pp. 431–560 {{MR|1178508}} {{ZBL|0776.05028}} </td></tr>
 +
<tr><td valign="top">[a10]</td> <td valign="top"> J. Williamson, "Hadamard's determinant theorem and the sum of four squares" ''Duke Math. J.'' , '''11''' (1944) pp. 65–81</td></tr>
 +
<tr><td valign="top">[a11]</td> <td valign="top"> M.Y. Xia, "An infinite class of supplementary difference sets and Williamson matrices" ''J. Combin. Th. A'' , '''58''' (1991) pp. 310–317 {{MR|1129121}} {{ZBL|0758.05032}} </td></tr>
 +
</table>

Latest revision as of 09:35, 10 November 2023

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

[a1] S.S. Agaian, "Hadamard matrices and their applications" , Lecture Notes Math. , 1168 , Springer (1985) MR0818740
[a2] L.D. Baumert, M. Hall Jr., "A new construction for Hadamard matrices" Bull. Amer. Math. Soc. , 71 (1965) pp. 169–170 MR0169860 Zbl 0156.02803
[a3] D.Z. Djokovic, "Williamson matrices of order $4 n$ for $n = 33,35,39$" Discrete Math. , 115 (1993) pp. 267–271 Zbl 0771.05024
[a4] A.V. Geramita, J. Seberry, "Orthogonal designs: Quadratic forms and Hadamard matrices" , M. Dekker (1979) Zbl 0411.05023
[a5] J.M. Goethals, J.J. Seidel, "A skew–Hadamard matrix of order 36" J. Austral. Math. Soc. A , 11 (1970) pp. 343–344 MR0269527 Zbl 0226.05015
[a6] M. Plotkin, "Decomposition of Hadamard matrices" J. Combin. Th. A , 2 (1972) pp. 127–130 MR0300914 Zbl 0241.05016
[a7] W.D. Wallis, A.P. Street, J.S. Wallis, "Combinatorics: Room squares, sum-free sets and Hadamard matrices" , Lecture Notes Math. , 292 , Springer (1972) MR0392580
[a8] J.S. Wallis, "Construction of Williamson type matrices" Linear and Multilinear Algebra , 3 (1975) pp. 197–207 MR0396299 Zbl 0321.05021
[a9] J. Seberry, M. Yamada, "Hadamard matrices, sequences and block designs" J.H. Dinitz (ed.) D.R. Stinson (ed.) , Contemporary Design Theory: A Collection of Surveys , Wiley (1992) pp. 431–560 MR1178508 Zbl 0776.05028
[a10] J. Williamson, "Hadamard's determinant theorem and the sum of four squares" Duke Math. J. , 11 (1944) pp. 65–81
[a11] M.Y. Xia, "An infinite class of supplementary difference sets and Williamson matrices" J. Combin. Th. A , 58 (1991) pp. 310–317 MR1129121 Zbl 0758.05032
How to Cite This Entry:
Williamson matrices. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Williamson_matrices&oldid=11318
This article was adapted from an original article by C. Koukouvinos (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article