(20061226) Identity (I), Permutation Matrices, Exchange Matrix (J)
The various permutations of the columns of the identity (I).
Those square matrices whose elements vanish except for
one unit element per row and per column
are known as permutation matrices.
Each corresponds to a permutation of the columns of the identity matrix (I)
and they form collectively
a multiplicative group isomorphic to the
symmetric group
on a set of n elements.
One particular permutation matrix is the socalled exchange matrix (J)
which is the "mirror image" of the identity matrix itself. For example:
I_{6} =
1^{ }
0^{ }
0^{ }
0^{ }
0^{ }
0^{ }
0^{ }
1^{ }
0^{ }
0^{ }
0^{ }
0^{ }
0^{ }
0^{ }
1^{ }
0^{ }
0^{ }
0^{ }
0^{ }
0^{ }
0^{ }
1^{ }
0^{ }
0^{ }
0^{ }
0^{ }
0^{ }
0^{ }
1^{ }
0^{ }
0^{ }
0^{ }
0^{ }
0^{ }
0^{ }
1^{ }
J_{6} =
0^{ }
0^{ }
0^{ }
0^{ }
0^{ }
1^{ }
0^{ }
0^{ }
0^{ }
0^{ }
1^{ }
0^{ }
0^{ }
0^{ }
0^{ }
1^{ }
0^{ }
0^{ }
0^{ }
0^{ }
1^{ }
0^{ }
0^{ }
0^{ }
0^{ }
1^{ }
0^{ }
0^{ }
0^{ }
0^{ }
1^{ }
0^{ }
0^{ }
0^{ }
0^{ }
0^{ }
In spite of this superficial finitedimensional resemblance
with the identity matrix, there's no nice generalization
of the exchange matrix to infinitely many dimensions.
(20070213) Defining matrix operations
from operations on elements
Dirac's notation is convenient to express the elements of a matrix A.
The scalar at row i and column j in matrix A,
is often denoted a_{ij}
Similar ad hoc notations are adequate when
juggling with just a few distinct matrices, in spite of the fact that
the name of the doublysubscripted symbol is not directly related to the name
of the matrix itself (A)...
That flaw is avoided by the nice selfcontained notation
(due to P.A.M. Dirac)
shown on the righthand side of the following equation:
a_{ij} =
< i  A  j >
This is sometimes called the element of Abetween i and j.
Abstract meanings are given to separate parts of that notation:
 j > is a ket (or "column vector")
of an orthonormal basis and < i  is the dual of
such a thing (a bra or "row vector").
These interpretations are important and do repay study, but they're not a prerequisite
to use the notation as a whole.
For example, the following equation defines the
sum A+B of two matrices A and B by giving
every element of it, in terms of a simple addition of scalars :
< i  A+B  j >
=
< i  A  j > +
< i  B  j >
More interestingly, here's how the
product AB of two matrices is defined :
< i  AB  j >
=
å_{k}
< i  A  k > < k  B  j >
That general rule for matrix multiplication was made explicit in 1812
(using more traditional index notations) by the French mathematician
Jacques Binet
(17861856; X1804) who is also remembered for two totally unrelated
things, which are both known as "Binet's formulas":
If we denote by z* the conjugate
aib of the complex
number z = a+ib,
(z=z* when z is a real number) then we may define as
follows the conjugate transposeA* of the complex matrix A:
" i ,
" j ,
< i  A*  j >
=
< j  A  i >*
This operation is far more important than transposition without conjugation
(which is virtually useless in the complex realm).
With respect to A, A* is variously called
conjugate transpose,
Hermitian conjugate,
adjoint,
Hermitian adjoint or dual.
It's may be called transpose for real matrices.
Here's how to prove for matrices the relation which
gives the adjoint of a product:
(AB)* = B* A*
(this holds for
whatever is called "adjoint" or "dual" among other
multiplicative
objects for which the term is defined).
< i  (AB)*  j >
=
< j  AB  i >*
=
S_{k}
( < j  A  k > < k  B  i > )*
=
S_{k}
< j  A  k >* < k  B  i >*
=
S_{k}
< k  A*  j > < i  B*  k >
=
S_{k}
< i  B*  k > < k  A*  j >
=
< i  B* A*  j >^{ }
(20100810) Determinant of a Matrix
(Seki, 1683)
It's defined as a completely antisymmetrical multilinear form.
In a vector space of dimension n,
a completely antisymmetrical form is a scalarvalued function
of n vectors, which is linear with respect to every argument and
has the property of being unchanged by any
even permutation of the arguments
and negated by any odd one.
Even and odd permutations have
signature +1 and 1, respectively.
Permutations are bijective functions of a finite set
onto itself.
The signature of a function s
which is not bijective is zero
( sgn(s) = 0).
In dimension 3 for example,
such a function f would be trilinear and verify:
f ( v_{1 }, v_{2 }, v_{3 })
=
f ( v_{2 }, v_{3 }, v_{1 })
=

