¹¹institutetext: ¹ Hacettepe University, Department of Mathematics,
Beytepe, 06800, Ankara, Turkey
¹¹email: [email protected], [email protected]
² Middle East Technical University, Institute of Applied Mathematics,
06800, Ankara, Turkey
¹¹email: [email protected]

Butson-Hadamard matrices and Plotkin-optimal $p^{k}$ -ary codes

Damla Acar¹ Bülent Saraç¹ Oğuz Yayla²

Abstract

A Butson-Hadamard matrix $H$ is a square matrix of dimension $n$ whose entries are complex roots of unity such that $HH^{*}=nI$ . In the first part of this work, some new results on generalized Gray map are studied. In the second part, codes obtained from Butson-Hadamard matrices and some bounds on the minimum distance of these codes are proved. In particular, we show that the code obtained from a Butson-Hadamard matrix meets the Plotkin bound under a non-homogeneous weight. We also give the parameters of some code families which are obtained from modified Butson-Hadamard matrices under a (non)homogeneous Gray map.
2020 AMS Subject Classification: 05B20,94B60,94B65

Keywords:

Butson-Hadamard matrices, codes, generalized Gray map, Plotkin bound

1 Introduction

A Hadamard matrix of order $n$ is an $n\times n$ matrix whose entries are ${1,-1}$ satisfying $HH^{T}=nI_{n}$ . Here $I_{n}$ is the $n\times n$ identity matrix. Hadamard [8] conjectured that such matrices exist for every $n$ that is a multiple of $4$ . See [9, 11, 16] for more information about Hadamard matrices and their applications. Hadamard matrices can be generalized in many ways. Two of them are Butson-Hadamard (BH) matrices which are introduced by Butson in [3] and generalized Hadamard (GH) matrices by Drake in [6].

A Butson-Hadamard matrix $H$ is an $n\times n$ matrix whose entries are complex roots of unity such that

HH^{*}=nI_{n}

where $H^{*}$ is the Hermitian transpose of $H$ . If all the entries of $H$ are $k$ -th roots of unity then we say that $H$ is a ${\rm BH}(n,k)$ .

Another generalization of Hadamard matrices is (group) generalized Hadamard matrices. Let $G=\{g_{1},g_{2},\ldots,g_{m}\}$ be a finite group and let $H$ be an $n\times n$ matrix whose entries are elements of $G$ . For convenience, we identify the group $G$ with the naturally embedded copy of $G$ in the group ring $\mathbb{Z}[G]=\{\sum^{m}_{i=1}a_{i}g_{i}|a_{i}\in\mathbb{Z}\}.$ A natural involution on $\mathbb{Z}[G]$ , which we shall call conjugation, is defined by

\overline{(\sum a_{i}g_{i})}:=\sum a_{i}g^{-1}_{i}.

(1)

Then, for the matrices with entries in $\mathbb{Z}[G]$ , define an adjoint, $M^{*}=[m_{ij}]^{*}:=[\overline{m_{ji}}].$ That is the adjoint is performed by first taking the transpose of the matrix and then conjugating each entry. We call that an $n\times n$ matrix $H$ whose entries are in $G$ is a (group) generalized Hadamard matrix if

HH^{*}\equiv nI_{n}\mod\sum_{g\in G}{g}.

(2)

For brevity, we say that such a matrix $H$ is a ${\rm GH}(n,G)$ .

For example, the following is a ${\rm GH}(5,C_{5}$ ), where $\zeta$ is a generator of the cyclic group $C_{5}$ of order 5.

H=\left(\begin{array}[]{ccccc}1&\zeta&\zeta^{4}&\zeta^{4}&\zeta\\ \zeta&1&\zeta&\zeta^{4}&\zeta^{4}\\ \zeta^{4}&\zeta&1&\zeta&\zeta^{4}\\ \zeta^{4}&\zeta^{4}&\zeta&1&\zeta\\ \zeta&\zeta^{4}&\zeta^{4}&\zeta&1\\ \end{array}\right)

Also we can say that a ${\rm GH}(n,G)$ can exist only if $n$ is a multiple of $|G|$ . See also [12] for more information about generalized Hadamard matrices.

It is known that a BH (resp. GH) matrix can be transformed to an equivalent matrix consisting of 1s in the first row and column by dividing rows or columns, or by interchanging rows or columns. So, a BH (resp. GH) matrix is said to be normalized if the first row and column consist entirely of 1s.

In this paper we first study the parameters for code families where the rows of BH and modified BH matrices are assigned to be codewords. The minimum distance between the rows of normalized GH matrices has been studied widely, see [11, Sections 4.4 and 9.4]. In addition to minimum distance, the rank and kernel of the codes obtained from a GH matrix were recently studied in [4, 5], and codes from a cocyclic GH matrix and their equivalence to combinatorial difference sets are studied in [1, 2]. On the other hand, Greferath, McGuire and O’Sullivan [7] showed that the codes obtained from BH matrices meet the Plotkin bound under any homogeneous weight. Stepanov [18] also constructed codes obtained from modified BH matrices, which have parameters close to the Plotkin bound.

In this paper, we give a lower bound for the minimum distance of the codes obtained from a normalized BH matrix and an amenable BH matrix in Theorem 4.1 and 4.2, respectively. Then, we prove their minimum distance under a homegeneous Gray map, in Corollary 1. We also consider codes obtained from the image of the modified BH matrices under a non-homogeneous Gray map, and we prove their minimum distances in Theorem 4.3. We also show that the distances between the rows are same, hence the code is equidistant. Moreover, we show that the code meets the Plotkin bound in Corollary 4.

The paper is organized as follows. We study the generalized Plotkin bound in Section $2$ and generalized Gray map in Section $3$ . In Section $4$ we give some results on the minimum distance of codes obtained from BH and modified BH matrices. The codes obtained from the image of BH matrices under the non-homogeneous Gray map are given in Section $5$ .

2 The generalized Plotkin bound

Hadamard codes have been widely studied in the literature, see for instance [11]. Greferath et al. in [7] considered BH matrices and determined the parameters of the code obtained from normalized BH matrices, where they considered homogeneous weights. Their result is given below, but we first give the definition of a homogeneous weight.

Definition 1

[7] A real-valued function $w$ on the finite ring $R$ is called a homogeneous weight if $w(0)=0$ and the following hold:
(i) $Rx=Ry$ implies $w(x)=w(y)$ for all $x,y\in R$ .
(ii) There exists a real number $\gamma$ such that

\sum_{y\in Rx}w(y)=\gamma|Rx|,\forall x\in R\backslash\{0\},

where the number $\gamma$ is called the average value of $w$ on $R$ .

For instance, the Lee weight $w_{L}$ on ${\mathbb{Z}}_{4}$ defined by $w_{L}(0)=0,w_{L}(1)=w_{L}(3)=1$ and $w_{L}(2)=2$ is a homogeneous weight with the average value $\gamma=1$ .

A $q$ -ary $(n,M,d)$ code is defined to be a nonempty subset of ${\mathbb{Z}}_{q}^{n}$ of size $M$ , where d is the minimum distance of the code determined by the distance function induced by a specified homogeneous weight on ${\mathbb{Z}}_{q}^{n}$ . For an $(n,M,d)$ code with $d>\gamma n$ , the generalized Plotkin bound states that $M\leq d/(d-\gamma n)$ , and it is called Plotkin-optimal when

\displaystyle M>d/(d-\gamma n)-1,

(3)

where $\gamma$ is the average value of the specified homogeneous weight.

Theorem 2.1

[7] Let $H=[\zeta_{h}^{a_{ij}}]$ be a normalized Butson-Hadamard matrix of type ${\rm BH}(n,h)$ for some primitive $h$ -th root of unity $\zeta_{h}$ . Then the code in $({\mathbb{Z}}_{h})^{n-1}$ formed by taking the rows of $H^{\prime}=[a_{ij}]$ and omitting the first coordinate is a code over ${\mathbb{Z}}_{h}$ with parameters $(n-1,n,\gamma n)$ that meets the Plotkin bound.

3 Generalized Gray maps

