Block Structured Hadamard matrices from certain arrays

Topno, Sheet; Saurabh, Shyam

doi:10.61091/jcmcc117-15

Abstract

References

Journal of Combinatorial Mathematics and Combinatorial Computing

Volume 117
Pages: 169-175

Research article

Block Structured Hadamard matrices from certain arrays

^¹, ^²

¹Department of Mathematics, Ranchi University, Ranchi, Jharkhand, India.

²Department of Mathematics, Tata College Chaibasa, Jharkhand, India.

Received: 20/11/2023
Accepted: 02/12/2023
Published: 06/12/2023

Copyright Link
License

Abstract

We have constructed Block structured Hadamard matrices in which odd number of blocks are used in a row (column). These matrices are different than those introduced by Agaian. Generalised forms of arrays developed by Goethals-Seidel, Wallis-Whiteman and Seberry-Balonin heve been employed. Such types of matrices are applicable in the constructions of nested group divisible designs.

Keywords: Hadamard matrix, Kronecker product, Block structure, Group divisible design

1. Introduction

Hadamard matrices discovered by Sylvester in 1867 [1] have profound structural properties. These kind of matrices have Hadamard matrices as their sub blocks. In his matrices even number of Hadamard blocks were arranged in a row (or column). However in 1985 Agaian [2] introduced Hadamard matrices with odd number of Hadamard blocks in a row. These matrices are named Block Structured Hadamard matrices. He has demonstrated their application in signal processing as well [3]. The matrices constructed by him are in correspondence to the Williamson matrices arranged in his array.

Williamson’s array has been further generalized by Goethals and Seidel [4]. Matrices suitable for Goethals- Seidel arrays have been constructed by several authors [5, 6, 7]. In 2015, Seberry and Balonin [8] introduced what is known as the “propus array” and its generalizations. This was accomplished by imposing certain restrictions on Williamson’s array and applying the arrangement principles from the Goethals-Seidel array.

The result presented in this paper involves the construction of block-structured Hadamard matrices using the generalizations of Goethals-Seidel array and Seberry-Balonin array. Similar to that of Agaian, these matrices also have odd number of blocks arranged in a row. However these are different from Agaian’s matrices, as these do not correspond to Williamson matrices. Furthermore, their applications in nested group divisible design are also discussed.

The paper is organized as follows: Section 2 contains all the relevant definitions and results. Section 3 comprises of the main result of this paper. Results are presented in three main theorems and two corollaries. Examples of each type are also included here. Section 4 is conclusion in which we have discussed some properties and an application of block structured Hadamard matrices in the construction of nested group divisible designs.

2. Preliminaries

