Twisted Gabidulin codes and new Maximum Rank Distance codes

(1)

Introduction

Nowadays almost anyone is able to communicate over long distance with other people. This is one of the greatest accomplishment of the modern age. This achievement has been possible thanks to information theory. Suppose that a sender wants to communicate with a receiver using a channel. Of course, if the channel were noiseless then any message sent by the sender over the channel would be received flawlessly. Unfortunately, in real life we almost always use noisy channels to communicate between us since noise can occur from many sources. The main aim of information theory is to enable us to communicate with each other in an efficient way. In 1948, Claude Shannon published “A Mathematical Theory of Communication”, a work focused on the problem of how best to encode the information that a sender wants to transmit to a receiver using a noisy communication channel. The messages sent via the noisy communication channel are words of a code known by the sender and by the receiver. The latter has to decode the word that he receives and that usually is different from the one sent by the sender. Coding theory is the branch of Information theory that deals with the design of efficient codes. Codes are studied by various scientific disciplines, for example computer science, electrical engineering and mathematics. Our work is divided into four chapters and it is focused on the study of some algebraic properties of codes.

In the first chapter, after some basic reminds of finite fields and coding theory, we focus on block codes. Let q be a prime power and let n be a positive integer, block codes of length n are subsets of the finite vector space Fnq. Moreover, we usually work on Fq-subspaces of Fnq that we call linear

codes. In order to know “how many errors” a code C ⊆ Fnq can always correct

in the transmission of a message it is useful to introduce a metric over the finite vector space Fnq. Setting a distance between elements of Fnq it is possible

to define the concept of minimum distance of the code C. The most famous metric is the one induced by the Hamming distance. In the Hamming metric the parameters of a code i.e. the minimum distance, the cardinality and the length are related by an important inequality, the Singleton bound. Let q be a prime power and let m and n be two positive integers, we consider another metric over the finite vector space Fnqm, the rank metric. Rank-metric codes

have been introduced by Delsarte in [3] and rediscovered by Gabidulin in ii

(3)

INTRODUCTION iii [4]. Since then, rank-metric codes have been used in many applications, in particular for network coding. Let us consider, for example, a network that a single sender uses to transmit information to a single receiver. Suppose that the sender information is divided into m packets of length n over a finite field Fq. A node of the network receives many packets and, instead

of merely send them to other nodes, it first mixes randomly those packets and then send them to other nodes. The receiver get some packets and has to reconstruct the m packets sent by the sender. Rank-metric codes play an important role in the construction of codes which are well-suited for this scenario. Like in the Hamming metric the parameters of a code are related by the Singleton bound, in rank metric they are related by a Singleton-type bound. Codes that attain this bound are called Maximum Rank Distance (MRD) codes.

In the second chapter, we describe the first known family of MRD codes that both Delsarte and Gabidulin constructed, indipendently, in their works. This family was later generalized by Kshevetskiy and Gabidulin in [6]. Given a prime power q, two positive coprime integers m and s, n elements g1, g2, . . . , gn∈ Fqm linearly independent over F_q (hence n ≤ m) and a

pos-itive integer k ≤ n then the generalized Gabidulin code Gk,s(g1, g2, . . . , gn)

with support g = (g1, g2, . . . , gn), length n, dimension k and parameter s is

the Fqm-subspace generated by the rows of the s-Moore matrix

Mk,s(g) =       g1 g2 . . . gn gq₁s gq₂s . . . gqns .. . ... . .. ... g₁qs(k−1) g₂qs(k−1) . . . gnqs(k−1)       .

In this work we focus on linear codes i.e. Fqm-subspaces of Fn_qm and we call

linear MRD code an MRD code that is also a linear code. In [5] the authors showed that for some set of parameters any linear MRD code is Gabidulin (i.e. a generalized Gabidulin code with s = 1). Moreover, they found criteria to state whether a given linear code is MRD and to state if a given MRD code is generalized Gabidulin.

It has been proved that almost every linear code is MRD [12] but not many general constructions of linear MRD codes are known. In the third chapter, we first show it and then we describe a family of MRD codes that was introduced by Sheekey in [15] and later generalized by Lunardon, Trom-betti and Zhou in [9]. These MRD codes are called generalized twisted Gabi-dulin codes. Some generalized twisted GabiGabi-dulin codes are linear codes. Let q be a prime power and let m and s be two positive coprime integers. Let, moreover, g1, g2, . . . , gn ∈ Fqm be n elements linearly independent over F_q

(hence n ≤ m) and let k be a positive integer such that 1 < k < n − 1. Then, if η ∈ Fqm is an element whose field norm is different from (−1)km,

(4)

INTRODUCTION iv the rows of the matrix

Mk,s(η, g) =       g1+ ηgq sk 1 g2+ ηg qsk 2 . . . gn+ ηg qsk n gq₁s g₂qs . . . gqns .. . ... . .. ... g₁qs(k−1) g₂qs(k−1) . . . gnqs(k−1)      

generate Hk,s(η, 0, g1, g2, . . . , gn), the linear generalized twisted Gabidulin

code with support g = (g1, g2, . . . , gn), length n, dimension k and parameters

s and η.

The fourth, and last, chapter is divided into two parts. In the first one, we characterize all linear MRD codes that are contained in the generalized Gabidulin code Gk+1,s(g1, g2, . . . , gn) and that contain the generalized

Gabi-dulin code Gk−1,s(gq s 1 , g qs 2 , . . . , g qs

n ). A linear generalized twisted Gabidulin

code Hk,s(η, 0, g1, g2, . . . , gn) satisfies these properties. Moreover, one can

see that characterize those codes is equivalent to characterize the values of the parameter η ∈ Fqm for which the rows of the matrix

Mk,s(η, g) =       g1+ ηgq sk 1 g2+ ηgq sk 2 . . . gn+ ηgq sk n gq₁s g₂qs . . . gqns .. . ... . .. ... g₁qs(k−1) g₂qs(k−1) . . . gnqs(k−1)      

generate an MRD code. We state some theorems and propositions that characterize all such values of η depending on the generalized Gabidulin codes Gk−1,s(gq s 1 , g qs 2 , . . . , g qs n) and Gk+1,s(g1, g2, . . . , gn). Furthermore, we

show that for some sets of parameters all linear MRD codes of the type described above are generalized twisted Gabidulin codes. We also show that for other sets of parameters there exist linear MRD codes of the type described above that are not generalized twisted Gabidulin codes.

In the second part of the fourth chapter, we propose a probabilistic con-struction for new MRD codes that are not equivalent to generalized Gabi-dulin codes but that are quite “similiar” to them. In order to do that, we consider a generalized Gabidulin code G with parameter s whose generator matrix in systematic form is G and we show a lower bound on the proba-bility that changing exactly one element of G then the resulting matrix still generates an MRD code but not a generalized Gabidulin one with parameter s.

(5)

Chapter 1

Preliminaries

The aim of this chapter is to introduce the reader to our work. In order to do that, we recall to mind some useful properties of finite fields. After that, we give an introduction to coding theory. The last section of this chapter is an introduction to rank-metric codes and to Maximum Rank Distance codes.

1.1 Basics of finite fields

In this section we recall some helpful definitions and results on finite fields that will be useful in this work. For the proof of the following results one can see [7].

Theorem 1.1. Let F be a finite field. Then, F has pn elements where n is a positive integer and p is a prime number. The characteristic of F is p. Lemma 1.2. If F is a finite field with q elements, then every a ∈ F satisfies aq = a.

Theorem 1.3. For every prime p and every positive integer n there exists a finite field with pn elements. Any finite field with q = pn elements is isomorphic to the splitting field of xq− x over Fp.

Theorem 1.4. Let Fq be the finite field with q = pn elements. Then, every

subfield of Fq has order pm, where m is a positive divisor of n. Conversely,

if m is a positive divisor of n, then there is exactly one subfield of Fq with

pm elements.

Lemma 1.5. Let s and m be two positive integers such that gcd(s, m) = d and let q be a prime power. Then, Fqm∩ F_qs = F_qd.

Corollary 1.6. Let s and m be two coprime positive integers. Then, the roots of xqs − x in Fqm are exactly the elements of F_q.

(6)

CHAPTER 1. PRELIMINARIES 2 Theorem 1.7. For every finite field Fq, the multiplicative group F∗q of

non-zero elements of Fq is cyclic.

Definition 1.8. A generator of the cyclic group F∗q is called a primitive

element of Fq.

Theorem 1.9. If f is an irreducible polynomial in Fq[x] of degree m, then

f has a root α in Fqm. Furthermore, all the roots of f are simple and are

given by the m distinct elements α, αq, αq2, . . . , αqm−1 of Fqm.

Corollary 1.10. Let f be an irreducible polynomial in Fq[x] of degree m.

Then, the splitting field of f over Fq is given by Fqm.

Definition 1.11. Let Fqm be an extension of F_q and let α ∈ F_qm. Then,

the elements α, αq, . . . , αqm−1 are called conjugates of α with respect to Fq.

Definition 1.12. The automorphism σ over Fqm that fixes F_q and defined

as

σ : Fqm → F_qm

α 7→ αq_.

is called the Frobenius automorphism.

Remark 1.13. Notice that, since σ is an automorphism, it holds that (α1+ . . . + αk)q = αq1+ . . . + α

