数理解析研究所講究録 1394 巻 2004 年 88-96

88

ON THE CONSTRUCTION OF HADAMARD MATRICESROWENA T. BAY LONf
KYUSHU UNIVERSITYGRADUATE SCHOOL OF MATHEMATICS 33
FUKUOKA 812-8581
JAPAN
EMAIL: BAYLON@MATH.KYLTSHU-U.AC.JP-U.AC.JP$\mathrm{B}\mathrm{A}\mathrm{Y}\mathrm{L}\mathrm{O}\mathrm{N}\wedge\subset\underline{\mathrm{Q}|}\mathrm{M}\mathrm{A}\mathrm{T}\mathrm{H}.\mathrm{I}i\mathrm{Y}\mathrm{L}^{\mathrm{T}}\mathrm{S}\mathrm{H}\mathrm{U}$ABSTRACT. This paper constructs Hadamard matrices of order $4n$ . Given
the first 4 rows aixd columns of a Hadamard matrix of order $4n$ , we study
its $(n-1)\mathrm{x}(n -1)$ blodc matrix properties. Since the incidence matrices
of symmetric 2-designs do not violate the obtained properties, we use themin the construction. We obtained the total number of Hadamard matrix
construction structures by only using incidence matrices of symmetric %designs. Furthermore, at most 4 different incidence matrices with theircorresponding complements can have a Hadam ard matrix structure. Other
than this number is not possible.

1. INTRODUC.TION

A Hadamard matr of orderof 1’s and -1’s satisfying$r\dot{u}.r$$n$

is a square matrix $H$ whose entries consist$HH^{T}=nI$

where
is the transpose of $H$ and I is the identity matrix of order . It is
known that Hadamard matrices exist only when $n=2$ or is a multiple of 4.
However, the converse still remains as a conjecture at present [11]. In particular,$\leq 28,$ Hadamard matrices are completelyforclassified and the complete
listing of such matrices can be found in Sloane’s homepage[14]. This paper
aims to construct Hadamard matrices of order ,4 by investigating Kimura’s
structure [9] for length 32. We determine the appropriate parameters of all the$H^{T}$

$n$

$n$

$n$

$n$

Date: March 29, 2004.

\dagger This work is (partially) supported by Kyushu University 21st Century COE Program,
Development of Dynamic Mathematics with High Functionality, of the Ministry of Education, Culture, Sports, Science azxd Technology of Japan.

$\epsilon\epsilon$.

submatrices, having order $n-$ l, that will yield a Hadamard matrix of order$4n$ . It is seen that the appropriate choice of incidence matrices of symmetric
2- $(n-1, \frac{n}{2}- 1, \frac{n}{4}-1)$ designs and their corresponding complements can besuch submatrices. The obtained Hadamard matrices are generator matrices toself-0rthogonal codes over.
$\mathrm{G}\mathrm{F}(2)$2. THE CONSTRUCTION(mod 4). We construct a Hadamard matrix of order $4n$ ffom aLetgiven 2-(n-l,) Hadamard design O. We consider the following.
structure of a Hadamard matrix of order $4n$ and denote it by$n\equiv 0$$\frac{n}{2}-1,$ $\frac{n}{4}-1$.