f ( v_{2 }, v_{1 }, v_{3 })
A key observation is that all such functions are proportional to each other.
Leibniz's formula entails a sum of n!
terms, each a product of n factors:
n
det ( A ) =
å
sgn ( s )
Õ
< i  A  s(i) >
sÎS_{n}
i = 1
(20120918) Minors & Cofactors
A minor is a determinant obtained by deleting n rows and n columns.
The number of deleted rows and columns can be zero
(the whole determinant is a minor of itself).
An nth minor is obtained by deleting n rows and n columns.
Of particular interest are the first minors of a
determinant, which are obtained by deleting one row (the ith one)
and one column (the jth one).
(20100812) Adjugate (classic adjoint):
Tranpose of the cofactors.
The adjugate of A verifies adj(A) A
= A adj(A) = det(A) I
The adjugate adj(A) of a matrix A
may no longer be called its "adjoint", which is now
a synonym of transpose conjugate
(denoted A* or
A ).
A matrix A is invertibleiff it has nonzero determinant, in which case:
A^{1} =
adj(A) / det(A)
As the determinant of the matrix A is an homogeneous
polynomial of its elements, it can be written uniquely in the following
way, where the polynomials A_{ij} and B_{ij}
do not depend on the element a_{ij}.
det(A) = a_{ ij} A_{ ij} + B_{ ij}
By definition, A_{ ij} is the cofactor
of a_{ ij}
(20100812) Eigenvectors and eigenvalues
The image of an eigenvector is proportional to it.
(20100812) Characteristic Polynomial P of a square matrix
It's independent on the choice of a vectorial basis.
Trace :
The trace of a matrix is the sum of the elements in its diagonal:
n
tr ( A ) =
å
< i  A  i >
i = 1
It's also the coefficient of (x) in the characteristic polynomial of
the operator.
As such, the trace is an intrinsic value associated to the operator itself,
irrespective of the choice of a coordinate basis.
So, we may talk freely about
the trace of an operator (or the trace of a tensor).
(20171203) Minimal Polynomial Q of a Square Matrix
A polynomial Q easy to obtain from the characteristic polynomial P.
Defining Q as the least monic polynomial havind the same roots as P,
we obtain it as P/R where R is the greatest (monic) common divisor
of P and its derivative P'.
It's not even necessary to know the roots of P to perform that calculation.
The characteristic polynomial P is irreducible
when it's equal to the minimal polynomial Q.
(20100812) CayleyHamilton Theorem (1855, 1858, 1878)
Any matrix is a root of its own characteristic polynomial.
That general theorem was first stated in 1858 by
Arthur Cayley who only checked it for
3dimensional matrices.
A special case (3dimensional rotations)
had been stated by Hamilton three years earlier.
The first general proof was published in 1878 by
Georg Frobenius (18491917).
As the coefficients of the characteristic polynomial of a matrix A
are polynomial functions of its elements, the assertion
states that a particular set of n^{2} polynomials functions
(of degree n) in n^{2} variables vanishes.
To prove that the coefficients of all the relevant polynomials vanish, it suffices to
establish that the associated polynomial functions vanish on a sufficiently large set
of points. In particular, a dense
set of points will do
(the zeroes of any continuous function form a closed set).
For an ndimensional vector space over complex numbers,
the set of matrices with distinct eigenvalues is dense
among all square matrices.
(20171203) JordanChevalleyDunford decomposition: M = D+N
Chevalley's algorithm finds the unique decomposition
of a matrix into the sum of its diagonalizable
and nilpotent parts, which commute.
History :
Although Camille Jordan published an early
form of it in 1870, that result took a full century to make its way into
a graduate textbook (Dunford & Schwartz, 1971).
It's now common knowledge among graduate students and it has entered the
standard undergradute curriculum for linear algebra.
What is still lost on most students and some faculty is the
remarkable fact that the decomposition can be effectively performed
without any knowledge of the eigenvalues of the matrix to be decomposed.
The ground field need not even be
algebraically closed
(like the complex numbers).
A perfect field is enough
(e,g., the rationals or anyfinite field).
That crucial observation is due to Claude Chevalley (1951)
which fully justifies the name of JordanChevalley decomposition,
which is now commonly used. Here's the chronology of the four key publications:
1870: Camille Jordan (18381922; X1855)
Traité des substitutions et des équations algébriques (Paris, 1870).
1951: Claude Chevalley (19091984)
Théorie des groupes de LieII. Groupes Algébriques
(Hermann, Paris, 1951).
1971: Nelson Dunford & Jacob T. Schwartz
(19302009)
Linear OperatorsIII. pp.19371941 & 2096 (Wiley, 1971).
Since the Dunford & Schwartz textbook (1971) was so instrumental in its
popularizarion, the concept was known for a while as
Dunford's decomposition, a term which is now being deprecated.
(Dunford's earliest research on the topic appeared 3 years after Chevalley's final results.)
As a clear example of reversechauvinism, the French have held on
to the attribution to Dunford longer than anyone else...
Proof :
In a context where the matrix could be put in
Jordan's normal form, the existence and uniqueness
of the JordanChevalley decomposition are fairly trivial.
However, as advertised, we aim for a stronger result and won't assume
that the characteristic polynomial or the minimal polynomial can be fully factored.
We merely assume that the gound field is a perfect field.
This is all the following algorithm need to uniquely determine the diagonalizable
part D of the matrix M. The nilpotent part N is then obtained as MD.
The ground field need not be algebraically closed
(as Chevalley's algorithm doesn't require that).
The last step will be to remark that N and D commute because they're
both obtained as polynomial functions of M
Chevalley's Algorithm :
Let M be the matrix to decompose.
Let Q be its minimal polynomial.
The diagonalizable part D of M is a zero of Q.
In elementary numerical analysis, the
NewtonRaphson method
can be used to find a numerical zero of a polynomial Q (or any
other differentiable function) as a limit of a sequence of approximations,
defined by recurrence:
x_{n+1} = x_{n}
 Q ( x_{n }) / Q' ( x_{n })