q k.

for any α1, . . . , αk∈ Fqm.

Theorem 1.14. The distinct automorphisms of Fqm over F_q are exactly the

mappings σ0, σ1, . . . , σm−1 defined by

σj(α) = αq

j

for α ∈ Fqm and 0 ≤ j ≤ m − 1.

Definition 1.15. For a ∈ Fqm the trace Tr

Fqm/Fq(α) of α over Fq is defined

by

Tr_F_qm_/F_q(α) = α + αq+ . . . + αqm−1.

Theorem 1.16. The trace function Tr_F_qm_/F_q satisfies the following proper-ties.

(a) Tr_F_qm_/F_q(α) ∈ Fq for all α ∈ Fqm.

(b) Tr_F_qm_/F_q(α + β) = Tr_F_qm_/F_q(α) + Tr_F_qm_/F_q(β) for all α, β ∈ Fqm.

(c) Tr_F_qm_/F_q(cα) = c Tr_F_qm_/F_q(α) for all c ∈ Fq and for all α ∈ Fqm.

(d) Tr_F_qm_/F_q is a linear transformation from Fqm onto F_q, where both are

(7)

CHAPTER 1. PRELIMINARIES 3 (e) Tr_F_qm_/F_q(α) = mα for all α ∈ Fq.

(f ) Tr_F_qm_/F_q(αq) = Tr_F_qm_/F_q(α) for all α ∈ Fqm.

Definition 1.17. For α ∈ Fqm the norm N

Fqm/Fq(α) of α over Fq is defined

by

N_F_qm_/F_q(α) = α · αq· . . . · αqm−1 _{= α}qm−1q−1 _.

Theorem 1.18. The norm function N_F_qm_/F_q satisfies the following proper-ties.

(a) N_F_qm_/F_q(αβ) = N_F_qm_/F_q(α) N_F_qm_/F_q(β) for all α, β ∈ Fqm.

(b) N_F_qm_/F_q maps Fqm onto F_q and F∗_qm onto F∗_q.

(c) The restriction of N_F_qm_/F_q to F∗qm defines a group homomorphism from

F∗qm to F∗_q.

(d) N_F_qm_/F_q(α) = αm for all α ∈ Fq.

(e) N_F_qm_/F_q(αq) = N_F_qm_/F_q(α) for all α ∈ Fqm.

Corollary 1.19. Let x ∈ F∗q, we denote by Vx the set of elements

Vx:= {y ∈ F∗qm s.t. N

Fqm/Fq(y) = x}.

It holds that |Vx| = q

m₋₁

q−1 .

1.2 An introduction to Coding theory

The purpose of this section is to give a brief mathematical introduction to Coding Theory. The interested reader is referred to [10] or [17] for a full introduction to this theory.

In 1948 Claude Shannon made a breakthrough in the development of information theory and coding theory publishing “A Mathematical Theory of Communication”, a work, divided into two parts, focused on the prob-lem of how best to encode the information that a sender wants to transmit to a receiver using a noisy communication channel. Noise can arise in any communication channel and this is why coding theory is widely used. This theory is useful for network communication, satellite communication and also for other physical media which are subject to errors. Moreover, coding theory has many applications in the theory of computer science. The main aims of coding theory are construct codes with efficient encoding and decod-ing procedures and construct codes that can correct many errors, in a sense that will be clear later. The encoding is the process that the sender has to carry on to transform its message for the receiver into a codeword. On the other hand, the decoding is the process that the receiver has to carry on, via

(8)

CHAPTER 1. PRELIMINARIES 4 a given method based on the original source encoding, to detect and correct errors in the transmission of the originally codeword. Let us take a practical example in the communication scenario.

Let us suppose that a sender wants to send k message symbols to a receiver using a noisy channel that is the only way that the sender and the receiver have to communicate. Since the sender wants to make sure that a certain number of errors can be detected, he encodes the k message symbols into a codeword, a sequence of n symbols with n ≥ k, that belongs to a fixed code, and then sends that codeword over the channel. The receiver receives a word consisting of n symbols that tries to decode in order to get the original codeword. How the sender can encode the message? How the receiver can decode the message?

To formalize the theory, we need the following definitions.

Definition 1.20. An alphabet is a finite set of elements, called symbols of the alphabet.

Definition 1.21. A word is a finite sequence of symbols of a given alphabet. Definition 1.22. A code is a set of words. A word of a given code is called a codeword.

A codeword is thus transmitted via the communication channel and the random noise could add some errors to the sent message. An error arises when a symbol of the codeword is changed in another one. If the received message is not a codeword, the receiver has usually to change it in the most likely codeword. The main methods to improve the reliability of transmis-sion use properties of finite fields hence our alphabets will be finite fields and thus their cardinalities will be prime powers.

We focus on some particular codes from an algebraic point of view, i.e. block codes over finite fields.

Definition 1.23. Let Fq be a finite field and let n be a positive integer.

C ⊆ Fn

q is a block code over Fq with length n.

Therefore, in our first setting the alphabet is the finite field Fq, any word

is a sequence of n symbols that belong to Fq and any code is a subset of Fnq.

We recall what is a metric on a set.

Definition 1.24. A metric on a set X is a function (called distance) d : X × X → R≥0

such that for any x, y, z ∈ X the following conditions are satisfied. (a) d(x, y) ≥ 0 and d(x, y) = 0 if and only if x = y.

(9)

CHAPTER 1. PRELIMINARIES 5 (c) d(x, z) ≤ d(x, y) + d(y, z).

Providing Fnq of a metric it is possible to understand how many errors

we can always correct in the transmission of a codeword of a given code C ⊆ Fn

q. We need the definition of minimum distance of a code.

Definition 1.25. Let C ⊆ Fnq be a non-trivial code (i.e. it contains at least

2 codewords) and let d be a metric on Fnq. The minimum distance(with the

given metric) of C is

min{d(x, y) | x ∈ C, y ∈ C, x 6= y}. We state a basic lemma for the decoding process.

Lemma 1.26 (Unique Decoding Capability). Let C ⊆ Fnq be a code with

minimum distance d in a given metric dm(·, ·) and let x be a word in Fnq.

Then, there is at most one codeword c ∈ C such that dm(x, c) ≤ bd−1₂ c.

Moreover, if there is a codeword c ∈ C such that 0 < dm(x, c) < d then

x /∈ C.

Proof. See [10]. Theorem 2.1.

If the receiver receives the word x instead of the codeword c we say that the number of errors occured in the transmission is dm(x, c). From Lemma

1.26 we deduce that using the nearest codeword decoding, i.e. mapping the received word in one of the closest codewords, the receiver can always decode uniquely up to bd−1₂ c errors and detect up to d − 1 errors.

Since we are working with codes that are subsets of vector spaces, we can study those that are vector subspaces.

Definition 1.27. Let C ⊆ Fnq be a code and let K be a subfield of Fq.

Then, C is a K-linear code of dimension k if it forms a K-subspace of Fnq of

dimension k. If K = Fq then we call C a linear code.

The notation [n, k, d]q is usually used to describe a linear code over Fq

with length n, dimension k and minimum distance, with a given metric, d. The cardinality of a [n, k, d]qcode is qk. We introduce the concept of weight

for an element of Fnq and the concept of minimum weight for a code C ⊆ Fnq.

Definition 1.28. Let C ⊆ Fnq be a code, let d be a metric on Fnq and let

x ∈ Fnq be a vector. Then, the weight of x is

w(x) := d(x, 0). The minimum weight of C is

(10)

CHAPTER 1. PRELIMINARIES 6 Remark 1.29. If C ⊆ Fnq is a linear code then the minimum distance of C

is equal to the minimum weight of C.

Definition 1.30. Let C be a [n, k, d]q code. Then, a generator matrix of C

is a matrix G ∈ Fk×nq whose rows generates this k-dimensional vector space

over Fq. Denoting by rs(G) the row space of G, i.e. the subspace generated

by the rows of the matrix G, we get that C = rs(G). The vectors in Fk

q are called the information words. These are the

mes-sages that the sender can send to the receiver. A generator matrix G ∈ Fk×nq

of a linear code C is useful to encode the information words into codewords. Indeed if v ∈ Fkq then v · G belongs to the code. On the other hand, if c ∈ C

then there exists v ∈ Fkq such that v · G = c.

Definition 1.31. Let x, y ∈ Fnq be two vectors. The dot product of x and y

is hx, yi = n−1 X i=0 xiyi.

Definition 1.32. Let C ⊆ Fnq be a linear code. Then, the dual code of C is

the set of vectors

C⊥_{:= {x ∈ F}n

q : hx, ci = 0 ∀ c ∈ C}.

Remark 1.33. Let C be a [n, k, d]q code. Then, C⊥ is a [n, n − k, d⊥]q

code. The minimum distance d⊥ of C⊥ is not necessarily determined by the parameters of C i.e. from its cardinality, its minimum distance and its length.

Definition 1.34. A parity check matrix H ∈ F(n−k)×nq of a [n, k, d]q code C

is a generator matrix of C⊥⊆ Fn

q, the dual code of C.

Thus, for any c ∈ C, we get that c·HT = 0 and, denoted by G a generator matrix of C, that G · HT = 0. Therefeore, the code C is the right kernel of a parity check matrix of C.

