Related Links (Outside this Site)

---

(2006-12-26)   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 so-called exchange matrix (J) which is the "mirror image" of the identity matrix itself.  For example:

I6   =		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

J6   =		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 finite-dimensional resemblance with the identity matrix, there's no nice generalization of the exchange matrix to infinitely many dimensions.

---

(2007-02-13)   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, may be denoted  a_ij

However, the correspondence should be made explicit for  every  new matrix involved in symbolic computations or proofs,  since the name of the doubly-subscripted symbol is not directly related to the name of the matrix itself  (A)... 

This flaw is avoided by the nice self-contained notation  (due to P.A.M. Dirac) shown on the right-hand side of the following equation:

a_ij   =   < i | A | j >

This is sometimes called the  element  of  A  between  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 are not needed to use the notation as a whole in some definitions and proofs.  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 >   =   S_k  < i | A | k >  < k | B | j >

That rule for matrix multiplication was discovered in 1812  (using more traditional index notations)  by Jacques Binet (1786-1856; X1804)  who is remembered for the Binet formulas which allow an easy proof that the orbits of two gravitating bodies are conic sections.  Binet also gave his name to the explicit expression for the n-th term of a sequence obeying a second-order recurrence  (especially the Fibonacci sequence).

If we denote by  z*  the conjugate  a-ib  of the complex number  z = a+ib,  (z=z* when z is a real number)  then we may define as follows the  conjugate transpose  A*  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, dual, adjugate or simply conjugate.  It's called transpose in the case of real matrices.

Here's how we may prove for matrices the relation which gives the adjoint of a product:  (AB)* =  B* A*  (this relation holds for whatever is called "adjoint" or "dual" among other multiplicative objects for which the term is defined).

< i | (AB)* | j >	=   < j | AB | i >*
	=   Sk  < j | A | k >*  < k | B | i >*
	=   Sk  < k | A* | j >  < i | B* | k >
	=   Sk  < i | B* | k >  < k | A* | j >
	=   < i | B* A* | j >

---

(2006-01-18)   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 ) ⁱ.  [Some authors consider the transpose of this.]

Mn+1   =		1	1	1	1	...	1
		x0	x1	x2	x3	...	xn
		x02	x12	x22	x32	...	xn2
		x03	x13	x23	x33	...	xn3
		...	...	...	...	...	...
		x0n	x1n	x2n	x3n	...	xnn

The determinant of the above Vandermonde matrix has a nice expression:

	n-1		n
det ( Mn+1 )   =	Õ		Õ	( xj - xi )
	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.  As such polynomials can only differ by a constant factor, they are necessarily equal if  some  like terms in both of them are equal.  Such an equality is easily proven for the "last" term, by induction on  n.  (HINT:  The coefficient of the last variable raised to the n-th power is the Vandermonde determinant for the n previous variables.) 

Alexandre-Théophile Vandermonde (1735-1796)

