Hadamard matrix

From Wikipedia, the free encyclopedia

In mathematics, a Hadamard matrix is a square matrix whose entries are either +1 or −1 and whose rows are mutually orthogonal. This means that every two different rows in a Hadamard matrix represent two perpendicular vectors. Such matrices can almost directly be used as an error-correcting code using a Hadamard code (generalized in Reed–Muller codes), and are also used in balanced repeated replication (BRR), used by statisticians to estimate the variance of a parameter estimator. Hadamard matrices are named after the French mathematician Jacques Hadamard.

Contents

[edit] Properties

It follows from the definition that a Hadamard matrix H of order n satisfies

H^{\mathrm{T}} H = n I_n \

where In is the n × n identity matrix. Thus \det H =\pm n^{n/2}.

Suppose that M is a complex matrix of order n, whose entries are bounded by |Mij| ≤1, for each i, j between 1 and n. Then Hadamard's determinant bound states that

|\operatorname{det}(M)| \leq n^{n/2}.

Equality in this bound is attained for a real matrix M if and only if M is a Hadamard matrix.

The order of a Hadamard matrix must be 1, 2, or a multiple of 4.

[edit] Sylvester's construction

Examples of Hadamard matrices were actually first constructed by James Joseph Sylvester in 1867. Let H be a Hadamard matrix of order n. Then the partitioned matrix

\begin{bmatrix} H & H\\ H & -H\end{bmatrix}

is a Hadamard matrix of order 2n. This observation can be applied repeatedly and leads to the following sequence of matrices, also called Walsh matrices.

H_1 = \begin{bmatrix} 1 \end{bmatrix},
H_2 = \begin{bmatrix} 1 & 1 \\ 1 & -1 \end{bmatrix},

and

H_{2^k} = \begin{bmatrix} H_{2^{k-1}} & H_{2^{k-1}}\\ H_{2^{k-1}} & -H_{2^{k-1}}\end{bmatrix} = H_2\otimes H_{2^{k-1}},

for 2 \le k \in N , where \otimes denotes the Kronecker product.

In this manner, Sylvester constructed Hadamard matrices of order 2k for every non-negative integer k. [1]

Sylvester's matrices have a number of special properties. They are symmetric and traceless. The elements in the first column and the first row are all positive. The elements in all the other rows and columns are evenly divided between positive and negative. Sylvester matrices are closely connected with Walsh functions.

[edit] Alternative construction

If we map the elements of the Hadamard matrix using the group homomorphism \{1,-1,\times\}\mapsto \{0,1,\oplus\} , we can describe an alternative construction of Sylvester's Hadamard matrix. First consider the matrix Fn, the n\times 2^n matrix whose columns consist of all n-bit numbers arranged in ascending counting order. We may define Fn recursively by

F_1=\begin{bmatrix} 0 & 1\end{bmatrix}
F_n=\begin{bmatrix} 0_{1\times 2^{n-1}} & 1_{1\times 2^{n-1}} \\ F_{n-1} & F_{n-1} \end{bmatrix}.

In can be shown by induction that the image of the Hadamard matrix under the above homomorphism is given by

H_{2^n}=F_n^TF_n.

This construction demonstrates that the rows of the Hadamard matrix H_{2^n} can be viewed as a length 2n linear error-correcting code of rank n, and minimum distance 2n − 1 with generating matrix Fn.

This code is also referred to as a Walsh code. (Not to be confused with the Hadamard code, which is constructed from the Hadamard matrix H_{2^n} by a slightly different procedure.)

[edit] The Hadamard conjecture

The most important open question in the theory of Hadamard matrices is that of existence. The Hadamard conjecture proposes that a Hadamard matrix of order 4k exists for every positive integer k.