Remark 1.35. From the last propositions we can see some advantages of using linear codes.

1. A linear code C is determined by its generator matrix. Thus, less space is necessary to store C.

2. The minimum distance d of a linear code is equal to its minimum weight. Therefore, fewer calculations are required to calculate d. 3. Working with linear codes, it is simple to encode a message into a

(11)

CHAPTER 1. PRELIMINARIES 7 We introduce a definition that will be useful in Chapter 2.

Definition 1.36. Let K be a subfield of a finite field Fq and let C ⊆ Fnq be

a linear code. Then C|_K := C ∩ Kn _{is the subfield subcode (or the restriction}

of C to K).

The following lemma easily follows.

Lemma 1.37. Let K be a subfield of a finite field Fq and let C ⊆ Fnq be a

linear code. Then, the length of C|_Kis equal to the length of C, the dimension of C|_K is at most the dimension of C and the minimum distance of C|_K is at least the minimum distance of C.

Undoubtedly the most famous metric is the one given by the Hamming distance that we present in the next subsection.

1.2.1 Hamming metric

Definition 1.38. Let x, y ∈ Fn

q be vectors. The Hamming distance dH(x, y)

between them is the number of coefficients in which they differ i.e. dH(x, y) := |{i | 1 ≤ i ≤ n, xi 6= yi}|.

It is trivial to check that the Hamming distance defines a metric on Fnq.

Definition 1.39. Let x ∈ Fnq be a vector. The Hamming weight x is the

number of non-zero components of x i.e.

wH(x) := |{i | 1 ≤ i ≤ n, xi 6= 0}|.

The Hamming distance is a good way to measure the error content of a received message if, in the channel we are using, an error in a position does not influence other positions and if an error symbol can be each of remaining symbols of the alphabet with equal probability.

Setting the Hamming distance on a given code we get the definition of minimum Hamming distance of this code i.e.

Definition 1.40. Let C ⊆ Fnq be a non-trivial code. Then, the minimum

Hamming distance of C is the integer

dH(C) := min{dH(x, y) | x ∈ C, y ∈ C, x 6= y}.

When it can not cause a misunderstanding we will use, with a slight abuse of notation, the notation dH for the minimum Hamming distance of the code

C.

Working with the Hamming distance, the parameters of a given code are related by the Singleton bound.

(12)

CHAPTER 1. PRELIMINARIES 8 Theorem 1.41 (Singleton bound). Let C ⊆ Fnq be a code and let dH be its

minimum Hamming distance. Then,

|C| ≤ qn−dH+1_.

In particular, if C is a [n, k, dH]q code, it holds that

dH ≤ n − k + 1.

Definition 1.42. Let C be a [n, k, dH]q code where dH is the minimum

Hamming distance of C. If dH = n − k + 1 then C is a Maximum Distance

Separable (MDS) code.

1.3 Rank-metric codes

We introduce the general setting that we will use from now on. Given a prime power q and two positive integers m and n we will work with another metric over the finite vector space Fnqm, the Rank metric that we introduce

below.

It is well known that Fqmis a field extension of F_qof degree m. It can be

viewed as a vector space of dimension m over Fqand Fnqm can be viewed as a

vector space of dimension mn over Fq. Let us consider ν = (v1, v2, . . . , vm),

an ordered basis of Fqm over F_q. For any element α ∈ F_qmthere exist unique

a1, . . . , am∈ Fq such that α = m X i=1 aivi.

Therefore, for any vector c = (c1, . . . , cn) ∈ Fnqm there exists a unique matrix

C =      C1,1 C1,2 . . . C1,n C2,1 C2,2 . . . C2,n .. . ... . .. ... Cm,1 Cm,2 . . . Cm,n      such that cj = m X i=1 Ci,jvi ∀ j = 1, . . . , n.

Such a matrix C is the matrix representation of c over Fq. We denote by ψν

the bijective map from Fnqm to Fm×n_q that associates to any vector of Fn_qm its

matrix representation over Fq. Using the latter map we are able to define

(13)

CHAPTER 1. PRELIMINARIES 9 Definition 1.43. Let ν = (v1, v2, . . . , vm) be an ordered basis of Fqm over

Fq and let a, b ∈ Fnqm be two vectors. Then, the rank distance between a

and b is the rank of the difference of their matrix representations over Fq,

i.e.

d(a, b) := rank(ψν(a) − ψν(b)).

Remark 1.44. The rank distance between a and b does not depend on the choice of the ordered basis of Fqm over F_q.

To prove that this function is really a distance, we recall a famous lemma. Lemma 1.45. Let K be a field and let A, B ∈ Km×n be two matrices. Then

rank(A + B) ≤ rank(A) + rank(B).

Lemma 1.46. The rank distance introduced in Definition 1.43 induces a metric over Fnqm.

Proof. We have to prove that the rank distance satisfies the positive defi-niteness, the symmetry and the triangle inequality. Let A, B, C ∈ Fm×n

q

be three matrices.

The positive definiteness follows from the fact that rank(A − B) ≥ 0 with equality if and only if A = B.

Moreover, rank(A − B) = rank(B − A) proving symmetry. Furthermore, by Lemma 1.45, we get that

rank(A − C) = rank(A − B + B − C) ≤ rank(A − B) + rank(B − C) that proves the triangle inequality.

Definition 1.47. Let ν = (v1, v2, . . . , vm) be an ordered basis of Fqm over

Fq and let a ∈ Fnqm be a vector. Then, the rank weight of a is the rank of its

matrix representation over Fq i.e.

rk_Fq(a) := rank(ψν(a))

Remark 1.48. The rank weight of a does not depend on the choice of the ordered basis of Fqm over F_q.

Definition 1.49. Let ν = (v1, v2, . . . , vm) be an ordered basis of Fqm over

Fqand let C ⊆ Fnqmbe a non-trivial code. Then, the minimum rank distance

of C is the integer

d(C) := min{rank(ψν(x) − ψν(y)) | x ∈ C, y ∈ C, x 6= y}.

When it can not cause a misunderstanding we will use, with a slight abuse of notation, the notation d for the minimum rank distance of the code C.

(14)

CHAPTER 1. PRELIMINARIES 10

1.3.1 Balls and spheres

In rank metric, a sphere of radius τ around a word a ∈ (Fqm)n is the set

of all words whose rank distance from a is exactly τ and a ball of radius τ around a word a ∈ (Fqm)n is the set of all words whose rank distance from

a is at most τ . Such a sphere will be denoted by SR(a, τ ) and such a ball

by BR(a, τ ). In order to compute their cardinalities we need some results.

To be able to state them, we fix some notation.

The Grassmannian space Gq(k, n) is the set of all k-dimensional

sub-spaces of the vector space Fnq and its cardinality is the Gaussian binomial

coefficient n_k

q.

The general linear group of degree n over Fq is the set

GLn(q) := {A ∈ Fn×nq | rank(A) = n}.

In the following theorem we calculate the value of n_k_q. Theorem 1.50. n k q = k−1 Y i=0 qn− qi qk_{− q}i.

Proof. To compute the Gaussian binomial coefficient n_k_q we have to cal-culate the number of bases of all k-dimensional subspaces of Fnq and then

divide this number by the number of bases of any k-dimensional subspace, that is equal to | GLk(q)|. The number of bases of all k-dimensional

sub-spaces of Fnq is the number of lists of k linearly independent vectors lying in

Fnq therefore, it is equal to

k−1

Y

i=0

qn− qi.

Furthermore, | GLk(q)| is the number of invertible matrices of order k. Thus,

it is equal to the number of lists of k linearly independent vectors lying in Fkq that is

k−1

Y

i=0

qk− qi_.

Corollary 1.51. The set

E_q_{(k, m, n) := {E ∈ F}m×n q | rank(E) = k}. has cardinality m k q k−1 Y i=0 (qn− qi).

(15)

CHAPTER 1. PRELIMINARIES 11 Proof. Any matrix that belongs to Eq(k, m, n) generates a column space of

dimension k. First of all, we calculate the number of matrices that belong to Eq(k, m, n) and whose columns generate a fixed subspace W of dimension

k. Then, we multiply this number by the number of subspaces of dimension k in Fmq . Let M ∈ Fm×kq be a matrix whose columns generate W . For any

B ∈ Eq(k, m, n) whose column space is W there exists exactly one matrix

C ∈ Eq(k, k, n) such that B = M C, and conversely. It means that the

number of matrices that belong to Eq(k, m, n) and whose columns generate

W is equal to the number of matrices that belong to Eq(k, k, n). Therefore,

the number of matrices that belong to Eq(k, m, n) whose columns space is

W is equal to the number of lists of k linearly independent vectors lying in Fnq. Moreover, the number of subspaces of dimension k in Fmq is mk

q and it

proves the statement.

Now we can use Corollary 1.51 to obtain the cardinalities of a sphere and a ball. We get

Remark 1.52. The cardinalities of SR(a, τ ) and BR(a, τ ) are independent

of the choice of a.

1.3.2 Maximum Rank Distance codes

For rank-metric codes there is an analogue of the Singleton bound for the Hamming metric. Codes that attain this bound are widely studied especially for network coding. In this subsection we introduce these codes by focusing on some of their characteristic properties.