We recall some basic definitions here [4, 9, 10, 11 , 12]. An Hadamard matrix is a square matrix $H$ of order $n$ with entries $\pm 1$ such that $H H^{⊤} = n I_{n}$ . Four matrices $A, B, C, D$ of order $n$ with entries $\pm 1$ are called Williamson matrices if (i) $A, B, C, D$ are circulant, symmetric and commuting (ii) $A^{2} + B^{2} + C^{2} + D^{2} = 4 n I_{n}$ . If $A, B, C, D$ of same order are circulant $\pm 1$ matrices satisfying $A A^{⊤} + B B^{⊤} + C C^{⊤} + D D^{⊤} = 4 n I_{n}$ then these are called Goethals-Seidel (GS) matrices. Dokovic et al. [6] have constructed GS matrices of type ( $s s s s$ ), ( $s s s k$ ), ( $s s k k$ ), ( $s k k k$ ) where ‘ $s$ ’ stand for symmetric and ‘ $k$ ’ for skew type GS matrices. In this article we shall be using ( $s s s a$ ) and ( $k k k a$ ) type GS matrices, where ‘ $a$ ’ stands for any (symmetric, skew type or other) type of matrix. An Hadamard matrix $H$ of order $4 t n$ will be called Block Structured if all its $4 t \times 4 t$ blocks are Hadamard matrices for a given $t$ . If $A = [a_{i j}]$ and $B = [b_{i j}]$ be two matrices of order $m$ and $n$ respectively then the Kronecker product $A \otimes B$ is the matrix of order $m n$ given by $A \otimes B = [a_{i j} B]$ . Two matrices $A$ and $B$ are said to be Amicable if $A B^{⊤} = B A^{⊤}$ .
Let the elements $z_{i}$ of an additive abelian group $G$ be ordered in a fixed way. Let $X \subset G$ . Then the matrix $M = (m_{i j})$ defined by
$m_{i j} = ψ (z_{j} - z_{i}), w h e r e ψ (z_{j} - z_{i}) = {\begin{cases} 1 & i f z_{j} - z_{i} \in X, \\ 0 & o t h e r w i s e, \end{cases}$
is called type 1 incidence matrix of $X$ in $G$ , and the matrix $N = (n_{i j})$ defined by
$n_{i j} = ψ (z_{j} + z_{i}), w h e r e ψ (z_{j} + z_{i}) = {\begin{cases} 1 & i f z_{j} + z_{i} \in X, \\ 0 & o t h e r w i s e, \end{cases}$
is called type 2 incidence matrix of $X$ in $G$ . A Circulant matrix $M = (m_{i j})$ defined by $m_{i j} = m_{1, j - i + 1}$ is a special case of type 1 matrix and a backcirculant matrix $N = (n_{i j})$ defined by $n_{i j} = n_{1, i + j - 1}$ is a special case of type 2 matrix. Following proposition is useful in development of the results in this paper.

Proposition 1. [Seberry] If X and Y are type 1 matrices and Z is type 2 matrix then
$X Y = Y X$ , $X^{⊤} Y = Y X^{⊤}$ , $X Y^{⊤} = Y^{⊤} X$ , $X^{⊤} Y^{⊤} = Y^{⊤} X^{⊤}$ and
$X Z^{⊤} = Z X^{⊤}$ , $X Z = Z^{⊤} X^{⊤}$ , $X^{⊤} Z^{⊤} = Z X$ , $X^{⊤} Z = Z^{⊤} X$ .

Notation: Throughout this paper $I_{n}$ denotes the identity matrix of order $n$ and $J_{n}$ denotes the all-1 matrix of order $n$ . Wherever $I$ and $J$ are used without subscript, they have the same meaning and their orders can be determined from the context.

3. Main Result

Lemma 1. Let $A_{i}, i = 0, 1, 2, 3$ be circulant matrices of order n and let $R = [r_{i j}]$ be defined as $r_{i, n - i + 1} = 1, r_{i j} = 0$ otherwise. Then

$(A_{i} R)^{⊤} = (A_{i} R) & (A_{i}^{⊤} R)^{⊤} = (A_{i}^{⊤} R), i = 1, 2, 3$
$A_{0} (A_{i} R)^{⊤} = (A_{i} R) A_{0}^{⊤}$ , i=1, 2, 3
$A_{0} (A_{i}^{⊤} R)^{⊤} = (A_{i}^{⊤} R) A_{0}^{⊤}$ , i=1, 2, 3
$(A_{i} R) (A_{j}^{⊤} R)^{⊤} = (A_{j}^{T} R) (A_{i} R)^{⊤}, i, j = 1, 2, 3$
$(A_{i} R) (A_{i + j} R)^{⊤} = (A_{i + j}^{⊤} R) (A_{i}^{⊤} R)^{⊤} & (A_{i + j}^{⊤} R) (A_{i}^{⊤} R)^{⊤} = (A_{i}^{⊤} R) (A_{i + j}^{⊤} R)^{⊤}, i, j = 1, 2$ , $i + j \leq 3$

Proof. Using Proposition 1.

Using this lemma following Theorem can be proven easily.

Theorem 1. Let there exist $(0, 1, - 1)$ -matrices $X_{i}, Y_{j}; 0 \leq i \leq 3, 1 \leq j \leq 3$ of order $4 t; (t \in N)$ such that
(i) $X_{0} X_{0}^{⊤} = X_{i} X_{i}^{⊤} + Y_{i} Y_{i}^{⊤} = t I_{4 t}; 1 \leq i \leq 3$
(ii) $X_{0} X_{i}^{⊤} + X_{i} X_{0}^{⊤} = 0 = X_{0} Y_{i}^{⊤} + Y_{i} X_{0}^{⊤}, i = 1, 2, 3$
(iii) $X_{i} Y_{i}^{⊤} = 0 = Y_{i} X_{i}^{⊤}$ , $\forall i = 1, 2, 3$
(iv) $X_{i} Y_{j}^{⊤} + X_{j} Y_{i}^{⊤} = 0 = Y_{j} X_{i}^{⊤} + Y_{i} X_{j}^{⊤}, 1 \leq i \neq j \leq 3$
(v) $X_{i} X_{i + j}^{⊤} + Y_{i + j} Y_{i}^{⊤} = 0 = X_{i + j} X_{i}^{⊤} + Y_{i} Y_{i + j}^{⊤}, i, j = 1, 2$ , $i + j \leq 3$ .
Then we have
(1) If there exist Goethals-Seidel matrices $A_{i}, i = 0, 1, 2, 3$ of order n of the type (kkka) or (sssa) then there exists a block structured Hadamard matrix of order $4 n t$ with Hadamard blocks of order $4 t$ .
(2) If there exist type 2 matrix $A_{0}$ and three type 1 matrices $A_{i}$ ; $1 \leq i \leq 3$ defined on the same Abelian group of order n such that $\sum_{i = 0}^{3} A_{i} A_{i}^{⊤} = 4 n I_{n}$ then there exists a block structured Hadamard matrix of order $4 n t$ with Hadamard blocks of order $4 t$ .

Proof. (1) Define a matrix $H$ by $\begin{aligned} H = A_{0} \otimes X_{0} + A_{1} R \otimes X_{1} + A_{1}^{⊤} R \otimes Y_{1} + A_{2} R \otimes X_{2} + A_{2}^{⊤} R \otimes Y_{2} + A_{3} R \otimes X_{3} + A_{3}^{⊤} R \otimes Y_{3}, \end{aligned}$ where $A_{i}$ s correspond to ‘ $s$ ’ or ‘ $k$ ’ type for $i = 1, 2, 3$ and $A_{0}$ corresponds to ‘ $a$ ’ type. Then $\begin{aligned} H H^{⊤} = & A_{0} A_{0}^{⊤} \otimes X_{0} X_{0}^{⊤} + \sum_{i = 1}^{3} {(A_{i} R) (A_{i} R)^{⊤} \otimes X_{i} X_{i}^{⊤} + (A_{i}^{⊤} R) (A_{i}^{⊤} R)^{⊤} \otimes Y_{i} Y_{i}^{⊤}} \\ + [\sum_{i = 1}^{3} {(A_{0} (A_{i} R)^{⊤} \otimes X_{0} X_{i}^{⊤} + (A_{i} R) A_{0}^{⊤} \otimes X_{i} X_{0}^{⊤} + A_{0} (A_{i}^{⊤} R)^{⊤} \otimes X_{0} Y_{i}^{⊤} + (A_{i}^{⊤} R) A_{0}^{⊤} \otimes Y_{i} X_{0}^{⊤})} \\ + \sum_{j = 1}^{3} \sum_{i = 1}^{3} {(A_{i} R) (A_{j}^{⊤} R)^{⊤} \otimes X_{i} Y_{j}^{⊤} + (A_{j}^{⊤} R) (A_{i} R)^{⊤} \otimes Y_{j} X_{i}^{⊤}} \\ + \sum_{i = 1}^{2} {(A_{i} R) (A_{i + 1} R)^{⊤} \otimes X_{i} X_{i + 1}^{⊤} + (A_{i + 1} R) (A_{i} R)^{⊤} \otimes X_{i + 1} X_{i}^{⊤} \\ + (A_{i}^{⊤} R) (A_{i + 1}^{⊤} R)^{⊤} \otimes Y_{i} Y_{i + 1}^{⊤} + (A_{i + 1}^{⊤} R) (A_{i}^{⊤} R)^{⊤} \otimes Y_{i + 1} Y_{i}^{⊤})} \\ + \sum_{i = 1} {(A_{i} R) (A_{i + 2} R)^{⊤} \otimes X_{i} X_{i + 2}^{⊤} + (A_{i + 2} R) (A_{i} R)^{⊤} \otimes X_{i + 2} X_{i}^{⊤} \\ + (A_{i}^{⊤} R) (A_{i + 2}^{⊤} R)^{⊤} \otimes Y_{i} Y_{i + 2}^{⊤} + (A_{i + 2}^{⊤} R) (A_{i}^{⊤} R)^{⊤} \otimes Y_{i + 2} Y_{i}^{⊤})}] \end{aligned}$

