On Generalizing the Method of Scarpis to Complex Hadamard Matrices

Mason Sargent1, Kaitlyn Lee1, Jeff Rushall1
1Department of Mathematics and Statistics, Northern Arizona University, Flagstaff, Arizona, USA, 86011

Abstract

A complex Hadamard matrix is a matrix Hn{ωi|1im}n×n of order n, where ω is a primitive mth root of unity, that satisfies HnHn=nIn, where Hn denotes the complex conjugate transpose of Hn. 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 n×n matrix Hn{±1}n×n that satisfies HnHnT=nIn. In 1896, Hadamard showed that every matrix M{±1}n×n satisfied the inequality det|(M)|nn/2, and any M{±1}n×n 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) ri,rj satisfies rirj=0 if and only if ij. It is straightforward to show the following (see [1] for details).

Proposition 1. If Hn is a Hadamard matrix of order n, then:

  1. n must be 1,2 or 4k, where kN.

  2. Both Hn and HnT are also Hadamard.

  3. Permuting rows and/or columns leaves Hn Hadamard.

  4. Multiplying any row or column by 1 leaves Hn Hadamard.

Two Hadamard matrices Hn and Hn of order n are equivalent, denoted HnHn, if Hn can be obtained from Hn 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 1’s in the initial row and column.

In 1896, Scarpis [2] published an unusual technique for constructing Hadamard matrices of order p(p+1), where p is a prime with p3( 4). 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 q(q+1) where q is any prime power with q3( 4). 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 <40,000. Moreover, the results of Mukhopadhyay are based on the existence of L-matrices, but no examples of L-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 Hn be a normalized Hadamard matrix of order n=p+1, where p3( 4) is prime.

  1. Arrange the columns of Hn so that row 2 consists of alternating 1’s and 1’s.

  2. Construct H2, the matrix formed by deleting the 2nd row of Hn.

  3. Construct the p×p(p+1) matrix M=H2J (J is the 1×p vector of 1’s).

  4. Construct C, the core of Hn, whose rows are denoted a0,a1,,ap1.

  5. For each 0rp1, construct the p×p(p+1) block matrix Mr defined by Mr=[ara0ara2ra(p2)ra(p1)rara1ar+1a2r+1a(p2)r+1a(p1)r+1arap1ar+(p1)a2r+(p1)a(p2)r+(p1)a(p1)r+(p1)]. Then the block matrix M below is a Hadamard matrix of order p(p+1): M=[M M0 M1  Mp1]T.

Figure 1 is for a color-coded example of a Scarpis Hadamard matrix, constructed using the prime p=7. As mentioned in [7], the Scarpis construction, used in conjunction with the methods of Paley and Sylvester, results in new orders of Hadamard matrices.

3. A Generalization of the Scarpis Construction

Given any primitive mth root of unity ω, a complex Hadamard matrix of order n, or CHM, often called a Butson-type Hadamard matrix, is a matrix Hn{ωi|1im}n×n that satisfies HnHn=nIn, where Hn denotes the complex conjugate transpose of Hn. Unlike the real case, there exists a CHM of every order. The following are well-known results, see [1] for details.

Proposition 3. If Hn is a CHM, then

  1. Permuting rows and/or columns of Hn yields a CHM.

  2. Each of Hn, HnT and Hn is also a CHM.

  3. Multiplying a row/column of Hn by any mth root of unity yields a CHM.

  4. If Hn is normalized, each noninitial row or column sums to 0.

Two CHMs Hn and Hn are equivalent, denoted HnHn, if Hn can be obtained from a permutation of the rows or columns of Hn, allowing any row or column to be multiplied by any mth root of unity.

The Scarpis construction generalizes directly into a CHM, but with two important differences: the construction can be based on any prime p, and any row may be deleted from Hn, the initial normalized CHM. Here is our generalization.