Definition 1.53. Let C ⊆ Fnqmbe a rank-metric code and let K be a subfield

of Fqm. Then, C is a K-linear rank-metric code of dimension k if it forms

an K-subspace of Fnqm of dimension k. If K = F_qm then we call C a linear

rank-metric code.

Theorem 1.54 (Singleton-like bound). Let C ⊆ Fnqm be a rank-metric code

with minimum rank distance d. Then,

|C| ≤ minnqn(m−d+1), qm(n−d+1) o

. (1.1)

In particular, if C ⊆ Fnqm is a linear rank-metric code of dimension k we get

that d ≤ min njm n(n − k) k + 1, n − k + 1 o . (1.2)

(16)

CHAPTER 1. PRELIMINARIES 12 For n > m, the first bound is tighter than the second.

For n ≤ m, the second bound is tighter than the first.

Proof. Setting the Hamming distance on the code C, we denote by dH its

minimum Hamming distance. We know, by Theorem 1.41, that |C| ≤ qm(n−dH+1)_.

Let x, y ∈ C be two elements of the code such that x − y has exactly dH

non-zero components and let ν = (v1, v2, . . . , vm) be an ordered basis of Fqm

over Fq. We denote by X = ψν(x) the matrix representation of x over Fq

and by Y = ψν(y) the one of y. Then, the matrix X − Y has exactly dH

rows that are non-zeros and it implies that rank(X −Y ) ≤ dH hence d ≤ dH.

Thus, we get that

|C| ≤ qm(n−dH+1) _{≤ q}m(n−d+1)_. _(1.3)

Let µ = (w1, w2, . . . , wn) be an ordered basis of Fqn over F_q. Considering

the rank-metric code

CT _{= {x ∈ F}_qn such that ψ_ν(y) = ψ_µ(x)T for some y ∈ C},

we easily get that the minimum rank distance of CT is d and that |C| = |CT|. Applying Equation (1.3) on CT, we get that

|CT| ≤ qn(m−d+1). Since |C| = |CT|, the statement is proven.

The Singleton-like bound for rank-metric codes is a key theorem for our work. Indeed we will focus on codes that attain this bound.

Definition 1.55. Let C ⊆ Fnqm be a rank-metric code with minimum rank

distance d. Then, C is a Maximum Rank Distance code (shortly MRD code) if it attains Bound (1.1).

MRD codes are an analogue of MDS codes with the rank distance. From now on we will focus on linear MRD codes i.e. linear rank-metric codes that are MRD and, unless otherwise specified, we will assume that n ≤ m. To prove the next results we follow the ideas of [4]. We introduce the set

E_q_{(k, n) := {E ∈ F}k×n

q | rank(E) = k}.

Remark 1.56. Given x = (x1, . . . xn) ∈ Fnqm then rk_F_q(x) ≤ k ≤ n implies

that there exist Yx ∈ Eq(k, n) and zx ∈ Fkqm such that x = z_xY_x.

Theorem 1.57. Let C ⊆ Fnqm be a linear rank-metric code of dimension k

and let H be a parity check matrix of C. Then, the minimum rank distance d of C is s if and only if the following properties are satisfied.

(17)

CHAPTER 1. PRELIMINARIES 13 1. There exists ¯Y ∈ Eq(s, n) such that rank( ¯Y HT) < s.

2. If Y ∈ Eq(s − 1, n) then rank(Y HT) = s − 1.

Proof. Let c ∈ C be an element of the code such that rk_Fq(c) = s hence by

Remark 1.56 there exist zc∈ Fsqm and Y_c∈ Fs×n_q such that c = z_cY_c. Since H

is a parity check matrix of C we get that cHT _{= 0 therefore z}

cYcHT = 0 and

rank(YcHT) < s since the rows of YcHT are linearly dependent. Moreover,

let Y ∈ F(s−1)×nq be a matrix of rank s − 1. The rows of the matrix Y HT

are linearly independent because, given z ∈ Fs−1qm , then zY HT = 0 implies

that z is the null vector otherwise zY ∈ C and rk_Fq(zY ) < s. Hence, the

first direction is proven.

For the other direction notice that, by hypothesis 1, there exists z ∈ Fsqm

such that z ¯Y HT = 0 so z ¯Y ∈ C and therefore, using that rk_Fq(z ¯Y ) ≤ s, we

get d ≤ s. Assume that there exists a ∈ C such that rk_Fq(a) < s. Using

Remark 1.56 and hypothesis 2 we get a contradiction.

Theorem 1.58. Let C ⊆ Fnqm be a linear rank-metric code of dimension k

and let H be a parity check matrix of C. Then, C is MRD if and only if Y HT has rank n − k for any Y ∈ Eq(n − k, n).

Proof. By the proof of Theorem 1.57, any Y ∈ F(n−k)×nq of rank n − k is

such that Y HT has rank n − k if and only if d − 1 ≥ n − k. Using Theorem 1.54 the statement follows.

Remark 1.59. Given M ∈ Eq(k, n) then, there exists M⊥ ∈ Eq(n − k, n)

that is orthogonal to M , namely M⊥MT = 0 holds. The dual code of any MRD code is MRD.

Theorem 1.60. Let C ⊆ Fnqm be a linear rank-metric code of dimension k.

Then, C is MRD if and only if its dual code C⊥ is MRD.

Proof. Let H be a parity check matrix of C. By Theorem 1.54, is enough to prove that d⊥, the minimum rank distance of C⊥, is greater than k. Suppose that it is false, hence there exists c ∈ C⊥ such that rk_F_q(c) = s ≤ k. By Remark 1.56, c = zcYc with zc∈ Fkqm and Yc∈ Fk×nq of rank k. By Remark

1.59, there exists Y_c⊥∈ F(n−k)×nq of rank n − k such that Yc⊥YcT = 0 hence

Y_c⊥Y_cTz_cT = 0 therefore Y_c⊥cT = 0. By Theorem 1.58, we get a contradiction which proves the first direction.

Since C = (C⊥)⊥, the other direction immediately follows.

Corollary 1.61. Let C ⊆ Fnqm be a linear rank-metric code of dimension k

and let G be generator matrix of C. Then, C is MRD if and only if Y GT has rank k for any Y ∈ Eq(k, n).

(18)

CHAPTER 1. PRELIMINARIES 14 Proof. The generator matrix G of the code C is a parity check matrix of its dual code C⊥⊆ Fn

qm of dimension n − k. By Theorem 1.58, C⊥ is an MRD

code if and only if Y GT has rank k for any Y ∈ Fk×nq of rank k. Using

Theorem 1.60 the statement follows because C is an MRD code if and only if C⊥ is an MRD code.

1.3.3 Equivalence between rank-metric codes

There exist different definitions of equivalence between two rank-metric codes. In order to introduce the definition that we will use, we need the definition of semi-linear map and the definition of semi-linear Fq-rank

isom-etry.

Definition 1.62. Let p be a prime and let q be a power of p. A map f : Fnq 7→ Fnq is Fq/Fp-semi-linear if it satisfies the following conditions:

(a) f (x + y) = f (x) + f (y) for every x, y ∈ Fn q.

(b) there exists γ ∈ Gal(Fq/Fp) such that f (αx) = αγ(f (x)) for every

α ∈ Fq and every x ∈ Fnq where Gal(Fq/Fp) denotes the Galois group

of the field extension Fq/Fp.

Definition 1.63. An invertible map f : Fnqm7→ Fn_qm is a semi-linear Fq-rank

isometry on Fnqm if f is an F_qm/F_p-semi-linear map and preserves the rank

weight.

Using the latter definition, we can give the definition that we will use of equivalence between two rank-metric codes.

Definition 1.64. Two rank-metric codes C, C0 _{⊆ F}n

qm are semi-linearly

rank-metric equivalent if there exists a semi-linear Fq-rank isometry f such that

C0 = f (C).

In [11] Morrison characterized the semi-linear Fq-rank isometries on Fnqm.

Lemma 1.65. The semi-linear Fq-rank isometries on Fnqm are of the form

(λ, A, ρ) ∈ F∗qm× GL_n(q) o Aut(Fqm), acting on Fnqm 3 (v₁, . . . , v_n) via (v1, . . . , vn)(λ, A, ρ) = (ρ(λv1), . . . , ρ(λvn))A.

In particular, if C ⊆ Fnqm is a linear rank-metric code with minimum rank

distance d, then

C0 = ρ(λC)A

is a linear rank-metric code with minimum rank distance d. Proof. See [11]. Proposition 3.10.

(19)

Chapter 2

The first family of MRD

codes

The seminal works [3](1975) and [4](1985) marked the birth of rank-metric codes. In these works Delsarte and, indipendently, Gabidulin discovered the first known family of Maximum Rank Distance codes. The codes they described are called Gabidulin codes. From the existence of those codes, we know that linear MRD codes exist for any set of parameters. Kshevetskiy and Gabidulin generalized the previous family of linear MRD codes and in [6](2005) they constructed the family of generalized Gabidulin codes. For many years this was the only known family of linear MRD codes hence, the question was if there were other general constructions of linear MRD codes. In [5], Horlemann-Trautmann and Marshall showed that for some choice of the parameters, all linear MRD codes are Gabidulin. In order to do that, they gave new characterizations of generalized Gabidulin codes and linear MRD codes.

