In
mathematics
Mathematics is an area of knowledge that includes the topics of numbers, formulas and related structures, shapes and the spaces in which they are contained, and quantities and their changes. These topics are represented in modern mathematics ...
, a Hadamard matrix, named after the French
mathematician
A mathematician is someone who uses an extensive knowledge of mathematics in their work, typically to solve mathematical problems.
Mathematicians are concerned with numbers, data, quantity, structure, space, models, and change.
History
On ...
Jacques Hadamard
Jacques Salomon Hadamard (; 8 December 1865 – 17 October 1963) was a French mathematician who made major contributions in number theory, complex analysis, differential geometry and partial differential equations.
Biography
The son of a teac ...
, is a
square matrix
In mathematics, a square matrix is a matrix with the same number of rows and columns. An ''n''-by-''n'' matrix is known as a square matrix of order Any two square matrices of the same order can be added and multiplied.
Square matrices are often ...
whose entries are either +1 or −1 and whose rows are mutually
orthogonal
In mathematics, orthogonality is the generalization of the geometric notion of ''perpendicularity''.
By extension, orthogonality is also used to refer to the separation of specific features of a system. The term also has specialized meanings in ...
. In geometric terms, this means that each pair of rows in a Hadamard matrix represents two
perpendicular
In elementary geometry, two geometric objects are perpendicular if they intersect at a right angle (90 degrees or π/2 radians). The condition of perpendicularity may be represented graphically using the ''perpendicular symbol'', ⟂. It can ...
vector
Vector most often refers to:
*Euclidean vector, a quantity with a magnitude and a direction
*Vector (epidemiology), an agent that carries and transmits an infectious pathogen into another living organism
Vector may also refer to:
Mathematic ...
s, while in
combinatorial
Combinatorics is an area of mathematics primarily concerned with counting, both as a means and an end in obtaining results, and certain properties of finite structures. It is closely related to many other areas of mathematics and has many ap ...
terms, it means that each pair of rows has matching entries in exactly half of their columns and mismatched entries in the remaining columns. It is a consequence of this definition that the corresponding properties hold for columns as well as rows. The ''n''-dimensional
parallelotope spanned by the rows of an ''n''×''n'' Hadamard matrix has the maximum possible ''n''-dimensional
volume
Volume is a measure of occupied three-dimensional space. It is often quantified numerically using SI derived units (such as the cubic metre and litre) or by various imperial or US customary units (such as the gallon, quart, cubic inch). The de ...
among parallelotopes spanned by vectors whose entries are bounded in
absolute value
In mathematics, the absolute value or modulus of a real number x, is the non-negative value without regard to its sign. Namely, , x, =x if is a positive number, and , x, =-x if x is negative (in which case negating x makes -x positive), an ...
by 1. Equivalently, a Hadamard matrix has maximal
determinant
In mathematics, the determinant is a scalar value that is a function of the entries of a square matrix. It characterizes some properties of the matrix and the linear map represented by the matrix. In particular, the determinant is nonzero if and ...
among matrices with entries of absolute value less than or equal to 1 and so is an extremal solution of
Hadamard's maximal determinant problem.
Certain Hadamard matrices can almost directly be used as an
error-correcting code
In computing, telecommunication, information theory, and coding theory, an error correction code, sometimes error correcting code, (ECC) is used for controlling errors in data over unreliable or noisy communication channels. The central idea is ...
using a
Hadamard code
The Hadamard code is an error-correcting code named after Jacques Hadamard that is used for error detection and correction when transmitting messages over very noisy or unreliable channels. In 1971, the code was used to transmit photos of Mar ...
(generalized in
Reed–Muller code
Reed–Muller codes are error-correcting codes that are used in wireless communications applications, particularly in deep-space communication. Moreover, the proposed 5G standard relies on the closely related polar codes for error correction in ...
s), and are also used in
balanced repeated replication Balanced repeated replication is a statistical technique for estimating the sampling variability of a statistic obtained by stratified sampling.
Outline of the technique
# ''Select balanced half-samples'' from the full sample.
# ''Calculate t ...
(BRR), used by
statistician
A statistician is a person who works with theoretical or applied statistics. The profession exists in both the private and public sectors.
It is common to combine statistical knowledge with expertise in other subjects, and statisticians may wor ...
s to estimate the
variance
In probability theory and statistics, variance is the expectation of the squared deviation of a random variable from its population mean or sample mean. Variance is a measure of dispersion, meaning it is a measure of how far a set of numbers ...
of a
parameter
A parameter (), generally, is any characteristic that can help in defining or classifying a particular system (meaning an event, project, object, situation, etc.). That is, a parameter is an element of a system that is useful, or critical, when ...
estimator
In statistics, an estimator is a rule for calculating an estimate of a given quantity based on observed data: thus the rule (the estimator), the quantity of interest (the estimand) and its result (the estimate) are distinguished. For example, the ...
.
Properties
Let ''H'' be a Hadamard matrix of order ''n''. The transpose of ''H'' is closely related to its inverse. In fact:
:
where ''I
n'' is the ''n'' × ''n''
identity matrix
In linear algebra, the identity matrix of size n is the n\times n square matrix with ones on the main diagonal and zeros elsewhere.
Terminology and notation
The identity matrix is often denoted by I_n, or simply by I if the size is immaterial o ...
and ''H''
T is the
transpose
In linear algebra, the transpose of a matrix is an operator which flips a matrix over its diagonal;
that is, it switches the row and column indices of the matrix by producing another matrix, often denoted by (among other notations).
The tr ...
of ''H''. To see that this is true, notice that the rows of ''H'' are all orthogonal vectors over the field of real numbers and each have length
. Dividing ''H'' through by this length gives an
orthogonal matrix
In linear algebra, an orthogonal matrix, or orthonormal matrix, is a real square matrix whose columns and rows are orthonormal vectors.
One way to express this is
Q^\mathrm Q = Q Q^\mathrm = I,
where is the transpose of and is the identity ma ...
whose transpose is thus its inverse. Multiplying by the length again gives the equality above. As a result,
:
where det(''H'') is the
determinant
In mathematics, the determinant is a scalar value that is a function of the entries of a square matrix. It characterizes some properties of the matrix and the linear map represented by the matrix. In particular, the determinant is nonzero if and ...
of ''H''.
Suppose that ''M'' is a complex matrix of order ''n'', whose entries are bounded by , ''M
ij'', ≤ 1, for each ''i'', ''j'' between 1 and ''n''. Then
Hadamard's determinant bound states that
:
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.
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
:
is a Hadamard matrix of order 2''n''. This observation can be applied repeatedly and leads to the following sequence of matrices, also called
Walsh matrices.
:
and
:
for
, where
denotes the
Kronecker product
In mathematics, the Kronecker product, sometimes denoted by ⊗, is an operation on two matrices of arbitrary size resulting in a block matrix. It is a generalization of the outer product (which is denoted by the same symbol) from vectors to ...
.
In this manner, Sylvester constructed Hadamard matrices of order 2
''k'' for every non-negative integer ''k''.
Sylvester's matrices have a number of special properties. They are
symmetric
Symmetry (from grc, συμμετρία "agreement in dimensions, due proportion, arrangement") in everyday language refers to a sense of harmonious and beautiful proportion and balance. In mathematics, "symmetry" has a more precise definiti ...
and, when ''k'' ≥ 1 (2
''k'' > 1), have
trace
Trace may refer to:
Arts and entertainment Music
* ''Trace'' (Son Volt album), 1995
* ''Trace'' (Died Pretty album), 1993
* Trace (band), a Dutch progressive rock band
* ''The Trace'' (album)
Other uses in arts and entertainment
* ''Trace'' ...
zero. The elements in the first column and the first row are all
positive
Positive is a property of positivity and may refer to:
Mathematics and science
* Positive formula, a logical formula not containing negation
* Positive number, a number that is greater than 0
* Plus sign, the sign "+" used to indicate a posi ...
. The elements in all the other rows and columns are evenly divided between
positive and negative. Sylvester matrices are closely connected with
Walsh function
In mathematics, more specifically in harmonic analysis, Walsh functions form a complete orthogonal set of functions that can be used to represent any discrete function—just like trigonometric functions can be used to represent any continuous fu ...
s.
Alternative construction
If we map the elements of the Hadamard matrix using the
group homomorphism
In mathematics, given two groups, (''G'', ∗) and (''H'', ·), a group homomorphism from (''G'', ∗) to (''H'', ·) is a function ''h'' : ''G'' → ''H'' such that for all ''u'' and ''v'' in ''G'' it holds that
: h(u*v) = h(u) \cdot h(v)
wh ...
, we can describe an alternative construction of Sylvester's Hadamard matrix. First consider the matrix
, the
matrix whose columns consist of all ''n''-bit numbers arranged in ascending counting order. We may define
recursively by
:
It can be shown by induction that the image of the Hadamard matrix under the above homomorphism is given by
:
This construction demonstrates that the rows of the Hadamard matrix
can be viewed as a length
linear
error-correcting code
In computing, telecommunication, information theory, and coding theory, an error correction code, sometimes error correcting code, (ECC) is used for controlling errors in data over unreliable or noisy communication channels. The central idea is ...
of
rank
Rank is the relative position, value, worth, complexity, power, importance, authority, level, etc. of a person or object within a ranking, such as:
Level or position in a hierarchical organization
* Academic rank
* Diplomatic rank
* Hierarchy
* ...
''n'', and
minimum distance with
generating matrix
This code is also referred to as a
Walsh code
The Hadamard code is an error-correcting code named after Jacques Hadamard that is used for error detection and correction when transmitting messages over very noisy or unreliable channels. In 1971, the code was used to transmit photos of M ...
. The
Hadamard code
The Hadamard code is an error-correcting code named after Jacques Hadamard that is used for error detection and correction when transmitting messages over very noisy or unreliable channels. In 1971, the code was used to transmit photos of Mar ...
, by contrast, is constructed from the Hadamard matrix
by a slightly different procedure.
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 4''k'' exists for every positive integer ''k''. The Hadamard conjecture has also been attributed to Paley, although it was considered implicitly by others prior to Paley's work.
A generalization of Sylvester's construction proves that if
and
are Hadamard matrices of orders ''n'' and ''m'' respectively, then
is a Hadamard matrix of order ''nm''. This result is used to produce Hadamard matrices of higher order once those of smaller orders are known.
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). In 1933,
Raymond Paley
Raymond Edward Alan Christopher Paley (7 January 1907 – 7 April 1933) was an English mathematician who made significant contributions to mathematical analysis before dying young in a skiing accident.
Life
Paley was born in Bournemouth, Engl ...
discovered the
Paley construction, which produces a Hadamard matrix of order ''q'' + 1 when ''q'' is any
prime
A prime number (or a prime) is a natural number greater than 1 that is not a product of two smaller natural numbers. A natural number greater than 1 that is not prime is called a composite number. For example, 5 is prime because the only ways ...
power that is
congruent
Congruence may refer to:
Mathematics
* Congruence (geometry), being the same size and shape
* Congruence or congruence relation, in abstract algebra, an equivalence relation on an algebraic structure that is compatible with the structure
* In mod ...
to 3 modulo 4 and that produces a Hadamard matrix of order 2(''q'' + 1) when ''q'' is a prime power that is congruent to 1 modulo 4. His method uses
finite field
In mathematics, a finite field or Galois field (so-named in honor of Évariste Galois) is a field that contains a finite number of elements. As with any field, a finite field is a set on which the operations of multiplication, addition, subtr ...
s.
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 architecture, a hall is a relatively large space enclosed by a roof and walls. In the Iron Age and early Middle Ages in northern Europe, a mead hall was where a lord and his retainers ate and also slept. Later in the Middle Ages, the gr ...
in 1962 at
JPL. They used a construction, due to
Williamson, that has yielded many additional orders. Many other methods for constructing Hadamard matrices are now known.
In 2005, Hadi Kharaghani and Behruz Tayfeh-Rezaie published their construction of a Hadamard matrix of order 428. As a result, the smallest order for which no Hadamard matrix is presently known is 668.
, there are 12 multiples of 4 less than or equal to 2000 for which no Hadamard matrix of that order is known.
They are:
668, 716, 892, 1132, 1244, 1388, 1436, 1676, 1772, 1916, 1948, and 1964.
Equivalence and uniqueness
Two Hadamard matrices are considered
equivalent
Equivalence or Equivalent may refer to:
Arts and entertainment
*Album-equivalent unit, a measurement unit in the music industry
* Equivalence class (music)
*'' Equivalent VIII'', or ''The Bricks'', a minimalist sculpture by Carl Andre
*''Equiva ...
if one can be obtained from the other by negating rows or columns, or by interchanging rows or columns. Up to equivalence, there is a unique Hadamard matrix of orders 1, 2, 4, 8, and 12. There are 5 inequivalent matrices of order 16, 3 of order 20, 60 of order 24, and 487 of order 28. Millions of inequivalent matrices are known for orders 32, 36, and 40. Using a
coarser notion of equivalence that also allows
transposition, there are 4 inequivalent matrices of order 16, 3 of order 20, 36 of order 24, and 294 of order 28.
Hadamard matrices are also uniquely recoverable, in the following sense: If an Hadamard matrix
of order
has
entries randomly deleted, then with overwhelming likelihood, one can perfectly recover the original matrix
from the damaged one. The algorithm of recovery has the same computational cost as matrix inversion.
Special cases
Many special cases of Hadamard matrices have been investigated in the mathematical literature.
Skew Hadamard matrices
A Hadamard matrix ''H'' is ''skew'' if
A skew Hadamard matrix remains a skew Hadamard matrix after multiplication of any row and its corresponding column by −1. This makes it possible, for example, to normalize a skew Hadamard matrix so that all elements in the first row equal 1.
Reid and Brown in 1972 showed that there exists a doubly regular
tournament
A tournament is a competition involving at least three competitors, all participating in a sport or game. More specifically, the term may be used in either of two overlapping senses:
# One or more competitions held at a single venue and concentr ...
of order ''n'' if and only if there exists a skew Hadamard matrix of order ''n'' + 1. In a mathematical tournament of order ''n'', each of ''n'' players plays one match against each of the other players, each match resulting in a win for one of the players and a loss for the other. A tournament is regular if each player wins the same number of matches. A regular tournament is doubly regular if the number of opponents beaten by both of two distinct players is the same for all pairs of distinct players. Since each of the ''n'' (''n''−1) / 2 matches played results in a win for one of the players, each player wins (''n''−1) / 2 matches (and loses the same number). Since each of the (''n''−1) / 2 players defeated by a given player also loses to (''n''−3) / 2 other players, the number of player pairs (''i'', ''j'') such that ''j'' loses both to ''i'' and to the given player is (''n''−1) (''n''−3) / 4. The same result should be obtained if the pairs are counted differently: the given player and any of the (''n''−1) other players together defeat the same number of common opponents. This common number of defeated opponents must therefore be (''n''−3) / 4. A skew Hadamard matrix is obtained by introducing an additional player who defeats all of the original players and then forming a matrix with rows and columns labeled by players according to the rule that row ''i'', column ''j'' contains 1 if ''i'' = ''j'' or ''i'' defeats ''j'' and −1 if ''j'' defeats ''i''. This correspondence in reverse produces a doubly regular tournament from a skew Hadamard matrix, assuming the skew Hadamard matrix is normalized so that all elements of the first row equal 1.
Regular Hadamard matrices
Regular Hadamard matrices In mathematics a regular Hadamard matrix is a Hadamard matrix whose row and column sums are all equal. While the order of a Hadamard matrix must be 1, 2, or a multiple of 4, regular Hadamard matrices carry the further restriction that the order be ...
are real Hadamard matrices whose row and column sums are all equal. A necessary condition on the existence of a regular ''n''×''n'' Hadamard matrix is that ''n'' be a perfect square. A
circulant
In linear algebra, a circulant matrix is a square matrix in which all row vectors are composed of the same elements and each row vector is rotated one element to the right relative to the preceding row vector. It is a particular kind of Toeplitz ...
matrix is manifestly regular, and therefore a circulant Hadamard matrix would have to be of perfect square order. Moreover, if an ''n''×''n'' circulant Hadamard
matrix existed with ''n'' > 1 then ''n'' would necessarily have to be of the form 4''u''
2 with ''u'' odd.
Circulant Hadamard matrices
The circulant Hadamard matrix conjecture, however, asserts that, apart from the known 1×1 and 4×4 examples, no such matrices exist. This was verified for all but 26 values of ''u'' less than 10
4.
Generalizations
One basic generalization is a
weighing matrix
In mathematics, a weighing matrix of order n and weight w is a matrix W with entries from the set \ such that:
:WW^\mathsf = wI_n
Where W^\mathsf is the transpose of W and I_n is the identity matrix of order n. The weight w is also called th ...
. A weighing matrix is a square matrix in which entries may also be zero and which satisfies
for some w, its weight. A weighing matrix with its weight equal to its order is a Hadamard matrix.
Another generalization defines a
complex Hadamard matrix A complex Hadamard matrix is any complex
N \times N matrix H satisfying two conditions:
*unimodularity (the modulus of each entry is unity): , H_, =1 j,k=1,2,\dots,N
*orthogonality: HH^ = NI ,
where denotes the Hermitian transpose of H and ...
to be a matrix in which the entries are complex numbers of unit
modulus and which satisfies ''H H
* = n I
n'' where ''H
*'' is the
conjugate transpose
In mathematics, the conjugate transpose, also known as the Hermitian transpose, of an m \times n complex matrix \boldsymbol is an n \times m matrix obtained by transposing \boldsymbol and applying complex conjugate on each entry (the complex con ...
of ''H''. Complex Hadamard matrices arise in the study of
operator algebras
In functional analysis, a branch of mathematics, an operator algebra is an algebra of continuous linear operators on a topological vector space, with the multiplication given by the composition of mappings.
The results obtained in the study ...
and the theory of
quantum computation
Quantum computing is a type of computation whose operations can harness the phenomena of quantum mechanics, such as superposition, interference, and entanglement. Devices that perform quantum computations are known as quantum computers. Though ...
.
Butson-type Hadamard matrices In mathematics, a complex Hadamard matrix ''H'' of size ''N'' with all its columns (rows) mutually orthogonal, belongs to the Butson-type ''H''(''q'', ''N'') if all its elements are powers of ''q''-th root of unity,
:: (H_)^q=1 j,k=1,2,\dot ...
are complex Hadamard matrices in which the entries are taken to be ''q''
th roots of unity
In mathematics, a root of unity, occasionally called a de Moivre number, is any complex number that yields 1 when raised to some positive integer power . Roots of unity are used in many branches of mathematics, and are especially important in ...
. The term ''complex Hadamard matrix'' has been used by some authors to refer specifically to the case ''q'' = 4.
Practical applications
*
Olivia MFSK
Olivia MFSK is an amateur radioteletype protocol, using multiple frequency-shift keying (MFSK) and designed to work in difficult (low signal-to-noise ratio plus multipath propagation) conditions on shortwave bands. The signal can be accurately re ...
– an amateur-radio digital protocol designed to work in difficult (low signal-to-noise ratio plus multipath propagation) conditions on shortwave bands.
*
Balanced repeated replication Balanced repeated replication is a statistical technique for estimating the sampling variability of a statistic obtained by stratified sampling.
Outline of the technique
# ''Select balanced half-samples'' from the full sample.
# ''Calculate t ...
(BRR) – a technique used by statisticians to estimate the
variance
In probability theory and statistics, variance is the expectation of the squared deviation of a random variable from its population mean or sample mean. Variance is a measure of dispersion, meaning it is a measure of how far a set of numbers ...
of a
statistical estimator
Estimation theory is a branch of statistics that deals with estimating the values of parameters based on measured empirical data that has a random component. The parameters describe an underlying physical setting in such a way that their value ...
.
*
Coded aperture
Coded apertures or coded-aperture masks are grids, gratings, or other patterns of materials opaque to various wavelengths of electromagnetic radiation. The wavelengths are usually high-energy radiation such as X-rays and gamma rays. By blocking ra ...
spectrometry – an instrument for measuring the spectrum of light. The mask element used in coded aperture spectrometers is often a variant of a Hadamard matrix.
* Feedback delay networks – Digital reverberation devices which use Hadamard matrices to blend sample values
*
Plackett–Burman design
Plackett–Burman designs are experimental designs presented in 1946 by Robin L. Plackett and J. P. Burman while working in the British Ministry of Supply.
Their goal was to find experimental designs for investigating the dependence of some meas ...
of experiments for investigating the dependence of some measured quantity on a number of independent variables.
*
Robust parameter designs for investigating noise factor impacts on responses
*
Compressed sensing
Compressed sensing (also known as compressive sensing, compressive sampling, or sparse sampling) is a signal processing technique for efficiently acquiring and reconstructing a Signal (electronics), signal, by finding solutions to Underdetermined ...
for signal processing and undetermined linear systems (inverse problems)
*
Quantum Hadamard gate for
quantum computing
Quantum computing is a type of computation whose operations can harness the phenomena of quantum mechanics, such as superposition, interference, and entanglement. Devices that perform quantum computations are known as quantum computers. Though ...
and the
Hadamard transform
The Hadamard transform (also known as the Walsh–Hadamard transform, Hadamard–Rademacher–Walsh transform, Walsh transform, or Walsh–Fourier transform) is an example of a generalized class of Fourier transforms. It performs an orthogonal ...
for quantum algorithms.
See also
*
Combinatorial design
Combinatorial design theory is the part of combinatorial mathematics that deals with the existence, construction and properties of systems of finite sets whose arrangements satisfy generalized concepts of ''balance'' and/or ''symmetry''. These co ...
*
Hadamard transform
The Hadamard transform (also known as the Walsh–Hadamard transform, Hadamard–Rademacher–Walsh transform, Walsh transform, or Walsh–Fourier transform) is an example of a generalized class of Fourier transforms. It performs an orthogonal ...
*
Quincunx matrix
In mathematics, the matrix
: \begin
1 & -1 \\
1 & 1
\end
is sometimes called the quincunx matrix. It is a 2×2 Hadamard matrix, and its rows form the basis of a diagonal square lattice consisting of the integer points whose coordinate ...
*
Walsh matrix
In mathematics, a Walsh matrix is a specific square matrix of dimensions 2, where ''n'' is some particular natural number. The entries of the matrix are either +1 or −1 and its rows as well as columns are orthogonal, i.e. dot product i ...
*
Quantum logic gate
In quantum computing and specifically the quantum circuit model of computation, a quantum logic gate (or simply quantum gate) is a basic quantum circuit operating on a small number of qubits. They are the building blocks of quantum circuits, lik ...
Notes
Further reading
*
*
*
*
*
*
*
*
*
*
*
External links
Skew Hadamard matricesof all orders up to 100, including every type with order up to 28;
* in
OEIS
The On-Line Encyclopedia of Integer Sequences (OEIS) is an online database of integer sequences. It was created and maintained by Neil Sloane while researching at AT&T Labs. He transferred the intellectual property and hosting of the OEIS to the ...
*
On-line utilityto obtain all orders up to 1000, except 668, 716, 876 & 892.
JPL: In 1961, mathematicians from NASA’s Jet Propulsion Laboratory and Caltech worked together to construct a Hadamard Matrix containing 92 rows and columns
{{Matrix classes
Combinatorial design
Matrices
Unsolved problems in mathematics