Hadamard Matrix

If you have worked with CDMA spreading codes or the Walsh-Hadamard transform, you have already used a Hadamard matrix. It is one of the simplest matrices with perfectly orthogonal rows, and every entry is +1 or -1, so a computer can multiply by it with additions and subtractions only. I'll first state the definition and its consequences. Then we'll build larger Hadamard matrices from smaller ones, use one as a transform, and go through the applications.

What is a Hadamard matrix ?

A Hadamard matrix is a special type of square matrix with elements either +1 or -1. The unique property of Hadamard matrices is that their rows and columns are orthogonal, which means that when any two distinct rows or columns are multiplied element-wise and then summed, the result is zero. In other words, the dot product of any two distinct rows or columns is zero.

The smallest nontrivial case is the 2 x 2 matrix below. Its two rows are [1 1] and [1 -1], and their dot product is 1 - 1 = 0. The labels point out the three conditions: the matrix is square, its entries are 1 and -1, and its rows are orthogonal.

2 x 2 Hadamard matrix with its square shape, plus and minus one entries and orthogonal rows marked

Figure 1. The 2 x 2 Hadamard matrix H₂. It is square, holds only +1 and -1, and its two rows are orthogonal.

All three conditions fit into one equation : an n x n matrix H of +1 and -1 entries is a Hadamard matrix when H H^T = n I. Each diagonal entry is n, because a row dotted with itself adds n ones. Each off-diagonal entry is 0, because distinct rows are orthogonal.
The inverse is almost free : from H H^T = n I, the inverse is H^-1 = H^T/n. After scaling by 1/√n, the matrix H/√n is an orthogonal matrix.
Only some sizes are possible : a Hadamard matrix of order n exists only for n = 1, n = 2 or n a multiple of 4. For example, no 3 x 3 matrix of +1 and -1 has orthogonal rows.
Every multiple of 4 is believed to work : the Hadamard conjecture says that a Hadamard matrix exists for every multiple of 4. It is still unproven, and 668 is the smallest order for which no construction is known.
Sign flips keep the property : multiplying any row or any column by -1, or swapping rows or columns, gives another Hadamard matrix.

How to generate bigger Hadamard matrix ?

A 2 x 2 matrix is too small for most uses, because a CDMA system or a transform needs 8, 64 or more orthogonal rows. The simplest way to get them is to reuse a Hadamard matrix you already have as a building block. This construction is due to Sylvester, and it gives every size that is a power of 2.

We can generate a larger hadmard matrix from smaller hadmard matrix based on the following mathematical equation. This is basically recursive formula.

Recursive formula H of size 2 to the k built from four blocks of size 2 to the k minus 1, equal to the Kronecker product of H2 and the smaller matrix

Figure 2. Sylvester construction. Four copies of the smaller matrix, one of them negated, form the next size up, which is the Kronecker product H₂ ⊗ H_2^k-1.

The subscript is the size : H_2^k is a 2^k x 2^k matrix. Each step doubles the size, so the construction produces orders 1, 2, 4, 8, 16 and so on.
Orthogonality carries over : rows from the top half and rows from the bottom half share the same left block. Their right blocks differ only in sign, so the two halves of the dot product cancel.
The Kronecker product is the compact form : H₂ ⊗ A replaces each entry of H₂ by that entry times the whole matrix A. With A = H_2^k-1, this gives exactly the block matrix of Figure 2.
Other constructions fill the gaps : sizes such as 12 or 20 are multiples of 4 but not powers of 2. They need other methods, for example the Paley construction.

Example

The example below starts from the 1 x 1 matrix [1] and applies the formula twice. Watch the lower right block in each step, because it is the only negated copy. It is where the -1 entries come from.

Sylvester construction from H1 to H2 and H4

Figure 3. Building H₂ and H₄ from H₁ = [1]. H₄ has four mutually orthogonal rows of length 4.

H₄ passes the check : H₄ H₄^T = 4 I. For example, rows 2 and 3 are [1 -1 1 -1] and [1 1 -1 -1], and their dot product is 1 - 1 - 1 + 1 = 0.
The first row and the first column are all ones : every Sylvester matrix is in this normalized form, because the upper left block is never negated.
The Sylvester matrices are symmetric : H₄ equals its own transpose, so H₄^-1 = H₄/4.
The determinant is as large as it can be : det(H₄) = 16 = 4², and det(H₈) = 4096 = 8⁴. In general |det H| = n^n/2 for a Hadamard matrix of order n.

How does a Hadamard matrix transform a vector ?

Most applications use a Hadamard matrix by multiplying it with a vector. The product is called the Walsh-Hadamard transform. It plays the same role as the Fourier transform, but its basis vectors are square waves of +1 and -1 instead of sines and cosines.