2.1 Generalized Gabidulin codes

In this section we present generalized Gabidulin codes. From now on, when it is clear which is the prime power q that we are considering, we will use the notation [i] instead of qi_.

Definition 2.1. Given a prime power q and a positive integer m, a poly-nomial p ∈ Fqm[x]/(x[m]− x) is a linearized polynomial if it has the form

p(x) =

m−1

X

i=0

pix[i].

The set of all such polynomials over Fqm is denoted by L_m(F_qm) and it is

a ring with the operations of sum and composition. The maximum i such that pi 6= 0 is the q-degree of p.

(20)

CHAPTER 2. THE FIRST FAMILY OF MRD CODES 16 Remark 2.2. Notice that if p ∈ Lm(Fqm) then for any α ∈ F_qm, β ∈ F_qm

and c ∈ Fq it holds that

p(α + β) = p(α) + p(β), p(cβ) = cp(β).

Thus, if Fqm is considered as a vector space over F_q, p induces a linear

operator on Fqm. Hence, any F_q-linear combination of roots of p is also a

root of p.

The following theorem is a simple consequence of the latter Remark. Theorem 2.3. Let p ∈ Lm(Fqm) be a nonzero linearized polynomial and let

Fqt be an extension field of F_qm that contains all the roots of p. Then each

root of p has the same multiplicity, which is either 1 or a power of q, and the roots form a linear subspace of Fqt, where F_qt is regarded as a vector space

of dimension t over Fq.

It is also not difficult to prove that there exists a partial converse of this theorem i.e.

Theorem 2.4. Let U be a linear subspace of Fqm, considered as a vector

space over Fq. Then, for any nonnegative integer k the polynomial

L(x) = Y

β∈U

(x − β)[k]

is a linearized polynomial over Fqm, whose space of roots is U .

Remark 2.5. Notice that the coefficient of x[k] of the polynomial L(x) in Theorem 2.4 is the product of all the elements of U that are not 0.

Before defining the family of generalized Gabidulin codes we need to introduce, given two positive integers k and s, a key subset of linearized polynomials i.e. Gk,s := n p0x + p1x[s]+ . . . + pk−1x[s(k−1)] | pi ∈ Fqm o . We denote by Gk the subset Gk,1.

Furthermore, we need to introduce a particular matrix that is a sort of q-analogue of the Vandermonde matrix and it is called Moore matrix.

(21)

CHAPTER 2. THE FIRST FAMILY OF MRD CODES 17 Definition 2.6. Let a = (a1, a2, . . . , an) ∈ Fnqm be a vector. Given two

positive integers k and s we define the k × n s-Moore matrix

Mk,s(a) :=      a1 a2 . . . an σs(a1) σs(a2) . . . σs(an) .. . ... . .. ... σs(k−1)(a1) σs(k−1)(a2) . . . σs(k−1)(an)     

where σ denotes the Frobenius automorphism that fixes Fq and defined as

σ : Fqm → F_qm

α 7→ αq_.

We denote by Mk(a) the matrix Mk,1(a) and we call Moore matrix the

1-Moore matrix.

Notice that if α ∈ Fqm then for any integer i it holds that σi(α) = α[i].

Given a square Moore matrix there exists a simple formula for computing its determinant. Moreover, this formula gives a relation between the rank of the Moore matrix Mk(a1, a2, . . . , an) and the dimension of the Fq-subspace

generated by a1, a2, . . . , an.

Lemma 2.7. Let a = (a1, a2, . . . , an) ∈ Fnqm be a vector. Then, the

deter-minant of the square Moore matrix Mn(a) is

det(Mn(a)) = a1 n−1 Y i=1 Y b1,...,bi∈Fq ai+1− i X h=1 bhah . (2.1)

In particular, the matrix Mn(a) is invertible if and only if a1, a2, . . . , an are

linearly independent over Fq.

Proof. We will prove (2.1) by induction on n. The case n = 1 is trivial. Assuming that the formula is proven for n, we want to prove it for n + 1. For 1 ≤ i ≤ n + 1, we define qi := det      a1 a2 . . . ai

σ(a1) σ(a2) . . . σ(ai)

..

. ... . .. ...

σi−1(a1) σi−1(a2) . . . σi−1(ai)

     .

Let us consider, moreover, the linearized polynomial

q(x) := det      a1 a2 . . . an x

σ(a1) σ(a2) . . . σ(an) x[1]

.. . ... . .. ... ... σn(a1) σn(a2) . . . σn(an) x[n]      .

(22)

CHAPTER 2. THE FIRST FAMILY OF MRD CODES 18 By expansion along the last column we get

q(x) = qnx[n]+ n−1

X

i=0

cix[i],

for some c1, . . . , cn that belong to Fqm. It is obvious that every a_i with

1 ≤ i ≤ n is a root of the linearized polynomial q(x) hence any linear combination of them over Fq is a root of q(x). Therefore, if a1, . . . , an are

linearly independent over Fq, then q(x) has qn distinct roots and we get

q(x) = qn Y b1,...,bn∈Fq x − n X k=1 akbk .

By the inductive hypothesis, qn= a1 n−1 Y i=1 Y b1,...,bi∈Fq ai+1− i X h=1 bhah . Thus, qn+1= q(an+1) = a1 n−1 Y i=1 Y b1,...,bi∈Fq ai+1− i X h=1 bhah Y b1,...,bn∈Fq an+1− n X k=1 akbk

and it proves the statement.

On the other hand, if a1, . . . , an are linearly dependent over Fq, then

there exist c1, . . . , cn∈ Fq not all of which are 0 such that n X i=1 aici= 0. Therefore, n X i=1 σj(ai)ci = 0 for j = 0, . . . , n.

Hence, q(x) is the null polynomial because it is the determinant of a matrix whose columns are linearly dependent. So, qn+1 = q(an+1) = 0 and the

statement is proven because if a1, . . . , an+1 are linearly dependent over Fq

then the right hand side of (2.1) is equal to 0.

Corollary 2.8. Let g = (g1, g2, . . . , gn) ∈ Fnqm such that rk_F_q(g) = n. If

k ≤ n, then the matrix

Mk(g) :=      g1 g2 . . . gn σ(g1) σ(g2) . . . σ(gn) .. . ... . .. ... σk−1(g1) σk−1(g2) . . . σk−1(gn)      has rank k.

(23)

CHAPTER 2. THE FIRST FAMILY OF MRD CODES 19 We can finally define generalized Gabidulin codes.

Definition 2.9. Let g = (g1, g2, . . . , gn) ∈ Fnqm such that rk_F_q(g) = n and let

k and s be be two positive integers such that gcd(s, m) = 1 and k ≤ n. Then, the generalized Gabidulin code Gk,s(g) with support g, length n, dimension

k and parameter s is the set Gk,s(g) :=

n

(f (g1), f (g2), . . . , f (gn)) : f ∈ Gk,s

o .

If s = 1 then we use the notation Gk(g) instead of Gk,1(g) and we call such

code a Gabidulin code.

For any generalized Gabidulin code C with parameter s, there exists an s-Moore matrix that is a generator matrix for C.

Proposition 2.10. Let g = (g1, g2, . . . , gn) ∈ Fnqm such that rk_F_q(g) = n

and let k and s be two positive integers such that gcd(s, m) = 1 and k ≤ n. Then, the code generated by the s-Moore matrix

Mk,s(g) =      g1 g2 . . . gn σs(g1) σs(g2) . . . σs(gn) .. . ... . .. ... σs(k−1)(g1) σs(k−1)(g2) . . . σs(k−1)(gn)     

is the generalized Gabidulin code Gk,s(g) with support g, length n, dimension

k and parameter s.

Proof. Denoting by C the linear code generated by Mk,s(g) we get that c ∈ C

if and only if there exist a0, . . . , ak−1∈ Fqm such that

c = k−1 X i=0 aiσsi(g1), k−1 X i=0 aiσsi(g2), . . . , k−1 X i=0 aiσsi(gn) ! .

Hence, we get that c ∈ C if and only if there exists a polynomial p of the form p(x) =Pk−1

i=0aix[si] such that

c = p(g1), p(g2), . . . , p(gn).

The statement immediately follows.

Remark 2.11. As stated in Chapter 1, we are assuming that n ≤ m when we pick n elements of Fqm linearly independent over F_q.

We can now prove that any Gabidulin code is MRD.

Theorem 2.12. Let g = (g1, g2, . . . , gn) ∈ Fnqm such that rk_F_q(g) = n and

let k be a positive integer such that k ≤ n. Then, the Gabidulin code Gk(g)

(24)

CHAPTER 2. THE FIRST FAMILY OF MRD CODES 20 Proof. Let G = Mk(g) be the generator matrix of Gk(g). By Corollary 1.61,

it is enough to prove that for any Y ∈ Eq(k, n), the matrix Y GT has rank

k. Let Y =      y1,1 y1,2 . . . y1,n y2,1 y2,2 . . . y2,n .. . ... . .. ... yk,1 yk,2 . . . yk,n     

be a matrix of rank k whose elements belong to Fq. Hence,

Y GT =      Pn i=1y1,igi Pn i=1y1,iσ(gi) . . . Pn i=1y1,iσk−1(gi) Pn