If the starting point is close enough to the root, the sequence so defined
converges quadratically to that root
(i.e., the number of correct digits roughly doubles withh each iteration).
Chevalley's idea was to apply the same strategy and the same iteration
formula to matrices instead of numbers.
The nice surprise is that the convergence is even much
better, as the limit is reached
in finitely many steps (no more than the
binary logarithm of the dimension of the matrix).
Let's show that:
(20170104) Perron Vector of a Matrix with Positive Elements
The spectral radius r
of such a matrix is a simple positive eigenvalue.
The spectral radius of a square matrix is the largest modulus of
its eigenvalues. A simple eigenvalue is a simple root
of the characteristic polynomial. It's associated with an eigenspace of dimension 1.
(20060118) Vandermonde Matrices
A Vandermonde matrix is also sometimes called an alternant matrix.
The Vandermonde matrix associated with a sequence (x_{n }) is the square matrix
of the successive powers of the elements in that sequence.
The element on row i and column j is
(x_{j })^{ i}.
[Some authors consider the transpose of this.]
M_{n+1} =
1
1
1
1
...
1
x_{0}^{ }
x_{1}^{ }
x_{2}^{ }
x_{3}^{ }
...
x_{n}^{ }
x_{0}^{2}
x_{1}^{2}
x_{2}^{2}
x_{3}^{2}
...
x_{n}^{2}
x_{0}^{3}
x_{1}^{3}
x_{2}^{3}
x_{3}^{3}
...
x_{n}^{3}
...
...
...
...
...
...
x_{0}^{n}
x_{1}^{n}
x_{2}^{n}
x_{3}^{n}
...
x_{n}^{n}
The determinant of the above Vandermonde matrix has a nice expression:
n1
n
det ( M_{n+1}^{ }) =
Õ
Õ
^{ } ( x_{j}  x_{i} )
i = 0
j = i+1
Proof :
Both sides of the equation
are polynomials of degree n(n+1)/2
in n+1 variables, which vanish when two of the variables are equal.
Since such polynomials are necessarily proportional, they must be
equal if some pair of matching coefficients are equal.
That's easily proven for the last pair, by induction on n.
(HINT: The coefficient of the last variable raised
to the nth power is the Vandermonde determinant for the n previous variables.)
Earlier authors
had stumbled upon determinants when solving several
simultaneous linear equations in as many unknowns.
Those include Cardano (in the 2 by 2 case only)
Leibniz, Cramer (1750)
and Bézout (1764).
However, Vandermonde published the first investigation (1771)
of determinants in their own right, as functions of the coefficients of a matrix.
The importance of the idea was immediately recognized by
Laplace (1772) and Lagrange (1773).
Curiously, the determinant concept was made clear before the concept of a matrix itself.
The modern name "determinant" was coined by Gauss in 1801.
When it does not vanish, this quantity "determines" that a system of equations has
a unique solution
(in which case it's called a "Cramer system", in highschool parlance).
Strangely enough, Vandermonde himself
never mentioned the above type of matrices, now named after him.
For lack of a better explanation, it has been speculated (by
Lebesgue
and others)
that whoever atttributed this enduring "credit" mistook one of Vandermonde's
superscripts for an exponent !
What's perhaps the greatest contribution of Vandermonde is often overlooked:
Vandermonde came up with the idea of studying functions which are
invariant under any permutation of a given polynomial's roots.
He did so in the first of only four mathematical papers he ever published:
Mémoire sur la résolution des équations (1770).
Arguably, this publication marks the very beginning of modern algebra.
This idea of Vandermonde's would ultimately lead to the celebrated AbelRuffini
theorem (which states the impossibility of a general solution by radicals for algebraic
equations of degree 5 or more). The subsequent work of
Lagrange, Ruffini,
Abel and
Galois begat
Group Theory and
Field Theory.
Xinglongdada
(20120504, email)
A Totally Positive Matrix
If 0 < a_{1} < a_{2} < ... <
a_{n} and
0 ≤ l_{1} < l_{2}
< ... < l_{n} prove that the determinant of the following matrix A_{n} is positive.
A_{n} =
a_{1}^{l1}
a_{2}^{l1}
a_{3}^{l1}
...
a_{n}^{l1}
a_{1}^{l2}
a_{2}^{l2}
a_{3}^{l2}
...
a_{n}^{l2}
...
...
...
...
...
a_{1}^{ln}
a_{2}^{ln}
a_{3}^{ln}
...
a_{n}^{ln}
Such a matrix is known as a generalized Vandermonde matrix.
It's a classical example of a totally positive matrix
(i.e., a real matrix whose minors are all positive)
which is to say that we always obtain a square matrix of positive
determinant by deleting from it an equal number
(possibly zero) of rows and columns.
(Note that, if a matrix is a generalized Vandermonde matrix, so are all its submatrices.)
The fact that all generalized Vandermonde determinants are positive happens to be
a consequence of the fact that they are all nonzero...
Indeed, there's
a continuous path (depending on a parameter u that goes continuously
from 0 to 1) which goes continuously from the above determinant to an
ordinary Vandermonde determinant (which is clearly positive by virtue
of the above formula which expresses it as a product
of positive factors). The determinant at point u along that path is obtained
by replacing the exponent
l_{i} with the positive quantity:
l'_{i} =
(1u) l_{i} + u (i1)
For any u in [0,1], the above inequalities between exponents are preserved.
A continuous function of u over [0,1] cannot go from a negative to a positive
value without vanishing at some point.
So, to show that
all generalized Vandermonde determinants are positive, we only need to establish that
none of them is zero. Let's prove that:
Proof :
We proceed by induction on the size n
of the matrix (n = 1 being trivial).
Let's assume (by induction hypothesis) that there are no
vanishing generalized Vandermonde determinants of size less than n.
Then, if we had a vanishing generalized Vandermonde determinant of size n,
there would be a linear combination of different powers of x vanishing
for at least n positive values of x (namely,
a_{1} ...a_{n}).
That is to say that we'd have coefficients c_{i}
(not all vanishing) for which:
0 =
c_{1} x^{l1} +
c_{2} x^{l2} + ... +
c_{n} x^{ln}
for at least n positive values of x.
So,
0 =
c_{1} +
c_{2} x^{l2 l1} + ... +
c_{n} x^{ln l1}
for those same values.
By Rolle's theorem, the
derivative of the righthand side would
vanish at least once in each of the n1 intervals separating the n known distinct roots.
So would that derivative multiplied into the positive quantity x. Therefore:
0 =
c_{2} (l_{2} l_{1})
x^{l2 l1} + ... +
c_{n} (l_{n} l_{1})
x^{ln l1}
for at least n1 values of x>0
(20121007) Cholesky reduction of a Hermitian matrix:
There's a lowertriangular matrix L such that L L* = A
By definition, a lowertriangular matrix is a matrix with
only zero elements above the diagonal.
This decomposition was introduced by the French engineer
AndréLouis Cholesky
in the special case where the matrix A is a positivedefinite
symmetrical real matrix. In that case,
the matrix L has real coefficients and nonzero diagonal elements.
The matrix L isn't unique, as
L,
(L*)^{t} and (L*)^{t} are satisfactory too.
A related construction which applies to any
definite Hermitian matrix
(not necessarily positive) involves a diagonal real matrix D
and a lowertriangular matrix L
whose diagonal elements are all equal to 1 (unity).
L D L* = A
Conversely, any matrix of this form is clearly Hermitian (A* = A).
In the special case where A is real, L
and D are real too.
The requirement of definiteness (no zero eigenvalue) can be dropped.
It's only useful to make the actual construction of L more
straightforward.
Applications :
Because the decomposition can be performed quite efficiently,
it can be used to solve a symmetric system of linear equations in real numbers
much faster than with generalpurpose Gaussian elimination
(such symmetrical systems arise in the
linear
least square method, in particular):
L L* x = b
The triangular systems
Ly = b and
L* x = y
are sequentially solved.
Cholesky's method was published posthumously in 1924.
It received little or no attention until World War II,
when Jack Todd
taught it in his analysis course at King's College, London.
In 1948, Alan Turing proved the
numerical stability of the procedure (after empirical results published the same year by
J.D. Fox, H.D. Huskey & J.H. Wilkinson).
Emma
Lehmer
proved that W_{n } vanishes if and only if
n is a multiple of 6.
The integer W_{n}
boils down to the circulant of n binomial coefficients
(more precisely, a line of Pascal's triangle,
without the rightmost "1").
The element at line i and column j is best described as equal to C(n,ij).
With the above notations, x_{j} = C(n,j)
[where j goes from 0 to n1 ]. So:
If p divides q , then W_{p}
divides W_{q} .
The n^{th} Mersenne number (2^{n}1)
divides W_{n} and the quotient
W_{n} / (2^{n}1) is a perfect square...
(20060118) Hankel Matrices & Hankel Transform
A Hankel matrix is a matrix whose skewdiagonals are constant.
(Such a matrix is also known as persymmetric or orthosymmetric.)
In other words, the value of the element on the i^{th} row and j^{th}
column of a persymmetric matrix
depends only on the sum of the indices (i+j).
M_{n} =
x_{0}^{ }
x_{1}^{ }
x_{2}^{ }
x_{3}^{ }
...
x_{n1}^{ }
x_{1}^{ }
x_{2}^{ }
x_{3}^{ }
x_{4}^{ }
...
x_{n}^{ }
x_{2}^{ }
x_{3}^{ }
x_{4}^{ }
x_{5}^{ }
...
x_{n+1}^{ }
x_{3}^{ }
x_{4}^{ }
x_{5}^{ }
x_{6}^{ }
...
x_{n+2}^{ }
...
...
...
...
...
...
x_{n1}^{ }
x_{n}^{ }
x_{n+1}^{ }
x_{n+2}^{ }
...
x_{2n2}^{ }
With those notations, the Hankel transform
of the sequence x_{n}
is defined to be the sequence
y_{n} = det ( M_{n+1 })
which starts with y_{0} = x_{0}.
Unfortunately, the above is not the only
thing called Hankel transform...
(20060118) Catberg Matrix_{ } The Hankel matrix of the reciprocals of Catalan numbers...
Its element on the i^{th} row and j^{th} column is
(i+j+1) / C(2i+2j , i+j).
(20070216) _{ } Sign Matrices, Phase Matrices
The elements of a phase matrix are complex numbers of module 1.
Thus, the elements of a phase matrix are
complex numbers of the form:
e^{ iq} =
cos q +
i sin q
[ where q is real ]
If such a matrix is real, it's called a sign matrix
(its elements are +1 or 1).
(20070124) _{ } Hadamard Matrices
( real or complex coefficients )
An Hadamard matrix consists of orthogonal
rows of unit elements.
Introduction (real coefficients) :
In the realm of real numbers,
Hadamard matrices are square matrices whose elements are
either 1 or +1 and whose rows are pairwise orthogonal.
They're named after the Frenchman Jacques
Hadamard (18651963) the very influential longlived analyst who gave
functional analysis its name (1910) and will always be
remembered for his 1896 proof of the Prime Number Theorem,
simultaneous with the independent proof from Charles de la
ValléePoussin
(18661962).
In 1893, Hadamard did write an important paper about those matrices,
but they were actually first investigated in 1867,
under the quaint name of anallagmatic pavements,
by James Joseph Sylvester (18141897).
Such matrices are often represented graphically as square mosaics of
square tiles that are either light or dark...
Here are special Hadamard matrices,
known as Walsh matrices, whose orders are
powers of 2 (1, 2, 4, 8, 16).
In the socalled normalized cases,
one row and one column have a uniform color which is traditionally light
(so that there are ½ n(n+1) light squares
and ½ n(n1) dark ones).
The exact colorcode can't be fixed (as the opposite of
an Hadamard matrix
is also Hadamard) but we usually assume that the dominant (light) color stands
for the value +1. When its first column and its first row have a uniform value
of +1, the matrix is said to be dephased
(a jargon term discussed below,
originally applied to complex Hadamard matrices c. 1970).
The above serves to illustrate a remark of Sylvester (1867)
that an Hadamard matrix of order 2n
may be obtained from a known Hadamard matrix H of order n,
simply by juxtaposing four copies of H and negating one of those:
H
H
H
H
More generally, an Hadamard matrix of order mn
may be constructed from an Hadamard matrix K of order m and
an Hadamard matrix H of order n by substituting in K all occurrences of
+1 by H and all occurences of 1 by H
(the above is the special case m = 2).
In other words, the
Kronecker product
of two Hadamard matrices is also an Hadamard matrix...
Abstract Algebraic Definition (real or complex realm) :
Hadamard matrices of order n may be defined as square matrices of order n
whose elements have unit length ( modulus )
and which verify the relation:
M M* = n I_{n}
In this, M* is the transpose of a real matrix M or, more generally,
the transpose conjugate
of a complex one. Matrices with complex
elements of unit moduli which satisfy the above relation are called
complex Hadamard matrices.
They were introduced in 1970 by Richard J. Turyn
(1930?)
as interesting generalizations of the more traditional (real) Hadamard matrices,
which can be considered to be merely of a restricted subtype.
A (complex) Hadamard matrix is trivially obtained from another by using one or
several of the following types of transformations:
Multiply a row or a column by an element of unit modulus (like 1).
Replace a row or a column by its (elementwise) conjugate.
Permutate rows or permutate columns.
Matrices so obtained from each other are said to be
Hadamardequivalent.
A complex Hadamard matrix where all firstrow and firstcolumn elements
are equal to 1 is said to be dephased.
Any complex Hadamard matrix is equivalent to a dephased one
(HINT: Use the first type of transformations.)
It's not difficult to prove that all
complex Hadamard matrices of order 2 are
Hadamardequivalent to
the aforementioned Walsh matrix of order 2.
=
1
1
1
1
Similarly, there's essentially only one complex Hadamard matrix of order 3.
It involves a primitive cube root of 3,
denoted w :
1
1
1
where
w
= w_{3}
= ½ (1 + i Ö3 )
1
w
w^{2}
1
w^{2}
w
That's an example of a socalled ButsonHadamard matrix,
namely a complex Hadamard matrix of order n whose elements are
pth roots of unity. Those were first discussed in 1961 by
Alton T. Butson
(19261997)
before Turyn's general approach to complex Hadamard matrices (1970).
For any order n, one example of a ButsonHadamard matrix
is given by the Vandermonde matrix
of all the nth roots of unity
(which is Hadamardequivalent
to their circulant matrix).
Another example is provided, for any
composite
order, by extending to complex Hadamard matrices what we've
already remarked about real ones, namely that the Kronecker product of
two (complex) Hadamard matrices is a (complex) Hadamard matrix.
In particular, if H is a complex Hadamard matrix of order m,
a complex Hadamard matrix of order 3m is obtained from the following pattern:
H
H
H
where
w
= w_{3}
= ½ (1 + i Ö3 )
H
w H
w^{2} H
H
w^{2} H
w H
This can be applied repeatedly to obtain the following ternary equivalent of
the aforementioned
(binary) Walsh matrices, using a threecolor code:
For any odd prime p,
a complex Hadamard matrix whose elements are p^{th }
roots of unity must have an order which is a multiple of p.
Conversely, it is conjectured that such matrices exist for any order which is a multiple
of p.
The existence of ordinary (real) Hadamard matrices
(as discussed next) can be construed to
be the case p=2,
for which a slightly different rule holds...
Existence of (Real) Hadamard Matrices of Order n :
Back to ordinary Hadamard matrices (whose elements are either 1 or +1).
The empty matrix (of order 0) is vacuously
an Hadamard matrix.
The order of any Hadamard matrix
must be 1, 2, or a multiple of 4 (Hadamard, 1893).
Conversely,
the HadamardPaley conjecture (better known as the Hadamard Conjecture )
states that there are Hadamard matrices of all such orders...
In 1933, Raymond Paley used finite fields
to construct Hadamard matrices of all orders of the form q+1
(resp. 2q+2) where q is the power of
a prime congruent to 3 (resp. 1) modulo 4.
Paley's Theorem states that Hadamard matrices
can be constructed (using
Paley's construction
and the aforementioned construction of Sylvester)
for all positive orders divisible by 4 except
those in the following sequence (i.e.,
multiples of 4 not equal to a power of 2 multiplied
by q+1, for some power q of an odd prime):
For many of those remaining orders,
Hadamard matrices have been discovered by other methods.
Here's a brief summary...
In 1962, Baumert, Golomb,
and Hall found an Hadamard matrix of order 92, using
the general approach
introduced in 1944, by John Williamson
(who so constructed an Hadamard matrix of order 172).
A Williamson matrix of order 4m is an Hadamard matrix obtained as follows from 4 matrices of
order m (with unit elements) A, B, C and D,
provided 4 matching relations are satisfied:
For example, we may build an Hadamard matrix of order 12 with 4 matrices of order 3,
by letting one of them be the matrix U whose 9 elements are equal to +1
(the square of U is 3U) while the 3 others are equal to U2I.
With A = U, the resulting Hadamard matrix of order 12
(which isn't normalized in the above sense)
is shown graphically below, next to the Hadamard matrices of order 24 and 48
obtained from it with the aforementioned Sylvester construct:
It turns out that all (real) Hadamard matrices of order 12 are
equivalent.
In particular, the above order12 Hadamard matrix is Hadamardequivalent to
the following, which is normalized (dephased) and symmetrical:
In 1985, K. Sawade found an Hadamard matrix of order 268.
If we denote by M the symmetrical of any M with respect to its
antidiagonal,
the above matrix
is based on 4 matrices A, B, C, D of order m = 107
put together in the following pattern, which gives an Hadamard matrix
of order 4m if and only if all the 10 conditions listed are met.
(Note that MN = N M .)
A
B
C
D
AA* + BB* + CC* + DD* = 4 m I_{m}
B B* = BB*
C C* = CC*
D D* = DD*
B
A
D
C
C
D
A
B
D
C
B
A
A B*  B A* = D C*  C D*
A C*  C A* = B D*  D B*
A D*  D A* = B C*  C B*
A B*  B A* = D C*  CD*
A C*  C A* = B D*  DB*
A D*  D A* = C B*  BC*
Since June 2004, the order
668 has been the smallest multiple of 4
for which no Hadamard matrix is yet known
(as of July 2014).
Usage note :
Both spellings "a Hadamard matrix" and "an Hadamard matrix" can be construed
as correct:
The former one applies to an anglicized pronounciation of "Hadamard"
("h" and "d" both pronounced) whereas the latter must be used with
the original French pronounciation
(initial "h" and final "d" both silent).
(20061231) _{ } Sylvester matrix of two polynomials
The resultant of two polynomials is the determinant of that matrix.
Consider two polynomials A and B of respective degrees m and n.
m
n
A =
å
a_{i} x^{ i}
B = ^{ }
å
b_{j} x^{ j}
i = 0
j = 0
Their Sylvester matrix is a square matrix (of dimension m+n) whose
first n rows feature the m+1 coefficients of A and whose last m rows feature the
n+1 coefficients of B. It is defined as follows:
M_{m+n} =
a_{m}^{ }
a_{m1}^{ }
a_{m2}^{ }
a_{m3}^{ }
...
0_{ }^{ }
0_{ }^{ }
a_{m}^{ }
a_{m1}^{ }
a_{m2}^{ }
...
0_{ }^{ }
0_{ }^{ }
0_{ }^{ }
a_{m}^{ }
a_{m1}^{ }
...
0_{ }^{ }
...
...
...
...
...
...
0_{ }^{ }
0_{ }^{ }
0_{ }^{ }
...
a_{0}^{ }
0_{ }^{ }
0_{ }^{ }
0_{ }^{ }
0_{ }^{ }
...
a_{1}^{ }
a_{0}^{ }
b_{n}^{ }
b_{n1}^{ }
b_{n2}^{ }
b_{n3}^{ }
...
0_{ }^{ }
...
...
...
...
...
...
0_{ }^{ }
0_{ }^{ }
0_{ }^{ }
...
b_{1}^{ }
b_{0}^{ }
The determinant of that matrix equals the socalled
resultant of A and B
which may be expressed as follows,
in terms of all the complex roots
(a_{i} ,
b_{j })
of those polynomials and their leading coefficients
a_{m} and b_{n} :
m
n
r (A,B) =
det ( M_{m+n }) =
(a_{m })^{ n} (b_{n })^{ m}
(20061231) Discriminant of a polynomial _{ }
(Sylvester, 1851)
The resultant of a polynomial and its derivative.
The word "discriminant" was coined by James Joseph Sylvester
(18141897) who found the correct expression for cubic polynomials (in 1851)
and generalized it to any polynomial (including the wellknown quadratic case).