Namespaces
Variants
Actions

Difference between revisions of "Hadamard matrix"

From Encyclopedia of Mathematics
Jump to: navigation, search
(Importing text file)
 
m (tex encoded by computer)
Line 1: Line 1:
A square matrix <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h046/h046080/h0460801.png" /> of order <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h046/h046080/h0460802.png" />, with entries <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h046/h046080/h0460803.png" /> or <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h046/h046080/h0460804.png" />, such that the equation
+
<!--
 +
h0460801.png
 +
$#A+1 = 49 n = 0
 +
$#C+1 = 49 : ~/encyclopedia/old_files/data/H046/H.0406080 Hadamard matrix
 +
Automatically converted into TeX, above some diagnostics.
 +
Please remove this comment and the {{TEX|auto}} line below,
 +
if TeX found to be correct.
 +
-->
  
<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/h/h046/h046080/h0460805.png" /></td> <td valign="top" style="width:5%;text-align:right;">(*)</td></tr></table>
+
{{TEX|auto}}
 +
{{TEX|done}}
  
holds, where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h046/h046080/h0460806.png" /> is the transposed matrix of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h046/h046080/h0460807.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h046/h046080/h0460808.png" /> is the unit matrix of order <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h046/h046080/h0460809.png" />. Equality (*) is equivalent to saying that any two rows of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h046/h046080/h04608010.png" /> are orthogonal. Hadamard matrices have been named after J. Hadamard who showed [[#References|[1]]] that the determinant <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h046/h046080/h04608011.png" /> of a matrix <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h046/h046080/h04608012.png" /> of order <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h046/h046080/h04608013.png" />, with complex entries, satisfies the Hadamard inequality
+
A square matrix $  H = \| h _ {ij} \| $
 +
of order $  n $,  
 +
with entries $  + 1 $
 +
or  $  - 1 $,  
 +
such that the 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/h/h046/h046080/h04608014.png" /></td> </tr></table>
+
$$ \tag{* }
 +
HH  ^ {T}  = n I _ {n}  $$
 +
 
 +
holds, where  $  H  ^ {T} $
 +
is the transposed matrix of  $  H $
 +
and  $  I _ {n} $
 +
is the unit matrix of order  $  n $.  
 +
Equality (*) is equivalent to saying that any two rows of  $  H $
 +
are orthogonal. Hadamard matrices have been named after J. Hadamard who showed [[#References|[1]]] that the determinant  $  | A | $
 +
of a matrix  $  A = \| a _ {ij} \| $
 +
of order  $  n $,
 +
with complex entries, satisfies the Hadamard inequality
 +
 
 +
$$
 +
| A |  ^ {2}  \leq  \prod _ { i= } 1 ^ { n }  s _ {ii} ,
 +
$$
  
 
where
 
where
  
<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/h/h046/h046080/h04608015.png" /></td> </tr></table>
+
$$
 +
s _ {ik}  = \sum _ {j = 1 } ^ { n }
 +
a _ {ij} \overline{ {a _ {kj} }}\; ,
 +
$$
 +
 
 +
and  $  \overline{ {a _ {kj} }}\; $
 +
is the element conjugate to  $  a _ {kj} $(
 +
cf. [[Hadamard theorem|Hadamard theorem]] on determinants). In particular, if  $  | a _ {ij} | \leq  M $,
 +
then  $  | A | \leq  M  ^ {n} n  ^ {n/2} $.
 +
It follows that a Hadamard matrix is a square matrix consisting of  $  \pm  1 $'
 +
s with maximal absolute value  $  n  ^ {n/2} $
 +
of the determinant. The properties of Hadamard matrices are: 1)  $  HH  ^ {T} = nI _ {n} $
 +
implies  $  H  ^ {T} H = nI _ {n} $
 +
and vice versa; 2) transposition of rows or columns and multiplication of the elements of an arbitrary row or column by  $  - 1 $
 +
again yields a Hadamard matrix; 3) the tensor product of two Hadamard matrices is also a Hadamard matrix, of order equal to the product of the orders of the factors. In other words, if  $  A = \| a _ {ij} \| $
 +
and  $  B = \| b _ {ij} \| $
 +
are Hadamard matrices of orders  $  m $
 +
and  $  n $
 +
respectively, then  $  C = \| a _ {ij} B \| $
 +
is a Hadamard matrix of order  $  mn $.  
 +
A Hadamard matrix with its first row and first column consisting only of  $  + 1 $
 +
terms is said to be normalized. The order of a Hadamard matrix is  $  n = 1, 2 $
 +
or  $  n \equiv 0 $(
 +
$  \mathop{\rm mod}  4 $).  
 +
The normalized Hadamard matrices of orders 1 and 2 are:
 +
 
 +
$$
 +
[ 1],\ \
 +
\left [
  
and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h046/h046080/h04608016.png" /> is the element conjugate to <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h046/h046080/h04608017.png" /> (cf. [[Hadamard theorem|Hadamard theorem]] on determinants). In particular, if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h046/h046080/h04608018.png" />, then <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h046/h046080/h04608019.png" />. It follows that a Hadamard matrix is a square matrix consisting of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h046/h046080/h04608020.png" />'s with maximal absolute value <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h046/h046080/h04608021.png" /> of the determinant. The properties of Hadamard matrices are: 1) <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h046/h046080/h04608022.png" /> implies <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h046/h046080/h04608023.png" /> and vice versa; 2) transposition of rows or columns and multiplication of the elements of an arbitrary row or column by <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h046/h046080/h04608024.png" /> again yields a Hadamard matrix; 3) the tensor product of two Hadamard matrices is also a Hadamard matrix, of order equal to the product of the orders of the factors. In other words, if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h046/h046080/h04608025.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h046/h046080/h04608026.png" /> are Hadamard matrices of orders <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h046/h046080/h04608027.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h046/h046080/h04608028.png" /> respectively, then <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h046/h046080/h04608029.png" /> is a Hadamard matrix of order <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h046/h046080/h04608030.png" />. A Hadamard matrix with its first row and first column consisting only of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h046/h046080/h04608031.png" /> terms is said to be normalized. The order of a Hadamard matrix is <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h046/h046080/h04608032.png" /> or <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h046/h046080/h04608033.png" /> (<img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h046/h046080/h04608034.png" />). The normalized Hadamard matrices of orders 1 and 2 are:
+
\begin{array}{cr}
 +
1 & 1 \\
 +
1  &- 1  \\
 +
\end{array}
  
<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/h/h046/h046080/h04608035.png" /></td> </tr></table>
+
\right ] .
 +