i=1y2,igi Pni=1y2,iσ(gi) . . . Pni=1y2,iσk−1(gi)

..

. ... . .. ...

Pn

i=1yk,igi Pni=1yk,iσ(gi) . . . Pni=1yk,iσk−1(gi)

     =      Pn i=1y1,igi σ( Pn i=1y1,igi) . . . σk−1( Pn i=1y1,igi) Pn i=1y2,igi σ( Pn i=1y2,igi) . . . σk−1( Pn i=1y2,igi) .. . ... . .. ... Pn

i=1yk,igi σ(Pni=1yk,igi) . . . σk−1(Pni=1yk,igi)

     .

So, Y GT is the transpose of a Moore matrix. Since g1, . . . , gn are linearly

independent over Fq and Y has rank k we get that

rk_Fq * _n X i=1 y1,igi, n X i=1 y2,igi, . . . , n X i=1 yk,igi + = k.

Therefore, by Lemma 2.7, we get that Y GT has rank k and the statement is proven.

An important property of Gabidulin codes is that also their dual codes are Gabidulin.

let k be a positive integer such that k ≤ n and let G = Gk(g). Then H,

the dual code of G, is a Gabidulin code. Moreover, H = Gn−k(h) where

h = (h1, . . . , hn) ∈ (Fqm)n is a non-zero solution for the following n − 1

linear equations

n

X

i=1

hiσt(gi) = 0 ∀ t ∈ [k + 1, n + k − 1]. (2.2)

Proof. Denoting by H = Mn−k(h), we have to prove that H is a generator

matrix for H and that h1, . . . , hn are linearly independent over Fq. The

(25)

CHAPTER 2. THE FIRST FAMILY OF MRD CODES 21 σk+1(g1), . . . , σk+1(gn) over Fq. Defining ¯g := (σk+1(g1), . . . , σk+1(gn)) we

can rewrite Equation (2.2)

Mn−1(¯g) · hT = 0. (2.3)

We denote by ¯G the Gabidulin code Gn−1(¯g). Using Proposition 1.60 and

Theorem 2.12 we know that the dual code of ¯G is MRD hence its minimum rank distance is n. Recalling Equation (2.3), we get that h belongs to the dual code of ¯G, therefore rk_F_q(h) = n. In order to prove that H is a generator matrix for H it is now enough to show that

G · HT = 0. Namely, that n X i=1 σl(gi)σw(hi) = 0 ∀ l ∈ [0, k − 1], w ∈ [0, n − k − 1].

It is straightforward to prove that it is equivalent to

n

X

i=1

hiσt(gi) = 0 ∀ t ∈ [k + 1, n + k − 1].

Since the latter equations hold by hypothesis, the statement is proven. Gabidulin codes show that for any set of parameters there exists a linear MRD code with these parameters. Moreover, also any generalized Gabidulin codes is MRD. To prove this, we follow the ideas of [6] and we need three preliminary lemmas.

Lemma 2.14. Let g = (g1, g2, . . . , gm) ∈ Fmqm such that rk_F_q(g) = m and let

s be a positive integer such that gcd(s, m) = 1. Then, the matrix

Ms,m(¯g) =      g1 g2 . . . gm σs(g1) σs(g2) . . . σs(gm) .. . ... . .. ... σs(m−1)(g1) σs(m−1)(g2) . . . σs(m−1)(gm)      is invertible.

Proof. We define the set

S := {sj (mod m) | 0 ≤ j ≤ m − 1 }.

Since gcd(s, m) = 1 we get that S = {0, . . . , m − 1}. Hence, the matrix Ms,m(¯g) is a row permutation of the matrix

Mm(¯g) =      g1 g2 . . . gm σ(g1) σ(g2) . . . σ(gm) .. . ... . .. ... σm−1(g1) σm−1(g2) . . . σm−1(gm)      .

(26)

CHAPTER 2. THE FIRST FAMILY OF MRD CODES 22 Lemma 2.15. Let g = (g1, g2, . . . , gm) ∈ Fmqm such that rk_F_q(g) = m and let

s be a positive integer such that gcd(s, m) = 1. Then, g1, . . . , gm considered

as elements of Fqms ⊇ F_qm are linearly independent over F_qs.

Proof. If s = 1 the statement is clearly true. If s > 1 we suppose that g1, . . . , gm are linearly dependent over Fqs ⊆ F_qms. So, there exist m

ele-ments a1, . . . , am ∈ Fqs ⊆ F_qms, not all of which are 0, such that

m

X

i=1

aigi= 0. (2.4)

Thus, it holds that

m

X

i=1

aiσsj(gi) = 0, ∀ j ∈ [0, m − 1]. (2.5)

By Equations (2.5), it follows that      g1 g2 . . . gm σs(g1) σs(g2) . . . σs(gm) .. . ... . .. ... σs(m−1)_(g 1) σs(m−1)(g2) . . . σs(m−1)(gm)           a1 a2 .. . am      =      0 0 .. . 0      .

Hence, by Lemma 2.14, a1= . . . = am = 0 which yields a contradiction.

Lemma 2.16. Let g = (g1, g2, . . . , gn) ∈ Fnqm such that rk_F_q(g) = n and let

s be a positive integer such that gcd(s, m) = 1. Then, g1, . . . , gn considered

as elements of Fqms ⊇ F_qm are linearly independent over F_qs.

Proof. Extending the ordered set (g1, . . . , gn) of n linearly independent

ele-ments to an ordered set (g1, . . . , gm) of m linearly independent elements and

using Lemma 2.15 the statement follows.

let k and s be two positive integers such that k ≤ n and gcd(s, m) = 1. Then, the generalized Gabidulin code Gk,s(g) is MRD.

Proof. If s = 1 we get the MRD code Gk(g). If s > 1 we denote by d

the minimum rank distance of Gk,s(g) and we consider Q = qs. Treating

g1, . . . , gnas elements of FQm we get, by Lemma 2.16, that they are linearly

independent over FQ. Notice that

Mk,s(g) =      g1 g2 . . . gn gQ₁ gQ₂ . . . gQn .. . ... . .. ... g₁Qk−1 g₂Qk−1 . . . gnQk−1      .

(27)

CHAPTER 2. THE FIRST FAMILY OF MRD CODES 23 We get that Mk,s(g) can be considered as the generator matrix of a Gabidulin

code C0 over FQm of dimension k and distance d0. Hence, C0is an MRD code

over FQm. The subfield subcode over F_qm of C0 is the code G_k,s(g) and

clearly it has dimension k. By Remark 1.37, we know that d ≥ d0 and, since d0 = n − k + 1 and d ≤ n − k + 1, we get that d = n − k + 1 and therefore G_k,s_{(g) is an MRD code over F}_qm.

As the dual codes of Gabidulin codes are Gabidulin codes, the dual codes of generalized Gabidulin codes are generalized Gabidulin codes.

let k and s be two positive integers such that k ≤ n, gcd(s, m) = 1 and let G = G_k,s(g). Then H, the dual code of G, is a generalized Gabidulin code. Moreover, H = Gn−k,s(h) where h = (h1, . . . , hn) ∈ (Fqm)n is a non-zero

solution for the following n − 1 linear equations

n

X

i=1

hiσst(gi) = 0 ∀ t ∈ [k + 1, n + k − 1]. (2.6)

Proof. To prove this theorem is enough to readapt the proof of Theorem 2.13.

Using Lemma 2.16 we can generalize Lemma 2.7 in the following way Lemma 2.19. Let a = (a1, a2, . . . , an) ∈ Fnqm be a vector and let s be a

positive integer such that gcd(s, m) = 1. Then, the determinant of the square s-Moore matrix Mn,s(a) is

det(Mn,s(a)) = a1 n−1 Y i=1 Y b1,...,bi∈Fqs ai+1− i X h=1 bhah . (2.7)

In particular, the s-Moore matrix is invertible if and only if a1, a2, . . . , an

are linearly independent over Fq.

Proof. Let Q = qs. By Lemma 2.16, a1, . . . , an∈ Fqm are linearly

indepen-dent over Fq if and only if a1, . . . , an ∈ FQm are linearly independent over

FQ. Notice that Mn,s(a) =      a1 a2 . . . an aQ₁ aQ₂ . . . aQn .. . ... . .. ... aQ₁n−1 aQ₂n−1 . . . aQnn−1      .

Thus, by Lemma 2.7, we get that det(Mn,s(a)) = a1 n−1 Y i=1 Y b1,...,bi∈FQ ai+1− i X h=1 bhah . (2.8)

(28)

CHAPTER 2. THE FIRST FAMILY OF MRD CODES 24 It is now naturally to ask whether a rank-metric code that is not a generalized Gabidulin code can be equivalent to a generalized Gabidulin code. We will see in a corollary of the next proposition that this can not happen.

Proposition 2.20. The family of generalized Gabidulin codes is closed un-der the semilinear Fq-rank isometries.

Proof. Let g = (g1, g2, . . . , gn) ∈ Fnqm such that rk_F_q(g) = n and let k and

s be two positive integers such that k ≤ n and gcd(s, m) = 1. Given ρ ∈ Aut(Fqm), λ ∈ F∗_qm, A ∈ GLn(q) and the generalized Gabidulin code