$...\cdot..\cdot.\cdot$$...\cdot$$..-\cdot.\cdot.\cdot$$0000000111111111111111111111A_{1}B_{1}D_{1}C_{1}$$H_{4n}$$:=$$0000000111111111111111111111A_{3}B_{3}D_{3}C_{3}$$\mathrm{o}\mathrm{o}\mathrm{o}\mathrm{o}\mathrm{o}\mathrm{o}_{9},0111111111111111111111A_{A}B_{2}D_{2}C_{\vee}$$\{\begin{array}{l}1111110010101001111111111100\underline{1}10101010110011001\end{array}$.

$H_{4n}$..

$\cdot$(1)$0000000000000000000001111111A_{4}B_{4}D_{4}C_{4}^{\cdot}$

3. PROPERTIES OF THE (n$-1)\cross(n$ -1) BLOCK MATRICES, A2, ,
To construct matrix (1), we need to find the block matrices,, , , , , , , ,,,. All of these areand$(n-1)$ $\cross(n-1)$ matrices. We denote the weight (number of 1’s entry) of
a vector as $wt(x)$ and the number of l’s intersection between any two row
vectors , as $x*y.$$A_{1}$$A_{4}$$B_{1}$$B_{2}$$B_{3}$$B_{4}$$C_{1}$$C_{2}$$C_{3}$$C_{4}$$D_{1}$$D_{2}$$D_{3}$$A_{3}$$D_{4}$

$x$

$x$

$y$

,
,
,
Lemma 3.1. Roett vectors of block matrices Ax, A2,
andare of weight. Also, row vectors of block matrices B$,, , , andare of weight .
$A_{3\mathrm{z}}A_{4},$$D_{3}$$D_{2}$$C_{2}$$C_{4}$$D_{1}$$( \frac{n}{2}-1)$$D_{4}$$\frac{n}{2}$$B_{1}$$B_{2}$$C_{1}$$C_{3}$,$B_{4}$,

so
To construct matrix (1), we make use of the $(n-1)\cross$ (n –1) incidence
matrices of that is, block matrices , , A3, , , , , ,and) Hadamard designs
are incidence matrices of some 2-(n-l,, andare incidence matrices of some
and, block matrices , , , ,complements of the above designs. We can also consider incidence matrices
from inequivalent 2- ( $n-$ l,) Hadamard designs.
$M$Let
be the $(4n-4)$ $\cross(4n -4)$ matrix obtained from deleting the first fourrows and columns of matrix (1). Then
$A_{1}$$\mathfrak{D}$$A_{4}$$A_{2}$$D_{3}$$B_{1}$$B_{2}$$C_{1}$$C_{3}$$D_{2}$$\frac{n}{2}-1,$ $\frac{n}{4}-1$$B_{4}$$B_{3}$$C_{2}$$C_{4}$$D_{4}$$D_{1}$$\frac{n}{2}-1,$ $\frac{n}{4}-1$

$kI$

ABC:

$[_{D}$$:=$$|A_{2}D_{2}C_{2}B_{2}$$|\begin{array}{l}A_{3}B_{3}C_{3}D_{3}\end{array}|$(2)$D_{4}A_{4}B_{4}C_{4}]$We define $\beta_{i}(i=1,2,3,4)$ as follows:$\beta_{1}=(A_{1}, A_{2}, A_{3}, A_{4})$$\beta_{-},$$=(B_{1}, B_{2}, B_{3}, B_{4})$$\beta_{3}=(C_{1}, C_{2}, C_{3}, C_{4})$$\beta_{4}=(D_{1}, D_{2}, D_{3}, D_{4})$be the set of $(n-1)\cross(n-1)$ incidence matrices of some 2– $(n-$, 7-1, $-1$ ) designs andbe an element of . Denoteas the incidence$S’$matrix of its corresponding complement andas the set of. We check$M$some conditions of the block matrices into obtain different constructionsof a Hadamard matrix using the given structure. Also, we determine the maximum number of distinct matrices from which can altogether construct a
Hadamard matrix. Observe thatsince matrix $M$ has 16 block matrices.
Let

$S$

$1$

$S$

$M_{i}$$\mathrm{j}$$M_{i}’$$M_{i}’$$\mathrm{S}$$\sigma$$\sigma\leq 16$

Lemma 3.2. Let$A$$x_{A}*y_{B}=0,1$

Lemma 3.3. Let
and $y_{B}\in B,$$x_{4}-,$$*y_{B}$ $=$,$A$, $B\in S$ . Then for any vectors$\ldots$orLemma 3.4. Let
and $y_{B}\in B,$$A$@ $A$ and $y_{B}\in B,$$\frac{n}{2}-1.$, $B\in S$ and$( \frac{n}{2}-1)$$x_{A}$$-k\iota f$$0 \leq k\leq\frac{n}{2}-1$. Then for any vectors$x_{A}\in A$

and only if $x_{A}*y_{B}=k.$, $B\in S$ and$0 \leq k\leq\frac{n}{2}-1$. Then for any vectors$x_{A}\in A$

91
if and only if $x_{A}*y_{B}=k.$$x_{\mathit{1}^{t}}’*y_{B’}=k+1$

Let$A_{1\mathit{1}}=\uparrow I_{i}$. Then we have the following possible values of$\beta_{1}$:(i) If the ’s $(i=1,2,3,4)$ are equal, then we have1.
.
(ii) If -,4; $(i=1,2,3,4)$ have two different values, then we have$A_{i}$$\beta_{1}=(\Lambda/I_{i}, lvI_{i}, \mathit{1}\mathrm{k}I_{i}, \mathrm{J}\sqrt I_{i})$$=(Mi, \Lambda/Ii, lt/Ij, hIj)$
2.
)
3.
(JWi,
,
)
4.
(Afi,
5.
, )
( , M. ,6.
$\beta_{1}=(i)hI_{j},$7.
.
8.
$\beta_{1}$$\beta_{1}$$=$$M_{j},$ $NI_{j},$ $M_{i}$$\beta_{1}=$$hI_{j}$$M_{i},$ $M_{j}$$\beta_{1}$$=(hI_{i}, M\dot{.}, M_{i}, M_{j})$$\beta_{1}$$=$$hI\dot{.}$$\cdot$$l\mathcal{V}Ij$$M_{\dot{*}}$$\Lambda I_{i},$$hI\dot{.})$$\beta_{1}=(M_{i}, M_{j}, M_{j}, M_{j})$(iii) If $A_{i}(i=1,2,3, 4)$ have three different values, then we have$=(hI_{i}, M_{j}, NI_{k}, hI_{i})$9.
10. $\beta_{1}=(NI_{i}, hIj, hI_{k}, M_{k})$11. $\beta_{1}=(NI_{i}, Mj, J/Ik, Mj)$
12. $\beta_{1}=(hI_{i}, kI_{i}, Mj, M_{k})$,)( , /I ,
13.
, )
(hI ,
14.
(iv) If $A_{i}(i= 1,2, 3, 4)$ have four different values, then we have
15. $\beta_{1}=(M_{i}, M_{j}, M_{k}, M_{l})$$\beta_{1}$$\beta_{1}=$$\beta_{1}=$$NI_{i}$${ }$$NI_{j}$$M_{k}$$M_{j},$ $M_{i}$$hI_{k}$$\lambda^{\gamma}$$j$

The following is an algorithm in constructing the possible structures of $M$
which would generate a Hadamard matrix of order An:

above.
(1) Consider the 15 possible values of(2) For each case, generate the possible values of ’2 At this point, 15 sets of$\beta_{1}$$\cdot$are generated.
(3) For every pair of and , generate the possible values of .
and ’3, generate the possible values of(4) For every triple of ,$\beta_{2}$$\beta_{2}$$\beta_{1}$$\beta_{1}$$\beta_{2}$$\beta_{3}$$\beta_{4}$.

Theorem 3.5. There are 149 possible structures of M which would generatea Hadamard matrix of order An:
In finding values of $\beta_{i}(i=1,2,3,4)$ , we use different variables and checkpossibilities to find the maximum number of distinct block matrices which canaltogether construct a Hadamard matrix of order An. Hence we also have thefollowing theorem:$\mathrm{a}\mathbb{I}$\S 2Theorem 3.6. The maximum number of distinct block matrices in matrix $M$
which would construct a Hadamard matrix of order An is 4.
4. THE HADAMARD MATRIX OF ORDER 32

We construct a Hadamard matrix of order 32 using the method in the previous section, $n=32$ is the next length to be classified as $n\leq 28$ are completely classified. There are 26 matrices found in Seberry’s homepage[15] and6 matrices found in Sloane’s page[14]. Araya, Harada and Kharaghani[l] also
enumerated a number of them. It is known that there are at least 66,000
inequivalent Hadamard matrices of length 32[3].
The following are direct consequences of the results in the previous section:(1) Letbe the first row vector and let , be any distinct row vectors otherthan . Then $x_{1}*y= \frac{n}{2}=16$ and $x*y= \frac{n}{4}=8$ when $x\neq 1.$(2) Row vectors of block matrices, A2,, , , , ,andare of weight 3. Also, row vectors of block matrices #3, , , ,,andare of weight 4.
$x$$x_{1}$$y$$x_{1}$$A_{1}$$A_{3},4_{4}$$B_{1}$$B_{2}$$C_{1}$$C_{3}$$B_{4}$$D_{2}$$C_{2}$$D_{3}$$C_{4}$$D_{1}$$D_{4}$

We investigate other properties of the block matrices of a Hadamard matrixof order 32 by asking the question, “How many repetitions of row vectors are
possible in constructing each block matri.x?” The answer to this question gives
the following result.
Proposition 4.1. 3 repetitions of a vector in a block matrix is not possible,
and $D_{i}(i= 1, 2, 3, 4)$ .
for block matrices ,$A_{i}$$B_{i_{l}}C_{i}$Hence, we are left with two remaining possibilities i.e., either a row vector
in a block matrix can be repeated twice or each row vector is distinct.

5. SOME EXAMPLBS
We make use of the incidence matrices of the isomorphic 2-(7, 3, 1) designs
and their respective complements, the 2–(7,4, 2) designs. Note that these
designs are unique and are self-dua1[2]. There are 30 cosets of the 2-(7, 3, 1)
designs and there are $(7!)^{2}/168$ incidence matrices. We use MAGMA in computing some Hadamard matrix examples. The following are some construction
examples.

83
Example 5.1.

$[\Lambda I_{i}hI_{i}hI_{i}h\mathit{1}_{i}$,$|l\Lambda NI_{}f_{i}\mathrm{V}I_{i}M_{i}$$|\begin{array}{l}\mathrm{J}/I_{i}M_{i}’M_{i}hf_{i}\end{array}|$$M_{i}M_{i}’M_{i}\mathit{1}\mathcal{V}I_{i},$

’

$]$

,

If the construction used has one distinct block matrix, we obtain 1 inequivalent Hadamard matrix of order 32 with automorphism group order equal to16515072.

Example 5.1.

$[hNhI_{i}i_{j}MI_{i}’|\begin{array}{l}NI_{i}M_{j}M’\dot{.}M\end{array}|$$MM:MM$$|M_{j}’M_{j}’M_{j}’M.\cdot]$

If the constr uction used has two distinct block matrices, we can obtain at mostHadama matrices of order 32. We have computed some$\frac{7^{\prime 2}}{168}.\cross(\frac{7!^{2}}{168}-1)$$rd$

Hadamard matrix examples $fmm$ the above particular construction and obtained 11 different automorphism group orders namely: 256, 768, 1024, 2048,
3072, 24576, 384, 512, $4096_{f}$ 6144 and 65536.

Example 5.3.

$[l\mathcal{V}M_{\mathrm{j}}I_{k}’hI_{k}M_{i}|l\mathrm{Y}I_{k}’M_{j}M_{k}M_{i}$$\frac{If\tau^{2}}{168},.\cross the$($|\begin{array}{l}MM_{j}’M_{j}M_{j}\end{array}|$$M_{j}’M_{j}’M_{j}M.,\cdot]$$Hadamardmat\uparrow\dot{\eta}\mathrm{C}CSthreedistinctblock$$c \frac{7!^{2}on}{168}-1)\cross(\frac{7!u_{2}}{168}-2)struct\mathrm{i}onsedhas$

mofator idce rs,$32we$ $canobtainatmostWehavecomputed$

some Hadamard matrix examples from the above particular constru ction andobtained 13 different automorphism group orders namely: 256, 768, 1024, 2048,
3072, 24576, 64, 128, 192, 384, 512, 1536 and 4096.
Example 5.4.

$[\Lambda hhI_{i}I_{i}I_{i}hI_{i}’|\lambda NkI_{j}’I_{j}\prime I_{j}hI_{j}$$|\begin{array}{l}M_{k}M_{k}’M_{k}NI_{k}\end{array}|$$M_{l}’M_{l}’M_{l}M_{l}’]$E14

If the construction used has four distinct block matrices, we can obtain at mostHadamard matrix of order 32.
$\frac{\overline{\prime}!^{2}}{168}\cross(\frac{-\prime!^{\underline{9}}}{168}-1)\cross(\frac{-\prime!^{2}}{168}-2)\cross(\frac{\overline{(}!^{2}}{168}-3)$

To classify the obtained Hadamard matrices of order 32, equivalence and automorphism group order must be considered. This can be done using MAGMA,
too. Since computing requires a massive time, the total number of inequivalent
Hadamard matrix of order 32 from the different obtained structures were notcompletely computed.

6. RANKS OF A HADAMARD MATRIX OF ORDER 32 OVER $GF(2)$ AND
Codes
Let
be a generator matrix of a linear binary $[n, k]$ code. The codes
obtained fromwhen(mod 8) is self-0rthogonal and in particular,
it yields self dual when
. The 2-rank ofis the dimension of the$[n, k]$ code over
, and is written as $rank_{2}(H_{n})$ . This section enumerates
of examples 5.1, 5.2, 5.3 and 5.4. Ranks ofwere also computed
using MAGMA.
We denote a Hadamard matrix of order 32 as. From [2], rank2(Hz2)$16$ . Ranin example 5.1 is 7; in examples 5.2 and 5.3 axe 8, 9, 10, 11,
12 and 13. $Rank_{2}(H_{32})=14,15,16$ axe not obtained from the computed
examples but the author is hopeful to find examples of such ranks from the
149 different constructions. If
exists with $rank_{2}(H_{32})=16$ from any of
our constructions, then we can also classify the $[32, 16]$ type II self dual codes
obtained from Hadamard matrices with Hall sets[8].
$H_{n}$$H_{n}$$n$$\equiv 0$$k= \frac{n}{2}$$H_{n}$$C_{\tau}F(2)$$rank_{2}^{\wedge}(H_{n})$$H_{n}$$H_{32}$$6\leq$$\leq$$k_{2}^{\wedge}(H_{32})$$H_{32}$$\sim/$. CONCLUSIONS AND RECOMMENDATIONSIn this paper, after checking the properties and conditions of the block matrices of matrix (1), we had come up with the following:. Construction of Hadamard matrices of order $4n$ if $n\equiv 0$ (mod 4) and
2- $(n-1, \frac{n}{2}-1,7 - 1)$ Hadamard designs exist.
. We were successful in enumerating all the possible constructions of a Hadamard
matrix of order $4n$ using Kimura’s structure, restricting the row vectors ofeach block matrix to be distinct and using the incidence matrices of a symmetric 2-design as block matrices of of such matrix.
For a Hadamard matrix of order 32 in particular, we also have come up withthe following:$\mathrm{a}$$\mathrm{b}$as$\mathrm{a}$$\mathrm{b}$$\mathrm{c}$. Some examples with their automorphism group orders and$Rank_{2}(H_{32})$

werecomputed,. 3 or more repetitions of a row vector in any of theblock matrices do
not yield Hadamard matrix.
. The possibility of constructing a Hadamard matrix using block matrices
withrepeated twice has not been explored.
$7\cross 7$$\mathrm{v}\mathrm{e}\mathrm{c}\mathrm{t}\mathrm{o}\mathrm{r}/\mathrm{s}$Thus we are left with the following questions:(1) Is there a possibility to construct a Hadamard matrix of order $4n$ using Kimura’s
structure if for any , Hadamard 2- $(n-1, 7-1, \frac{n}{4}- 1)$ design does not exist?
(2) If for $n=8,3$ or more repetitions of a row vector in any of the 7blockmatrices of
do not yield Hadamard matrix, what would be the case for$n>8$ ?
(3) Is there any relationship between the rank of a Hadamard matrix of order $4n$$(n\geq 8)$ and the constructions?
(4) Which of the constructions could generate Hadamard matrix of orderhighest rank?
(5) Letbe a Hadamard matrix of order An. Is $rank_{2}(H_{4n})= \frac{n}{2}$ possible in these
constructions? If so, then we can also clasify some Type II self dual codes from$n$$\mathrm{x}7$$H_{32}$$4n\mathrm{o}\mathrm{f}$$H_{4n}$$H_{4n}$.

REFERENCES[1] M. Araya, M. Harada and H. Kharaghani, Some Hadamard Matrices of Order 32 andTheir Binary Codes (submitted).
[2] E.F. Assmus, Jr. and J.D. Key, Designs and Their Codes, (Cambridge University Press,
Great Britain, 1992).
[3] R. Craigen, Hadamard Matrices and Designs, The CRC Handbook of Combinatorial.
Designs , C.J. Colbourn aaxd J.H. Dinitz(Eds.), CRC Press, Boca Raton 1996,[4] M.Hall, Jr.jHada mard Matrices of Order 16, J.P.L. Research Summary No. 36-101(1961) 21-26.
[5] M.Hall, Jr.,Hadamard Matrices of Order 20, J.P.L. Technical Report No. 32-761(1965).
[6] N. Ito, J.S. Leon and J.Q. Longyear, Classification of 3-(24, 12,5) Designs and 24Dimensional Hadamard matrices, J. Combin. Theory A31 (1981) 66-93.
[7] H. Kimura, New Hadamard matrices of Order 24, Graphs Combin. 5 (1989) 236-242.
[8] H. Kimura, Classification of Hadamard Matrices of Order 28, Discrete Math. 133(1994) 171-180.
[9] Kimura, Hiroshi. (private comm unication)[10] E.S. Lander, Symmetric Designs: An Algebraic Approach London Mathematical Society
Lecture Notes Series, Cambridge University Press, Cambridge(1974).
$370-3\overline{/}7$ee[11] F.J. Macwilliams and N.J.A. Sloane, The Theory of Error-Correcting Codes, (North
Holland, Amsterdam, 1977).
[12] M. Ozeki, Hadamard Matrices and Type II Doubly-Even Error-Correcting codes J.
Combin. Theory A 44 (1987) 274-287.
[13] E.M. Rains and N.J.A. Sloane, Self-Dual Codes, Handbook of Coding Theory , V.S.
Pless and W.C. Huffman(Eds.), Elsevier Science B.V. 1998, 177-294.
[14] (http:.att.com.
.html)[15] (http://www.uow.edu.au/.html)$//\mathrm{w}\mathrm{w}\mathrm{w}.\mathrm{r}\mathrm{e}\mathrm{s}\mathrm{e}\mathrm{a}\mathrm{r}\mathrm{c}\mathrm{h}$$\mathrm{n}\mathrm{j}\mathrm{a}\mathrm{s}/\mathrm{h}\mathrm{a}\mathrm{d}\mathrm{a}\mathrm{m}\mathrm{a}\mathrm{r}\mathrm{d}/\mathrm{i}\mathrm{n}\mathrm{d}\mathrm{e}\mathrm{x}$$\mathrm{j}\mathrm{e}\mathrm{n}\mathrm{n}\mathrm{i}\mathrm{e}/\mathrm{h}\mathrm{a}\mathrm{d}\mathrm{a}\mathrm{m}\mathrm{a}\mathrm{r}\mathrm{d}/\mathrm{i}\mathrm{n}\mathrm{d}\mathrm{e}\mathrm{x}$