$$
  
The existence of a Hadamard matrix has been demonstrated for several classes of values of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h046/h046080/h04608036.png" /> (see, for example, [[#References|[2]]], [[#References|[3]]]). At the time of writing (the 1980s), it has not yet been proved that a Hadamard matrix exists for any <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h046/h046080/h04608037.png" /> (<img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h046/h046080/h04608038.png" />). For methods of constructing Hadamard matrices see [[#References|[2]]]. Hadamard matrices are used in the construction of certain types of block designs [[#References|[2]]] and codes [[#References|[3]]] (cf. [[Block design|Block design]]; [[Code|Code]]). A Hadamard matrix of order <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h046/h046080/h04608039.png" /> is equivalent to a <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h046/h046080/h04608040.png" />-design.
+
The existence of a Hadamard matrix has been demonstrated for several classes of values of $  n $(
 +
see, for example, [[#References|[2]]], [[#References|[3]]]). At the time of writing (the 1980s), it has not yet been proved that a Hadamard matrix exists for any $  n \equiv 0 $(
 +
$  \mathop{\rm mod}  4 $).  
 +
For methods of constructing Hadamard matrices see [[#References|[2]]]. Hadamard matrices are used in the construction of certain types of block designs [[#References|[2]]] and codes [[#References|[3]]] (cf. [[Block design|Block design]]; [[Code|Code]]). A Hadamard matrix of order $  n = 4t $
 +
is equivalent to a $  ( 4t - 1, 2t - 1, t - 1 ) $-
 +
design.
  
A generalized Hadamard matrix is a square matrix <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h046/h046080/h04608041.png" /> of order <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h046/h046080/h04608042.png" />, with as entries <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h046/h046080/h04608043.png" />-th roots of unity, which satisfies the equality
+
A generalized Hadamard matrix is a square matrix $  H ( p, h) $
 +
of order h $,  
 +
with as entries $  p $-
 +
th roots of unity, which satisfies the equality
  
<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/h/h046/h046080/h04608044.png" /></td> </tr></table>
+
$$
 +
HH  ^ {cT}  = h I _ {h} ,
 +
$$
  
where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h046/h046080/h04608045.png" /> is the conjugate transpose of the matrix <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h046/h046080/h04608046.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h046/h046080/h04608047.png" /> is the unit matrix of order <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h046/h046080/h04608048.png" />. Generalized Hadamard matrices have properties analogous to 1) and 3) (cf. [[#References|[4]]]).
+
where $  H  ^ {cT} $
 +
is the conjugate transpose of the matrix $  H $
 +
and $  I _ {h} $
 +
is the unit matrix of order h $.  
 +
Generalized Hadamard matrices have properties analogous to 1) and 3) (cf. [[#References|[4]]]).
  
 
====References====
 
====References====
 
<table><TR><TD valign="top">[1]</TD> <TD valign="top">  J. Hadamard,  "Résolution d'une question relative aux déterminants"  ''Bull. Sci. Math. (2)'' , '''17'''  (1893)  pp. 240–246</TD></TR><TR><TD valign="top">[2]</TD> <TD valign="top">  M. Hall,  "Combinatorial theory" , Blaisdell  (1967)  pp. Chapt. 14</TD></TR><TR><TD valign="top">[3]</TD> <TD valign="top">  W.W. Peterson,  "Error-correcting codes" , M.I.T. &amp; Wiley  (1961)</TD></TR><TR><TD valign="top">[4]</TD> <TD valign="top">  A.T. Butson,  "Generalized Hadamard matrices"  ''Proc. Amer. Math. Soc.'' , '''13'''  (1962)  pp. 894–898</TD></TR></table>
 
<table><TR><TD valign="top">[1]</TD> <TD valign="top">  J. Hadamard,  "Résolution d'une question relative aux déterminants"  ''Bull. Sci. Math. (2)'' , '''17'''  (1893)  pp. 240–246</TD></TR><TR><TD valign="top">[2]</TD> <TD valign="top">  M. Hall,  "Combinatorial theory" , Blaisdell  (1967)  pp. Chapt. 14</TD></TR><TR><TD valign="top">[3]</TD> <TD valign="top">  W.W. Peterson,  "Error-correcting codes" , M.I.T. &amp; Wiley  (1961)</TD></TR><TR><TD valign="top">[4]</TD> <TD valign="top">  A.T. Butson,  "Generalized Hadamard matrices"  ''Proc. Amer. Math. Soc.'' , '''13'''  (1962)  pp. 894–898</TD></TR></table>
 
 
  
 
====Comments====
 
====Comments====
Hadamard matrices are equivalent to so-called Hadamard <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h046/h046080/h04608050.png" />-designs; they are also important in statistical applications [[#References|[a6]]].
+
Hadamard matrices are equivalent to so-called Hadamard $  2 $-
 +
designs; they are also important in statistical applications [[#References|[a6]]].
  
 
====References====
 
====References====
 
<table><TR><TD valign="top">[a1]</TD> <TD valign="top">  W.D. Wallis,  A.P. Street,  J.S. Wallis,  "Combinatorics: room squares, sum-free sets, Hadamard matrices" , Springer  (1972)</TD></TR><TR><TD valign="top">[a2]</TD> <TD valign="top">  D.R. Hughes,  F.C. Piper,  "Design theory" , Cambridge Univ. Press  (1988)</TD></TR><TR><TD valign="top">[a3]</TD> <TD valign="top">  F.J. MacWilliams,  N.J.A. Sloane,  "The theory of error-correcting codes" , '''I-II''' , North-Holland  (1977)</TD></TR><TR><TD valign="top">[a4]</TD> <TD valign="top">  S.S. Agaian,  "Hadamard matrices and their applications" , ''Lect. notes in math.'' , '''1168''' , Springer  (1985)</TD></TR><TR><TD valign="top">[a5]</TD> <TD valign="top">  T. Beth,  D. Jungnickel,  H. Lenz,  "Design theory" , Cambridge Univ. Press  (1986)</TD></TR><TR><TD valign="top">[a6]</TD> <TD valign="top">  A. Hedayat,  W.D. Wallis,  "Hadamard matrices and their applications"  ''Ann. Stat.'' , '''6'''  (1978)  pp. 1184–1238</TD></TR></table>
 
<table><TR><TD valign="top">[a1]</TD> <TD valign="top">  W.D. Wallis,  A.P. Street,  J.S. Wallis,  "Combinatorics: room squares, sum-free sets, Hadamard matrices" , Springer  (1972)</TD></TR><TR><TD valign="top">[a2]</TD> <TD valign="top">  D.R. Hughes,  F.C. Piper,  "Design theory" , Cambridge Univ. Press  (1988)</TD></TR><TR><TD valign="top">[a3]</TD> <TD valign="top">  F.J. MacWilliams,  N.J.A. Sloane,  "The theory of error-correcting codes" , '''I-II''' , North-Holland  (1977)</TD></TR><TR><TD valign="top">[a4]</TD> <TD valign="top">  S.S. Agaian,  "Hadamard matrices and their applications" , ''Lect. notes in math.'' , '''1168''' , Springer  (1985)</TD></TR><TR><TD valign="top">[a5]</TD> <TD valign="top">  T. Beth,  D. Jungnickel,  H. Lenz,  "Design theory" , Cambridge Univ. Press  (1986)</TD></TR><TR><TD valign="top">[a6]</TD> <TD valign="top">  A. Hedayat,  W.D. Wallis,  "Hadamard matrices and their applications"  ''Ann. Stat.'' , '''6'''  (1978)  pp. 1184–1238</TD></TR></table>

Revision as of 19:42, 5 June 2020


A square matrix $ H = \| h _ {ij} \| $ of order $ n $, with entries $ + 1 $ or $ - 1 $, such that the equation

$$ \tag{* } HH ^ {T} = n I _ {n} $$

holds, where $ H ^ {T} $ is the transposed matrix of $ H $ and $ I _ {n} $ is the unit matrix of order $ n $. Equality (*) is equivalent to saying that any two rows of $ H $ are orthogonal. Hadamard matrices have been named after J. Hadamard who showed [1] that the determinant $ | A | $ of a matrix $ A = \| a _ {ij} \| $ of order $ n $, with complex entries, satisfies the Hadamard inequality

$$ | A | ^ {2} \leq \prod _ { i= } 1 ^ { n } s _ {ii} , $$

where

$$ s _ {ik} = \sum _ {j = 1 } ^ { n } a _ {ij} \overline{ {a _ {kj} }}\; , $$

and $ \overline{ {a _ {kj} }}\; $ is the element conjugate to $ a _ {kj} $( cf. Hadamard theorem on determinants). In particular, if $ | a _ {ij} | \leq M $, then $ | A | \leq M ^ {n} n ^ {n/2} $. It follows that a Hadamard matrix is a square matrix consisting of $ \pm 1 $' s with maximal absolute value $ n ^ {n/2} $ of the determinant. The properties of Hadamard matrices are: 1) $ HH ^ {T} = nI _ {n} $ implies $ H ^ {T} H = nI _ {n} $ and vice versa; 2) transposition of rows or columns and multiplication of the elements of an arbitrary row or column by $ - 1 $ again yields a Hadamard matrix; 3) the tensor product of two Hadamard matrices is also a Hadamard matrix, of order equal to the product of the orders of the factors. In other words, if $ A = \| a _ {ij} \| $ and $ B = \| b _ {ij} \| $ are Hadamard matrices of orders $ m $ and $ n $ respectively, then $ C = \| a _ {ij} B \| $ is a Hadamard matrix of order $ mn $. A Hadamard matrix with its first row and first column consisting only of $ + 1 $ terms is said to be normalized. The order of a Hadamard matrix is $ n = 1, 2 $ or $ n \equiv 0 $( $ \mathop{\rm mod} 4 $). The normalized Hadamard matrices of orders 1 and 2 are:

$$ [ 1],\ \ \left [ \begin{array}{cr} 1 & 1 \\ 1 &- 1 \\ \end{array} \right ] . $$

The existence of a Hadamard matrix has been demonstrated for several classes of values of $ n $( see, for example, [2], [3]). At the time of writing (the 1980s), it has not yet been proved that a Hadamard matrix exists for any $ n \equiv 0 $( $ \mathop{\rm mod} 4 $). For methods of constructing Hadamard matrices see [2]. Hadamard matrices are used in the construction of certain types of block designs [2] and codes [3] (cf. Block design; Code). A Hadamard matrix of order $ n = 4t $ is equivalent to a $ ( 4t - 1, 2t - 1, t - 1 ) $- design.

A generalized Hadamard matrix is a square matrix $ H ( p, h) $ of order $ h $, with as entries $ p $- th roots of unity, which satisfies the equality

$$ HH ^ {cT} = h I _ {h} , $$

where $ H ^ {cT} $ is the conjugate transpose of the matrix $ H $ and $ I _ {h} $ is the unit matrix of order $ h $. Generalized Hadamard matrices have properties analogous to 1) and 3) (cf. [4]).

References

[1] J. Hadamard, "Résolution d'une question relative aux déterminants" Bull. Sci. Math. (2) , 17 (1893) pp. 240–246
[2] M. Hall, "Combinatorial theory" , Blaisdell (1967) pp. Chapt. 14
[3] W.W. Peterson, "Error-correcting codes" , M.I.T. & Wiley (1961)
[4] A.T. Butson, "Generalized Hadamard matrices" Proc. Amer. Math. Soc. , 13 (1962) pp. 894–898

Comments

Hadamard matrices are equivalent to so-called Hadamard $ 2 $- designs; they are also important in statistical applications [a6].

References

[a1] W.D. Wallis, A.P. Street, J.S. Wallis, "Combinatorics: room squares, sum-free sets, Hadamard matrices" , Springer (1972)
[a2] D.R. Hughes, F.C. Piper, "Design theory" , Cambridge Univ. Press (1988)
[a3] F.J. MacWilliams, N.J.A. Sloane, "The theory of error-correcting codes" , I-II , North-Holland (1977)
[a4] S.S. Agaian, "Hadamard matrices and their applications" , Lect. notes in math. , 1168 , Springer (1985)
[a5] T. Beth, D. Jungnickel, H. Lenz, "Design theory" , Cambridge Univ. Press (1986)
[a6] A. Hedayat, W.D. Wallis, "Hadamard matrices and their applications" Ann. Stat. , 6 (1978) pp. 1184–1238
How to Cite This Entry:
Hadamard matrix. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Hadamard_matrix&oldid=47158
This article was adapted from an original article by S.A. Rukova (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article