G := G_k,s(g) we want to prove, by Lemma 1.65, that G0 = ρ(λG)A is a generalized Gabidulin code. Supposing that

A =      a1,1 a1,2 . . . a1,n a2,1 a2,2 . . . a2,n .. . ... . .. ... an,1 an,2 . . . an,n     

we get, by a straightforward calculation, that

ρ(λ)      ρ(Pn

i=1ai,1gi) ρ(Pni=1ai,2gi) . . . ρ(Pni=1ai,ngi)

σs_(ρ(Pn

i=1ai,1gi)) σs(ρ(Pni=1ai,2gi)) . . . σs(ρ(Pni=1ai,ngi))

. . . . . . . .. ... σs(k−1)_(ρ(Pn

i=1ai,1gi)) σs(k−1)(ρ(Pni=1ai,2gi)) . . . σs(k−1)(ρ(Pni=1ai,ngi))



   

is a generator matrix of G0. Thus, also

     ρ(Pn

i=1ai,1gi) ρ(Pni=1ai,2gi) . . . ρ(Pni=1ai,ngi)

σs_(ρ(Pn

i=1ai,1gi)) σs(ρ(Pni=1ai,2gi)) . . . σs(ρ(Pni=1ai,ngi))

. . . ... . .. ... σs(k−1)_(ρ(Pn i=1ai,1gi)) σs(k−1)(ρ( Pn i=1ai,2gi)) . . . σs(k−1)(ρ( Pn i=1ai,ngi))     

is a generator matrix of G0. Since g1, . . . , gn are linearly independent it is

easy to check that rk_F_q * ρ n X i=1 ai,1gi , ρ n X i=1 ai,2gi , . . . , ρ n X i=1 ai,ngi + = k. Therefore, it holds that

G0 = Gk,s ρ n X i=1 ai,1gi , ρ n X i=1 ai,2gi , . . . , ρ n X i=1 ai,ngi ! .

Hence, G0 is a generalized Gabidulin code of dimension k with parameter s.

Corollary 2.21. If C ⊆ Fnqm is a linear MRD code that is not a generalized

Gabidulin code then C is not equivalent to a generalized Gabidulin code. Proof. It directly follows from Proposition 2.20.

(29)

CHAPTER 2. THE FIRST FAMILY OF MRD CODES 25

2.2 New criteria for rank-metric codes

In [5], Horlemann-Trautmann and Marshall found new criteria to state whether a given linear rank-metric code is MRD and to state if a given linear MRD code is generalized Gabidulin. Moreover, they proved that for some sets of parameters a linear rank-metric code is MRD if and only if it is Gabidulin. In this section we recall the main results of their work.

2.2.1 New criteria for linear MRD codes

In this subsection we state two criteria to check whether a generator matrix of a linear rank-metric code generates an MRD code and we also prove that any linear MRD code has a generator matrix in a standard form, called systematic form. We first need an auxiliary result.

Lemma 2.22. Any generator matrix G ∈ Fk×nqm of a linear MRD code of

dimension k has only non-zero maximal minors.

Proof. Any maximal minor diof G is the determinant of a square submatrix

Gi of G of order k. Hence, there exists Vi ∈ Eq(k, n) such that

di = det(Gi) = det(ViGT).

By Corollary 1.61, di 6= 0 and the statement is proven.

Lemma 2.23. Any linear MRD code C ⊆ Fnqm of dimension k has a unique

generator matrix G ∈ Fk×nqm in systematic form, i.e.

G = [ Ik | X ].

Moreover, all entries of X are from Fqm\ F_q.

Proof. The first statement follows from Lemma 2.22. Furthermore, every codeword of C needs to have at least n − k entries from Fqm\F_q because the

minimum rank distance of C is n − k + 1.

Theorem 2.24. Let G ∈ Fk×nqm be a generator matrix of a rank-metric code

C ⊆ Fn

qm. Then, C is MRD if and only if, for any A ∈ GLn(q), every

maximal minor of GA is non-zero.

Proof. If C is MRD we know, by Lemma 1.65, that for any A ∈ GLn(q) it

holds that GA is a generator matrix for an MRD code. By Lemma 2.22, the first direction follows.

To prove the other direction, suppose that C is a non-MRD code. Hence, there exists a non-zero codeword c ∈ C of rank at most n − k. Thus, there exists A ∈ GLn(q) such that cA has the first k entries equal to 0. Therefore,

there exists a generator matrix of CA with cA as a row and the first maximal minor of this generator matrix is zero which yields a contradiction.

(30)

CHAPTER 2. THE FIRST FAMILY OF MRD CODES 26 In order to state the other criterion, we introduce the set

Tq(k, n) =E ∈ Fk×nq | E is in reduced row echelon form and rank(E) = k . Proposition 2.25. Let C ⊆ Fnqm be a linear code and let G ∈ Fk×n_qm be a

generator matrix of C. Then, C is MRD if and only if rank(EGT) = k

for any E ∈ Tq(k, n).

Proof. Let Y ∈ Fk×nq be a matrix, we denote by EY its reduced row echelon

form. So, there exists a matrix R ∈ GLk(q) such that Y = REY. Therefore,

we get

det(Y GT) = det(REYGT) = det(R) det(EYGT).

Since det(R) 6= 0, we get that Y GT is invertible if and only if EYGT is

invertible. Thus, the statement follows from Corollary 1.61.

2.2.2 New criterion for generalized Gabidulin codes

In this subsection we state a theorem to check if a given MRD code is generalized Gabidulin. To state this theorem, we need some lemmas and a proposition. First of all, we fix some notation. Let M ∈ Fk×nqm be a matrix

i.e. M =      m1,1 m1,2 . . . m1,n m2,1 m2,2 . . . m2,n .. . ... . .. ... mk,1 mk,2 . . . mk,n     

we denote by M[i] the matrix obtained applying i times the Frobenius au-tomorphism coordinate-wise on M i.e.

M[i] =      σi(m1,1) σi(m1,2) . . . σi(m1,n) σi(m2,1) σi(m2,2) . . . σi(m2,n) .. . ... . .. ... σi(mk,1) σi(mk,2) . . . σi(mk,n)      .

We will use the same notation also when we apply i times the Frobenius automorphism on vectors coordinate-wise. Analogously, if C ⊆ Fnqm then

C[i] _{= {c}[i]_{| c ∈ C}.}

Lemma 2.26. Let A ∈ GLk(qm). Then (A−1)[1]= (A[1])−1

Proof. Since

A−1A = Ik ⇔ (A−1A)[1]= Ik

⇔ (A−1)[1]A[1] = Ik

⇔ (A−1)[1]= (A[1])−1 the lemma follows.

(31)

CHAPTER 2. THE FIRST FAMILY OF MRD CODES 27 Lemma 2.27. Let v = (v1, . . . , vn) ∈ (Fqm)n and let s be a positive integer

such that gcd(s, m) = 1. If rk_Fqhv1, v2, . . . , vni = r, then v, v

[s]_{, . . . , v}[s(r−1)]

are linearly independent over Fqm.

Proof. Suppose that there exist a0, . . . , ar−1 ∈ Fqm, not all of which are 0,

such that

r−1

X

i=0

aiv[si]= 0.

Hence, v1, . . . , vnare roots of the linearized polynomial a(x) =Pr−1i=0aix[si].

By Remark 2.2, all the elements of the vector space hv1, . . . , vniFqs are roots

of a. By hypothesis, we know that rk_Fqhv1, . . . , vni = r therefore, by Lemma

2.16, we get that rk_F_qshv₁, . . . , vni = r. Thus, a(x) has at least qrs roots in

Fqms therefore its degree is at least qrs which yields a contradiction.

Lemma 2.28. Suppose that W = {w1, . . . , wk} ∈ (Fnqm)k is a set of

vec-tors linearly independent over Fqm. Given a positive integer s such that

gcd(s, m) = 1 then W[s] _{= {w}[s] 1 , . . . , w

[s]

k } ∈ (Fnqm)k is a set of vectors

lin-early independent over Fqm.

Proof. Suppose false the statement. So, there exist λ1, . . . , λk ∈ Fqm, not

all of which are 0, such that

k X i=1 λiwi[s]= 0 ⇔ k X i=1 σ−s(λi)wi [s] = 0 ⇔ k X i=1 σ−s(λi)wi = 0.

Hence, W is not a set of vectors linearly independent over Fqm, which yields

a contradiction.

Lemma 2.29. Let W ⊆ Fnqm be a subspace of dimension k ≤ n and let s

be a positive integer such that gcd(s, m) = 1. If W[s] _{= W then W has}

a generator matrix in Fk×nq . In particular, W contains elements of rank 1

over Fq.

Let {w1, . . . , wk} ⊆ Fnqm be a basis for W where w_i = (w_i,1, w_i,2, . . . , w_i,n)

for i = 1, 2, . . . , k. By Lemma 2.28, we know that {w₁[s], . . . , w[s]_k } ⊆ Fn qm is

a basis for W. Then, there exists A ∈ GLk(qm) such that      σs_(w 1,1) σs(w1,2) . . . σs(w1,n) σs_(w 2,1) σs(w2,2) . . . σs(w2,n) .. . ... . .. ... σs(wk,1) σs(wk,2) . . . σs(wk,n)      = A      w1,1 w1,2 . . . w1,n w2,1 w2,2 . . . w2,n .. . ... . .. ... wk,1 wk,2 . . . wk,n      . (2.9)