In this section we consider two kinds of generalized Gray maps. At first, we give the generalized Gray map $G_{1}$ , originated in [10] (see Definition 2 below). Note that $G_{1}$ gives rise to a homogeneous weight. As Theorem 2.1 states, codes obtained from rows of BH matrices satisfy the Plotkin bound under any homogeneous weight [7]. On the other hand, very little is known when the map is non-homogeneous. Hence, we consider a generalized Gray map $G_{2}$ which yields a non-homogeneous weight $w_{2}$ (see Definition 3). We also prove some lemmas on $G_{2}$ in which we give the minimum distance of BH codes under the weight $w_{2}$ defined by $G_{2}$ .

Definition 2

Let $k$ be a positive integer, $u$ be any element of ${\mathbb{Z}}_{p^{k}}$ and $u=\sum_{i=1}^{k}u_{i}p^{i-1}$ its $p$ -ary expansion for some $u_{i}\in\{0,1,\ldots,p-1\}$ . The image of $u$ by a Gray map $G_{1}$ is defined to be the Boolean function on $GF(p)^{k-1}$ :

\displaystyle{}\begin{array}[]{lll}G_{1}(u):(y_{1},\ldots,y_{k-1})\rightarrow u_{k}+\sum_{i=1}^{k-1}u_{i}y_{i}.\end{array}

(5)

Example 1

Suppose that $k=3$ and $p=2$ . Then the Gray map for $u$ is defined as follows:

\displaystyle{}\begin{array}[]{lll}G_{1}(u):(y_{1},y_{2})\rightarrow u_{3}+u_{1}y_{1}+u_{2}y_{2},\end{array}

(7)

where $(y_{1},y_{2})\in\mathbb{Z}^{2}_{2}$ , in lexicographical order, are taken as follows:

$y_{2}$	$y_{1}$
0	0
0	1
1	0
1	1

If $u=6$ , then its binary representation is equal to $(u_{3}u_{2}u_{1})=(110)$ . Therefore if $(y_{1},y_{2})=(0,0)$ then we get $G_{1}(6)=1$ . If we continue like this we can get Boolean function $G_{1}(u)=(1100)$ .

Let $w$ be the Hamming weight and $w_{1}$ be a weight on ${\mathbb{Z}}_{p^{k}}$ defined by $w_{1}(u)=w(G_{1}(u))$ . We note that $w_{1}(0)=0$ and for any $u\neq 0$