$\begin{aligned} = & A_{0} A_{0}^{⊤} \otimes X_{0} X_{0}^{⊤} + \sum_{i = 1}^{3} A_{i} A_{i}^{⊤} \otimes (X_{i} X_{i}^{⊤} + Y_{i} Y_{i}^{⊤}) \\ + [\sum_{i = 1}^{3} {A_{0} (A_{i} R)^{⊤} \otimes (X_{0} X_{i}^{⊤} + X_{i} X_{0}^{⊤}) + A_{0} (A_{i}^{⊤} R)^{⊤} \otimes (X_{0} Y_{i}^{⊤} + Y_{i} X_{0}^{⊤})} \\ + \sum_{j = 1}^{3} \sum_{i = 1}^{3} (A_{i} R) (A_{j}^{⊤} R)^{⊤} \otimes (X_{i} Y_{j}^{⊤} + Y_{j} X_{i}^{⊤}) \\ + \sum_{i = 1}^{2} {(A_{i} R) (A_{i + 1} R)^{⊤} \otimes (X_{i} X_{i + 1}^{⊤} + Y_{i + 1} Y_{i}^{⊤}) + (A_{i + 1} R) (A_{i} R)^{⊤} \otimes (X_{i + 1} X_{i}^{⊤} + Y_{i} Y_{i + 1}^{⊤})} \\ + \sum_{i = 1} {(A_{i} R) (A_{i + 2} R)^{⊤} \otimes (X_{i} X_{i + 2}^{⊤} + Y_{i + 2} Y_{i}^{⊤}) + (A_{i + 2} R) (A_{i} R)^{⊤} \otimes (X_{i + 2} X_{i}^{⊤} + Y_{i} Y_{i + 2}^{⊤})}] \end{aligned}$

