A complex Hadamard matrix is a matrix of order , where is a primitive root of unity, that satisfies , where denotes the complex conjugate transpose of . We show that the Scarpis technique for constructing classic Hadamard matrices generalizes to Butson-type complex Hadamard matrices.
Keywords: Hadamard, Determinant, Complex
1. Introduction
A Hadamard matrix is an matrix that satisfies . In 1896,
Hadamard showed that every matrix satisfied the inequality det, and any that met
this upper bound was Hadamard. It follows from this definition that if a
matrix is Hadamard, the inner product of any two rows (or columns) satisfies
if and only if . It is
straightforward to show the following (see [1] for details).
Proposition 1. If is a Hadamard matrix of order , then:
must be or , where .
Both and are also
Hadamard.
Permuting rows and/or columns leaves Hadamard.
Multiplying any row or column by leaves Hadamard.
Two Hadamard matrices and
of order are equivalent, denoted , if can be obtained from by permuting rows, permuting
columns, and negating rows and columns. It is easy to show that generates an equivalence relation on
the set of all Hadamard matrices of a given order. A resulting
equivalence class is often represented by a normalized Hadamard
matrix – that is, a Hadamard matrix with all ’s in the initial row and column.
In 1896, Scarpis [2]
published an unusual technique for constructing Hadamard matrices of
order , where is a prime with . His approach appears somewhat ad hoc
and is awkward to implement, which may be one of the reasons that his
method, while sound, has not received the same attention as the more
straightforward approaches of, among others, Sylvester and Paley. To
date, the only other direct use of the method of Scarpis appears in
[3], where Djokovic shows the
Scarpis construction also generates Hadamard matrices of order where is any prime power with . In this article, we will show that
the method of Scarpis can be generalized to construct complex Hadamard
matrices.
2. The Scarpis Construction
Before presenting both the Scarpis construction and our
generalization to CHMs, some historical clarification is needed.
Williamson [4] mentions,
but does not use, the method of Scarpis in his Hadamard constructions;
he simply compares the known orders of Hadamard matrices that result
from the methods of Paley and Scarpis to show that his results generate
new orders of Hadamard matrices.
Mukhopadhyay [5] identifies
some orders of Williamson Hadamard matrices that exist, but his approach
is based on the Paley construction, and these orders only coincide with
the orders of Hadamard matrices outlined by Scarpis in their base case.
In addition, Seberry [6] notes
that the Mukhopadhyay construction yields no new Hadamard matrices of
orders . Moreover, the
results of Mukhopadhyay are based on the existence of -matrices, but no examples of -matrices are provided. On the other
hand, both the original Scarpis method and our CHM-based generalization
are constructive. Thus, our main result, that the Scarpis construction
can be generalized to CHMs, is distinct from the work in [5] and [6].
Here is the original construction of Scarpis.
Proposition 2. Let be a normalized Hadamard matrix of
order , where is prime.
Arrange the columns of so that row consists of alternating ’s and ’s.
Construct , the
matrix formed by deleting the row of .
Construct the matrix ( is
the vector of
1’s).
Construct , the core of
, whose rows are denoted .
For each , construct the block matrix
defined by Then the block matrix below is a Hadamard matrix of order
:
Figure 1 is for a color-coded example of a Scarpis
Hadamard matrix, constructed using the prime . As mentioned in [7], the Scarpis construction, used
in conjunction with the methods of Paley and Sylvester, results in new
orders of Hadamard matrices.
Figure 1: A Scarpis Hadamard Matrix of Order , Using , Color-coded as
Indicated
3. A Generalization
of the Scarpis Construction
Given any primitive root
of unity , a complex
Hadamard matrix of order , or
CHM, often called a Butson-type Hadamard matrix, is a matrix
that satisfies , where denotes the complex conjugate
transpose of . Unlike the real
case, there exists a CHM of every order. The following are well-known
results, see [1] for
details.
Proposition 3. If is a CHM, then
Permuting rows and/or columns of yields a CHM.
Each of , and is also a CHM.
Multiplying a row/column of by any root of unity yields a
CHM.
If is normalized,
each noninitial row or column sums to .
Two CHMs and are equivalent, denoted , if can be obtained from a
permutation of the rows or columns of , allowing any row or column to be
multiplied by any root of
unity.
The Scarpis construction generalizes directly into a CHM, but with
two important differences: the construction can be based on any prime
, and any row may be deleted from
, the initial normalized CHM.
Here is our generalization.
Theorem 1. Let be any prime, and let be a normalized CHM of order . Now define the
following
,
the row of , whose entries are .
, the matrix resulting from removing
from .
, the order matrix defined via .
, the core of , whose rows are in order .
For each , construct the matrix , defined
in block form as Then the block matrix below is a CHM of order :
We now give an example, using , of this generalized Scarpis
construction.
Example 1. Let . Note that is a normalized quaternary CHM. Deleting the
third row of gives us Note that Also note that which simplifies to The core of is . We then label the rows of as Next, we construct each block matrix . For brevity, we will only construct
where is a matrix and each block is of size . Note, for instance, that
Finally, we construct :
.
For a color-coded visual representation of , see Figure 2.
Figure 2: A Color-coded Scarpis Quaternary CHM of
Order , Using and Selecting
Proof. Given any prime , to prove that the matrix in the statement of Theorem 1 yields
a CHM, we will show that every pair of distinct rows of is mutually orthogonal. To begin, note
that the orthogonality of pairs of distinct rows of follows
directly from the orthogonality of the rows of .
Secondly, we must show pairwise orthogonality of distinct rows within
each . To this end, we fix and compare two rows of . Recall that the row blocks that
build these rows are generated from the rows of . Note that one pair of row blocks in
one column are identical, whereas the remaining pairs of row blocks in
all other columns are distinct. It is clear that this is the case for
any prime : any two rows of will, by definition, include one pair
of row blocks of that are
identical, while the remaining pairs of row blocks of will be distinct.
Let be any row of . Because the entries in are roots of unity, it
follows that , since is a vector of length . Also note that because each is a row of the core of a
normalized matrix with all distinct rows pairwise orthogonal, each of
their inner products are . Since
is the core of , it follows that for distinct and , .
Thirdly, we must show that each row of is orthogonal to each row of . Consider the inner product of the
row of and an arbitrary row of for some , which involves products of the form
where is an arbitrary entry in and is an arbitrary entry in a row of
distinct from and is the vector of all ’s. Since is the core of , the elements in each row of sum to . Thus, It then follows that inner product of the entire
row of and an arbitrary row of for some is since this is the complex inner product of two
rows of the original complex Hadamard matrix .
Lastly, we must show that for any , the rows of and
are pairwise orthogonal. Let
denote the row of , and let denote the row of , where . That is,
,
.
Note that the inner product of and satisfies
,
where the subscripts are reduced modulo . This sum will have pairs of distinct vector products, and
exactly one such pair wherein the two vectors are the same. The matching
pair occurs at the unique value of that satisfies . It then follows that .
Therefore, is a CHM.
As Djokovic shows in [3],
the classic Scarpis construction can be modified to generate Hadamard
matrices of order where
is any prime power and . This restriction on is unnecessary in CHM constructions as
CHMs can exist of order where
.
Let be the set
of complex Hadamard matrices of a given order and let denote the unique finite
field of order . Given a bijection
where is
an odd prime power, the algorithm described in Theorem 1 yields a map in which the multiplication occurs in
– specifically,
and . These
observations lead to the following generalization of Theorem 1.
Corollary 1. Let be a CHM of order where is an odd prime power. Then there
exists a CHM of order .
It is worth noting that the pattern of + and – signs in the row removed from in the classic Scarpis construction
is identical to the pattern of + and – signs attached to the columns of
each block matrix . This is not
a coincidence. In fact, just as in our generalized Scarpis construction,
any row could have been removed from in the classic Scarpis construction.
In a similar vein, Scarpis unnecessarily negated the core of in his construction, whereas Djokovic
does not do so in his generalization to prime powers. In what follows,
we let denote a given matrix
with the row removed.
Corollary 2. In the classic Scarpis
construction, given any , let denote the entries of the removed row, and let denote the remaining matrix. The
resulting block matrices for
that comprise the
resulting Scarpis Hadamard matrix are given by
It appears that each choice of a deleted row of the original CHM
results in the larger Scarpis-constructed CHM. The different choices of
generally result in different
equivalence classes; however, this is not always true and it is unclear
under what circumstances this does not hold.
We note that our Scarpis-inspired CHM construction can be employed in
more general contexts, such as using Vandermonde matrices generated
using a primitive complex
root of unity as the initial seed matrix. See Figure 3 for an example.
Figure 3: Vandermonde-type Scarpis CHM Using Roots of Unity
In our
generalized complex Scarpis construction, determine conditions under
which the choices of a
deleted row of a given CHM results in larger Scarpis-constructed CHMs
belonging to different equivalence classes.
Acknowledgments
We thank the anonymous referees for their helpful comments.
References:
Horadam, K.J., Hadamard Matrices and Their
Applications. Princeton University Press, 2007.
Scarpis, U., 1898. Sui determinanti di valore massimo. Rendiconti
della R. Istituto Lombardo di Scienze e Lettere, 31(2),
pp.1441-1446.
Dragomir, Ž., and Doković, 2017. ’Generalization of Scarpis’ theorem
on Hadamard matrices’. Linear and Multilinear Algebra, 65(10),
pp. 1985-1987.
Williamson, J. 1944. Hadamard’s Determinant Theorem and the Sum of
Four Squares. Duke Mathematical Journal, 11(1), pp.65-81.
Mukhopadhyay, A.C., 1978. Some infinite classes of Hadamard matrices.
Journal of Combinatorial Theory, Series A, 25(2),
pp.128-141.
Seberry, J., 1980. Some infinite classes of Hadamard matrices.
Journal of the Australian Mathematical Society, 29(2),
pp.235-242.
Hedayat, A.S., Sloane, N.J.A. and Stufken, J., 2012. Orthogonal
Arrays: Theory and Applications. Springer Science & Business
Media.