The above Vandermonde determinant and Vandermonde matrix are named after the French mathematician Alexandre-Théophile Vandermonde (1735-1796) who is the rightful founder of the modern theory of determinants...

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 Bezout (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 high-school 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 Abel-Ruffini 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.

---

(2006-01-18)   Toeplitz Matrices
A Toeplitz matrix is a matrix whose diagonals are constant.

In other words, the value of the element on the i^th row and j^th column of a  Toeplitz matrix  depends only on the difference  (j-i).

Mn   =		x0	x1	x2	x3	...	xn-1
		x-1	x0	x1	x2	...	xn-2
		x-2	x-1	x0	x1	...	xn-3
		x-3	x-2	x-1	x0	...	xn-4
		...	...	...	...	...	...
		x1-n	x2-n	x3-n	x4-n	...	x0

Such matrices have been named after  Otto Toeplitz  (1881-1940).

---

(2006-12-25)   Circulant Matrices & Circulant Determinants
A  circulant matrix  is a nice special case of a Toeplitz matrix.

The value of the element on the i^th row and j^th column of an  n  by  n    circulant matrix  depends only on the difference  (j-i)  modulo n.

Mn   =		x0	x1	x2	x3	...	xn-1
		xn-1	x0	x1	x2	...	xn-2
		xn-2	xn-1	x0	x1	...	xn-3
		xn-3	xn-2	xn-1	x0	...	xn-4
		...	...	...	...	...	...
		x1	x2	x3	x4	...	x0

Each row is thus equal to the previous row shifted one place to the right.

The determinant and eigenvalues  ( l_k )  of the above circulant matrix are:

	n-1				n-1
det ( Mn )   =	Õ	lk		lk   =	å	w jk  xj
	k = 0				j = 0

In this,  w  =  exp ( ^2ip/_n )  is a  primitive  n^th  root of unity.  For example:

a b   b a

=   a 2 - b 2   =   ( a + b ) ( a - b )

 

	a b c   c a b   b c a		=   a 3 + b 3 + c 3  -  3 abc     =   ( a + b + c ) ( a + w b + w2 c ) ( a + w2 b + w c )
			with   w  =  w3  =  ½ (-1 + i Ö3 )

 

	a b c d   d a b c   c d a b   b c d a		=   a 4 - b 4 + c 4 - d 4 - 2 a 2 c 2 + 2 b 2 d 2
			- 4 a 2 bd + 4 ab 2 c - 4 bc 2 d + 4 acd 2
			=   (a+b+c+d) (a+ib-c-id) (a-b+c-d) (a-ib-c+id)

The determinant of a circulant matrix is commonly called the  circulant determinant  or, for short, the  circulant  of the  n  coefficients involved.  (The order of those coefficients is relevant only when  n  is even.)

---

(2006-12-27)   Wendt's Determinant   ( W_n )
The circulant of the binomial coefficients.   (A048954)

In his investigation of  Fermat's Last Theorem,  E. Wendt introduced this  integer  as the resultant of the polynomials  Xⁿ-1  and  (X+1)ⁿ-1.  E. Lehmer proved that  W_n  vanishes if and only if   n  is a multiple of 6.

This quantity boils down to the circulant of the binomial coefficients  (namely, a line of Pascal's triangle, without the rightmost "1").

With the above notations, x_j = C(n,j)  [where  j  goes from  0  to  n-1 ].  So:

	n-1
Wn   =   det ( Mn )   =	Õ	[ ( 1 + wnk ) n - 1 ]
	k = 0

 

If  p  divides  q ,  then  W_p  divides  W_q .  The n^th Mersenne number  (2ⁿ-1)  divides  W_n  and the quotient  |W_n| / (2ⁿ-1)  is a perfect square...

---

(2006-01-18)   Hankel Matrices & Hankel Transform
A Hankel matrix is a matrix whose skew-diagonals 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).

Mn   =		x0	x1	x2	x3	...	xn-1
		x1	x2	x3	x4	...	xn
		x2	x3	x4	x5	...	xn+1
		x3	x4	x5	x6	...	xn+2
		...	...	...	...	...	...
		xn-1	xn	xn+1	xn+2	...	x2n-2

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₀ = x₀.

Unfortunately, the above is not the only thing called  Hankel transform...

---

(2006-01-18)   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).

---

(2007-02-16)   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).

---

(2007-01-24)   Hadamard Matrices 
An Hadamard matrix consists of orthogonal rows of unit elements.

Introduction :

In the realm of real numbers, an Hadamard matrix is a square matrix whose elements are all either -1 or +1 and whose rows are pairwise orthogonal.

Such matrices are named after the Frenchman Jacques Hadamard (1865-1963) who is also remembered for his 1896 proof of the Prime Number Theorem (simultaneous with, and independent from, the proof of  de la Vallée-Poussin ).  In 1893, Hadamard did write an important paper about those matrices, but Hadamard matrices were actually first investigated in 1867, under the quaint name of  anallagmatic pavements,  by James Joseph Sylvester (1814-1897).

They may be 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 and 16).

In this, the light color stands for +1.  The usual convention in  normalized  cases where one whole row and one whole column have a uniform color is indeed that this color stands for +1.  In a normalized Hadamard matrix, there are  ½ n(n+1)  positive elements and  ½ n(n-1)  negative ones.  (The color code is relatively unimportant, since the opposite of an Hadamard matrix is also Hadamard.)

The above also serves to illustrate an observation 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 :

Hadamard matrices of order n may also be defined as square matrices of order n whose elements have an absolute value of 1 (one) 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.  Those were introduced in 1970 by R.J. Turyn, as proper generalizations of the ordinary (real) Hadamard matrices.  Many property of ordinary Hadamard matrices may just as well be discussed in the complex realm.  For example:

A (complex) Hadamard matrix is trivially obtained from another by using one or several of the following transformations.

• Multiply a row or a column by an element of unit modulus (like -1).
• Replace a row or a column by its (element-wise) conjugate.
• Permutate rows or permutate columns.

Matrices so obtained from each other are said to be  Hadamard-equivalent.  A complex Hadamard matrix where all first-row and first-column 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 the above transformations.)

It's not difficult to prove that all  complex Hadamard matrices  of order 2 are Hadamard-equivalent 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  =  w3  =  ½ (-1 + i Ö3 )
	1	w	w2
	1	w2	w