Theorem 1. Let p be any prime, and let Hn be a normalized CHM of order n=p+1. Now define the following

  1. rk, the kth row of Hn, whose entries are x1,x2,,xn.

  2. Hk, the p×n matrix resulting from removing rk from Hn.

  3. M, the order p(p+1) matrix defined via M=HkJ.

  4. C, the core of Hn, whose rows are in order a0,a1,,ap1.

  5. For each 0rp1, construct the p×p(p+1) matrix Mr, defined in block form as [x1arx2a0x3arx4a2rxn1a(p2)rxna(p1)rx1arx2a1x3ar+1x4a2r+1xn1a(p2)r+1xna(p1)r+1x1arx2ap1x3ar+(p1)x4a2r+(p1)xn1a(p2)r+(p1)xna(p1)r+(p1)]. Then the block matrix M below is a CHM of order p(p+1): M=[M M0 M1  Mp1]T.

We now give an example, using p=5, of this generalized Scarpis construction.

Example 1. Let p=5. Note that Hn=[11111111iiii1i1iii1ii1ii1iii1i1iiii1] is a normalized quaternary CHM. Deleting the third row of Hn gives us H3=[11111111iiii1ii1ii1iii1i1iiii1]. Note that r3=[1i1iii]. Also note that M=[11111111iiii1ii1ii1iii1i1iiii1][11111], which simplifies to [1111111111111111111111111111111111111111iiiiiiiiiiiiiiiiiiii11111iiiiiiiiii11111iiiiiiiiii11111iiiiiiiiiiiiiii11111iiiii11111iiiiiiiiiiiiiiiiiiii11111]. The core of H is C=[1iiiii1iiiii1iiiii1iiiii1]. We then label the rows of C as a0=[1iiii],a1=[i1iii],a2=[ii1ii],a3=[iii1i],a4=[iiii1]. Next, we construct each block matrix Mr. For brevity, we will only construct M0 M0=[a0ia01a0ia0ia0ia0a0ia11a1ia1ia1ia1a0ia21a2ia2ia2ia2a0ia31a3ia3ia3ia3a0ia41a4ia4ia4ia4], where M0 is a 5×30 matrix and each ai block is of size 1×5. Note, for instance, that ia2=i[ii1ii]=[11i11]. Finally, we construct M:

M=[M M0 M1 M2 M3 M4]T.

For a color-coded visual representation of M, see Figure 2.

Proof. Given any prime p, to prove that the matrix M in the statement of Theorem 1 yields a CHM, we will show that every pair of distinct rows of M is mutually orthogonal. To begin, note that the orthogonality of pairs of distinct rows of M=HkJ follows directly from the orthogonality of the rows of Hn.

Secondly, we must show pairwise orthogonality of distinct rows within each Mr. To this end, we fix r and compare two rows of Mr. Recall that the row blocks that build these rows are generated from the rows of C. 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 p: any two rows of Mr will, by definition, include one pair of row blocks of C that are identical, while the remaining n=p+1 pairs of row blocks of C will be distinct.

Let at=[at,1at,2at,p] be any row of C. Because the entries in at are roots of unity, it follows that atat¯=p, since at is a vector of length p. Also note that because each an is a row of the core of a normalized matrix with all distinct rows pairwise orthogonal, each of their inner products are 0. Since C is the core of Hn, it follows that for distinct s and t, atas¯=1.

Thirdly, we must show that each row of M is orthogonal to each row of Mr. Consider the inner product of the bth row of M and an arbitrary row of Mr for some r, which involves products of the form yiJxiat¯, where xi is an arbitrary entry in rk and yi is an arbitrary entry in a row of Hn distinct from rk and J is the 1×p vector of all 1’s. Since C is the core of Hn, the elements in each row of C sum to 1. Thus, yiJxiat¯=(yixi¯)Jat¯=yixi¯(at,1¯+at,2¯++at,p¯)=yixi¯(1)=yixi¯. It then follows that inner product of the entire bth row of M and an arbitrary row of Mr for some r is y1x1¯+y2x2¯++ynxn¯=0, since this is the complex inner product of two rows of the original complex Hadamard matrix Hn.