$\begin{aligned} = & A_{0} A_{0}^{⊤} \otimes X_{0} X_{0}^{⊤} + \sum_{i = 1}^{3} A_{i} A_{i}^{⊤} \otimes (X_{i} X_{i}^{⊤} + Y_{i} Y_{i}^{⊤}) \\ + [0 + {\sum_{i = j} A_{i}^{2} \otimes (X_{i} Y_{i}^{⊤} + Y_{i} X_{i}^{⊤}) + \sum_{i \neq j} A_{i} A_{j} \otimes (X_{i} Y_{j}^{⊤} + Y_{j} X_{i}^{⊤} + X_{j} Y_{i}^{⊤} + Y_{i} X_{j}^{⊤})} + 0 + 0] \end{aligned}$

$\begin{aligned} = & {\sum_{i = 0}^{4} A_{i} A_{i}^{⊤}} \otimes t I_{4 t} \\ = & 4 n t I_{4 n t} . \end{aligned}$

Hence $H$ is an Hadamard matrix. Now each $4 t \otimes 4 t$ block (say $H_{i j}$ ) is a linear combination of $X_{i}^{'} s$ and $Y_{i}^{'} s$ of the form
$H_{i j} = \sum_{i = 0}^{3} ρ_{i} X_{i} + \sum_{j = 1}^{3} σ_{j} Y_{j}$ , $ρ_{i}, σ_{j} \in {1, - 1} .$
Case 1: $A_{i}$ s are of the type ( $k k k a$ )
Then $A_{i}^{⊤} = - A_{i}$ , $i = 1, 2, 3$
$\Rightarrow$ $A_{i}^{⊤} R = - A_{i} R$ , $i = 1, 2, 3$
$\Rightarrow$ $ρ_{i} = - σ_{i}$ , $i = 1, 2, 3.$
Case 2: $A_{i}$ s are of the type ( $s s s a$ )
Then $A_{i}^{⊤} = A_{i}$ , $i = 1, 2, 3$
$\Rightarrow A_{i}^{⊤} R = A_{i} R$ , $i = 1, 2, 3$
$\Rightarrow ρ_{i} = σ_{i}$ , $i = 1, 2, 3$ .
Now $\begin{aligned} H_{i j} H_{i j}^{⊤} = & \sum_{i = 0}^{3} X_{i} X_{i}^{⊤} + \sum_{i = 1}^{3} Y_{i} Y_{i}^{⊤} \pm [\sum_{i = 1}^{3} (X_{0} X_{i}^{⊤} + X_{i} X_{0}^{⊤} + X_{0} Y_{i}^{⊤} + Y_{i} X_{0}^{⊤}) \\ \pm \sum_{j} \sum_{i} (X_{i} Y_{j}^{⊤} + Y_{j} X_{i}^{⊤}) \pm \sum (X_{i} X_{i + 1}^{⊤} + X_{i + 1} X_{i}^{⊤} + Y_{i} Y_{i + 1}^{⊤} + Y_{i + 1} Y_{i}^{⊤})] \\ = & 4 t I_{4 t} . \end{aligned}$ $\Rightarrow$ each $4 t \otimes 4 t$ block of $H$ is an Hadamard matrix.
(2) Proof is similar to case (1), just define H by
$H = A_{0} \otimes X_{0} + \sum_{i = 1}^{3} {A_{i} \otimes X_{i} + A_{i}^{⊤} \otimes Y_{i}}$