The rightmost matrix has rank k so we can assume, without loss of general-ity, that its first k columns are linearly independent. If we denote by W1 the

(32)

CHAPTER 2. THE FIRST FAMILY OF MRD CODES 28 columns are the last n − k of the same matrix we get that W1 is invertible

and therefore that W₁[s] is invertible by Lemma 2.28. From Equation (2.9), we get that A = W₁[s]W₁−1 hence

W₂[s]= W₁[s]W₁−1W2. (2.10)

Applying s times the Frobenius map on both sides of Equation (2.10) and using Lemma 2.26, we get

W₂[2s]= W₁[2s](W₁−1)[s]W₂[s]

= W₁[2s](W₁[s])−1W₁[s]W₁−1W2

= W₁[2s]W₁−1W2.

Thus, it holds that

W₁[2s](W₁−1)[s]W₂[s]= W₁[2s]W₁−1W2.

Moreover, using that W₁[2s] is invertible, we get (W₁−1W2)[s]= W1−1W2.

By Corollary 1.6, W₁−1W2 has only entries in Fq. Using that a generator

matrix for W is [ W1 | W2] and that W1 ∈ GLk(qm), we get that

W₁−1[ W1 | W2] = [ Ik| W1−1W2] ∈ Fk×nq

is a generator matrix for W and its rows have rank weight 1 over Fq.

Proposition 2.30. Suppose that C ⊆ Fnqm is a linear code of dimension

k ≥ 2 and minimum rank distance d at least k. Let s be a positive integer such that gcd(s, m) = 1. If dim(C ∩ C[s]) = k − 1 (this automatically implies that k < n) then there exists a generator matrix for C of the form

¯ G =      g1 g2 . . . gn σs(g1) σs(g2) . . . σs(gn) .. . ... . .. ... σs(k−1)(g1) σs(k−1)(g2) . . . σs(k−1)(gn)      with g1, g2, . . . , gn∈ Fqm.

Proof. By induction on k. If k = 2 then dim(C ∩ C[s]) = 1 hence there exists c ∈ C such that hci_F_qm = C ∩ C[s]. Since c ∈ C[s] then c[−s] ∈ C therefore rk_F_q(c[−s]_{) ≥ 2 because d ≥ k = 2 so, by Lemma 2.27, we get that c and c}[−s]

(33)

CHAPTER 2. THE FIRST FAMILY OF MRD CODES 29 are linearly independent over Fqm hence C = hc, c[−s]i

Fqm and a generator matrix of C is ¯ G =c [−s] c .

Assuming the Proposition proven for k we want to prove it for k + 1. We define W := C ∩ C[s] and we recall that d ≥ k ≥ 2. We get, by Proposition 2.29, that W[s] 6= W because the minimum rank distance of W is at least 2 since W ⊆ C. Moreover, C[s]= hW, W[s]i_F_qm because W, W[s]⊆ C[s] _both

with codimension 1. Hence, we can apply the inductive hypothesis to W and we get that there exists w ∈ W such that

W = hw, w[s], . . . , w[s(k−2)]i_F_qm.

Since W ⊆ C we get that W[s] ⊆ C[s] _{thus {w}[s]_{, w}[2s]_{, . . . , w}[s(k−1)]_{} ∈ C}[s]_.

Furthermore, w ∈ W ⊆ C[s] therefore {w, w[s], . . . , w[s(k−1)]} ∈ C[s] _{and this}

set is a basis for C[s] by Lemma 2.27. Thus, the inductive step is proven because {w[−s], w, . . . , w[s(k−2)]} is a basis for C.

Lemma 2.31. Let s be a positive integer such that gcd(s, m) = 1 and let C be a linear MRD code of dimension k < n with generator matrix

¯ G =      g1 g2 . . . gn σs(g1) σs(g2) . . . σs(gn) .. . ... . .. ... σs(k−1)_(g 1) σs(k−1)(g2) . . . σs(k−1)(gn)      .

Then, g1, . . . , gn are linearly independent over Fq.

Proof. If g1, . . . , gnare linearly dependent over Fq then there exists a vector

a = (a1, . . . , an) ∈ Fnq such that n

X

i=1

aigi= 0.

Therefore, it holds that

n

X

i=1

aiσj(gi) = 0 if j ∈ N.

Hence, given a matrix A ∈ GLn(q) whose first column is a, we get that the

first column of ¯GA is 0 that implies, by Theorem 2.24, that C is not an MRD code which yields a contradiction.

Theorem 2.32. Let C ⊆ Fn

qm be a linear MRD code of dimension k < n and

let s be a positive integer such that gcd(s, m) = 1. Then, dim(C ∩C[s]) = k−1 if and only if C is a generalized Gabidulin code.

(34)

CHAPTER 2. THE FIRST FAMILY OF MRD CODES 30 Proof. Suppose that C is a generalized Gabidulin code. Thus, there exists a support g such that C = Gk,s(g). Using the structure of the generator

matrix of C we immediately get that dim(C ∩ C[s]) = k − 1 and it proves the first direction.

We distinguish two cases to prove the other direction.

(a) k ≤ n+1₂ . Denoted by d the minimum distance of C, we get that d = n − k + 1 ≥ n − n + 1

2 + 1 = n + 1

2 ≥ k.

Hence d ≥ k and, from Proposition 2.30, we get that C has a generator matrix of the form

¯ G =      g1 g2 . . . gn σs(g1) σs(g2) . . . σs(gn) .. . ... . .. ... σs(k−1)(g1) σs(k−1)(g2) . . . σs(k−1)(gn)      .

Using Lemma 2.31, we get that g1, . . . , gn are linearly independent

over Fq and the statement follows.

(b) k > n+1₂ . We denote by C⊥ _{⊆ F}n

qm the dual code of C and by d⊥

its minimum distance. We get that its dimension is n − k and that d⊥ = k + 1 because it is MRD by Theorem 1.60. By hypothesis, it holds that k +1 > n−k hence we can use Proposition 2.30 and Lemma 2.31 to prove that C⊥is a generalized Gabidulin code. The statement follows by Proposition 2.13.

Using Lemma 2.23 we can rewrite the criterion from Theorem 2.32. Lemma 2.33. Let C ⊆ Fnqm be an MRD code of dimension k and let G be

its generator matrix in systematic form i.e. G = [ Ik | X ].

If s is a positive integer such that gcd(s, m) = 1 then C is a generalized Gabidulin code with parameter s if and only if rank(X[s]_{− X) = 1.}

Proof. By Theorem 2.32, C is a generalized Gabidulin code with parameter s if and only if dim(C ∩ C[s]) = k − 1. Hence

dim(C ∩ C[s]) = k − 1 ⇔ rank Ik X Ik X[s] = k + 1 ⇔ rank Ik X 0 X[s]− X = k + 1 ⇔ rank(X[s]_{− X) = 1.}

(35)

CHAPTER 2. THE FIRST FAMILY OF MRD CODES 31

2.2.3 Classes of parameters such that any linear MRD code is a Gabidulin code

In this subsection we show that there exist classes of parameters such that any linear MRD code with these parameters is a Gabidulin code.

Theorem 2.34. All linear MRD codes in Fnqm of dimension k = n − 1 or

k = 1 are Gabidulin codes.

Proof. Let C ⊆ Fnqm be a linear MRD code of dimension 1 with generator

matrix

G = (g1, . . . , gn).

Since C is MRD, its minimum rank distance is n therefore g1, . . . , gnare

lin-early independent over Fqand hence C is the Gabidulin code G1(g1, . . . , gn).

Using Theorem 2.18, the statement is proven also for MRD codes of dimen-sion n − 1.

Corollary 2.35. Let 1 ≤ n ≤ 3. Then C ⊆ Fnqm is a linear MRD code if

and only if C is a Gabidulin code.

Proof. It immediately follows from Theorem 2.34.

Using Lemma 2.33 we can prove that there is an other class of parameters such that any linear MRD code with these parameters is a Gabidulin code. Proposition 2.36. Let C ⊆ F4₂4 be a linear MRD code. Then C is a

Gabi-dulin code.

Proof. Let k be the dimension of C. If k = 1 or k = 3 we get, by Theorem 2.34, that the statement is true. If k = 2 we know, by Lemma 2.23, that C has a generator matrix of the form

G =1 0 a b

0 1 c d

for some a, b, c, d ∈ F24\F₂.

Let A ∈ GLn(q) be an invertible matrix. Since C is MRD we know,

by Theorem 2.24, that every maximal minor of GA is non-zero. Thus, the matrix G     1 e1 e2 e3 0 1 e4 e5 0 0 1 e6 0 0 0 1     =1 e1 e2+ a e3+ ae6+ b 0 1 e4+ c e5+ ce6+ d

has only non-zero maximal minors for any e1, . . . , e6 ∈ F2. Hence we get

Twisted Gabidulin codes and new Maximum Rank Distance codes

Contents

Introduction

Chapter 1

Preliminaries

1.1

Basics of finite fields

1.2

An introduction to Coding theory

1.3

Rank-metric codes

Chapter 2

The first family of MRD

codes

2.1

Generalized Gabidulin codes

2.2

New criteria for rank-metric codes