Sylvester's 1867 construction yields Hadamard matrices of order 1, 2, 4, 8, 16, 32, etc. Hadamard matrices of orders 12 and 20 were subsequently constructed by Hadamard (in 1893). [2] Later, in 1933, Raymond Paley showed how to construct a Hadamard matrix of order q+1 where q is any prime power which is congruent to 3 modulo 4. [3] He also constructed matrices of order 2(q+1) for prime powers q which are congruent to 1 modulo 4. His method uses finite fields. The Hadamard conjecture should probably be attributed to Paley. The smallest order that cannot be constructed by a combination of Sylvester's and Paley's methods is 92. A Hadamard matrix of this order was found using a computer by Baumert, Golomb, and Hall in 1962. They used a construction, due to Williamson, that has yielded many additional orders. Many other methods for constructing Hadamard matrices are now known.

Hadi Kharaghani and Behruz Tayfeh-Rezaie announced on 21 June 2004 that they constructed a Hadamard matrix of order 428. As a result, the smallest order for which no Hadamard matrix is presently known is 668.

[edit] Equivalence of Hadamard matrices

Two Hadamard matrices are considered equivalent if one can be obtained from the other by negating rows, negating columns, interchanging rows, and interchanging columns. Up to equivalence, there is a unique Hadamard matrix in orders 1, 2, 4, 8, and 12. There are 5 inequivalent matrices in order 16, 3 in order 20, 60 in order 24, and 487 in order 28. Millions of inequivalent matrices are known in orders 32, 36, and 40.

[edit] Skew Hadamard matrices

A Hadamard matrix H is skew if H^T + H= 2I \ .

Reid and Brown in 1972 showed that there exists a "doubly regular tournament of order n" if and only if there exists a skew Hadamard matrix of order n+1.

[edit] Generalizations and special cases

There are many generalizations and special cases of Hadamard matrices investigated in the mathematical literature. One basic generalization is a weighing matrix in which one allows also zeros in the entries of the matrix and requires the number of +1, −1 to be a certain constant throughout the matrix. Another generalization are complex Hadamard matrices in which the entries are complex numbers of unit modulus and for which the matrix satisfies H H*= n In where H* is the conjugate transpose of H. Complex Hadamard matrices arise in the study of operator algebras and the theory of quantum computation. Butson-type Hadamard matrices are a special case of complex Hadamard matrices in which the entries are taken to be qth roots of unity. The term "complex Hadamard matrix" has been used by some authors to refer specifically to the case q = 4. A special case of real Hadamard matrices are circulant Hadamard matrices. Such a square matrix is defined by its first row, and every other row is a cyclic shift of its predecessor row. Circulant Hadamard matrices of orders 1 and 4 are known and it is conjectured that no other orders exist. Regular Hadamard matrices are real Hadamard matrices whose row and column sums are all equal.

[edit] Practical applications

  • Olivia MFSK - an amateur-radio digital protocol designed to work in difficult (low signal-to-noise ratio plus multipath propagation) conditions on shortwave bands.