\displaystyle{}w_{1}(u):=\left\{\begin{array}[]{cc}p^{k-1}-p^{k-2}&\mbox{if }u\in{\mathbb{Z}}_{p^{k}}\backslash\{p^{k-1},2p^{k-1},\ldots,(p-1)p^{k-1}\}\\ p^{k-1}&\mbox{otherwise.}\end{array}\right.

(10)

Then one can easily deduce from Definition 1 that $w_{1}$ is a homogeneous weight. In what follows, we list some properties of $G_{1}$ .

i.

Let $k$ be a positive integer and $u=\sum_{i=1}^{k}u_{i}2^{i-1}\in{\mathbb{Z}}_{2^{k}}$ for some $u_{i}\in\{0,1\}$ . Then $G_{1}(u)$ is a homomorphism from ${\mathbb{Z}}_{2}^{k-1}$ to ${\mathbb{Z}}_{2}$ .

ii.

Let $a,b\in{\mathbb{Z}}_{{2}^{k}}$ such that $a\neq b$ . Then

\displaystyle{}d(G_{1}(a),G_{1}(b))=\left\{\begin{array}[]{cc}2^{k-1}&\mbox{if }a-b=2^{k-1}\\ 2^{k-2}&\mbox{otherwise}.\end{array}\right.

(13)

Here $d(G_{1}(a),G_{1}(b))$ is the Hamming distance between $G_{1}(a)$ and $G_{1}(b)$ .

In this paper we also consider another Gray map which yields a non-homogeneous weight.

Definition 3

[20] Let $p>2$ be a prime number and $k$ be a positive integer. A Gray map, denoted $G_{2}$ , on ${\mathbb{Z}}_{p^{k}}$ is defined as follows:

i.

If $u\leq p^{k-1}$ , then $G_{2}(u)\in{\mathbb{Z}}_{p}^{p^{k-1}}$ has 1 in the first $u$ location and $0$ ’s elsewhere.
ii.

If $u\geq p^{k-1}+1$ , then $G_{2}(u)=\bar{q}+G_{2}(r)$ , where $q$ and $r<p^{k-1}$ are positive integers such that $u=qp^{k-1}+r$ and $\bar{q}=(qqq\cdots qqq)$ .

Let $w_{2}$ be the weight on ${\mathbb{Z}}_{{p}^{k}}$ defined by $w_{2}(u)=w(G_{2}(u))$ . Then we have

\displaystyle{}w_{2}(u):=\left\{\begin{array}[]{ccc}u&\mbox{if }&u\leq p^{k-1}\\ p^{k-1}&\mbox{if}&p^{k-1}\leq u\leq p^{k}-p^{k-1}\\ p^{k}-u&\mbox{if}&p^{k}-p^{k-1}<u\leq p^{k}-1.\end{array}\right.

(17)

As the following example shows, $w_{2}$ is not homogeneous in general.

Example 2

Let $p=3$ , $k=2$ and $R={\mathbb{Z}}_{9}$ . Now if we take $x=2$ and $y=8$ , then $Rx=Ry$ ; but since $G_{2}(2)=(110)$ , $G_{2}(8)=(002)$ , $w_{2}(x)$ and $w_{2}(y)$ are not equal. Therefore $w_{2}$ is not homogeneous by Definition 1.

Now we give four lemmas that we will use in the proof of Theorem 4.3.

Lemma 1

Let $m,n\in{\mathbb{Z}}_{p^{k}}$ with $m,n\neq 0$ . If either $m,n<p^{k-1}$ and $m+n=p^{k-1}$ or $m>n>(p-1)p^{k-1}$ and $m-n=(p-1)p^{k-1}$ , then the total number of $0$ ’s in $G_{2}(m)$ and $G_{2}(n)$ is $p^{k-1}.$

Proof

If $m,n<p^{k-1}$ and $m+n=p^{k-1}$ then the result is clear from the definition of $G_{2}$ . Let $m>n$ and $m-n=(p-1)p^{k-1}.$ Since $m>n$ and $m=n+(p-1)p^{k-1}$ we see that $n<p^{k-1}$ . Therefore, the number of $0$ ’s in $G_{2}(n)$ is equal to $p^{k-1}-n$ . On the other hand, $G_{2}(m)=G_{2}((p-1)p^{k-1}+n)$ , and by definition, the number of $0$ ’s in $G_{2}(m)$ is $n.$ This completes the proof.

Example 3

Let $p=3$ , $k=3$ . If we take $n=8$ and $m=n+(p-1)p^{k-1}=26$ then we can easily find that $G_{2}(n)=G_{2}(8)=(111111110)$ and $G_{2}(m)=G_{2}(26)=(000000002)$ . Therefore the total number of $0$ ’s in $G_{2}(m)$ and $G_{2}(n)$ is equal to $9=p^{k-1}.$

Lemma 2

Let $p$ be a prime number, $k\in{\mathbb{Z}}^{+}$ , $i,j\in{\mathbb{Z}}_{p^{k}}$ and $|i-j|=n$ . Then

\displaystyle{}d(G_{2}(i),G_{2}(j))=\left\{\begin{array}[]{cc}n&\mbox{if }n<p^{k-1}\\ p^{k-1}&otherwise.\end{array}\right.

(20)

Proof

First we consider $n<p^{k-1}$ . Without loss of generality we take $i>j$ . If $i\leq p^{k-1}$ then $G_{2}(i)=(111\ldots 11000\ldots 00)$ by the definition of $G_{2}$ , where it has the number $1$ in the first $i$ coordinates and the others are $0$ . We also have $j<p^{k-1}$ and $j=i-n$ as $j<i.$ Therefore $G_{2}(j)=(111\ldots 11000\ldots 00)$ such that the first $i-n$ coordinates are $1$ and the others are $0$ . So $d(G_{2}(i),G_{2}(j))=n$ . Now if $i>p^{k-1}$ then we can write $i=qp^{k-1}+r$ for some $q,r\in{\mathbb{Z}}^{+}$ such that $r<p^{k-1}.$ Then $G_{2}(i)=\overline{q}+G_{2}(r)$ . Also $j=i-n$ and $n<p^{k-1}$ . Now, if $n<r$ then we can say that $j=qp^{k-1}+r-n$ and $r-n<p^{k-1}$ . Therefore $d(G_{2}(i),G_{2}(j))=n$ . If $n\geq r$ then $j=(q-1)p^{k-1}+p^{k-1}-(n-r).$ Hence $G_{2}(i)=(q+1\quad q+1\ldots q+1\underbrace{qq\ldots qq}_{p^{k-1}-r})$ and $G_{2}(j)=(qq\ldots qq\underbrace{q-1\quad q-1\ldots q-1}_{n-r})$ . Also we can say that $p^{k-1}-r>n-r$ since $n>r,n<p^{k-1}$ . Therefore there are $p^{k-1}-r-n+r$ same coordinates in $G_{2}(i)$ and $G_{2}(j)$ . So $d(G_{2}(i),G_{2}(j))=n$ .

Now suppose that $j=qp^{k-1}+r,n=mp^{k-1}+r^{\prime}$ and $r+r^{\prime}=lp^{k-1}+r^{\prime\prime}$ for some $q,m,l,r,r^{\prime},r^{\prime\prime}\in{\mathbb{Z}}^{+}$ such that $r,r^{\prime},r^{\prime\prime}<p^{k-1}$ . Then $i=(q+m+l)p^{k-1}+r^{\prime\prime}$ and since $i<p^{k}$ we must have $q+m+l<p$ . It follows that $G(i)=\overline{q+m+l}+G_{2}(r^{\prime\prime})$ and $G_{2}(j)=\overline{q}+G_{2}(r)$ . Since $r\neq r^{\prime\prime}$ , we obtain $d(G_{2}(i),G_{2}(j))=p^{k-1}$ . Also it is clear that if $j\leq p^{k-1}$ , then $d(G_{2}(i),G_{2}(j))=p^{k-1}$ .

Lemma 3

Let $p$ be a prime number, $k\in{\mathbb{Z}}^{+}$ , $\zeta$ be a primitive $p^{k}$ -th root of unity and $a_{i}\in{\mathbb{Z}}^{+}$ for $i=1,2,\ldots,n$ . If $\zeta^{a_{1}}+\cdots+\zeta^{a_{n}}=0$ , then the total number of zeros in $[G_{2}(a_{1}),G_{2}(a_{2}),\ldots,G_{2}(a_{n})]$ is equal to $np^{k-2}$ .

Proof

We know that $a_{i}$ ’s satisfying $\zeta^{a_{1}}+\zeta^{a_{2}}+\cdots+\zeta^{a_{n}}=0$ will only be of the form $a_{i}=ip^{x}+j$ , where $x<k,j<p^{x}$ and $i=1,2,\ldots,p^{k-x}$ , see [13, Theorem 3.3]. Here we will give a proof only for the case $j=0$ , since we will give the case where $j$ is nonzero in Corollary. 3 We know that obtaining $0$ in the images $G_{2}(a_{i})$ for $i=1,2,\ldots,n$ is only possible for $1\leq a_{i}<p^{k-1}$ or $(p-1)p^{k-1}<a_{i}\leq p^{k}$ . So the number of $0$ in $G_{2}(a_{1}),G_{2}(a_{2}),\ldots,G_{2}(a_{p^{k-x}})$ are equal to $p^{k-1}-p^{x},p^{k-1}-2p^{x},\ldots,(p^{k-1-x}-1)p^{x}$ , respectively. Here there are $p^{k-1-x}-1$ elements. On the other hand, the number of zero in $G_{2}(a_{i})$ for $(p-1)p^{k-1}<a_{i}\leq p^{k}$ are $p^{x},2p^{x},\ldots,(p^{k-1-x}-1)p^{k-1},p^{k-1}$ , in order. Therefore, the total number of zeros in $G_{2}(a_{1}),G_{2}(a_{2}),\linebreak\ldots,G_{2}(a_{p^{k}-x})$ is

(p^{k-1-x}-1)p^{k-1}+p^{k-1}=p^{k-2}p^{k-x}=np^{k-2}.

Example 4

Let $p=3,k=3$ and $\zeta$ be the primitive $27-$ th root of unity. Also we know that $\zeta^{3}+\zeta^{6}+\zeta^{9}+\zeta^{12}+\zeta^{15}+\zeta^{18}+\zeta^{21}+\zeta^{24}+\zeta^{27}=0$ . Then $G_{2}(3)=(111000000),G_{2}(6)=(111111000),G_{2}(9)=(111111111),G_{2}(12)=(222111111),G_{2}(15)=(222222111),G_{2}(18)=(222222222),G_{2}(21)=(000111111)$ , $G_{2}(24)=(000000111),G_{2}(27)=(000000000)$ . Total number of zeros in these images is equal to $np^{k-2}=27.$

4 Butson-Hadamard codes

In this section we will study codes obtained via assigning rows of normalized BH matrices and their translates as codewords. Namely, let $\zeta$ be a primitive $k$ -th root of unity, $H=[\zeta^{a_{ij}}]$ be a normalized ${\rm BH}(n,k)$ matrix and $[a_{ij}]$ be the matrix with entries taken from the exponents of corresponding entries of $H$ . Then codes are constructed from the rows of $[a_{ij}]$ .

Codes from normalized generalized Hadamard matrices and their translates are widely studied, see [11, Chapter 4] and references therein. Besides, codes constructed from modified quaternary complex BH matrices are given in [17], which are close to the Plotkin bound. Another type modified ${\rm BH}$ matrices and the codes obtained from them are studied in [14].

Definition 4

Let $n,k$ be positive integers and $\zeta$ be a primitive $k$ -th root of unity, $H=[\zeta^{a_{ij}}]$ be a normalized $BH(n,k)$ matrix. Suppose that $N$ be the set of all $k$ -th roots of unity. If $R_{i}$ is the $i$ -th row of H then, $uR_{i}$ is called a translate of $R_{i}$ for some $u\in N$ .

We use the definitions given in [11, Definition 4.32] and we take the Hamming weight for the codes obtained from BH matrices in the following theorem.

Theorem 4.1

Let $n,k$ be positive integers, $\zeta$ be a primitive $k$ -th root of unity, $H=[\zeta^{a_{ij}}]$ be a normalized ${\rm BH}(n,k)$ matrix and $N$ be the set of all $k$ -th roots of unity. Let $H^{\prime}=[a_{ij}]$ and $l=\min\{i\geq 2:i|k\}$ .

i.

$A_{k}$ the $k$ -ary $(n-1,n,d_{A})$ code consisting of the rows of $H^{\prime}$ with the first column deleted. Here $d_{A}\geq n-\dfrac{n}{l}$ .
ii.

$B_{k}$ the $k$ -ary $(n-1,nk,d_{B})$ code consisting of the rows of exponent matrix of the translates $uH$ , $u\in N$ with first column deleted. Here $d_{B}\geq n-\dfrac{n}{l}-1$
iii.

$C_{k}$ the $k$ -ary $(n,nk,d_{C})$ code consisting of the rows of exponent matrix of the translates $uH$ , $u\in N$ . Here $d_{C}\geq n-\dfrac{n}{l}$
iv.

$D_{k}$ , $n=k$ , the $k$ -ary $(n+1,n^{2},d_{D})$ code consisting of the rows of exponent matrix of $(uH)c$ for all $u\in N$ and any fixed noninitial column $c$ of $H$ . Here $d_{D}\geq n-\dfrac{n}{l}$ .

Proof

i.

We first note that $l$ is a prime number. If $\zeta$ is a primitive $k$ -th root of unity then $\zeta^{\frac{k}{l}}$ is $l$ -th root of unity. Then $(\zeta^{\frac{k}{l}})+(\zeta^{\frac{k}{l}})^{2}+\ldots+(\zeta^{\frac{k}{l}})^{l}=0$ . This implies that we must have at least $l$ elements in order to get vanishing sum. On the other hand, since the rows of BH matrices are orthogonal, the number of same elements in two rows of $H$ must be smaller than $\frac{n}{l}$ . That is $n-d_{A}\leq\frac{n}{l}$ . So we have $d_{A}\geq n-\frac{n}{l}$ .
ii.

Let $u=\zeta^{m}$ be an element of $N$ . Then it is clear that the codes $A_{k}$ and shifting of $A_{k}$ with $m$ have same minimum distance. Now let $R_{i}$ and $R^{u}_{i}$ be the $i$ -th row of $H$ and $uH$ , respectively, with the first column deleted for $i=1,2,\ldots,n$ . So $d(R_{i},R^{u}_{j})=n-1$ if $i=j$ . On the other hand, as $R^{u}_{j}=uR_{j}$ we have $d(R_{i},R^{u}_{j})=n-1-\#\{u|u\in R_{i}^{-1}R_{j}^{u}\}$ for $i\neq j$ . If we use the same argument in the proof of (i), we can say that $\#\{u|u\in R_{i}^{-1}R_{j}^{u}\}\leq\frac{n}{l}$ . Therefore $d_{B}\geq n-\frac{n}{l}-1$ .
iii.

$C_{k}$ has codewords of length $n$ . Similar to the proof of (ii), we have $d_{C}\geq n-\frac{n}{l}$
iv.

$D_{k}$ and $C_{k}$ are only one column different from each other. Therefore $d_{D}\geq n-\frac{n}{l}$ .

Example 5

Let $\zeta$ be a primitive $36$ -th root of unity and

H_{1}=\left(\begin{array}[]{cccccccccccc}1&1&1&1&1&1&1&1&1&1&1&1\\ 1&\zeta^{12}&\zeta^{24}&\zeta^{28}&\zeta^{4}&\zeta^{16}&1&\zeta^{12}&\zeta^{24}&1&\zeta^{12}&\zeta^{24}\\ 1&\zeta^{24}&\zeta^{12}&\zeta^{20}&\zeta^{8}&\zeta^{32}&1&\zeta^{24}&\zeta^{12}&1&\zeta^{24}&\zeta^{12}\\ 1&\zeta^{27}&1&1&1&1&\zeta^{18}&\zeta^{9}&\zeta^{18}&\zeta^{18}&\zeta^{18}&\zeta^{18}\\ 1&\zeta^{3}&\zeta^{24}&\zeta^{28}&\zeta^{4}&\zeta^{16}&\zeta^{18}&\zeta^{21}&\zeta^{6}&\zeta^{18}&\zeta^{30}&\zeta^{6}\\ 1&\zeta^{15}&\zeta^{12}&\zeta^{20}&\zeta^{8}&\zeta^{32}&\zeta^{18}&\zeta^{33}&\zeta^{30}&\zeta^{18}&\zeta^{6}&\zeta^{30}\\ 1&1&1&\zeta^{18}&\zeta^{18}&\zeta^{18}&\zeta^{9}&1&1&\zeta^{27}&\zeta^{18}&\zeta^{18}\\ 1&\zeta^{12}&\zeta^{24}&\zeta^{10}&\zeta^{22}&\zeta^{34}&\zeta^{9}&\zeta^{12}&\zeta^{24}&\zeta^{27}&\zeta^{30}&\zeta^{6}\\ 1&\zeta^{24}&\zeta^{12}&\zeta^{2}&\zeta^{26}&\zeta^{14}&\zeta^{9}&\zeta^{24}&\zeta^{12}&\zeta^{27}&\zeta^{6}&\zeta^{30}\\ 1&\zeta^{27}&1&\zeta^{18}&\zeta^{18}&\zeta^{18}&\zeta^{27}&\zeta^{9}&\zeta^{18}&\zeta^{9}&1&1\\ 1&\zeta^{3}&\zeta^{24}&\zeta^{10}&\zeta^{22}&\zeta^{34}&\zeta^{27}&\zeta^{21}&\zeta^{6}&\zeta^{9}&\zeta^{12}&\zeta^{24}\\ 1&\zeta^{15}&\zeta^{12}&\zeta^{2}&\zeta^{26}&\zeta^{14}&\zeta^{27}&\zeta^{33}&\zeta^{30}&\zeta^{9}&\zeta^{24}&\zeta^{12}\end{array}\right)

be a ${\rm BH}(12,36)$ matrix. Here the minimum distance between the rows of $H_{1}$ is equal to $d_{A}=7$ by using SageMath [19], therefore $d_{A}\geq n-\frac{n}{l}$ is satisfied, where $n=12$ and $l=min\{i\geq 2:i|36\}=2$ . Similarly, for a primitive $10$ -th root of unity, $\zeta$ , let

H_{2}=\left(\begin{array}[]{ccccccccc}1&1&1&1&1&1&1&1&1\\ 1&\zeta^{5}&\zeta^{3}&\zeta^{3}&\zeta^{5}&\zeta^{9}&\zeta^{8}&\zeta^{7}&\zeta\\ 1&\zeta^{4}&\zeta^{5}&\zeta^{7}&\zeta&\zeta^{3}&\zeta^{5}&\zeta^{9}&\zeta^{9}\\ 1&\zeta^{3}&\zeta^{7}&\zeta^{5}&\zeta&\zeta^{8}&\zeta^{9}&\zeta^{3}&\zeta^{5}\\ 1&\zeta^{9}&\zeta&\zeta^{5}&\zeta^{5}&\zeta^{3}&\zeta^{7}&\zeta^{2}&\zeta^{7}\\ 1&\zeta^{9}&\zeta^{5}&\zeta&\zeta^{3}&\zeta^{5}&\zeta&\zeta^{7}&\zeta^{6}\\ 1&\zeta&\zeta^{7}&\zeta^{9}&\zeta^{6}&\zeta&\zeta^{5}&\zeta^{5}&\zeta^{3}\\ 1&\zeta^{7}&\zeta^{9}&\zeta^{4}&\zeta^{9}&\zeta^{5}&\zeta^{3}&\zeta^{5}&\zeta\\ 1&\zeta^{5}&\zeta^{2}&\zeta^{9}&\zeta^{7}&\zeta^{7}&\zeta^{3}&\zeta&\zeta^{5}\end{array}\right)

be a ${\rm BH}(9,10)$ matrix. It can be verified that the minimum distance between the rows of $H_{2}$ is equal to $d_{A}=7$ and satisfies $d_{A}\geq n-\frac{n}{l}$ , where $n=9$ and $l=2$ . Now consider $B_{k}$ . In this case, we have $A_{k}$ and its translates as codewords. If we calculate the minimum distance by SageMath, we get $d_{B}=5$ and so $d_{B}\geq n(1-\frac{1}{l})-1$ . Again, by using SageMath, we can get that the minimum distance for $C_{k}$ is $d_{C}=6$ , which satisfies $d_{C}\geq n-\frac{n}{l}$ .

Let $\zeta$ be a primitive $6$ -th root of unity. Then

H_{2}=\left(\begin{array}[]{cccccc}1&1&1&1&1&1\\ 1&\zeta&\zeta^{2}&\zeta^{3}&\zeta^{4}&\zeta^{5}\\ 1&\zeta^{2}&\zeta^{4}&1&\zeta^{2}&\zeta^{4}\\ 1&\zeta^{3}&1&\zeta^{3}&1&\zeta^{3}\\ 1&\zeta^{4}&\zeta^{2}&1&\zeta^{4}&\zeta^{2}\\ 1&\zeta^{5}&\zeta^{4}&\zeta^{3}&\zeta^{2}&\zeta\\ \end{array}\right)

is a ${\rm BH}(6,6)$ matrix. If we calculate the minimum distance for $D_{k}$ by SageMath, we get $d_{D}=3$ , so $d_{D}\geq n(1-\frac{1}{l})$ holds.

Remark 1

We note that it is easy to get a code with larger alphabet size without decreasing the minimum distance by combining two BH matrices under Chinese Remainder Theorem. Let $h,k$ be distinct prime numbers, $\zeta$ , $\alpha$ and $\beta$ be primitive $h$ -th, $k$ -th and $hk$ -th roots of unities, respectively. Also $H_{1}=[\zeta^{a_{ij}}]$ and $H_{2}=[\alpha^{b_{ij}}]$ be normalized ${\rm BH}(n,h)$ and ${\rm BH}(n,k)$ matrices, respectively. Let $d_{1}$ and $d_{2}$ be the minimum distance between the rows of $[a_{ij}]$ and $[b_{ij}]$ , respectively. Let $H=[\beta^{c_{ij}}]$ be the normalized matrix obtained from $H_{1}$ and $H_{2}$ such that $c_{ij}\equiv a_{ij}\mod h$ and $c_{ij}\equiv b_{ij}\mod k$ . Then the minimum distance of rows of $[c_{ij}]$ satisfies $d\geq\max\{d_{1},d_{2}\}$ .

Proposition 1

Let $R$ be a Frobenius ring and let $A=[a_{ij}]$ be a $n\times n$ matrix over $R$ . Suppose that for any $1\leq k,l\leq n$ with $k\neq l$ , the set

\displaystyle R_{k}-R_{l}:=\{a_{k1}-a_{l1},a_{k2}-a_{l2},\ldots,a_{kn}-a_{ln}\},

(21)

is a disjoint union of the cosets of right or left ideals of $R$ . Here $R_{k}$ and $R_{l}$ are the $k$ -th and $l$ -th rows of $A$ , respectively. Then for any generating character $\chi$ of $R$ , the matrix $H=[\chi(a_{ij})]$ is a Butson-Hadamard matrix.

Proof

Suppose that for $1\leq i,j\leq n$ with $i\neq j$ , $S_{i}$ and $S_{j}$ be the distinct rows of $H$ . Then $S_{i}=(\chi(a_{i1}),\chi(a_{i2}),\ldots,\chi(a_{in}))$ and $S_{j}=(\chi(a_{j1}),\chi(a_{j2}),\ldots,\chi(a_{jn}))$ . Therefore $S_{i}S_{j}^{*}=\displaystyle\sum_{k=1}^{n}\chi(a_{ik}-a_{jk})$ . We know that the sum of the images under $\chi$ over a right (or left) ideal of $R$ is equal to $0$ . Then for a fixed element $a\in R$ and a right (or left) ideal $I$ of $R$ , we have $\displaystyle\sum_{i\in I}\chi(a+i)=\displaystyle\sum_{i\in I}\chi(a)\chi(i)=\chi(a)\sum_{i\in I}\chi(i)=0$ ; so we can say that $S_{i}S_{j}^{*}=\displaystyle\sum_{k=1}^{n}\chi(a_{ik}-a_{jk})=0.$

If $i=j$ then $\displaystyle\sum_{k=1}^{n}\chi(a_{ik}-a_{jk})=\displaystyle\sum_{k=1}^{n}\chi(a_{ik}-a_{jk})=n$ . Therefore $H$ is a Butson-Hadamard matrix.

Definition 5

Let $R$ be a Frobenius ring and $A=[a_{ij}]$ be an $n\times n$ matrix over $R$ . Also suppose that $A$ satisfies (21). Then for any generating character $\chi$ of $R$ , the Butson-Hadamard matrix $H=[\chi(a_{ij})]$ is called an amenable Butson-Hadamard matrix.

Example 6

Suppose that $R$ is a finite Frobenius ring of characteristic $t$ and $\chi$ is a generating character for $R$ , $B:L\times M\rightarrow R$ be a nondegenerate bilinear pairing for the finite left $R$ -module $L$ and finite right $R$ -module $M$ . Then $H=[\chi(B(x,y))]_{L\times M}$ is a BH(t,m) Butson-Hadamard matrix, where $m=|L|=|M|$ by [15, Theorem 10]. All matrices created in this way are amenable Butson-Hadamard matrices since the elements in the row differences in $[B(x,y)]_{L\times M}$ form left ideals of $R$ .

Bilinear pairings give us amenable Butson-Hadamard matrices, but not all amenable $BH$ matrices have to be of this type. The matrix below is a counterexample.

Example 7

Let $R={\mathbb{Z}}_{6}$ and $A$ be a $6\times 6$ matrix over $R$ given as below.

A=\left(\begin{array}[]{ccccccc}0&0&0&0&0&0&0\\ 0&0&0&2&3&3&4\\ 0&1&3&5&0&3&3\\ 0&2&5&4&3&0&2\\ 0&3&4&2&5&2&0\\ 0&4&2&0&3&4&1\\ 0&4&2&3&1&0&4\end{array}\right)

It is readily checked that all pairwise row differences of $A$ are the unions of the cosets of $3{\mathbb{Z}}_{6}$ and $2{\mathbb{Z}}_{6}$ . Thus, if $\chi:R\longrightarrow\mathbb{C},\chi(a)=\zeta^{a}$ , where $\zeta$ is a primitive $6$ -th root of unity, then $H=[\chi(a_{ij})]$ is an amenable $BH(7,6)$ matrix.

Example 8

All matrices of type $BH(n,p^{k})$ are amenable $BH$ matrices where $p$ is a prime number and $k,n\in{\mathbb{Z}}^{+}$ , because every row difference in the additive representation of a $BH(n,p^{k})$ forms up a union of cosets of ideals $p^{i}Z_{p^{k}}$ for some $1\leq i\leq k-1$ , see [13, Theorem 3.3].

Remark 2

The authors of this article do not know the existence of a Butson-Hadamard matrix which is not amenable.

In Theorem 4.1 we have given lower bounds for the minimum distances of codes defined via rows of BH matrices. But in the following theorem we have obtained equality for these minimum distances by taking BH matrices as amenable.

Now suppose that $w$ is a homogeneous weight, $l=\max\{w(a):a\in{\mathbb{Z}}_{k}\}$ , $l^{\prime}=\min\{w(a):a\in{\mathbb{Z}}_{k}\backslash\{0\}\}$ and $\gamma$ is the average value of $w$ .

Theorem 4.2

Let $n$ and $k$ be positive integers, $H=[\zeta^{a_{ij}}]$ be a normalized amenable ${\rm BH}(n,k)$ matrix, $H^{\prime}=[a_{ij}]$ and $N$ be the set of all $k$ -th roots of unity. Also suppose that $A_{k},B_{k},C_{k}$ and $D_{k}$ are defined as in Theorem 4.1. Then $d_{A_{k}}=\gamma n,d_{B_{k}}=\gamma n-l,d_{C_{k}}=\gamma n$ and $d_{D_{k}}\in\{\gamma n,\gamma n+l^{\prime}\}$ .

Proof

We know that $d_{H}=\gamma n$ by Theorem 2.1. Now consider $B_{k}$ . Let $R_{i},R_{j}$ be the $i$ -th and $j$ -th rows of $H$ , respectively. Also suppose that $R^{\prime}_{j}$ is the $j$ -th row of $\zeta^{u}H$ such that $1\leq i,j\leq n$ and $i\neq j,u\in Z_{t}$ . So $R^{\prime}_{j}=\zeta^{u}R_{j}$ . If we use the same argument in the proof of 2.1 we can say that $f_{r+u}=|\{k\in\{1,\ldots,n\}:\log_{\zeta}(R_{ik}R^{-1}_{jk})=r+u\}|/n=f_{r}$ for all $r,u\in{\mathbb{Z}}_{t}$ . Here $\log_{\zeta}(R_{ik}R^{-1}_{jk})$ is the $k$ -th coordinate of $R_{i}R_{j}^{-1}.$ Therefore the proof of the Theorem 1 is also provided here as well. So $\sum_{k=1}^{k=n}(w(R_{ik}R^{-1}_{jk}))=\gamma n$ . But here since the first coordinates of $R_{i}$ and $R^{\prime}_{j}=uR_{j}$ will always be different if we delete the first coordinate, the minimum distance decrease by $l$ . After all this we get $d_{B_{k}}=\gamma n-l$ .

The $C_{k}$ code differs from $B_{k}$ only in the first coordinate. Therefore, from the results we obtained above we get $d_{C_{k}}=\gamma n.$

Finally we consider $D_{k}$ code. Since $D_{k}$ is obtained by adding a column to $C_{k}$ we can say that $d_{D_{k}}\in\{\gamma n,\gamma n+l^{\prime}\}$ .

As noted Example 8, all $BH$ matrices in the following corollary are amenable.

Corollary 1

Let $p>2$ be a prime number, $k\in{\mathbb{Z}}^{+}$ such that $k\geq 2$ and $\zeta$ be a primitive $p^{k}$ -th root of unity, $H=[\zeta^{a_{ij}}]$ be an $n\times n$ normalized Butson-Hadamard matrix and $N$ be the set of all $p^{k}$ -th roots of unity. Also let $H^{\prime}=[a_{ij}]$ and define $A_{k},B_{k},C_{k},D_{k}$ codes as in Theorem 4.1. Then, $d_{G_{1}(A_{k})}=n(p-1)p^{k-2}$ , $d_{G_{1}(B_{k})}=n(p-1)p^{k-2}-p^{k-1}$ , $d_{G_{1}(C_{k})}=n(p-1)p^{k-2}$ , $d_{G_{1}(D_{k})}\in\{p^{2k-2}(p-1),p^{k-2}(p^{k+1}-p^{k}+p-1)\}$ .

Proof

$d_{G_{1}(A_{k})}$ is a consequence of Theorem 2.1. We need to find the $\gamma$ average value of $w$ . Now since $G_{1}$ is balanced except for the elements of $L=\{p^{k-1},2p^{k-1},\ldots,p^{k}\}$ . Namely for every $1\leq\alpha\leq p^{k}$ such that $\alpha\notin L$ there are equal number of $0,1,\ldots,p-1$ in $G_{1}(\alpha)$ . For any $\beta\in L\backslash\{0\},w(\beta)=p^{k-1}$ . Therefore $l=p^{k-1}-p^{k-2},l^{\prime}=p^{k-1}$ and

\gamma=\frac{(p-1)p^{k-1}+(p^{k}-p)(p^{k-1}-p^{k-2})}{p^{k}}=p^{k-1}-p^{k-2}=(p-1)p^{k-2}.

So the result is obtained when the $\gamma$ is written instead of the Theorem 4.2.

Now we will give an example of Theorem 4.2.

Example 9

Let $p=3$ , $k=2$ and $\zeta$ be the primitive $9$ -th root of unity. Then

H=\left(\begin{array}[]{ccccccccc}1&1&1&1&1&1&1&1&1\\ 1&\zeta&\zeta^{2}&\zeta^{3}&\zeta^{4}&\zeta^{5}&\zeta^{6}&\zeta^{7}&\zeta^{8}\\ 1&\zeta^{2}&\zeta^{4}&\zeta^{6}&\zeta^{8}&\zeta&\zeta^{3}&\zeta^{5}&\zeta^{7}\\ 1&\zeta^{3}&\zeta^{6}&1&\zeta^{3}&\zeta^{6}&1&\zeta^{3}&\zeta^{6}\\ 1&\zeta^{4}&\zeta^{8}&\zeta^{3}&\zeta^{7}&\zeta^{2}&\zeta^{6}&\zeta&\zeta^{5}\\ 1&\zeta^{5}&\zeta&\zeta^{6}&\zeta^{2}&\zeta^{7}&\zeta^{3}&\zeta^{8}&\zeta^{4}\\ 1&\zeta^{6}&\zeta^{3}&1&\zeta^{6}&\zeta^{3}&1&\zeta^{6}&\zeta^{3}\\ 1&\zeta^{7}&\zeta^{5}&\zeta^{3}&\zeta&\zeta^{8}&\zeta^{6}&\zeta^{4}&\zeta^{2}\\ 1&\zeta^{8}&\zeta^{7}&\zeta^{6}&\zeta^{5}&\zeta^{4}&\zeta^{3}&\zeta^{2}&\zeta\end{array}\right)

is an amenable ${\rm BH}(9,9)$ matrix. Then

G_{1}(H^{\prime})=\left(\begin{array}[]{ccccccccccccccccccccccccccc}0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0\\ 0&0&0&0&1&2&0&2&1&1&1&1&1&2&0&1&0&2&2&2&2&2&0&1&2&1&0\\ 0&0&0&0&2&1&1&2&0&2&2&2&2&1&0&0&1&2&1&1&1&1&0&2&2&0&1\\ 0&0&0&1&1&1&2&2&2&0&0&0&1&1&1&2&2&2&0&0&0&1&1&1&2&2&2\\ 0&0&0&1&2&0&2&1&0&1&1&1&2&0&1&0&2&1&2&2&2&0&1&2&1&0&2\\ 0&0&0&1&0&2&0&1&2&2&2&2&0&2&1&2&0&1&1&1&1&2&1&0&1&2&0\\ 0&0&0&2&2&2&1&1&1&0&0&0&2&2&2&1&1&1&0&0&0&2&2&2&1&1&1\\ 0&0&0&2&0&1&1&0&2&1&1&1&0&1&2&2&1&0&2&2&2&1&2&0&0&2&1\\ 0&0&0&2&1&0&2&0&1&2&2&2&1&0&2&1&2&0&1&1&1&0&2&1&0&1&2\end{array}\right).

If we calculate the average weight we get $\gamma=2$ . By using SageMath [19], we obtain that $d_{G_{1}(A_{k})}=18=\gamma n$ , $d_{G_{1}(B_{k})}=15=\gamma n-l,d_{G_{1}(C_{k})}=18=\gamma n$ . Here $l=\max\{w(a):a\in{\mathbb{Z}}_{k}\setminus\{0\}\}=3$ . Let $c$ be the $4$ -th column of $H^{\prime}$ . Then we get $d_{G_{1}(D_{k})}=18$ . These minimum distances comply with the results in Theorem 4.2.

If $w$ is a homogeneous weight with the average value $\gamma$ over a Frobenius ring $R$ , then $\sum_{r\in y+I}w(r)=\gamma|I|$ for every nonzero ideal $I$ of $R$ , see [7, Proposition 2.6], a property which plays a crucial role in proving that some linear codes produced from a bimodule over $R$ by using a non-degenerated bilinear form meet the Plotkin bound [7, Theorem 4.3]. Note that this important property of a homogeneous weight is shared also by the non-homogeneous weight $w_{2}$ induced by the Gray map $G_{2}$ with $\gamma=(p-1)p^{k-2}$ , see Corollary 2 below. In the following definition we formalize such a weight.

Definition 6

A weight $w$ on the finite ring $R$ is called quasi-homogeneous if $w(0)=0$ and there exists a real number $\gamma$ such that

\sum_{r\in a+I}w(r)=\gamma|I|,

for each nonzero ideal $I$ of $R$ . The number $\gamma$ is called the average value of $w$ .

Proposition 2

Let $k$ be a positive integer and $\gamma$ be a positive real number. Define a mapping $w:\mathbb{Z}_{p^{k}}\rightarrow\mathbb{R}$ by

w(u)=\begin{cases}\frac{\gamma}{p^{k-2}(p-1)}u,&\quad\text{if }u_{k-1}=0\\ \frac{\gamma p}{p-1},&\quad\text{if }0<u_{k-1}\leq p-2\\ \frac{\gamma p^{2}}{p-1}-\frac{\gamma}{p^{k-2}(p-1)}u,&\quad\text{if }u_{k-1}=p-1\end{cases}

for all $u\in\mathbb{Z}_{p^{k}}$ with the $p$ -ary expansion $u=u_{0}+u_{1}p+\cdots+u_{k-1}p^{k-1}$ . Then $w$ is a quasi-homogeneous weight on $\mathbb{Z}_{p^{k}}$ with the average value $\gamma$ .

Proof

Fix $0\leq s\leq k-1$ . We show that for any $a\in\mathbb{Z}_{p^{k}}$ ,

\sum_{u\in a+\langle p^{s}\rangle}w(u)=\gamma p^{k-s},

which completes the proof. Note that it is enough to assume $0\leq a\leq p^{s}-1$ . Note also that for any $u\in a+\langle p^{s}\rangle$ , there exists a unique $n\in\mathbb{Z}_{p^{k}}$ such that $0\leq n\leq p^{k-s}-1$ and $u=a+np^{s}$ . Write $a=a_{0}+a_{1}p+\cdots+a_{s-1}p^{s-1}$ and $n=n_{0}+n_{1}p+\cdots+n_{k-s-1}p^{k-s-1}$ , where $0\leq a_{i},n_{j}\leq p-1$ for each $i=0,\ldots,s-1$ and $j=0,\ldots,k-s-1$ . Hence, a typical element $u$ of $a+\langle p^{s}\rangle$ can be written uniquely as

u=a_{0}+a_{1}p+\cdots+a_{s-1}p^{s-1}+n_{0}p^{s}+n_{1}p^{s+1}+\cdots+n_{k-s-2}p^{k-2}+n_{k-s-1}p^{k-1},

where the $a_{i}$ ’s and $n_{j}$ ’s all lie in $\{0,\ldots p-1\}$ . We separate the sum of $w(u)$ ’s, where $u$ ranges over $a+\langle p^{s}\rangle$ , into three sums as follows:

(I) The sum of the $w(u)$ ’s for $u\in a+\langle p^{s}\rangle$ with $n_{k-s-1}=0$ , i.e.,

\frac{\gamma}{p^{k-2}(p-1)}\left[p^{k-s-1}a+p^{s}\frac{p^{k-s-1}(p^{k-s-1}-1)}{2}\right];

(II) the sum of the $w(u)$ ’s for $u\in a+\langle p^{s}\rangle$ with $0\leq n_{k-s-1}\leq p-2$ , i.e.,

\frac{\gamma p(p-2)p^{k-s-1}}{p-1};

(III) the sum of the $w(u)$ ’s for $u\in a+\langle p^{s}\rangle$ with $n_{k-s-1}=p-1$ , i.e.,

\frac{\gamma p^{2}p^{k-s-1}}{p-1}-\frac{\gamma}{p^{k-2}(p-1)}\left[p^{k-s-1}a+\frac{p^{s}p^{k-s-1}(p^{k-s-1}-1)}{2}+p^{k-s-1}(p-1)p^{k-1}\right].

It is now easy to see that the numbers in (I)–(III) sum up to $\gamma p^{k-s}$ .

Corollary 2

The weight $w_{2}$ on $\mathbb{Z}_{p^{k}}$ , where $p>2$ is a prime number and $k\in\mathbb{Z}^{+}$ , is a quasi-homogeneous weight with the average value $\gamma=p^{k-2}(p-1)$ .

Proof

Notice that $w_{2}$ coincides with the weight defined in Proposition 2 with $\gamma=p^{k-2}(p-1)$ .

Remark 3

In view of the proof of Proposition 1, we see that both weights $w_{1}$ and $w_{2}$ share the same average value $\gamma=(p-1)p^{k-2}$ . In fact, $w_{1}$ is the only homogeneous weight on $\mathbb{Z}_{p^{k}}$ with the average value $\gamma=(p-1)p^{k-2}$ , see Theorem 2.2 in [7]. It follows that our consideration of quasi-homogeneous weights enables us to work with more useful weights with the same common average value and flourishes our repository of weights in this manner.

Corollary 3

Let $p>2$ be a prime number, $k$ be a positive integer, and $i\in\{1,2,\ldots,k-1\}$ . Given any $j\in\mathbb{Z}_{p^{k}}$ , the total number of $0$ ’s in the elements of the set $\{G_{2}(u):u\in j+\langle p^{i}\rangle\}$ is independent of $j$ and equals $p^{2k-i-2}$ .

Proof

By Corollary 2, the total number of $0$ ’s in the elements of the set $\{G_{2}(u):u\in j+\langle p^{i}\rangle\}$ is

	$\displaystyle p^{k-1}p^{k-i}-\sum_{u\in j+\langle p^{i}\rangle}w_{2}(u)$	$\displaystyle=p^{2k-i-1}-p^{k-2}(p-1)p^{k-i}$
		$\displaystyle=p^{2k-i-2}$

Example 10

Choose $p=5$ , $k=2$ , $i=1$ and $j=3$ . The total number of $0$ ’s in $G_{2}(5)=(11111),G_{2}(10)=(22222),G_{2}(15)=(33333),G_{2}(20)=(44444),G_{2}(25)=(00000)$ is $p^{2k-i-2}=5$ . On the other hand, the total number of $0$ ’s in $G_{2}(8)=(22211),G_{2}(13)=(33322),G_{2}(18)=(44433),G_{2}(23)=(00044),G_{2}(3)=(11100)$ is $p^{2k-i-2}=5$ . Hence, the total number of $0$ ’s in both sets is the same.

Proposition 3

Let $p>2$ be a prime number, $k\in{\mathbb{Z}}^{+}$ such that $k\geq 2$ and $\zeta$ be a primitive $p^{k}$ -th root of unity, $H=[\zeta^{a_{ij}}]$ be an $n\times n$ normalized Butson-Hadamard matrix, $H^{\prime}=[a_{ij}]$ and $w^{\prime}$ be a quasi-homogeneous weight with the average value $\gamma$ . Then the minimum distance of the code consisting the rows of $H^{\prime}$ with the first column deleted is equal to $\gamma n$ .

Proof

Since $H$ is a Butson-Hadamard matrix we know that there exists $m\in{\mathbb{Z}}^{+}$ such that $n=mp$ . We will the proof by induction on $m$ .

For $m=1$ we have a $BH(p,p)$ matrix.Let $R_{i},R_{j}$ be the $i$ -th and $j$ -th rows of $H^{\prime}$ , respectively. Hence the elements of $R_{i}-R_{j}$ consists of the elements of $p^{k-1}{\mathbb{Z}}_{p^{k}}$ or the cosets of this ideal. More clearly $R_{i}-R_{j}=\{p^{k-1},2p^{k-1},\ldots,p^{k}\}$ or $\{p^{k-1}+i,2p^{k-1}+i,\ldots,p^{k}+i\}$ for all $1\leq i\leq p^{k-1}-1$ . So for $I=p^{k-1}{\mathbb{Z}}_{p^{k}}$ we can say that $\displaystyle\sum_{r\in I+y}w^{\prime}(r)=\gamma p=\gamma n$ . Now let $m>1$ be given and suppose that the theorem is true for all $m=l$ with $l\in{\mathbb{Z}}^{+}$ . Let us show the theorem is true for $m=l+1$ . Suppose that $m=l+1$ . We know that $d=\gamma n$ for $n=l$ . If we take $n=l+1$ this differs from the case $n=l$ only $p$ elements.The $p$ elements again only come from the $p^{k-1}{\mathbb{Z}}_{p^{k}}$ ideal or the cosets of this ideal. Therefore $d=\gamma lp+\gamma p=\gamma p(l+1)=\gamma n$ . This ends the proof.

Theorem 4.3

$d_{G_{2}(A_{k})}=n(p-1)p^{k-2}$ , $d_{G_{2}(B_{k})}=n-1$ , $d_{G_{2}(C_{k})}=n$ , $d_{G_{2}(D_{k})}\in\{n,n+1\}$ .

Proof

We can say that $d_{G_{2}(A_{k})}=\gamma n$ by Proposition 3 and Corollary 2 we get $d_{G_{2}(A_{k})}=n(p-1)p^{k-2}$ .

Now consider $G_{2}(B_{k})$ . Let $R_{i}=[a_{i2}\ldots a_{in}]$ and $R^{\prime}_{i}=[a^{\prime}_{i2}\ldots a^{\prime}_{in}]$ be the $i$ -th row of the exponent matrix of $H$ and $\zeta H$ with deleted first column, respectively. Then $|a_{ij}-a^{\prime}_{ij}|=1$ , so we get $d(G_{2}(a_{ij}),G_{2}(a^{\prime}_{ij}))=1$ for $j=2,3,\ldots,n$ by Lemma 2. Therefore the distance between $G_{2}(R_{i})$ and $G_{2}(R^{\prime}_{i})$ is equal to $n-1.$ Now suppose that $R^{\prime}_{j}$ be the $j$ -th row of the exponent matrix of $uH$ for an arbitrary $u\in N$ . By Corollary 3 and Lemma 3, we can say

d(G_{2}(R_{i}),G_{2}(R^{\prime}_{j}))=(n-1)p^{k-1}-np^{k-2}=p^{k-2}(n(p-1)-1)

for $i\neq j$ . Since $n-1<p^{k-2}(n(p-1)-1)$ , the minimum distance of $G_{2}(B_{k})$ is $d_{G_{2}(B_{k})}=n-1$ .

We next consider $G_{2}(C_{k})$ . Its codewords are constructed from the rows of the exponent matrix of $uH$ for $u\in N$ . Similar to (ii), by considering $i$ -th rows $R_{i}$ and $R^{\prime}_{i}$ of $H$ and $\zeta H$ respectively, we have $d(G_{2}(R_{i}),G_{2}(R^{\prime}_{i}))=n$ . And so, $d_{G_{2}(C_{k})}=n$ .

Finally the code $G_{2}({D_{k}})$ is the Gray image of the rows of $uH$ concatenated with a non-initial column $c$ of $H$ . So, by using (iii), we can say that $d_{G_{2}({D_{k}})}$ is either $n$ or $n+1$ .

Now we can directly obtain a Plotkin optimal code form $G_{2}$ image of $A_{k}$ in the following corollary.

Corollary 4

The code $G_{2}(A_{k})$ is a Plotkin-optimal $p$ -ary nonlinear $((n-1)p^{k-1},n,n(p-1)p^{k-2})$ code under the non-homogeneous $w_{2}$ weight. Similarly $G_{2}(B_{k}),G_{2}(C_{k})$ and $G_{2}(D_{k})$ are Plotkin-optimal $p$ -ary nonlinear $((n-1)p^{k-1},np^{k},n-1),(np^{k-1},np^{k},n),((n+1)p^{k-1},np^{k},d_{G_{2}(D_{k})})$ codes under the non-homogeneous $w_{2}$ weight where $d_{G_{2}(D_{k})}$ is in $\{n,n+1\}$ .

Remark 4

Theorem 4.3 is not a special case of Proposition 1. Because the weight we use in Theorem 4.3 is non-homogeneous. We know that the sum of elements of a row in any normalized Butson-Hadamard matrix is equal to $0$ . Therefore, the code $G_{2}(A_{k})$ is constant weight and equidistant code.

Example 11

Let $H=[\zeta^{a_{ij}}]$ be a ${\rm BH}(9,9)$ matrix defined as in Example 9. Then

H^{\prime}=[G_{2}(a_{ij})]=\left(\begin{array}[]{ccccccccccccccccccccccccccc}0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0\\ 0&0&0&1&0&0&1&1&0&1&1&1&2&1&1&2&2&1&2&2&2&0&2&2&0&0&2\\ 0&0&0&1&1&0&2&1&1&2&2&2&0&0&2&1&0&0&1&1&1&2&2&1&0&2&2\\ 0&0&0&1&1&1&2&2&2&0&0&0&1&1&1&2&2&2&0&0&0&1&1&1&2&2&2\\ 0&0&0&2&1&1&0&0&2&1&1&1&0&2&2&1&1&0&2&2&2&1&0&0&2&2&1\\ 0&0&0&2&2&1&1&0&0&2&2&2&1&1&0&0&2&2&1&1&1&0&0&2&2&1&1\\ 0&0&0&2&2&2&1&1&1&0&0&0&2&2&2&1&1&1&0&0&0&2&2&2&1&1&1\\ 0&0&0&0&2&2&2&2&1&1&1&1&1&0&0&0&0&2&2&2&2&2&1&1&1&1&0\\ 0&0&0&0&0&2&0&2&2&2&2&2&2&2&1&2&1&1&1&1&1&1&1&0&1&0&0\end{array}\right).

$G_{2}(A_{k})$ is consisting of the rows of $H^{\prime}$ with deleted first 3 columns as codewords. By SageMath [19], we have $d_{A_{k}}=18$ which satisfies $d_{A_{k}}=n(p-1)p^{k-2}$ . Similarly, by using SageMath, we get that $d_{G_{2}(B_{k})}=8=n-1$ , $d_{G_{2}(C_{k})}=9=n$ and $d_{G_{2}(D_{k})}=9=n$ , where $D_{k}$ is obtained by concatenating the $4$ -th column of $H$ to $C_{k}$ .

5 Conclusion

In this paper we studied modified Butson-Hadamard(BH) matrices and their applications to coding theory. First we obtained new results about non-homogeneous Gray map. Then we used these results to prove some results. We give a lower bound for the minimum distance of the codes which consist of the rows of BH matrices. Then we determine the parameters of the codes which occur as the images of rows of BH matrices and their translates under the homogeneous and non-homogeneous Gray maps. Here we achieve equidistant and nonlinear codes. Also we conclude that the codes obtained the images of the rows of BH matrices under a non-homogeneous Gray map are Plotkin optimal codes.

Acknowledgement

Oğuz Yayla has been supported by Middle East Technical University - Scientific Research Projects Coordination Unit under grant number 10795. Damla Acar has been supported by YÖK 100/2000 program and TÜBİTAK-BİDEB-2213-A Scholarship.

References

[1] Armario, J.A., Bailera, I., Borges, J., Rifà, J.: Quasi-Hadamard full propelinear codes. Mathematics in Computer Science 12(4), 419–428 (2018)
[2] Armario, J.A., Bailera, I., Egan, R.: Generalized Hadamard full propelinear codes. arXiv preprint arXiv:1906.06220 (2019)
[3] Butson, A.: Generalized Hadamard matrices. Proceedings of the American Mathematical Society 13(6), 894–898 (1962)
[4] Dougherty, S.T., Rifà, J., Villanueva, M.: Ranks and kernels of codes from generalized Hadamard matrices. IEEE Transactions on Information Theory 62(2), 687–694 (2015)
[5] Dougherty, S.T., Rifà, J., Villanueva, M.: Rank and kernel of $\mathbb{F}_{p}$ -additive generalised Hadamard codes. arXiv preprint arXiv:2001.11609 (2020)
[6] Drake, A.D.: Partial $\lambda$ -geometries and generalized Hadamard matrices over groups. Can. J. Math. XXXI, No. 3, 617–627 (1979)
[7] Greferath, M., McGuire, G., O’Sullivan, M.E.: On Plotkin-optimal codes over finite frobenius rings. Journal of Algebra and its Applications 5(06), 799–815 (2006)
[8] Hadamard, J.: Resolution d’une question relative aux determinants. Bull. des sciences math. 2, 240–246 (1893)
[9] Hedayat, A., Wallis, W.D.: Hadamard matrices and their applications. The Annals of Statistics 6(6), 1184–1238 (1978)
[10] Heng, Z., Yue, Q.: Generalized Gray map and a class of p-ary nonlinear codes. Finite Fields and Their Applications 36, 81–97 (2015)
[11] Horadam, K.J.: Hadamard Matrices and Their Applications. Princeton University Press (2007)
[12] Jungnickel, D.: On difference matrices, resolvable transversal designs and generalized Hadamard matrices. Mathematische Zeitschrift 167(1), 49–60 (1979)
[13] Lam, T.Y., Leung, K.H.: On vanishing sums of roots of unity. Journal of algebra 224(1), 91–109 (2000)
[14] Lee, M., Jiang, X., Hwang, G., Pokhrel, S.S.: Error correcting codes from modified butson-hadamard matrices. In: 2006 International Conference on Systems and Networks Communications, pp. 65–65. IEEE Computer Society (2006)
[15] McGuire, G., Ward, H.N.: Cocyclic hadamard matrices from forms over finite frobenius rings. Linear algebra and its applications 430(7), 1730–1738 (2009)
[16] Seberry, J.: Orthogonal designs. Springer, Cham (2017)
[17] Stepanov, S.A.: A new class of quaternary codes. Problems of Information Transmission 42(1), 1–9 (2006)
[18] Stepanov, S.A.: Nonlinear q-ary codes with large code distance. Problems of Information Transmission 53(3), 242–250 (2017)
[19] The Sage Developers: SageMath, the Sage Mathematics Software System (Version 8.2.0) (2020). https://www.sagemath.org
[20] Yildiz, B., Ozger, Z.O.: Generalization of the Lee weight to $\mathbb{Z}_{p^{k}}$ . TWMS Journal of Applied and Engineering Mathematics 2(2), 145 (2012)

Butson-Hadamard matrices and Plotkin-optimal pkp^{k}-ary codes

Abstract

Keywords:

1 Introduction

2 The generalized Plotkin bound

Definition 1

Theorem 2.1

3 Generalized Gray maps

Definition 2

Example 1

Definition 3

Example 2

Lemma 1

Proof

Example 3

Lemma 2

Proof

Lemma 3

Proof

Example 4

4 Butson-Hadamard codes

Definition 4

Theorem 4.1

Proof

Example 5

Remark 1

Proposition 1

Proof

Definition 5

Example 6

Example 7

Example 8

Remark 2

Theorem 4.2

Proof

Corollary 1

Proof

Example 9

Definition 6

Proposition 2

Proof

Corollary 2

Proof

Remark 3

Corollary 3

Proof

Example 10

Proposition 3

Proof

Theorem 4.3

Proof

Corollary 4

Remark 4

Example 11

5 Conclusion

Acknowledgement

References

Butson-Hadamard matrices and Plotkin-optimal $p^{k}$ -ary codes