Example 1. The matrices $X_{0} = [\begin{matrix} 1 & 0 & 0 & 0 & 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 & 0 & - 1 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 & 0 & - 1 & 0 \\ 0 & 0 & 0 & 1 & 0 & 0 & 0 & - 1 \\ - 1 & 0 & 0 & 0 & 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 & 0 & 0 & 0 & 1 \end{matrix}], X_{1} = [\begin{matrix} 0 & 1 & 0 & 0 & 0 & 1 & 0 & 0 \\ - 1 & 0 & 0 & 0 & 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & - 1 & 0 & 0 & 0 & 1 & 0 & 0 \\ - 1 & 0 & 0 & 0 & - 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \end{matrix}], X_{2} = [\begin{matrix} 0 & 0 & 1 & 0 & 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ - 1 & 0 & 0 & 0 & 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & - 1 & 0 & 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ - 1 & 0 & 0 & 0 & - 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \end{matrix}]$ $X_{3} = [\begin{matrix} 0 & 0 & 0 & 1 & 0 & 0 & 0 & 1 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ - 1 & 0 & 0 & 0 & 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & - 1 & 0 & 0 & 0 & 1 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ - 1 & 0 & 0 & 0 & - 1 & 0 & 0 & 0 \end{matrix}], Y_{1} = [\begin{matrix} 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 & 0 & 0 & - 1 \\ 0 & 0 & - 1 & 0 & 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & - 1 & 0 & 0 & 0 & - 1 \\ 0 & 0 & 1 & 0 & 0 & 0 & 1 & 0 \end{matrix}], Y_{2} = [\begin{matrix} 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & - 1 & 0 & 0 & 0 & 1 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 & 0 & - 1 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 & 0 & 0 & 1 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & - 1 & 0 & 0 & 0 & - 1 & 0 & 0 \end{matrix}],$ $Y_{3} = [\begin{matrix} 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 & 0 & - 1 & 0 \\ 0 & - 1 & 0 & 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & - 1 & 0 & 0 & 0 & - 1 & 0 \\ 0 & 1 & 0 & 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \end{matrix}]$ together with ( $s s s a$ ) or ( $k k k a$ ) type Goethals-Seidel matrices of order $n$ taken as $A_{i}^{s}$ give the Block Structured Hadamard matrix of order $8 n$ with Hadamard blocks of order $8$ .

Theorem 2. Let there exist three $(0, 1, - 1)$ -matrices of order $4 t$ $(t \in N)$ such that
(i) $X_{i} X_{i}^{⊤} = t I_{4 t}$ ; $i = 1, 3$ and $X_{2} X_{2}^{⊤} = 2 t I_{4 t}$
(ii) $X_{i} X_{j}^{⊤} + X_{j} X_{i}^{⊤} = 0$ ; $1 \leq i \neq j \leq 3$ .
Then we have
(1) If there exist four Williamson matrices $A_{i}, 1 \leq i \leq 4$ such that $A_{4} = A_{2}$ of order $n$ then there exists a block structured Hadamard matrix of order $4 n t$ with Hadamard blocks of order $4 t$ .
(2)If there exist three pairwise amicable $\pm 1$ matrices $A_{i}; 1 \leq i \leq 3$ of order $n$ such that $A_{1} A_{1}^{⊤} + 2 A_{2} A_{2}^{⊤} + A_{3} A_{3}^{⊤} = 4 n I_{n}$ then there exists a block structured Hadamard matrix of order $4 n t$ with Hadamard blocks of order $4 t$ .