The BRR variance estimate is found in the following way. First, the estimate is computed using the entire sample. Call this the "full-sample" estimate. Next, many subsamples are taken, each one chosen in a special way. Each of these subsamples will represent about half of the full-sample, so are called "half-samples." Since these half-samples are sampled multiple times, they are also commonly called "replicates." Their construction uses Hadamard matrices, and the details will be discussed later. Yet first the variance estimation formula is described.
For each replicate, a new estimate must be computed, called the "half-sample estimate" or sometimes the "replicate estimate." In BRR's most generic form (called Fay's method of BRR), the units in the full-sample yet not in the half-sample will have their weights deflated, and the units in the half-sample will have their weights inflated. The deflation is accomplished by multiplying the weight by factor k (called the Fay factor) and inflation by a factor (2-k), where 0 <= k < 1. The most common form of BRR is to let k = 0.
The BRR variance estimate is found in two steps. First, we find the average, over all replicates, of the squared difference of the replicate estimate from the full-sample estimate. Second, we divide this value by the square of (1-k).
The collection of half-samples is not chosen haphazardly, but rather are designed so that they form a "balanced" set of half-samples. Hadamard matrices are used to find the balance. The ideal situation is to have a sample design where there is one-stage of selection, the sampling frame is broken into a collection of sampling strata, and within each stratum, only two primary sampling units (PSUs) are selected. In this circumstance, a half-sample is formed by selecting one PSU from each stratum. Within each stratum, label the PSUs 1 and 2. To gain balance, we use a (square) Hadamard matrix with at least one column per stratum. The rows will represent replicates. If the entry in row r and column h is 1, then we pick PSU 1. If the entry is -1, we pick PSU 2.
Because Hadamard matrices are pairwise orthogonal (vector dot products are zero), the net result is this: for any two pairs of strata, the number of half-samples where the same PSU number is chosen for both strata, will be equal to the number of half-samples where different PSU numbers are chosen between the two strata. Such a collection of half-samples is called "balanced." A stronger situation is when the collection is "fully balanced." This occurs whenever all column sums of the matrix are zero, which means that for any stratum, the number of half-samples where PSU 1 is chosen equals the number of those where PSU 2 is chosen. Full-balance is not necessary, nor always possible, but if it exists, it "enhances" the balance.
The above situation described the ideal case (full sample = two units sampled per sampling stratum). In reality, often many units are sampled per sampling stratum. In these situations, within each stratum we must define two objects called "variance PSUs" (labeled 1 and 2), where each will contain about half the sampled units in the stratum. This is done randomly, or semi-randomly. If a systematic sample was used, the assignment of units to variance PSUs is usually done by first sorting the sample, similar to how the frame was sorted before it was sampled. Then, the first unit is randomly assigned to PSU 1 or 2. The rest are then assigned, in an alternating fashion, as one moves through the sorted list. In some situations, the number of strata is so large that this affects the efficiency of BRR, in such cases one solution is to collapse the sampling strata together to form new objects, called "variance strata." Another complication occurs if there are several stages of sampling. Unfortunately, BRR will not capture the variance from these other sampling stages, and only captures the variance from the first stage (the between-PSU variance). One final twist is when the multi-stage sample design has "certainty PSUs" (these are in all first-stage samples, that is, they are sampled with "certainty"). In these situations, for the certainty PSUs only, we usually drop down to the stage-two sample, and for BRR we now let variance strata equal stage-two sampling strata, and variance PSUs be made up of stage-two sampling units (secondary sampling units or SSUs). If there are (conditional) stage two certainties, we subdivide further (to TSUs), and so on. Often, to increase efficiency, the strata at these lower levels are collapsed, often to the PSU, and the PSU is now the the variance stratum.

[edit] References and external links

  1. ^ J.J. Sylvester. Thoughts on inverse orthogonal matrices, simultaneous sign successions, and tessellated pavements in two or more colours, with applications to Newton's rule, ornamental tile-work, and the theory of numbers. Philosophical Magazine, 34:461-475, 1867
  2. ^ J. Hadamard. Résolution d'une question relative aux déterminants. Bulletin des Sciences Mathématiques, 17:240-246, 1893
  3. ^ R. E. A. C. Paley. On orthogonal matrices. Journal of Mathematics and Physics, 12:311–320, 1933.
  • S. Georgiou, C. Koukouvinos, J. Seberry, Hadamard matrices, orthogonal designs and construction algorithms, pp. 133-205 in DESIGNS 2002: Further computational and constructive design theory, Kluwer 2003.
  • K.B. Reid & E. Brown, Doubly regular tournaments are equivalent to skew Hadamard matrices, J. Combinatorial Theory A 12 (1972) 332-338.
  • On-line utility to obtain all orders up to 1000, except 668, 716, 876 & 892.
  • R. K. Yarlagadda and J. E. Hershey, "Hadamard Matrix Analysis and Synthesis, (1996)