The forward transform is y = H x, and the inverse follows from H H^T = n I. For a symmetric Sylvester matrix it is x = H y / n. Take x = [1 2 3 4] with the H₄ of Figure 3. Row 1 adds all entries, so y₁ = 10. The other rows give y₂ = 1 - 2 + 3 - 4 = -2 and y₃ = 1 + 2 - 3 - 4 = -4. The last row gives y₄ = 1 - 2 - 3 + 4 = 0. Multiplying [10 -2 -4 0] by H₄ and dividing by 4 returns [1 2 3 4].

The first coefficient is the sum : y₁ is n times the mean of x, because the first row is all ones.
No multiplications are needed : every entry is +1 or -1, so each coefficient is a sum with signs. The fast Walsh-Hadamard transform uses the recursion of Figure 2 and needs n log₂ n additions and subtractions instead of n².
The Sylvester row order is not sorted by frequency : the rows of H₈ change sign 0, 7, 3, 4, 1, 6, 2 and 5 times. Walsh codes in sequency order reorder the same rows so that the number of sign changes increases from row to row.
Energy is kept up to a factor : without scaling, the transform multiplies the length of the vector by √n. H/√n is orthogonal, so the scaled transform keeps the length unchanged.

Application of Hadmard Matrix

Mostly thanks to the orthogonality property, Hadamard matrices are applied for some interesting characteristics and applications. For example, they are used in coding theory, signal processing, and experimental design. Additionally, Hadamard matrices are known to have the maximum determinant for matrices of their size, which means they are well-conditioned and have good numerical properties.

The maximum determinant statement needs its condition. Among all n x n matrices whose entries lie between -1 and +1, the absolute determinant is at most n^n/2, and a Hadamard matrix reaches that bound. For n = 3 no Hadamard matrix exists. The largest determinant of a 3 x 3 matrix of +1 and -1 is only 4, below the bound 3^3/2 of about 5.2.

Coding theory: Hadamard matrices are used to construct error-correcting codes like the Hadamard code. These codes can detect and correct errors in data transmission, making them particularly useful in digital communication systems.

Signal processing: In communication systems, Hadamard matrices can be employed for spreading sequences in Code Division Multiple Access (CDMA) schemes. The orthogonal properties of the Hadamard matrix allow multiple users to share the same frequency band without interference. A typical example for this is Walsh Code being used in CDMA.

Cryptography: Hadamard matrices can be utilized in cryptographic schemes like the McEliece cryptosystem, which is a public-key cryptosystem based on error-correcting codes.

Compressed sensing: Hadamard matrices can be used to construct sensing matrices in compressed sensing, which is a signal processing technique for efficiently acquiring and reconstructing sparse signals.

Quantum computing: Hadamard matrices are used as the basis for the Hadamard gate, a single-qubit gate in quantum computing. The Hadamard gate is particularly important because it allows the creation of quantum superpositions, a fundamental concept in quantum computing.

Experimental design: In statistics, Hadamard matrices can be used to create orthogonal arrays for designing experiments. The orthogonality of the rows ensures that the experimental conditions are balanced, leading to more accurate and interpretable results.

Image processing: Hadamard matrices can be employed in techniques like the Hadamard Transform, which is a linear, orthogonal, and symmetric transformation used for image compression, data encryption, and pattern recognition.

Fast Fourier Transform (FFT) algorithms: The Fast Walsh-Hadamard Transform (FWHT) is a special case of the FFT that uses Hadamard matrices. It is a faster and more computationally efficient alternative to the regular FFT in certain applications

A Hadamard code from H₈ corrects one error : the 8 rows of H₈ and their 8 negatives give 16 codewords of length 8. Any two of them differ in at least 4 positions, so the code detects up to 3 errors and corrects 1.
Walsh codes are the rows of a Hadamard matrix : two users spread with different rows produce a zero correlation when their chips are aligned in time. This separation holds only with time alignment, which is why the CDMA downlink uses Walsh codes.
McEliece itself uses Goppa codes : the original McEliece cryptosystem is built on binary Goppa codes. Variants with first-order Reed-Muller codes, which are closely related to Hadamard codes, were proposed but later broken.
The Hadamard gate is the scaled H₂ : the gate matrix is H₂/√2, which is unitary. Applied to the state |0>, it gives an equal superposition of |0> and |1>.
The FWHT and the FFT share one structure : both split a length-n transform into two of length n/2. The FWHT needs only additions and subtractions, while the FFT also needs complex multiplications, so the FWHT is cheaper when square-wave basis vectors suit the signal.