Difference between revisions of "Williamson matrices"
(Importing text file) |
Ulf Rehmann (talk | contribs) m (MR/ZBL numbers added) |
||
Line 34: | Line 34: | ||
====References==== | ====References==== | ||
− | <table><TR><TD valign="top">[a1]</TD> <TD valign="top"> | + | <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 <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 {{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> |
Revision as of 17:35, 31 March 2012
A Hadamard matrix of order is an
-matrix
with as entries
and
such that
, where
is the transposed matrix of
and
is the unit matrix of order
. Note that the problem of constructing Hadamard matrices of all orders
is as yet unsolved (1998; the first open case is
). 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
,
,
, and
be pairwise commuting symmetric circulant
-matrices of order
such that
(such matrices are called Williamson matrices). Then the Williamson array
![]() |
is a Hadamard matrix of order . 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
-matrices
,
, of order
that satisfy the following conditions:
i) ,
;
ii) . Williamson-four matrices have been constructed for all orders
, with the exception of
, 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
are not yet known (1998). Williamson-four and Williamson-type-four matrices are known for many values of
. 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 , where
,
are prime numbers [a8].
A set of -matrices
is called a Williamson family, of type
, if the following conditions are fulfilled:
a) There exists a -matrix
of order
such that for arbitrary
,
;
b) . If
, then the type
is denoted by
.
If ,
, and
, then each Williamson family of type
coincides with a family of Williamson-type matrices.
If ,
for
, and
, then each Williamson family of type
coincides with a family of Williamson-type-eight matrices.
If ,
, and
,
,
![]() |
and , then each Williamson family of type
coincides with a family of generalized Williamson-type matrices.
An orthogonal design of order and type
(
) on commuting variables
is an
-matrix
with entries from
such that
![]() |
Let be a Williamson family of type
and suppose there exists an orthogonal design of type
and order
that consists of elements
,
. Then there exists a Hadamard matrix of order
. 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 ![]() ![]() |
[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 |
Williamson matrices. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Williamson_matrices&oldid=11318