That's an example of a so-called  Butson-Hadamard matrix, namely a complex Hadamard matrix of order  n  whose elements are  n-th roots of unity.  Those were first discussed by A.T. Butson in 1962  (before Turyn introduced more general complex Hadamard matrices in 1970).

For any order n, one example of a Butson-Hadamard matrix is given by the Vandermonde matrix of all the n-th roots of unity  (which is Hadamard-equivalent 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  =  w3  =  ½ (-1 + i Ö3 )
	H	w H	w2 H
	H	w2 H	w H

This can be applied repeatedly to obtain the following ternary equivalent of the aforementioned (binary) Walsh matrices, using a three-color 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 :

We're back to usual 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 Hadamard-Paley 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.  The ensuing  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.  (These are multiples of  4  not equal to a power of  2  multiplied by q+1, for some power q of an odd prime.)

92, 116, 156, 172, 184, 188, 232, 236, 260, 268, 292, 324, 356, 372, 376, 404, 412, 428, 436, 452, 472, 476, 508, 520, 532, 536, 584, 596, 604, 612, 652, 668, 712, 716, 732, 756, 764, 772, 808, 836, 852, 856, 872, 876, 892, 904, 932, 940, 944, 952, 956, 964, 980, 988, 996, 1004, 1012, 1016, 1028, 1036, 1068, 1072, 1076, 1100, 1108, 1132, 1148, 1168, 1180, 1192, 1196, 1208, 1212, 1220, 1244, 1268, 1276, 1300, 1316, 1336, 1340, 1364, 1372, 1380, 1388, 1396, 1412, 1432, 1436, 1444, 1464, 1476, 1492, 1508, 1528, 1556, 1564, 1588, 1604, 1612, 1616, 1636, 1652, 1672, 1676, 1692, 1704, 1712, 1732, 1740, 1744, 1752, 1772, 1780, 1796, 1804, 1808, 1820, 1828, 1836, 1844, 1852, 1864, 1888, 1892, 1900, 1904, 1912, 1916, 1928, 1940, 1948, 1960, 1964, 1972, 1976, 1992, 2008, 2024, 2032, 2036, 2052, 2056, 2060, 2072, 2076, 2092, 2108, 2116, 2136, 2148, 2152, 2156, 2164, 2172, 2200, 2212, 2216, 2228, 2264, 2276, 2284, 2292, 2296, 2300 ... (A046116)

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:

	A	B	C	D			AA* + BB* + CC* + DD*   =   4 m  Im AB* - BA*   =   CD* - DC* AC* - CA*   =   DB* - BD* AD* - DA*   =   BC* - CB*
	-B	A	D	-C
	-C	-D	A	B
	-D	C	-B	A

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  U-2I.

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 order-12 Hadamard matrix is Hadamard-equivalent to the following Hadamard matrix, which is normalized (dephased) and symmetrical:

In 1985, K. Sawade found an Hadamard matrix of order 268.

In June 2004, Hadi Kharaghani and Behruz Tayfeh-Rezaie built the Hadamard matrix of order 428  illustrated below  (1 pixel per matrix element).

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 M N  =  N M .)

	A	B	C	D			AA* + BB* + CC* + DD*   =   4 m  Im B B*  =  B B* C C*  =  C C* D D*  =  D D*
	-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* - C D* A C* - C A*   =   B D* - D B* A D* - D A*   =   C B* - B C*

 

Since June 2004,  the order  668  has been the smallest multiple of 4 for which no Hadamard matrix is yet known  (as of January 2007).

Hadamard Matrix :   Wikipedia  |  MathWorld

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 proper French pronounciation  (initial "h" and final "d"  both  silent).

---

(2006-12-31)   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   =	å	ai x i		B   =	å	bj 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:

Mm+n   =		am	am-1	am-2	am-3	...	0
		0	am	am-1	am-2	...	0
		0	0	am	am-1	...	0
		...	...	...	...	...	...
		0	0	0	...	a0	0
		0	0	0	...	a1	a0
		bn	bn-1	bn-2	bn-3	...	0
		...	...	...	...	...	...
		0	0	0	...	b1	b0

The determinant of that matrix equals the so-called  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 ( Mm+n )   =     (am ) n (bn ) m	Õ		Õ	( ai - bj )
	i = i		j = 1

---

(2006-12-31)   Discriminant of a polynomial   (Sylvester, 1851)
The resultant of a polynomial and its derivative.

The word "discriminant" was coined by James Joseph Sylvester (1814-1897) who found the correct expression for cubic polynomials (in 1851) and generalized it to  any  polynomial  (including the well-known quadratic case).