Lastly, we must show that for any rs, the rows of Mr and Ms are pairwise orthogonal. Let u denote the αth row of Mr, and let v denote the βth row of Ms, where 0α,βp1. That is,

u=[x1arx2aααx3a(r+αα)xna(p1)r+αα)],

v=[x1asx2aββx3a(s+ββ)xna(p1)s+ββ)].

Note that the inner product of u and v satisfies

uv¯=aras¯+i=0p1air+ααais+ββ¯,

where the subscripts are reduced modulo p. This sum will have p 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 i that satisfies i(rs)βα(mod p). It then follows that uv=0. Therefore, M is a CHM. ◻

As Djokovic shows in [3], the classic Scarpis construction can be modified to generate Hadamard matrices of order q(q+1) where q is any prime power and q3( 4). This restriction on q is unnecessary in CHM constructions as CHMs can exist of order p+1 where p1( 4).

Let CHn be the set of complex Hadamard matrices of a given order n and let Fq denote the unique finite field of order q. Given a bijection α:{0,1,2,3,q1}Fq, where q is an odd prime power, the algorithm described in Theorem 1 yields a map Φq,α:CHqCHq(q+1), in which the multiplication occurs in Fq – specifically, ai=aα(i) and ajr+k=aα(j)α(r)+α(k). These observations lead to the following generalization of Theorem 1.

Corollary 1. Let H be a CHM of order q+1 where q is an odd prime power. Then there exists a CHM of order q(q+1).

It is worth noting that the pattern of + and – signs in the 2nd row removed from Hn in the classic Scarpis construction is identical to the pattern of + and – signs attached to the columns of each block matrix Mr. This is not a coincidence. In fact, just as in our generalized Scarpis construction, any row could have been removed from Hn in the classic Scarpis construction. In a similar vein, Scarpis unnecessarily negated the core of Hn in his construction, whereas Djokovic does not do so in his generalization to prime powers. In what follows, we let H(k;) denote a given matrix H with the kth row removed.

Corollary 2. In the classic Scarpis construction, given any 1kp+1, let x1,x2,xn denote the entries of the removed kth row, and let H(k;) denote the remaining matrix. The resulting block matrices Mr for 0rp1 that comprise the resulting Scarpis Hadamard matrix are given by [x1arx2a0x3arx4a2rxn1a(p2)rxna(p1)rx1arx2a1x3ar+1x4a2r+1xn1a(p2)r+1xna(p1)r+1x1arx2ap1x3ar+(p1)x4a2r+(p1)xn1a(p2)r+(p1)xna(p1)r+(p1)].

It appears that each choice of a kth deleted row of the original CHM results in the larger Scarpis-constructed CHM. The different choices of k 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 p+1st root of unity as the initial seed matrix. See Figure 3 for an example.

Open Problem In our generalized complex Scarpis construction, determine conditions under which the choices of a kth 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:

  1. Horadam, K.J., Hadamard Matrices and Their Applications. Princeton University Press, 2007.

  2. Scarpis, U., 1898. Sui determinanti di valore massimo. Rendiconti della R. Istituto Lombardo di Scienze e Lettere, 31(2), pp.1441-1446.

  3. Dragomir, Ž., and Doković, 2017. ’Generalization of Scarpis’ theorem on Hadamard matrices’. Linear and Multilinear Algebra, 65(10), pp. 1985-1987.

  4. Williamson, J. 1944. Hadamard’s Determinant Theorem and the Sum of Four Squares. Duke Mathematical Journal, 11(1), pp.65-81.

  5. Mukhopadhyay, A.C., 1978. Some infinite classes of Hadamard matrices. Journal of Combinatorial Theory, Series A, 25(2), pp.128-141.

  6. Seberry, J., 1980. Some infinite classes of Hadamard matrices. Journal of the Australian Mathematical Society, 29(2), pp.235-242.

  7. Hedayat, A.S., Sloane, N.J.A. and Stufken, J., 2012. Orthogonal Arrays: Theory and Applications. Springer Science & Business Media.