Proof. (1) Define $H$ by $H = \sum_{i = 1}^{3} A_{i} \otimes X_{i}$ then
$\begin{aligned} H H^{⊤} = & \sum_{i = 1}^{3} A_{i} A_{i}^{⊤} \otimes X_{i} X_{i}^{⊤} + [\sum_{i = 1}^{2} (A_{i} A_{i + 1}^{⊤} \otimes X_{i} X_{i + 1}^{⊤} + A_{i + 1} A_{i}^{⊤} \otimes X_{i + 1} X_{i}^{⊤}) \\ + \sum_{i = 1} (A_{i} A_{i + 2}^{⊤} \otimes X_{i} X_{i + 2}^{⊤} + A_{i + 2} A_{i}^{⊤} \otimes X_{i + 2} X_{i}^{⊤})] \\ = & \sum_{i = 1}^{3} A_{i} A_{i}^{⊤} \otimes X_{i} X_{i}^{⊤} + [\sum_{i = 1}^{2} (A_{i} A_{i + 1}^{⊤} \otimes {X_{i} X_{i + 1}^{⊤} + X_{i + 1} X_{i}^{⊤}}) \\ + \sum_{i = 1} (A_{i} A_{i + 2}^{⊤} \otimes {X_{i} X_{i + 2}^{⊤} + X_{i + 2} X_{i}^{⊤}})] \end{aligned}$ $\begin{aligned} = & {A_{1} A_{1}^{⊤} + 2 A_{2} A_{2}^{⊤} + A_{3} A_{3}^{⊤}} \otimes t I_{4 t} \\ = & 4 n I_{n} \otimes t I_{4 t} \\ = & 4 n t I_{4 n t} . \end{aligned}$ Now, each $m \otimes m$ blocks of $H_{i j}$ is a linear combination of $X_{i}^{'} s$ i.e., $H_{i j} = \sum_{i = 1}^{3} ρ_{i} X_{i}$ ; $ρ_{i} \in {1, - 1}$ therefore, $\begin{aligned} H_{i j} H_{i j}^{⊤} = & \sum_{i = 1}^{3} X_{i} X_{i}^{⊤} \pm \sum_{1 \leq i \neq j \leq 3} (X_{i} X_{j}^{⊤} + X_{j} X_{i}^{⊤}) \\ = & 4 t I_{4 t} . \end{aligned}$ (2) Can be proven similarly.

Example 2. Take $X_{1} = [\begin{matrix} 1 & 0 & 0 & 0 \\ 0 & 0 & - 1 & 0 \\ 0 & - 1 & 0 & 0 \\ 0 & 0 & 0 & - 1 \end{matrix}], X_{2} = [\begin{matrix} 0 & 1 & 1 & 0 \\ 1 & 0 & 0 & - 1 \\ 1 & 0 & 0 & 1 \\ 0 & - 1 & 1 & 0 \end{matrix}], X_{3} = [\begin{matrix} 0 & 0 & 0 & 1 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & - 1 & 0 \\ 1 & 0 & 0 & 0 \end{matrix}] .$

Corollary 1. If there exist matrices $X_{i}$ , $i = 1, 2, 3$ of order $4 t$ , $t \in N$ satisfying conditions of Theorem 3, the matrices $X_{i}$ , $i = 1, 2, 3$ of order $8 t$ , $t \in N$ also exist.

Proof. Define new $X_{i}$ as $X_{i} \Rightarrow [\begin{matrix} 1 & 1 \\ 1 & - 1 \end{matrix}] \otimes X_{i}, i = 1, 2, 3.$

Corollary 1. If there exist matrices $X_{i}$ , $i = 1, 2, 3$ of order $4 t$ , $t \in N$ satisfying conditions of Theorem 3, and there exists three Amicable Hadamard matrices of order $r$ then there exist $X_{i}$ matrices of order $4 r t$ .

Proof. Let $H_{i}$ , $i = 1, 2, 3$ be Amicable Hadamard matrix of order $r$ . Define new $X_{i}$ as $X_{i} \Rightarrow X_{i} \otimes H_{i}, i = 1, 2, 3.$

Theorem 3. Let there exist $(0, 1, - 1)$ -matrices $X_{i}, Y_{j}$ ; $0 \leq i \leq 2, 1 \leq j \leq 2$ of order $4 t$ ; $t \in N$ such that
(i) $X_{0} X_{0}^{⊤} = X_{2} X_{2}^{⊤} + Y_{2} Y_{2}^{⊤} = t I_{4 t}$ and $X_{1} X_{1}^{⊤} + Y_{1} Y_{1}^{⊤} = 2 t I_{4 t}$
(ii) $X_{0} X_{i}^{⊤} + X_{i} X_{0}^{⊤} = 0 = X_{0} Y_{i}^{⊤} + Y_{i} X_{0}^{⊤}, i = 1, 2$
(iii) $X_{i} Y_{i}^{⊤} = 0 = Y_{i} X_{i}^{⊤}$ , $\forall i = 1, 2$
(iv) $X_{i} Y_{j}^{⊤} + X_{j} Y_{i}^{⊤} = 0 = Y_{j} X_{i}^{⊤} + Y_{i} X_{j}^{⊤}, 1 \leq i \neq j \leq 2$
(v) $X_{i} X_{i + j}^{⊤} + Y_{i + j} Y_{i}^{⊤} = 0 = X_{i + j} X_{i}^{⊤} + Y_{i} Y_{i + j}^{⊤}, i, j = 1$ , $i + j \leq 2$ .
Then we have, if there exist three pairwise commutative $\pm 1$ matrices $A_{i}; 0 \leq i \leq 2$ of order $n$ such that $A_{0} A_{0}^{⊤} + 2 A_{1} A_{1}^{⊤} + A_{2} A_{2}^{⊤} = 4 n I_{n}$ then there exists a block structured Hadamard matrix of order $4 n t$ with Hadamard blocks of order $4 t$ .

Proof. Proof is simillar to Theorem 1 and Theorem 2. Just take
$H = A_{0} \otimes X_{0} + A_{1} R \otimes X_{1} + A_{1}^{⊤} R \otimes Y_{1} + A_{2} R \otimes X_{2} + A_{2}^{⊤} R \otimes Y_{2}$ .

Example 3. From Example 1 take $X_{i}^{'} s$ and $Y_{i}^{'} s$ and set $X_{0} = X_{0}, X_{1} = X_{1} + X_{2}, X_{2} = X_{3}, Y_{1} = Y_{1} + Y_{2}, Y_{2} = Y_{3}$ to get the desired result.

3. Conclusion

In this paper we have constructed block structured Hadamard matrices different from those of Sylvester and Agaian. Matrices $X_{i}^{'} s$ and $Y_{i}^{'} s$ of Theorem 1 can be obtained from Goethals-Seidel array and its generalization. In this method block structured Hadamard matrix of order $4 n t$ is constructed using the blocks of a set containing at the most $16$ distinct Hadamard blocks of order $t$ . (Here two Hadamard blocks $H_{i}$ and $H_{j}$ are considered to be distinct if $H_{i} \neq \pm H_{j}$ .) Matrices $A_{i}^{'} s$ can be found in the works of several authors specially in [4, 11, 12].
Matrices $X_{i}^{'} s$ and $Y_{i}^{'} s$ of Theorem 2 can be obtained from Propus array and Propus type arrays. Seberry and Balonin have constructed required $A_{i}^{'} s$ matrices in abundance [8]. Methods of construction of these matrices are not proposed here. In this construction there are precisely four distinct Hadamard blocks viz. $\pm (X_{1} + X_{2} + X_{3})$ , $\pm (X_{1} - X_{2} + X_{3})$ , $\pm (X_{1} - X_{2} - X_{3})$ and $\pm (X_{1} + X_{2} - X_{3})$ . If the matrices $A_{i}^{'} s$ are constructed from Turyn’s method then there are only three distinct Hadamard blocks viz. $\pm (X_{1} + X_{2} + X_{3})$ , $\pm (X_{1} - X_{2} + X_{3})$ , $\pm (X_{1} - X_{2} - X_{3})$ .
Theorem 3 is a product of the Theorems 1 and 2. In this construction number of distinct Hadamard blocks are $16$ . Efforts could be made to find a method to construct matrices $X_{i}^{'} s$ and $Y_{i}^{'} s$ in general, which could result in some Hadamard matrices of new orders. Block structured Hadamard matrices may be used in nested group divisible (GD) designs as follows:
It is well known that replacing $1$ by $I_{2}$ and $- 1$ by $(J - I)_{2}$ in a Hadamard matrix $H$ of order $4 n t$ we obtain a series of resolvable semi-regular GD designs with parameters (see Saurabh and Sinha [13]): $v = b = m^{*} n^{*} = 8 n t, r = k = 4 n t, λ_{1} = 0, λ_{2} = 2 n t, m^{*} = 4 n t, n^{*} = 2.$

Further since H contains Hadamard blocks each of order $4 t$ , removing $s$ rows of blocks of incidence matrix of 1 we obtain a series of GD designs with parameters: $v = 8 t (n - s), b = 8 n t, r = 4 n t, k = 4 t (n - s), λ_{1} = 0, λ_{2} = 2 n t, m^{*} = 4 t (n - s), n^{*} = 2; s < n .$

Hence a GD design with parameters 2 is nested within a GD design with parameters 1. For details on GD designs we refer to Raghvarao and Padgett [14], Saurabh and Sinha [13] and Saurabh and Prasad [15].

Acknowledgment

The authors express their gratitude to Dr. Mithilesh Kumar Singh for his valuable suggestions on the presentation of this paper, as well as to the anonymous referees for their nice comments.

References:

Sylvester, J.J., 1867. LX. Thoughts on inverse orthogonal matrices, simultaneous signsuccessions, and tessellated pavements in two or more colours, with applications to Newton’s rule, ornamental tile-work, and the theory of numbers. The London, Edinburgh, and Dublin Philosophical Magazine and Journal of Science, 34(232), pp.461-475.[Google Scholor]
Agaian, S.S., 2006. Hadamard matrices and their applications (Vol. 1168). Springer-Verlag, Berlin Heidelberg, New York.[Google Scholor]
Agaian, S.S., Sarukhanyan, H., Egiazarian, K. and Astola, J., 2011, August. Hadamard transforms. SPIE Press, Bellingham, Washington USA.[Google Scholor]
Goethals, J.M. and Seidel, J.J., 1967. Orthogonal matrices with zero diagonal. Canadian Journal of Mathematics, 19, pp.1001-1010.[Google Scholor]
Shen, S. and Zhang, X., 2023. Constructions of Goethals-Seidel Sequences by Using $k$-Partition. Mathematics, 11(2), p.294.[Google Scholor]
Doković, D. Ž . and Kotsireas, I.S., 2018. Goethals-Seidel difference families with symmetric or skew base blocks. Mathematics in Computer Science, 12, pp.373-388.[Google Scholor]
Xia, M., Xia, T., Seberry, J. and Wu, J., 2005. An infinite family of Goethals-Seidel arrays. Discrete Applied Mathematics, 145(3), pp.498-504.[Google Scholor]
Seberry, J. and Balonin, N.A., 2015. The Propus Construction for Symmetric Hadamard Matrices. arXiv e-prints, pp.arXiv-1512.[Google Scholor]
Geramita, A.V., 1979. Orthogonal design, quadratic forms and hadamard matrices. Lecture notes in pure and applied mathematics, 43.[Google Scholor]
Hall, M., 1988. Combinatorial theory . Wiley- Interscience, 2nd edition.[Google Scholor]
Seberry, J., 2017. Orthogonal designs. Hadamard matrices, quadratic forms and algebra. Springer International Publishing AG.[Google Scholor]
Wallis, W.D., Street, A.P. and Wallis, J.S., 1972. Combinatorics: Room squares, sum-free sets, Hadamard matrices. Springer-Verlag, Berlin-Heidelberg, New York .[Google Scholor]
Saurabh, S. and Sinha, K., 2023. Matrix approaches to constructions of group divisible designs. Bulletin of the ICA, 97, pp.83-105.[Google Scholor]
Raghavarao, D. and Padgett, L.V., 2005. Block designs: analysis, combinatorics, and applications. Series on Applied Mathematics, 17, World Scientific, Singapore.[Google Scholor]
Saurabh, S. and Prasad, D., 2023. Certain Incomplete Block Designs from Combinatorial Matrices. Journal of the Indian Society for Probability and Statistics, 24(2), pp.535-544.[Google Scholor]

[1] Sylvester, J.J., 1867. LX. Thoughts on inverse orthogonal matrices, simultaneous signsuccessions, and tessellated pavements in two or more colours, with applications to Newton’s rule, ornamental tile-work, and the theory of numbers. The London, Edinburgh, and Dublin Philosophical Magazine and Journal of Science, 34(232), pp.461-475.[Google Scholor]

[2] Agaian, S.S., 2006. Hadamard matrices and their applications (Vol. 1168). Springer-Verlag, Berlin Heidelberg, New York.[Google Scholor]

[3] Agaian, S.S., Sarukhanyan, H., Egiazarian, K. and Astola, J., 2011, August. Hadamard transforms. SPIE Press, Bellingham, Washington USA.[Google Scholor]

[4] Goethals, J.M. and Seidel, J.J., 1967. Orthogonal matrices with zero diagonal. Canadian Journal of Mathematics, 19, pp.1001-1010.[Google Scholor]

[5] Shen, S. and Zhang, X., 2023. Constructions of Goethals-Seidel Sequences by Using $k$-Partition. Mathematics, 11(2), p.294.[Google Scholor]

[6] Doković, D. Ž . and Kotsireas, I.S., 2018. Goethals-Seidel difference families with symmetric or skew base blocks. Mathematics in Computer Science, 12, pp.373-388.[Google Scholor]

[7] Xia, M., Xia, T., Seberry, J. and Wu, J., 2005. An infinite family of Goethals-Seidel arrays. Discrete Applied Mathematics, 145(3), pp.498-504.[Google Scholor]

[8] Seberry, J. and Balonin, N.A., 2015. The Propus Construction for Symmetric Hadamard Matrices. arXiv e-prints, pp.arXiv-1512.[Google Scholor]

[9] Geramita, A.V., 1979. Orthogonal design, quadratic forms and hadamard matrices. Lecture notes in pure and applied mathematics, 43.[Google Scholor]

[10] Hall, M., 1988. Combinatorial theory . Wiley- Interscience, 2nd edition.[Google Scholor]

[11] Seberry, J., 2017. Orthogonal designs. Hadamard matrices, quadratic forms and algebra. Springer International Publishing AG.[Google Scholor]

[12] Wallis, W.D., Street, A.P. and Wallis, J.S., 1972. Combinatorics: Room squares, sum-free sets, Hadamard matrices. Springer-Verlag, Berlin-Heidelberg, New York .[Google Scholor]

[13] Saurabh, S. and Sinha, K., 2023. Matrix approaches to constructions of group divisible designs. Bulletin of the ICA, 97, pp.83-105.[Google Scholor]

[14] Raghavarao, D. and Padgett, L.V., 2005. Block designs: analysis, combinatorics, and applications. Series on Applied Mathematics, 17, World Scientific, Singapore.[Google Scholor]

[15] Saurabh, S. and Prasad, D., 2023. Certain Incomplete Block Designs from Combinatorial Matrices. Journal of the Indian Society for Probability and Statistics, 24(2), pp.535-544.[Google Scholor]

Contents

Journal of Combinatorial Mathematics and Combinatorial Computing

Block Structured Hadamard matrices from certain arrays

Abstract

1. Introduction

2. Preliminaries

3. Main Result

3. Conclusion

Acknowledgment

References:

Information

Guidelines

CP Initiatives

Follow CP