This is the accepted version of the journal article: Dougherty, Steven T.; Rifà i Coma, Josep; Villanueva, M. «Rank and kernel of ad- ditive generalised Hadamard codes». IEEE Transactions on Information Theory, Vol. 67, Issue 11 (November 2021), p. 7210-7220. DOI 10.1109/TIT.2021.3100433 This version is available at https://ddd.uab.cat/record/249135 under the terms of the license 1 Rank and Kernel of Additive Generalised Hadamard Codes Steven T. Dougherty, Josep Rifà, Senior Member, IEEE, and Mercè Villanueva Abstract—A subset of a vector space Fqn is additive if it is a is called the rank of C and is denoted by rank(C). If q = pe , linear space over the field Fp , where q = pe , p prime, and e > 1. p prime, we can also define Rp (C) and rankp (C) as the Bounds on the rank and dimension of the kernel of additive additive code spanned by C and its dimension, respectively. generalised Hadamard (additive GH) codes are established. For specific ranks and dimensions of the kernel within these bounds, The kernel of a code C over Fq , denoted by K(C), is defined additive GH codes are constructed. Moreover, for the case e = 2, as K(C) = {x ∈ Fqn : αx + C = C for all α ∈ Fq }. it is shown that the given bounds are tight and it is possible If q = pe , p prime, we can also define the p-kernel of to construct an additive GH code for all allowable ranks and C as Kp (C) = {x ∈ Fqn : x + C = C}. Since we dimensions of the kernel between these bounds. Finally, we also assume that 0 ∈ C, then K(C) is a linear subcode of C and prove that these codes are self-orthogonal with respect to the trace Hermitian inner product, and generate pure quantum codes. Kp (C) is an additive subcode. We denote the dimension of the kernel (resp., p-kernel) of C by ker(C) (resp., kerp (C)). Index Terms—Additive code, generalised Hadamard code, These concepts were first defined in [17] for codes over Fq , generalised Hadamard matrix, kernel, nonlinear code, rank. generalising the binary case described previously in [2], [16]. In [17], it was proved that any code C over Fq can be written as I. I NTRODUCTION the union of cosets of K(C) (resp., Kp (C)), and K(C) (resp., ET Fq = GF(q) denote the finite field with q elements, L where q = pe , p prime. Let Fnq be the vector space of dimension n over Fq . The Hamming distance between vectors Kp (C)) is the largest such linear code over Fq (resp., Fp ) for which this is true. Moreover, it is clear that K(C) ⊆ Kp (C). w, v ∈ Fnq , denoted by d(w, v), is the number of coordinates A generalised Hadamard (GH) matrix H(q, λ) = (hij ) of in which w and v differ. A code C over Fq of length n order n = qλ over Fq is a qλ × qλ matrix with entries from is a nonempty subset of Fnq . The elements of C are called Fq with the property that for every i, j, 1 ≤ i < j ≤ qλ, each codewords. The minimum distance of a code is the smallest of the multisets {his − hjs : 1 ≤ s ≤ qλ} contains every Hamming distance between any pair of distinct codewords. A element of Fq exactly λ times. It is known that since (Fq , +) code C over Fq is called linear if it is a linear space over Fq is an abelian group then H(q, λ)T is also a GH matrix, where and, it is called additive if it is linear over the prime field Fp . H(q, λ)T denotes the transpose of H(q, λ) [11]. An ordinary An additive code C over Fq has a dimension k 0 as a linear 0 Hadamard matrix of order 4µ corresponds to a GH matrix space over Fp and we can write |C| = pk = q k , where H(2, λ) over F2 , where λ = 2µ. k 0 = ke. The dimension of an additive code C over Fq is defined as the number k, which is not necessarily an integer Two GH matrices H1 and H2 of order n are said to number. be equivalent if one can be obtained from the other by a Two codes C1 , C2 ⊂ Fnq are said to be permutation permutation of the rows and columns and adding the same equivalent if there exists a permutation σ of the n coordinates element of Fq to all the coordinates in a row or in a column. such that C2 = {σ(c1 , c2 , . . . , cn ) = (cσ−1 (1) , . . . , cσ−1 (n) ) : We can always change the first row and column of a GH (c1 , c2 , . . . , cn ) ∈ C1 }. Without loss of generality, we shall as- matrix into zeros and we obtain an equivalent GH matrix sume, unless stated otherwise, that the all-zero vector, denoted which is called normalized. From a normalized GH matrix by 0, is in C. H, we denote by FH the code over Fq consisting S of the rows Two structural parameters of (nonlinear) codes are the of H, and CH the one defined as CH = α∈Fq (FH + α1), dimension of the linear span and the kernel. The linear span where FH + α1 = {h + α1 : h ∈ FH } and 1 denotes the of a code C over Fq , denoted by R(C), is the subspace over Fq all-one vector. The code CH over Fq is called generalised spanned by C, that is R(C) = hCi. The dimension of R(C) Hadamard (GH) code. Note that FH and CH are generally nonlinear codes over Fq . Steven T. Dougherty is with the Department of Mathematics, University of Scranton, Scranton PA 18510, USA To check whether two normalized GH matrices are equiva- Josep Rifà and Mercè Villanueva are with the Department of Information lent is known to be an NP-hard problem [15]. However, we can and Communications Engineering, Universitat Autònoma de Barcelona, 08193 use the invariants related to the linear span and kernel of the Cerdanyola del Vallès, Spain. The material in this paper was presented in part at the 2020 IEEE corresponding GH codes in order to help in their classification, International Symposium on Information Theory in Los Angeles, California, since if two GH codes have different ranks or dimensions USA, 2020 [9]. of the kernel, the normalized GH matrices are nonequivalent. Copyright (c) 2021 IEEE. Personal use of this material is permitted. However, permission to use this material for any other purposes must be Given a normalized GH matrix H, to establish the rank and obtained from the IEEE by sending a request to pubs-permissions@ieee.org. dimension of the kernel of the corresponding code FH is the 2 same as to establish these values for the code CH , since Therefore, we focus on additive GH codes over Fq with q = pe , e > 1. rank(CH ) = rank(FH ) + 1 and (1) Proposition II.1. [8, Proposition 9] Let H(q, λ) be a GH ker(CH ) = ker(FH ) + 1 matrix over Fq , where q = pe , p prime, and e ≥ 1. Let n = by [8, Lemma 1]. In this paper, we focus on the codes CH , qλ = pt s such that gcd(p, s) = 1. Then 1 ≤ ker(CH ) ≤ although everything could be rewritten in terms of the codes kerp (CH ) ≤ 1 + t/e. FH . It is important to emphasise that this is true as long as the GH matrix H is normalized. Lemma II.2. [8, Lemma 16] Let CH be a GH code of length The rank and dimension of the kernel for ordinary n = q h s over Fq , where s 6= 1 and s is not a multiple of q. Hadamard codes over F2 have already been studied. Specifi- Then ker(CH ) ≤ h. cally, lower and upper bounds for these two parameters were Lemma II.3. Let H(q, λ) be a GH matrix over Fq such that established, and the construction of an Hadamard code for all CH is additive. Let n = qλ = pt s such that gcd(p, s) = 1, allowable ranks and dimensions of the kernel between these where q = pe , p prime, and e ≥ 1. For any v ∈ CH , v ∈ bounds was given [18], [19]. The values of the rank and dimen- K(CH ) if and only if µv ∈ CH for all µ ∈ Fq . sion of the kernel for Z2 Z4 -linear Hadamard codes were given in [20], and these invariants for Z2s -linear Hadamard codes Proof. Assume that µv ∈ CH for all µ ∈ Fq . Since CH is have been studied in [6], [7]. The Z2 Z4 -linear Hadamard codes additive, for any w ∈ CH we have that µv + w ∈ CH . Hence, (resp. Z2s -linear Hadamard codes) are the Hadamard codes the statement follows. over F2 obtained as the Gray map image of Z2 Z4 -additive Proposition II.4. Let H(q, λ) be a GH matrix over Fq , where codes (resp. Z2s -additive codes), which are subgroups of q = pe , p prime, and e > 1. Let n = qλ = pt s such that β β Zα2 × Z4 (resp. Z2s ). gcd(p, s) = 1. Then Some of the results on the rank and dimension of the kernel (i) If CH is an additive code, then s = 1. for Hadamard codes over F2 have been generalised to GH (ii) The code CH is an additive code if and only if codes over Fq with q 6= 2 [8]. Specifically, some lower and upper bounds for the dimension of the kernel, and for the rankp (CH ) = kerp (CH ) = 1 + t/e. rank once the dimension of the kernel is fixed, were given. Moreover constructions of GH codes having different values (iii) If CH is an additive code and ker(CH ) = k, then for these invariants within these bounds, were presented. In e+t−k this paper, we continue studying the rank and dimension of ≤ rank(CH ) ≤ 1 + t − (e − 1)(k − 1). e−1 the kernel for GH codes over Fq . However, now we focus on a (iv) If CH is an additive code, then rank(CH ) = ker(CH ) = specific family of GH codes, namely the additive GH codes, 1 + t/e when CH is linear over Fq (t is a multiple of e), that is, additive codes over Fq obtained from GH matrices or otherwise H(q, λ). In the specific case q = p2 we use the additive GH codes over Fq to generate pure quantum codes. It is 1 ≤ ker(CH ) ≤ bt/ec. worth mentioning that the invariants rank and dimension of the kernel, used in this paper for additive GH codes, could be Proof. Since the number of codewords is |CH | = qn = pe+t s, extended to classify more general additive or quantum codes. if CH is additive, then we have that s = 1 and rankp (CH ) = The paper is organized as follows. In Section II, lower kerp (CH ) = 1 + t/e. This proves items (i) and (ii). and upper bounds on the dimension of the kernel, and the Let CH be an additive code with ker(CH ) = k. The kernel rank once the dimension of the kernel is fixed, are given. K(CH ) is the largest linear subspace over Fq in CH such that In Sections III and IV, several constructions of additive GH CH can be partitioned into cosets of K(CH ). Specifically, codes over Fq with q = pe , p prime and e > 1, are shown. there are |CH |/q k = q 1+t/e /q k = q 1+t/e−k = pe+t−ek In Section V, by using these constructions, we establish for cosets. Since CH and K(CH ) are linear over Fp , the above which allowable pairs (r, k), where r is the rank and k the cosets (that is, the elements of the quotient CH /K(CH )) have dimension of the kernel, there exists an additive GH code a linear structure over Fp . Therefore, there are e + t − ek having these invariants. Finally, in Section VI, we see that independent vectors over Fp generating these cosets, which the additive GH codes over Fp2 can be used to generate pure means that the number of independent vectors over Fq gen- quantum codes since they are self-orthogonal with respect to erating these cosets is upper bounded by e + t − ek. Hence the trace Hermitian inner product. rank(CH ) ≤ k + (e + t − ek) = 1 + t − (e − 1)(k − 1). From Lemma II.3, for any v ∈ / K(CH ), the intersection of the linear space over Fq generated by v and CH is, at most, of dimension II. B OUNDS ON THE RANK AND DIMENSION OF THE e − 1 over Fp . Therefore, for the lower bound, we have that KERNEL e+t−ek e+t−k e−1 + k = e−1 ≤ rank(CH ) and item (iii) follows. In this section, we state new results on the rank and dimen- For item (iv), when CH is linear over Fq , we have that sion of the kernel for additive generalised Hadamard codes. CH = K(CH ). Since |CH | = pe+t = q 1+t/e , t is a multiple Note that a GH matrix H(p, λ) over Fp , p prime, generates of e and rank(CH ) = k = 1+t/e. Otherwise, 1 ≤ k < 1+t/e an additive GH code CH of length n = λp = pt if and only by Proposition II.1 and item (ii). In this case, if t is a multiple if rank(CH ) = rankp (CH ) = kerp (CH ) = ker(CH ) = 1 + t. of e, clearly k ≤ bt/ec. Finally, if t is not a multiple of e, by 3 0 0 Lemma II.2, since n = q bt/ec ps , where 1 < ps < q, we have these constructions, we establish the values of the rank and that k ≤ bt/ec. dimension of the kernel for the obtained codes. Corollary II.5. Let H(q, λ) be a GH matrix over Fq , where A standard method to construct GH matrices from other q = p2 and p prime. If CH is an additive code of length GH matrices is given by the Kronecker sum construction [14], n = qλ = pt , then [23]. That is, if H(q, λ) = (hij ) is any qλ × qλ GH matrix over Fq , and B1 , B2 , . . . , Bqλ are any qµ × qµ GH matrices (i) rank(CH ) + ker(CH ) = 2 + t. over Fq , then the matrix in Table II gives a q 2 λµ × q 2 λµ (ii) If 2 - t, then rank(CH ) − ker(CH ) ≥ 3. GH matrix over Fq , denoted by H ⊕ [B1 , B2 , . . . , Bn ], where (iii) If 2 | t and CH is nonlinear over Fq , then rank(CH ) − n = qλ. If B1 = B2 = · · · = Bn = B, then we write ker(CH ) ≥ 2. H ⊕ [B1 , B2 , . . . , Bn ] = H ⊕ B. Proof. The first item is straightforward from item (iii) in Proposition II.4. TABLE II For the second item, if 2 = e - t, then t = 2h + 1. From K RONECKER SUM CONSTRUCTION item (iv) in Proposition II.4, ker(CH ) ≤ h and so rank(CH )−  h11 + B1 h12 + B1 ··· h1n + B1  ker(CH ) ≥ rank(CH )−h = 2+t−ker(CH )−h ≥ 2+t−2h =  h21 + B2 h22 + B2 ··· h2n + B2  H ⊕B = .. .. .. ..   3. For the third item, we can follow a similar argument, but  . . . .   considering that t = 2h. hn1 + Bn hn2 + Bn ··· hnn + Bn Example II.6. For q = p3 , the second column in Table I gives Let Sq be the normalized GH matrix H(q, 1) given by all possible values for the dimension of the kernel of additive the multiplicative table of Fq . As for ordinary Hadamard GH codes over Fp3 of length n = pt with 2 ≤ t ≤ 12. For matrices over F2 , starting from a GH matrix S 1 = Sq , we each one of these values, the third column shows the possible can recursively define S h as a GH matrix H(q, q h−1 ), con- values for the rank, given by Proposition II.4. 4 structed as S h = Sq ⊕ [S h−1 , S h−1 , . . . , S h−1 ] = Sq ⊕ S h−1 for h > 1, which is called a Sylvester GH matrix. Note TABLE I that the corresponding GH code CS h is linear over Fq , so PARAMETERS ker(CH ) AND rank(CH ) FOR ALL ADDITIVE GH CODES rank(CS h ) = ker(CS h ) = 1 + h, by Equation (1) or item (iv) CH OVER Fp3 OF LENGTH n = pt WITH 3 ≤ t ≤ 12. of Proposition II.4. Now, we recall some known results on the rank and di- t ker(CH ) rank(CH ) kerp (CH ) = rankp (CH ) mension of the kernel for GH codes constructed by using 3 2 2 2 the Kronecker sum construction. In these cases, starting with 1 3,4 2 additive GH codes, we obtain additive GH codes. 4 1 3,4,5 7/3 5 1 4,5,6 8/3 Lemma III.1. Let H1 and H2 be two GH matrices over 6 3 3 3 2 4,5 3 Fq and H = H1 ⊕ H2 . Then rank(CH ) = rank(CH1 ) + 1 4,5,6,7 3 rank(CH2 ) − 1 and ker(CH ) = ker(CH1 ) + ker(CH2 ) − 1. 7 2 4,5,6 10/3 Moreover, if CH1 and CH2 are additive, then CH is also 1 5,6,7,8 10/3 8 2 5,6,7 11/3 additive and rankp (CH ) = rankp (CH1 ) + rankp (CH2 ) − 1. 1 5,6,7,8,9 11/3 Proof. Straightforward from the proof of Lemma 3 in [8]. 9 4 4 4 3 5,6 4 Corollary III.2. Let B be a GH matrix over Fq and H = 2 5,6,7,8 4 1 6,7,8,9,10 4 Sq ⊕ B. Then rank(CH ) = rank(CB ) + 1 and ker(CH ) = 10 3 5,6,7 13/3 ker(CB ) + 1. Moreover, if CB is additive, then CH is also 2 6,7,8,9 13/3 additive and rankp (CH ) = rankp (CB ) + 1. 1 6,7,8,9,10,11 13/3 11 3 6,7,8 14/3 Proof. Straightforward from the proof of Corollary 4 in [8]. 2 6,7,8,9,10 14/3 1 7,8,9,10,11,12 14/3 12 5 5 5 4 6,7 5 Several switching constructions have been used to construct 3 6,7,8,9 5 2 7,8,9,10,11 5 perfect codes in [21], [22] ordinary Hadamard codes over F2 1 7,8,9,10,11,12,13 5 in [18], [19], and generalised Hadamard codes over Fq in [8]. In this paper, we present different constructions, based on this technique, in order to obtain additive GH codes with different ranks and dimensions of the kernel. The first III. K RONECKER AND SWITCHING CONSTRUCTIONS switching construction, given by Proposition III.3, allows us to construct additive GH codes over Fpe of length n = p2e In this section, we show that by using the Kronecker sum with kernel of dimension 2 and rank 4. construction from additive GH codes, we also obtain additive GH codes. Moreover, we present a switching construction Proposition III.3 (Switching Construction I). For q = pe , p that allows for the production of additive GH codes. For all prime, and any e > 1, there exists a GH matrix H(pe , pe ) such 4 (1) (q−2) that CH is an additive code over Fpe of length n = p2e = q 2 0i , 1i , ω i , . . ., ω i are the elements 0, 1, ω, . . . , ω q−2 re- i−1 with ker(CH ) = 2 and rank(CH ) = 4. peated q times, respectively, and ω is a primitive element in Fq , for all i ∈ {1, . . . , h}. All vectors v1 , . . . , vh have length Proof. Let 0, 1, ω (1) , . . ., ω (q−2) be the elements q h and are linearly independent over Fq . The corresponding 0, 1, ω, . . . , ω q−2 repeated q times, respectively, where ω is GH code CS h is linear over Fq , so rank(CS h ) = ker(CS h ) = a primitive element in Fq . Let S 2 = Sq ⊕ Sq be the Sylvester 1 + h. GH matrix H(q, q). We can assume without loss of generality Let K be the linear subcode of S h generated by the vectors that S 2 is generated over Fq by the row vectors v1 and v2 of v2 , . . . , vh . Note that all n = q h coordinates are naturally length n = q 2 , where divided into q h−1 groups of size q, which will be referred to v1 = (0, 1, ω 1 , . . . , ω q−2 , . . . , 0, 1, ω 1 , . . . , ω q−2 ), and as blocks, such that the columns of K in a block coincide. v2 = (0, 1, ω (1) , . . . , ω (q−2) ). Moreover, the rows of S h can be partitioned into q cosets of K, that is, S h = ∪β∈Fq (K + βv1 ). Let K be the linear subcode of S 2 generated by the row Now, consider the vectors g1 , . . . , ge−1 ∈ Fqn , where gj has vector v2 . The rows of S 2 can be partitioned into q cosets of exactly the values 0, 1, ω, . . . , ω q−2 in the coordinate positions K, that is, S 2 = ∪β∈Fq (K + βv1 ). Let βe ∈ Fp be the last (jq+1), . . . , (j +1)q, respectively, and zeros elsewhere, for all coordinate of the element β ∈ Fq represented as a vector from j ∈ {1, . . . , e−1}. Note that, for each j ∈ {1, . . . , e−1}, these Fpe . Then we construct the matrix q coordinate positions correspond to a block. Moreover, there [ [ [ are always enough blocks since e ≤ q ≤ q h−1 = pe(h−1) . Let H = (S 2 \ (K+βv1 ))∪ (K+βv1 +βe g) = Kβ , β ∈ Fq be β = (β0 , . . . , βe−1 ) represented as a vector in Fpe . β∈Fq , β∈Fq , β∈Fq Then, we construct the matrix βe 6=0 βe 6=0 [ H (s) = Kβ , (2) where g = (0, . . . , 0, 0, 1, ω 1 , . . . , ω q−2 ) and Kβ = K+βv1 + β∈Fq βe g. Ps It is easy to see that H is a GH matrix and CH is an where s ∈ {1, . . . , e − 1} and Kβ = K + βv1 + j=1 βj gj . additive code. Indeed, note that Kβ + Kγ = Kβ+γ for all Next, we prove that the corresponding code CH (s) is an β, γ ∈ Fq . Moreover, clearly, rank(FH ) = 2 + 1 = 3 and additive GH code for all s ∈ {1, . . . , e − 1}. First of all, the K ⊆ K(FH ). It is also easy to prove that K = K(FH ). length of H (s) is q h and the number of rows is also q h . The Therefore, ker(FH ) = 1. By Equation (1), ker(CH ) = 2 and code CH (s) is additive over Fq , since Kβ+γ = Kβ + Kγ for rank(CH ) = 4. any β, γ ∈ Fq . Finally, it can be seen easily that H (s) is a GH matrix by computing the differences between any two different Example III.4. We construct a GH matrix H(22 , 22 ) such rows. that CH is an additive code over F22 of length n = 24 with By Lemma II.3, it is straightforward to show that ker(CH ) = 2 and rank(CH ) = 4. We start with the GH K(H (s) ) = K, so we have that ker(CH (s) ) = h − 1 + 1 = h matrix S 2 = S4 ⊕S4 , which is linear over F22 and is generated by Equation (1). It is easy to see that all linearly independent by v1 = (0, 1, ω, ω 2 , 0, 1, ω, ω 2 , 0, 1, ω, ω 2 , 0, 1, ω, ω 2 ) and vectors v1 , . . . , vh from S h are in hCH (s) i. Moreover, the v2 = (0, 0, 0, 0, 1, 1, 1, 1, ω, ω, ω, ω, ω 2 , ω 2 , ω 2 , ω 2 ), where ω linearly independent vectors g1 , . . . , gs are also in hCH (s) i. is a primitive element in F22 and ω 2 = ω + 1. Let K = hv2 i. Hence, by Equation (1), rank(CH (s) ) = h + s + 1, which Then, S 2 = K ∪ (K + v1 ) ∪ (K + ωv1 ) ∪ (K + ω 2 v1 ). covers all values in the range of h + 2 to h + e. By the proof of Proposition III.3, we change the last eight rows of S 2 , and we obtain the GH matrix H(22 , 22 ) = We can make a slight modification in the proof of K ∪ (K + v1 ) ∪ (K + ωv1 + g) ∪ (K + ω 2 v1 + g), Proposition III.5 allowing the construction of GH matrices where g = (0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, ω, ω 2 ), that is, H(pe , p(h−1)e ) with h > 1, where the dimension of the kernel the matrix given in Table III. 4 k of the corresponding codes ranges from 2 to h and for each one of these values the rank takes any value from 2h−k +2 to The switching construction given by Proposition III.3 can h+1+(h−k +1)(e−1). Note that this switching construction be generalised to the case H(pe , p(h−1)e ) with h > 1, that is, includes the previous two switching constructions I and II when t is a multiple of e. A first generalisation is shown in given by Proposition III.3 and Proposition III.5, respectively. Proposition III.5, and a second one in Proposition III.6. Proposition III.6 (Switching Construction III). For q = pe , Proposition III.5 (Switching Construction II). For q = pe , p prime, and any e > 1, h > 1, there exists a GH matrix p prime, and any e > 1, h > 1, there exists a GH matrix H(pe , p(h−1)e ) such that CH is an additive code over Fpe of H(pe , p(h−1)e ) such that CH is an additive code over Fpe of length n = phe = q h with ker(CH ) = k and rank(CH ) = r, length n = phe = q h with ker(CH ) = h and rank(CH ) = r for all k ∈ {2, . . . , h} and for all r ∈ {h + 2, . . . , h + e}. r ∈ {2h − k + 2, . . . , 1 + t − (e − 1)(k − 1)}. Proof. Let S h be the Sylvester GH matrix H(q, q h−1 ). We can assume without loss of generality that S h is generated by Proof. We consider the vectors v1 , . . . , vh of length n = q h the vectors v1 , . . . , vh of length n = q h , where defined in the proof of Proposition III.5. Let K be the linear subcode of S h generated by the vectors v3 , . . . , vh . In this (1) (q−2) (1) (q−2) vi = (0i , 1i , ω i , . . . , ω i , . . . , 0i , 1i , ω i , . . . , ω i ), case, the rows of S h can be partitioned into q 2 cosets of 5 TABLE III T HE GH MATRIX H(22 , 22 ) CONSTRUCTED IN E XAMPLE III.4 .   0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 ω ω ω ω ω2 ω2 ω2 ω2     K ω2 ω2 ω2 ω2   0 0 0 0 ω ω ω ω 1 1 1 1  0 0 0 0 ω2 ω2 ω2 ω2 1 1 1 1 ω ω ω ω     0 1 ω ω2 0 1 ω ω2 0 1 ω ω2 0 1 ω ω2     0 1 ω ω2 1 0 ω2 ω ω ω2 0 1 ω2 ω 1 0      K + v1 0 1 ω ω2 ω ω2 0 1 ω2 ω 1 0 1 0 ω2 ω    ω2 ω2 ω2 ω2  0 1 ω ω 1 0 1 0 ω ω 0 1    0 ω ω2 1 0 ω ω2 1 0 ω ω2 1 0 ω2 1 ω       0 ω ω2 1 1 ω2 ω 0 ω 0 1 ω2 ω2 0 ω 1   K + ωv + g 1   0 ω ω2 1 ω 0 1 ω2 ω2 1 0 ω 1 ω 0 ω2     0 ω ω2 1 ω2 1 0 ω 1 ω2 ω 0 ω 1 ω2 0     0 ω2 1 ω 0 ω2 1 ω 0 ω2 1 ω 0 ω ω2 1     0 ω2 1 ω 1 ω 0 ω2 ω 1 ω2 0 ω2 1 0 ω   K + ω 2 v1 + g  0 ω2 1 ω ω 1 ω2 0 ω2 0 ω 1 1 ω2 ω 0  0 ω2 1 ω ω2 0 ω 1 1 ω 0 ω2 ω 0 1 ω2 K, that is, S h = ∪β,γ∈Fq (K + βv1 + γv2 ). Let β, γ ∈ Fq IV. N EW CONSTRUCTIONS WITH KERNEL OF DIMENSION 1 be β = (β0 , . . . , βe−1 ) and γ = (γ0 , . . . , γe−1 ), respectively, In this section, two new constructions of additive GH codes represented as vectors in Fpe . Then, we construct the matrix having a kernel of dimension 1, one with maximum rank and another one with minimum rank, are presented. In Section V, H (s1 ,s2 ) = [ Kβ,γ , (3) these constructions together with the Kronecker and switching β,γ∈Fq constructions presented in Section III will be used to construct additive GH codes having different ranks and dimensions of the kernel. where s1 , s2 ∈ {1, . . . , e − 1}, Kβ,γ = K + βv1 + Ps1 (1) Ps2 (2) First, we introduce a new construction of GH matrices j=1 βj gj + γv2 + j=1 γj gj . We take the vector (1) which allows us to guarantee that the obtained code CH of gj = gj defined as in the proof of Proposition III.5 length n = pt is additive over Fpe , has kernel of minimum (2) for j ∈ {1, . . . , e − 1}. The vector gj has exactly the dimension 1 and maximum rank t + 1. (1) (q−2) values 02 , 12 , ω 2 , . . ., ω 2 in the coordinate positions 2 2 Proposition IV.1. For q = pe , p prime, and any t > e > 1, (jq + 1), . . . , (j + 1)q , respectively, and zeros elsewhere, for there exists a GH matrix H(pe , pt−e ) such that CH is an all j ∈ {1, . . . , e − 1}. additive code over Fpe of length n = pt with ker(CH ) = 1 We can repeat again and again the above construction taking and rank(CH ) = t + 1. (z) in the z-th round vectors gj with exactly the values 0z , 1z , (1) (q−2) Proof. Let Spt = H(pt , 1) be the GH matrix, given by the ω z , . . ., ω z in the coordinate positions (jq z +1), . . . , (j+ z multiplicative table of Fpt , that is, the matrix 1)q , respectively, and zeros elsewhere, for all j ∈ {1, . . . , e− 1}. Again, there are always enough coordinates since e ≤ q = 0 0 0 ... 0 0   pe . We can follow this process until we consider the linear  0 1 t t ω . . . ω p −3 ω p −2  subcode K = hvh i, and we obtain the matrix H (s1 ,s2 ,...,sh−1 ) . t t   H(p , 1) =  0 ω ω 2 . . . ω p −2 1  , Next, we prove that the matrix H = H (s1 ,s2 ,...,sh−k+1 ) is  ... ... ... ... ... ...  t t t a GH matrix, and the corresponding code is additive. First 0 ω p −2 1 . . . ω p −4 ω p −3 of all, the length and the number of rows of H is q h . The (4) corresponding code CH is an additive code over Fq as in the where ω is a primitive element in Fpt . Let b0 + b1 x + · · · + proof of Proposition III.5. Finally, it can be easily seen that bt−1 xt−1 − xt ∈ Fp [x] be the primitive polynomial of ω and H is a GH matrix by computing the differences between any note that b0 6= 0. In this case, CH is a linear code over two different rows. Fpt and an additive code. By Proposition II.4, we have that Again, by Lemma II.3, it is easy to see that K(H) = K, so rankp (CH ) = kerp (CH ) = rank(CH ) = ker(CH ) = 2. we have that ker(CH ) = h − (h − k + 2) + 1 = k − 1 + 1 = k Now, for any e, 1 < e < t, we consider the projection map by Equation (1). For the rank(CH ), it is easy to see that all from Fpt to Fpe given by linearly independent vectors in CS h are also in hCH i. Apart v = (v1 , . . . , ve , ve+1 , . . . , vt ) ∈ Fpt −→ v = (v1 , . . . , ve ) ∈ Fpe . from that vectors, we also find in hCH i the linearly inde- (1) (1) (h−k+1) (h−k+1) pendent vectors g1 , . . . , gs1 , . . . , g1 , . . . , gsh−k+1 . Note that we can consider that the projection of ω ∈ Fpt Hence, rank(CH ) = h + 1 + s1 + · · · + sh−k+1 , which covers gives a primitive element ω = α ∈ Fpe . Let He be the matrix all values in the range from h + 1 + (h − k + 1) = 2h − k + 2 obtained from H after changing each entry v by v. Since in to h + 1 + (h − k + 1)(e − 1) = 1 + t − (e − 1)(k − 1). any row of H there are all the elements in Fpt , it is easy 6 to see that in any row of He there will be all the elements F22 and α2 = α + 1. Finally, by the proof of Proposition IV.1, in Fpe , but each one repeated pt−e times. The same happens we obtain the following GH matrix H(22 , 2): taking the difference of any two different rows in H. Hence,   He (pe , pt−e ) is a GH matrix. Since CH is an additive code 0 0 0 0 0 0 0 0 it is easy to see, by construction, that CHe is also an additive  0 1  α 0 α2 α α2 1   code.  0 α  0 α2 α α2 1 1  (r) 2  0 0 α2 α α2 1 1 α  Let He be the matrix He after removing the first row H(2 , 2) =  2 . (r)  0 α α α2 1 1 α 0  and column. Take any row v = (γ̄1 , γ̄2 , . . . , γ̄pt −1 ) of He ,  0 α α2 1  1 α 0 α2  where γ̄i ∈ Fpe for all i ∈ {1, 2, . . . , pt − 1}. The case when   0 α2 1  1 α 0 α2 α  entry γ̄i is zero corresponds to γi ∈ Fpt of the form γi = 0 1 1 α 0 α2 α α2 (0, 0, . . . , 0, λe+1 , . . . , λt ), or equivalently, γi = λe+1 ω e + (6) | {z } e 4 · · · + λt ω t−1 , where λi ∈ Fp for all i ∈ {e + 1, e + 2, . . . , t}. Now, we compute ωγi = λe+1 ω e+1 + · · · + λt−1 ω t−1 + λt ω t By Proposition II.4, for q = p2 (that is, for e = 2), we have and from ω t = b0 + b1 ω + · · · + bt−1 ω t−1 we have ωγi = that the rank of an additive GH code CH of length n = p2 λt (b0 + b1 α + · · · + be−1 αe−1 ). Hence, taking two consecutive (that is, with t = e = 2) has to be 3 if the dimension of the entries in v, for instance γ̄i , γ̄i+1 = ωγi , such that γ̄i = 0 and kernel is 1. The next result shows that there exists a code CH γ̄i+1 6= 0 we have that γ̄i+1 = λt (b0 + b1 α + · · · + be−1 αe−1 ), with these parameters for any p prime and p 6= 2. Therefore, for some nonzero λt ∈ Fp . Therefore, multiplying any row of (r) (r) in this case, we have that the given lower bound for the rank, He by αj , for any αj ∈ / Fp , we do not obtain a row of He . (r) once the dimension of the kernel is fixed, coincides with the Indeed, if αj v were a row in He , then αj γ̄i , αj γ̄i+1 would upper bound. be two consecutive entries in the row, where αj γ̄i = 0 and Note that, for q = 4, it is well known that there is only one αj γ̄i+1 6= 0, so αj γ̄i+1 = λ0t (b0 + b1 α + · · · + be−1 αe−1 ) for GH matrix H(4, 1), up to equivalence, which gives the linear some nonzero λ0t ∈ Fp , and so we have (λ0t −αj λt )(b0 +b1 α+ code CH of length n = 4 over F4 , having rank and dimension · · ·+be−1 αe−1 ) = 0. Since α is a primitive element in Fpe , we of the kernel equal to 2. obtain λ0t − αj λt = 0 which contradicts our assumption αj ∈ / Fp . Hence, from Lemma II.3 we obtain that the dimension of Proposition IV.3. For t = e = 2 and p an odd prime, there the kernel ker(FHe ) is zero (or equivalently, ker(CHe ) = 1). exists a GH matrix H(p2 , 1) such that CH is an additive code For the rank, we can improve the lower bound given over Fp2 of length n = p2 with ker(CH ) = 1 and rank(CH ) = in Proposition II.4. From the previous paragraph, for any 3. v ∈ CH \K(CH ), the intersection of the linear space over Proof. First, we construct a GH matrix H(p2 , 1) and then Fpe generated by v and CH is of dimension 1 over Fp . Hence, we prove that it fulfils the conditions of the statement. Let the number of independent vectors over Fpe generating the 2 v1 = (0, ω 0 , ω 1 , . . . , ω p −2 ), where ω is a primitive element pe+t−ek cosets of K(CH ) over CH is lower bounded by in Fp2 . Hence, v1 has a zero in the first position and ω i−1 e + t − ek = t and so t + k = t + 1 ≤ rank(CH ). Finally, from in the (i + 1)th position, for i ∈ {1, 2, . . . , p2 − 1}. Now, we item (iv) of Proposition II.4 we obtain the statement. define v2 as the vector having a zero in the first position and Example IV.2. We construct a GH matrix H(22 , 2) such that ω ip in the (i+1)th position. We construct the matrix H(p2 , 1) CH is an additive code over F22 of length n = 23 with having as rows all linear combinations over Fp of v1 and v2 . ker(CH ) = 1 and rank(CH ) = 4. We begin with the GH We permute the rows in order to have the all-zero row as the matrix H(23 , 1) given by the multiplicative table of F23 , that first one. Note that H(p2 , 1) is a matrix of order p2 over Fp2 , is, which has all zeros in the first row and column.   The vector v1 has no two positions with the same value. The 0 0 0 0 0 0 0 0 same is true for v2 (indeed, the coordinates of v2 correspond  0 1 ω ω2 ω3 ω4 ω5 ω6    0 ω ω2 ω3 ω4 ω5 ω6 1   to the image of the Frobenius automorphism x → xp ). The   0 ω2 ω3 ω4 ω5 ω6 1  elements of Fp2 which are in Fp are of the form ω λ(p+1) , for 3 ω  H(2 , 1) =  3 4 5 6 , λ ∈ {0, 1, . . . , p − 1}. Hence, the (i + 1)th position of any  0 ω4 ω5 ω6 ω 1 ω ω2   row in H(p2 , 1) is of the form ω λ(p+1) ω i−1 + ω γ(p+1) ω ip ,  0 ω ω ω 1 ω ω2 ω3    0 ω5 ω6 1  for i ∈ {1, 2, . . . , p2 − 1} and λ, γ ∈ {0, 1, . . . , p − 1}. The ω ω2 ω3 ω4  coordinates of any row of H(p2 , 1) are all different, otherwise 0 ω6 1 ω ω2 ω3 ω4 ω5 (5) we would have two indexes i, j such that where ω is a primitive element in F23 and ω 3 = ω + 1, Next, ω λ(p+1) ω i−1 + ω γ(p+1) ω ip = λγ(p+1) ω j−1 + ω γ(p+1) ω jp we write each entry of (5) by using coordinates over F2 and projecting them over F22 . Note that 0̄ = (0, 0, 0) = (0, 0) = 0, or, equivalently, ω λ(p+1)−1 (ω i − ω j ) = ω γ(p+1) (ω jp − ω ip ). 1̄ = (1, 0, 0) = (1, 0) = 1, ω = (0, 1, 0) = (0, 1) = α, Note that (ω jp − ω ip ) = (−1)p (ω i − ω j )p . Therefore, sim- ω 2 = (0, 0, 1) = (0, 0) = 0, ω 3 = (1, 1, 0) = (1, 1) = α2 , plifying, there would exist δ ∈ {0, 1, . . . , p − 1} such that ω 4 = (0, 1, 1) = (0, 1) = α, ω 5 = (1, 1, 1) = (1, 1) = α2 , ω δ(p+1)−1 = (ω i − ω j )p−1 . Raising this equality to p + 1, ω 6 = (1, 0, 1) = (1, 0) = 1, where α is a primitive element in we obtain (p + 1)(δ(p + 1) − 1) ≡ 0 (mod p2 − 1). Reducing 7 modulo 2ξ, where ξ is the highest power of 2 dividing p+1, we and minimum rank rank(CH ) = 3, given by the following two obtain p + 1 ≡ 0 (mod 2ξ), which contradicts the definition examples. We have checked computationally that the technique of ξ. This proves that H(p2 , 1) is a GH matrix. used in these two examples does not apply for p = 7 and Finally, by Proposition II.4, we just need to prove that p = 11. H(p2 , 1) is nonlinear. We see that multiplying v1 by ω p , Example IV.6. Let H(34 , 1) be the matrix having as we obtain a vector which is not any row of the matrix. It is rows all linear combinations over F3 of v1 , ωv1 , v2 enough to focus on the second column of the matrix. Assume and ωv2 , where v1 = (0, ω 0 , ω 1 , . . . , ω i , . . . , ω 79 ), v2 = the contrary, that is, there exist λ, γ ∈ {0, 1, . . . , p − 1} such (0, ω 2 , ω 11 , . . . , ω 2+9i , . . . , ω 73 ), and ω is a primitive element that ω p = ω λ(p+1) + ω γ(p+1) ω p or, equivalently, ω λ(p+1) = in F34 . We can check that it is a GH matrix. Clearly, by (1 − ω γ(p+1) )ω p . Since ω λ(p+1) and 1 − ω γ(p+1) ∈ Fp , we construction, CH is an additive code with rank(CH ) = 3. would have that ω p ∈ Fp , which is a contradiction. By Lemma II.3, we have that ker(CH ) = 1. 4 Example IV.4. We construct a GH matrix H(9, 1) such that Example IV.7. Let H(54 , 1) be the matrix having as CH is an additive code over F9 of length n = 9 with rows all linear combinations over F5 of v1 , ωv1 , v2 and ker(CH ) = 1 and rank(CH ) = 3. ωv2 , where v1 = (0, ω 0 , ω 1 , . . . , ω i , . . . , ω 623 ), v2 = Let v1 = (0, ω 0 , ω, ω 2 , ω 3 , ω 4 , ω 5 , ω 6 , ω 7 ) and v2 = (0, ω 6 , ω 31 , . . . , ω 6+25i , . . . , ω 605 ), and ω is a primitive ele- (0, ω 3 , ω 6 , ω, ω 4 , ω 7 , ω 2 , ω 5 , ω 0 ), where ω is a primitive ele- ment in F54 . We can check that it is a GH matrix. Clearly, by ment in F32 and ω 3 = ω + 2. By the proof of Proposition IV.3, construction, CH is an additive code with rank(CH ) = 3. By we obtain the matrix H(9, 1) as the matrix having as rows all Lemma II.3, we have that ker(CH ) = 1. 4 linear combinations over F3 of v1 and v2 , that is,   0 0 0 0 0 0 0 0 0 V. C OMBINING DIFFERENT CONSTRUCTIONS  0 1 ω ω2 ω3 ω4 ω5 ω6 ω7  In this section, we use the constructions of additive GH    0 ω3 ω6 ω ω4 ω7 ω2 ω5 1  codes given in Sections III and IV, to show the existence of    0 ω4 ω5 ω6 ω7 1 ω ω2 ω3  H(32 , 1) =  such codes having different ranks between the lower and upper  7 2 5   0 ω ω3 ω 1 ω3 ω6 ω ω4  .  0 ω ω 1 ω 6 ω 5 ω 7 ω 4 ω 2  bounds found in Section II, for a fixed dimension of the kernel. We also see that it is only possible to construct codes for all    0 ω5 ω7 ω4 ω2 ω ω3 1 ω6  allowable pairs rank and dimension of the kernel when e = 2,    0 ω6 ω4 ω3 ω5 ω2 1 ω7 ω  0 ω2 1 ω7 ω ω6 ω4 ω3 ω5 by using the above constructions. For e ≥ 3, mainly it is still (7) necessary to prove the existence of additive GH codes with a 4 kernel of dimension 1 and not having the maximum rank. First, in the next theorem, for q = pe , p prime and any By Proposition II.4, for q = p3 (that is, for e = 3), we have t > e > 1, we prove that there is an additive GH code CH over that the rank of an additive GH code CH of length n = p3 (that Fq of length n = pt with ker(CH ) = k for each possible value is, with t = e = 3) is 3 or 4 if the dimension of the kernel is 1. of k given by item (iv) of Proposition II.4. These codes are the However, by computer search, we found that there is not any ones having the maximum rank, that is, satisfying the upper additive GH matrix H(8, 1) with CH of rank 3, and they do bound given by item (iii) of Proposition II.4. This proves that exist with rank 4, for example the one given in Example IV.5. this upper bound for the rank, once the dimension of the kernel Therefore, the lower bound given by Proposition II.4 is not is fixed, is tight for all cases with t > e > 1. always tight. Note that when t = e > 1, there is an additive GH matrix Example IV.5. The following GH matrix H(23 , 1) over F23 H(q, 1), given by the multiplicative table of Fq , so the corre- generates an additive GH code CH of length n = 23 with sponding GH code CH = CSq of length n = pe = q is linear rank equal to 4 and a kernel of dimension 1, where ω is a over Fq and ker(CH ) = rank(CH ) = 2 [24]. According to primitive element in F23 and ω 3 = ω + 1. Proposition II.4, in this case, there could be additive GH codes  0 0 0 0 0 0 0 0  CH having ker(CH ) = 1 and rank(CH ) ∈ {3, . . . , 1 + e}. By  0 ω2 ω5 ω3 1 ω ω6 ω4  Proposition IV.3, for t = e = 2, there exist such codes having   0 ω3 ω 1 ω ω2 ω4 ω5  6  rank 3. However, it is still an open problem to prove their   0 1 ω2 ω6 ω4 ω3 ω5 ω   existence when q = pe and e ≥ 3 (except for q = 23 , q = 34 3 H(2 , 1) =  5 6 2 4 3 . and q = 54 ; by Examples IV.5 to IV.7, respectively), even  0 ω 6 ω 3 a4 ω 5 ω ω 1  in general for GH codes which are not necessarily additive.  0 ω ω ω ω 1 ω ω2    0 ω ω4 ω2 ω3 ω5 1 ω6   These are connected to Latin squares of order q − 1 and we 0 ω4 1 ω5 ω ω6 ω2 ω3 could use this approach to construct them. (8) Theorem V.1. For q = pe , p prime, and any t > e > 1, there 4 exists an additive GH code CH over Fq of length n = pt with For t = e = 4, we have found that there are GH matrices ker(CH ) = k if and only if H(p4 , 1) for p = 3 and p = 5 such that CH are additive (i) k ∈ {1, . . . , bt/ec} when e - t, codes with minimum dimension of the kernel ker(CH ) = 1 (ii) k ∈ {1, . . . , t/e + 1}, otherwise. 8 Moreover, rank(CH ) = 1 + t − (e − 1)(k − 1). TABLE IV PARAMETERS (rank(CH ), ker(CH )) FOR ALL ADDITIVE GH CODES CH Proof. The general proof is by induction over t > e, in steps OVER Fp2 OF LENGTH n = pt WITH 2 ≤ t ≤ 7. of e. In this sense, the first point is to show the existence of additive GH codes with the following parameters: t (rank(CH ), ker(CH )) kerp (CH ) = rankp (CH ) 2 (3,1) (2,2) 2 k = 1 when t ∈ {e + 1, . . . , 2e − 1}, 3 (4,1) 2.5 4 (5,1) (4,2) (3,3) 3 k ∈ {1, 2, 3} when t = 2e. 5 (6,1) (5,2) 3.5 6 (7,1) (6,2) (5,3) (4,4) 4 When t = 2e, by Corollary III.2, the additive GH code CH 7 (8,1) (7,2) (6,3) 4.5 corresponding to S 2 = Sq ⊕ Sq has k = 3 and rank(CH ) = 1 + t − (e − 1)(k − 1) = 3. By Proposition III.5, there exists an additive GH code CH over Fq with k = 2 and rank(CH ) = Example V.4. For q = 4, that is when p = 2 and e = 2, 1 + t − (e − 1)(k − 1) = 2 + e. From Proposition IV.1, the we can take into account some already known results on the existence of additive GH codes with k = 1 and maximum classification of GH matrices. rank is assured for all t > e > 1. • If n = 4 (t = 2), there is only one GH matrix H(4, 1) By Corollary III.2 and Lemma III.1, we can recursively over F4 having rank(CH ) = ker(CH ) = 2. Therefore, construct additive GH codes CH by using the Kronecker sum CH is linear over F4 , so additive. Actually, H(4, 1) construction, H = Sq ⊕ B, where B is an additive GH matrix corresponds to the Sylvester GH matrix S 1 = S4 . 0 of size pt = pt−e constructed in the previous step. Note that • If n = 8 (t = 3), there is only one GH matrix H(4, 2) 0 if CB of length pt has a kernel of dimension k 0 and maximum having rank(CH ) = 4 and ker(CH ) = 1. Therefore, rank r = 1 + t − (e − 1)(k 0 − 1), then CH of length pt with 0 0 CH is nonlinear over F4 . However, since rank2 (CH ) = t = t0 + e has a kernel of dimension k = k 0 + 1 and rank ker2 (CH ) = 2.5, it is additive. r = r0 + 1. Therefore, r = 1 + t0 − (e − 1)(k 0 − 1) + 1 = • If n = 16 (t = 4), it is known that there are 226 1 + t − (e − 1)(k − 1) and CH has maximum rank. This nonequivalent GH matrices H(4, 4) over F4 [10]. Table V construction covers all the values of k in the statement, except shows the ranks and dimensions of the kernel of the k = 1. However, Proposition IV.1 assures the existence of corresponding codes CH . Moreover, for each case, it additive GH codes with k = 1 and maximum rank for all also gives the value N a/N , where N is the number of t > e > 1. Therefore, the existence for all given parameters nonequivalent codes and N a the number of such codes is proved. that are additive. Finally, by Proposition II.4 and Lemma II.2, we have that these are the only possibilities for the dimension of the kernel TABLE V of an additive GH code. N UMBER OF NONEQUIVALENT ADDITIVE GH CODES OF LENGTH 16 OVER F4 VERSUS THE TOTAL NUMBER , FOR EACH POSSIBLE RANK AND DIMENSION OF THE KERNEL . When e = 2, by Corollary II.5, we have that for each possible dimension of the kernel, there is only one possible rank(CH ) ker(CH ) 3 4 5 6 7 8 rank. Therefore, when t > e = 2, the above theorem covers 3 1/1 all possible pairs (r, k), where r is the rank and k the 2 5/7 0/8 dimension of the kernel of the additive GH code. Moreover, 1 0/3 38/92 0/55 0/57 0/3 since Proposition IV.3 covers the case when t = e = 2, we have the following corollary. 4 2 Corollary V.2. For q = p , p prime, and any t ≥ 2, there Recall that the more general switching construction, given exists an additive GH code CH over Fq of length n = pt with by Proposition III.6, allows for the construction of additive ker(CH ) = k and rank(CH ) = r if and only if r = t + 2 − k GH codes having different ranks and dimensions of the kernel, and k satisfies when t is a multiple of e and k > 1. Now, we combine this (i) k ∈ {1, . . . , bt/ec} when e - t, construction with the Kronecker sum construction to cover (ii) k ∈ {1, . . . , t/e + 1}, otherwise. more cases, proving the existence of additive GH codes CH over Fq of length n = pt , where q = pe , when t is not a Proof. Straightforward by Propositions IV.3 and II.4, Corol- multiple of e and k > 1. lary II.5, and Theorem V.1. Proposition V.5. For q = pe , p prime, and any t not a multiple 2 Example V.3. For q = p , the second column in Table IV of e > 1, there exists an additive GH code CH over Fq of gives all possible values for the rank and dimension of the length n = pt with rank(CH ) = r and ker(CH ) = k, for all kernel of additive GH codes over Fp2 of length n = pt with k ∈ {2, . . . , h = bt/ec} and 2 ≤ t ≤ 7, given by Proposition II.4 and Corollary II.5. r ∈ {2h − k + t + e − he, . . . , 1 + t − (e − 1)(k − 1)}. By Corollary V.2, for each one of these pairs, there exists an additive GH code over Fp2 having these parameters. Proof. Take q = pe , p prime, and any t > e not a multiple 4 of e > 1. Set t = he + h0 , where h = bt/ec. Hence, we can write t = (h − 1)e + (e + h0 ). 9 If h = k, then r = 2h−k+t+e−he = 1+t−(e−1)(k−1), Proof. By Theorem V.6, we have that there exists an additive so the code has the maximum rank r, and its existence is given GH code CH over Fq of length n = pt with ker(CH ) = h by Theorem V.1. Note that if h = 2, then k = 2, so we can and rank(CH ) = r for all r ∈ {h + 2, . . . , h + e}, where focus on the case where h ≥ 3. h = t/e. In this case, the value h + 2 coincides with the If h ≥ 3, by Proposition III.6, there exists a GH code D lower bound d e+t−t/e e−1 e, given in Proposition II.4. Note that of length p(h−1)e with ker(D) = k for all k ∈ {2, . . . , h − 1} d e+t−t/e e = d e−1+1+t−t/e 1 e = 1 + d e−1 e + t/e = t/e + 2 = e−1 e−1 and rank(D) ∈ {2(h − 1) − k + 2, . . . , h + (h − k)(e − 1)}. h + 2. Similarly, the value h + e is equal to the upper bound Also, by Proposition IV.1, there exists a GH code E of length given by Proposition II.4, since 1 + t − (e − 1)(t/e − 1) = 0 pe+h with ker(E) = 1 and rank(E) = e + h0 + 1. Then, by t/e + e = h + e. Lemma III.1, using the Kronecker sum construction with D and E, we obtain an additive GH code C over Fq of length Example V.8. In Table I of Example II.6, all possible values n = pt with ker(C) = k and rank(C) = r, for all 2 ≤ k ≤ for the rank of additive GH codes of length n = pt with h − 1 and 2(h − 1) − k + 2 + e + h0 + 1 − 1 ≤ r ≤ h + (h − 2 ≤ t ≤ 12, once the dimension of the kernel is given, are k)(e−1)+e+h0 +1−1, or equivalently, 2h−k +t+e−he ≤ shown. By Theorem V.6, for each one of these values, except r ≤ 1 + t − (e − 1)(k − 1). Therefore, the result follows. for the ones in bold type, there exists an additive GH code having these parameters. Note that the additive GH codes constructed from the more As it is noticed in Corollary V.7, we can also see in Table I general switching construction, given by Proposition III.6, do that when t = 3h with t > 3, if k = h or k = h + 1, we not cover all possible pairs (r, k), where r is the rank and k the can construct an additive GH code CH with ker(CH ) = k dimension of the kernel, when t is a multiple of e and k > 1. and rank(CH ) = r for all possible values of r between the The upper bounds in Propositions II.4 and III.6 coincide since bounds given by Proposition II.4. 4 h + 1 + (h − k + 1)(e − 1) = 1 + t − (e − 1)(k − 1) if t = he. However, the lower bounds do not coincide in general. The By using the additive GH codes over Fp4 of length n = p4 smallest case where both propositions disagree is for e = 3, (with p = 3 and p = 5) and a kernel of dimension 1, given t = 9, h = 3 and k = 2. By using Proposition III.6, we in Examples IV.6 and IV.7, along with the Kronecker sum know that we can construct additive GH codes with these construction, we show the existence of additive GH codes over parameters having rank r for all r ∈ {6, 7, 8}. However, from Fp4 with greater length, kernel of dimension 1 and different Proposition II.4, we have that r ∈ {5, 6, 7, 8}, and it is not ranks. known whether there is a code having rank r = 5. Proposition V.9. For q = p4 , with p = 3 or p = 5, and any As we just noted for the case when t is a multiple of e t ≥ 4, there exists an additive GH code CH over Fq of length and k > 1, the codes constructed in Proposition V.5 when t is n = pt with ker(CH ) = 1 and rank(CH ) = t + 1 − 2i, for all not a multiple of e do not cover all possible pairs (r, k) given i ∈ {0, . . . , dt/4e − 2}. by Proposition II.4. Again, the upper bounds coincide, but not the lower bounds. The smallest case where they disagree is Proof. First, note that the upper bound for the rank is t + 1 for e = 3, t = 7, h = 2 and k = 2. By using Proposition V.5, when the dimension of the kernel is 1. For t ∈ {5, 6, 7, 8}, we there exist additive GH codes with these parameters having have that r = t + 1 and the statement is true by Theorem V.1. rank r = 6. However, from Proposition II.4, we have that Assume that it is true for t0 ∈ {4h0 − 3, 4h0 − 2, 4h0 − 1, 4h0 }, r ∈ {4, 5, 6}, and the existence of the case with r ∈ {4, 5} is h0 ≥ 2. That is, by induction hypothesis, there exist an additive not known. GH code CD with ker(CD ) = 1 and rank(CD ) = t0 + 1 − 2j for all j ∈ {0, . . . , h0 − 2}. By Examples IV.6 and IV.7, Theorem V.6. For q = pe , p prime, and any t > e > 1, there there exists an additive GH code CE with ker(CE ) = 1 and exists an additive GH code CH over Fq of length n = pt with rank(CE ) = 3. By Lemma III.1, applying the Kronecker sum ker(CH ) = k and rank(CH ) = r, for all k ∈ {2, . . . , h = construction to the corresponding GH matrices D and E, there bt/ec} and exist additive GH codes CH of length n = pt , with t = t0 + 4 r ∈ {lk , . . . , 1 + t − (e − 1)(k − 1)}, and h = h0 +1, having ker(CH ) = ker(CD )+ker(CE )−1 = 1 and rank(CH ) = rank(CD )+rank(CE )−1 = t0 +1−2j+3−1 where for all j ∈ {0, . . . , h0 − 2}, or equivalently, rank(CH ) = t − ( 4 + 1 − 2j + 2 = t + 1 − 2(j + 1) = t + 1 − 2i for all 2h − k + 2 if t is multiple of e, lk = i ∈ {1, . . . , h − 2}. Finally, again by Theorem V.1, there is a 2h − k + t + e − he, otherwise. code CH for i = 0, and the result follows. Proof. Straightforward from Propositions V.5 and III.6. Finally, we show that if the existence of additive GH codes e Corollary V.7. For q = p , p prime, and any t > e > 1, there with dimension of the kernel 1 and any rank between the given exists an additive GH code CH over Fq of length n = pt with lower and upper bounds is proved, then we would have the ker(CH ) = k and rank(CH ) = r, if and only if existence of any such code with rank r and kernel of dimension k for any possible pair (r, k). (i) r ∈ {t/e + 2, . . . , t/e + e} when k = t/e (t is a multiple of e); Theorem V.10. Let q = pe , p prime, and e > 1. If there (ii) r = 1 + t/e when k = 1 + t/e (t is a multiple of e). exist an additive GH code CH over Fq of length n = pt , 10 Pn p+1 Pn p+1 Pn p+1 t > e, with ker(CH ) = 1 and rank(CH ) = r for all that i=1 (vi − wi ) = i=1 vi = i=1 wi = Pp2 −2 r ∈ {d e+t−1 e−1 e, . . . , 1 + t}, then there exists an additive GH λ j=0 (ω j )p+1 = 0 by (9). Then we have code CH over Fq of length n = pt with ker(CH ) = k and rank(CH ) = r, for all k ∈ {2, . . . , bt/ec} and r ∈ n n {d e+t−k X X e−1 e, . . . , 1 + t + (e − 1)(k − 1)}. (vi − wi )p+1 = (vip − wip )(vi − wi ) = i=1 i=1 Proof. It follows from the same arguments as in the proof n X of Theorem V.1, by induction over t, in steps of e. Note (vip+1 + wip+1 − (vip wi + wip vi )) = (10) that, for the lower bound of the rank, by induction hypothe- i=1 ses, there exists an additive GH code of length pt−e with n X kernel of dimension k − 1 and rank d e+t−e−(k−1) e. After − (vip wi + wip vi ) = 0. e−1 applying the Kronecker sum construction, the new additive i=1 GH code CH of length 2t would have ker(CH ) = k and rank(CH ) = d e+t−e−(k−1) e + 1 = d e+t−k Therefore, if p is even, thenPhv, wi = 0. Otherwise, 0 = e−1 e−1 e. Pn n −β i=1 (vip wi + wip vi ) = p p i=1 ((βvi ) wi − wi (βvi )) = hβv, wi = βhv, wi and we also have that hv, wi = 0. Note that since β = ω (p+1)/2 when p is odd, β p = −β. VI. S ELF - ORTHOGONAL ADDITIVE GH CODES OVER Fp2 AND QUANTUM CODES Lemma VI.2. Let v, w be two different rows of a GH matrix H(4, λ). Then hv, wi ≡ λ (mod 2). If v = w then hv, wi ≡ The question of finding quantum-error correcting codes is 0 (mod 2). transformed into the question of finding additive codes over a Pn finite field which are self-orthogonal with respect to a certain Proof. We note that for a vector v = (v1 , . . . , vn ), i=1 vi3 trace inner product [1], [3]. In this section, we see that the is the weight of v since each nonzero element cubed is 1. Let additive GH codes over Fq with q = p2 constructed in the v 6= w. Note also that wt(v) = wt(w) = wt(v + w) = n − λ previous sections are self-orthogonal, so they can be used to by the properties of a GH matrix, where n = 4λ is the order. produce quantum codes. Then we have n n n n n For codes of length n over Fp2 , there are other well X X X X X known inner products besides the Euclidean inner product. (vi + wi )3 = vi3 + 3 vi2 wi + 3 vi wi2 + wi3 Let v = (v1 , . . . , vn ) and w = (w1 , . . . , wn ) ∈ Fpn2 . The i=1 i=1 i=1 i=1 i=1 Hermitian inner product, defined by [v, w]H = Pn p wt(v + w) = wt(v) + 3hv, wi + wt(w). i=1 vi wi and the trace Hermitian inner product,Pwhich is used for n additive codes over Pn Fp2 , that is hv, wi = i=1 (vi wip − vip wi ) Hence, hv, wi = n − λ = 3λ and so hv, wi ≡ λ (mod 2). p p or hv, wi = β i=1 (vi wi − vi wi ) depending on whether p If v = w, then wt(v+w) = 0 and by the same computation is even or odd, respectively [13], where β = ω (p+1)/2 and ω as before we have hv, wi ≡ 0 (mod 2). is a primitive element in Fp2 . We denote the orthogonal code defined by the trace Hermitian inner product as C ⊥ . Proposition VI.3. Let H(p2 , λ) be a GH matrix, where λ is 2 ⊥ Lemma VI.1. Let v, w be two rows of a GH matrix H(p , λ) even when p = 2. Then FH ⊂ FH is a self-orthogonal code. with p 6= 2. Then hv, wi = 0. Proof. By Lemmas VI.1 and VI.2, we have that any two Proof. Since the nonzero elements of Fp are the roots of the Pp−2 vectors are orthogonal with respect to the trace Hermitian inner polynomial xp−1 −1, we see that i=0 αi = 0, where α ∈ Fp product. is a primitive element and p 6= 2. Now, let ω be a primitive element in Fp2 and take α = ω p+1 Proposition VI.4. Let H(p2 , λ) be a GH matrix of order n = which is a primitive element in Fp . Then p2 λ = pt over Fp2 , where λ is even when p = 2, such that 2 CH is additive. Then CH is an additive self-orthogonal code, pX −2 p−2 X p+1 ⊥ X containing pt+2 codewords, and the minimum distance of CH (ω j )p+1 = (ω i+t(p−1) )p+1 = is 3. j=0 i=0 t=1 p−2 X p−2 X Proof. By construction and Proposition VI.3, the results are (p + 1) (ω i )p+1 = (p + 1) αi = 0. clear and all that is required is to show that the minimum ⊥ i=0 i=0 distance of CH is 3. For this, we use the MacWilliams identity, (9) which is proved for these codes in [4]. The (Hamming) weight enumerator of CH is For any two rows v = (v1 , . . . , vn ) and w = (w1 , . . . , wn ) t t−2 t −pt−2 t in a GH matrix H(p2 , λ), where n = p2 λ, we have WCH (x, y) = xp + (pt+2 − p2 )xp yp + (p2 − 1)y p 11 ⊥ and so, the (Hamming) weight enumerator of CH is ACKNOWLEDGMENT 1 WCH ⊥ (x, y) = WCH (x + (p2 − 1)y, x − y) = This work has been partially funded by the Spanish Gov- |CH | 1 h t ernment under grant reference PID2019-104664GB-I00 (AEI/ (x + (p2 − 1)y)p + 10.13039/501100011033). |CH | t−2 t −pt−2 (pt+2 − p2 )(x + (p2 − 1)y)p (x − y)p + t i (p2 − 1)(x − y)p . R EFERENCES (11) [1] A. E. Ashikhmin, and E. Knill, “Nonbinary quantum stabilizer codes,” Let a = pt , b = pt−2 and c = p2 − 1. Note that bc = a − b. IEEE Trans. Information Theory, vol. 47(7), pp. 3065-3072, 2001. t Then, the coefficient of xp −1 y in (11) is [2] H. Bauer, B. Ganter, and F. Hergert, “Algebraic techniques for nonlinear codes,” Combinatorica, vol. 3, pp. 21–33, 1983. 1  [3] A. R. Calderbank, E. M. Rains, P. W. Shor, and N. J. A. Sloane, ac − ac + p2 (a − 1)(bc − bc) = 0.  “Quantum Error Correction Via Codes Over GF (4),” IEEE Trans. |CH | Information Theory, vol. 44(4), pp. 1369–1387, 1998. t Analogously, the coefficient of xp −2 y 2 is [4] W. C. Huffman, “On the theory of Fq -linear Fqt -codes,” Advances in         Mathematics of Communications, vol. 7(3), pp. 349–378, 2013. 1 h 2 a a 2 2 b bc 2 2 i [5] K. Feng, “Quantum error-correcting codes.” in Coding Theory and c +c + p (a − 1) c + −c b = Cryptology, pp. 91-142, 2002. |CH | 2 2 2 2 [6] C. Fernández-Córdoba, C. Vela, and M. Villanueva, “On Z2s -linear c2 b(b − 1) + bc(bc − 1) − 2c2 b2 i   1 h a 2 Hadamard codes: kernel and partial classification,” Des. Codes Cryp- c p + p2 (a − 1) = togr., vol 87(2-3), pp. 417–435, 2019. |CH | 2 2 [7] C. Fernández-Córdoba, C. Vela, and M. Villanueva, “On Z8 -linear p2 h a −c2 b − cb i   Hadamard codes: rank and classification,” IEEE Trans. Information c + (a − 1) ) = Theory, vol. 66(2), pp. 970–982, 2019. ap2 2 2 [8] S. T. Dougherty, J. Rifà, and M. Villanueva, “Ranks and kernels of codes 1h ca − cb(c + 1) i from generalized Hadamard matrices,” IEEE Trans. Inform. Theory, vol. (a − 1) = 62(2), pp. 687–694, 2016. a 2 (a − 1)(ca − cb(c + 1)) (a − 1)(−a + bc + b) [9] S. T. Dougherty, J. Rifà, and M. Villanueva, “Constructions of = = 0. NonequivalentFp-AdditiveGeneralised Hadamard Codes,” in Proc. of 2a 2a 2020 IEEE International Symposium on Information Theory in Los (12) Angeles, California, USA, pp. 150–155, 2020. t [10] M. Harada, C. Lam, and V. Tonchev, “Symmetric (4, 4)-nets and The coefficient of xp −3 y 3 is generalized Hadamard matrices over groups or order 4,” Des. Codes    i Cryptography, vol. 34, pp. 71–87, 2005. 1 h a a c3 −c + [11] D. Jungnickel, “On difference matrices, resolvable designs and general- |CH | 3 3 ized Hadamard matrices,” Math. Z., vol. 167, pp. 49–60, 1979. 2        i [12] A. Ketkar, A. Klappenecker S. Kumar, and P. K. Sarvepalli, “Nonbinary p (a − 1) 3 bh bc b bc c − − c3 b + bc . stabilizer codes over finite fields”, IEEE Trans. Inform. Theory, vol. |CH | 3 3 2 2 52(11), pp. 4892–4914, 2006. (13) [13] G. Nebe, E. M. Rains, and N. J. A. Sloane, Self-Dual Codes and Invariant Theory, Algorithms and Computation in Mathematics, The first term in (13) is always positive. Therefore, in order Berlin/Heidelberg: Springer-Verlag, vol. 17, 2006. t to prove that the coefficient of xp −3 y 3 is positive, we only [14] Jong-Seon No and H.Y. Song, “Generalized Sylvester-type Hadamard matrices,” IEEE International Symposium on Information Theory, June need to check  that3thebsecond bcterm is non2 negative. Hence, 2000, pp. 472. 3 b bc 6[c 3 − 3 − c b 2 + bc 2 ] = bc[c (b − 1)(b − 2) − [15] E. Petrank, and R.M. Roth, “Is code equivalence easy to decide?” IEEE (bc − 1)(bc − 2) − 3bc2 (b − 1) + 3bc(bc − 1)] = bc(2c2 − 2), Trans. Inform.Theory, vol. 43, pp. 1602—1604, 1997. 2 which is non negative since c = p − 1 ≥ 1. This proves the [16] K. T. Phelps, M. LeVan, “Kernels of nonlinear Hamming codes,” Des. Codes Cryptography, vol. 6, pp. 247–257, 1995. statement. [17] K. T. Phelps, J. Rifà, and M. Villanueva, “Kernels and p-kernels of pr -ary 1-perfect codes,” Des. Codes Cryptography, vol. 37, pp. 243– Finally, we describe the connection of these additive GH 261, 2005. matrices or the corresponding CH codes with quantum codes, [18] K. T. Phelps, J. Rifà, and M. Villanueva, “Rank and kernel of binary by following [5, Theo. 6.10]. Hadamard codes,” IEEE Trans. Inform. Theory, vol. 51, no. 11, pp. 3931–3937, 2005. A q-ary quantum code of length n and dimension K is a qn n [19] K. T. Phelps, J. Rifà, and M. Villanueva, “Hadamard codes of length K-dimensional linear subspace Q of C (a q -dimensional 2t s (s odd): Rank and kernel,” Lecture Notes in Computer Science, vol. Hilbert space). It is denoted by [[n, k, d]]q , where k = logq K 3857, pp. 328–337, 2006. and d is the minimum distance, which means that Q can detect [20] K. T. Phelps, J. Rifà, and M. Villanueva, “On the additive (Z4-linear and non-Z4-linear) Hadamard codes: rank and kernel,” IEEE Trans. Inform. up to d − 1 errors and correct up to b d−1 2 c. Theory, vol. 52(1), pp. 316–319, 2006. 2 [21] K. T. Phelps and M. Villanueva, “Ranks of q-ary 1-perfect codes,” Des. Theorem VI.5. Let H(p , λ) be a GH matrix of order n = Codes Cryptography, vol. 27, pp. 139–144, 2002. p2 λ = pt over Fp2 , where λ is even when p = 2, such that [22] K. T. Phelps and M. Villanueva, “On perfect codes: rank and kernel,” CH is additive. Then CH gives a pure additive quantum-error- Des. Codes Cryptography, vol. 27, pp. 183–194, 2002. t t correcting code with parameters [[p , p − (t + 2), 3]]p . [23] S. S. Shrikhande, “Generalized Hadamard matrices and orthogonal arrays of strength two,” Canad. J. Math., vol. 16, pp. 736–740, 1964. Proof. It follows from [5] and Proposition VI.4. Note that [24] V. D. Tonchev, “On generalized Hadamard matrices of minimum rank,” ⊥ Finite Fields Appl., vol. 10, pp. 522-529, 2004. there are no vectors of weight less than 3 in CH \CH . 12 Steven T. Dougherty is a professor of Mathematics and the 2005 recipient of the Hasse Prize. He is the author of Combinatorics and Finite Geometry and Algebraic Coding Theory over Finite Commutative Rings. He has published over 100 papers and has lectured extensively in 12 countries. His research interests include coding theory, combinatorics, finite geometry and number theory. Josep Rifà was born in Manlleu, Catalonia (Spain) in July 1951. He received the graduate degree in Sciences (Mathematical Section) in 1973, from the University of Barcelona and the Ph.D. degree in Sciences (Computer Sciences Section) in 1987, from the UAB (Autonomous University of Barcelona). Since 1974 he was an assistant professor in the Mathematics Department, Barcelona University. In 1987 he joined the UAB and since 1992 he has been a full professor in this University. He was the former Head of Information and Communications Engineering Department at UAB as well as the former Vice-chairman of the Spanish Chapter of Information Theory of IEEE. He has worked in several projects of Spanish CICYT and other organizations on subjects related to digital communications, error correcting codes and encryption of digital information. His research interests include information theory, coding theory and cryptography. Currently, he serves as a Professor Emeritus at UAB. Mercè Villanueva was born in Roses, Catalonia, in January 1972. She received the B.Sc. degree in Mathematics in 1994 from the Autonomous University of Barcelona, the M.Sc. degree in Computer Science in 1996, and the Ph.D. degree in Science (Computer Science Section) in 2001 from the same university. In 1994 she joined the Department of Information and Communications Engineering, at the Autonomous University of Barcelona, as an Assistant Professor, and was promoted to Associate Professor in 2002. Her research interests include subjects related to combinatorics, algebra, coding theory, and graph theory.