arXiv CSopen access

New perspectives for code locality in the rank metric

New perspectives for code locality in the rank metric Camille Garnier1*, Julien Lavauzelle2*, Jade Nardi3* and Ilaria Zappatore1* 1

XLIM, CNRS UMR 7252, Université de Limoges, 123, avenue Albert Thomas, Limoges, 87060, France. 2 LAGA, CNRS UMR 7539, Université Paris 8, 2 Rue de la Liberté, Saint-Denis, 93200, France. 3 CNRS, IRMAR UMR 6625, Univ Rennes, F-35000 Rennes, France.

arXiv:2607.24295v1 [cs.IT] 27 Jul 2026

*Corresponding author(s). E-mail(s): [email protected]; [email protected]; [email protected]; [email protected]; Abstract In coding theory, local recovery enables the efficient recovery of some part of (lost) coded data by accessing only a small number of other data entries. Locality was mostly but intensively studied for the recovery of individual symbols, that is, in the context of the Hamming metric. In this work, we propose a new definition of locality for general rank-metric codes. This definition differs from a previous work of Kadhe, El Rouayheb, Duursma and Sprintson [IEEE Trans. Inf. Theory 2019], by allowing to efficiently recover any element of the support, and without relying on any choice of bases of the underlying vector spaces. Our work firstly relies on a precise study of code puncturing and shortening for codes viewed as spaces of linear maps. We then provide examples and general constructions, showing the difference between our notion and that of Kadhe et al. We then derive a Singleton-like bound for rank locally recoverable codes, and we finally prove that a construction similar to classical Tamo–Barg codes is optimal with respect to this bound. Keywords: coding theory, local recovery, rank-metric codes, Ore polynomials

1 Introduction Locally recoverable codes (LRCs) are error-correcting codes in which each codeword symbol can be recovered by accessing only a small subset of the remaining symbols. The property of local recoverability makes these codes well suited to distributed storage systems (DSSs). When a storage node becomes unavailable, it can be repaired by accessing only a limited number of other nodes, reducing the repair cost. The ideas underlying LRCs originate from [13] and [15], which introduced the principle of reducing the amount of information accessed during data recovery. LRCs were first systematically studied by Gopalan et al. [11]. They established a bound relating the code parameters (length, dimension and minimum distance) to its locality, i.e., the number of other coordinates that must be accessed to recover a given one. Families of codes achieving this bound are given in [15, 32], and further constructions appear in [1, 2, 14, 17, 21, 29, 33]. Note that the term “locally repairable codes” is also commonly used in the literature. In some works, it is used as a synonym for locally recoverable codes (e.g., [17, 24, 34]), whereas in others it is considered as a more general notion (e.g., [25, 27]). All the aforementioned works study local recoverability in the Hamming metric. However, the Hamming metric does not adequately model all types of errors encountered in communication and storage systems. For instance, in network coding, space-time coding, and cryptography, errors may affect entire subspaces rather than individual coordinates. Such errors can simultaneously corrupt many coordinates, and a repair scheme based on Hamming-style locality may require access to more

1

information than necessary to characterize the error. The rank metric provides a more suitable model in these scenarios; see [4] for a survey of its applications. Rank-metric codes are typically considered in two equivalent representations. A matrix rankmetric code, or matrix-code, consists of codewords that are matrices over a finite field, with the rank-metric defined as the rank of the difference between two codewords. A vector rank-metric code, or vector-code, is defined over an extension field and endowed with the rank-metric over the base field. After fixing a basis of the extension field over the base field, each coordinate of a codeword can be expanded with respect to this basis. Consequently, every codeword is represented by a matrix whose columns correspond to the coordinates of the original vector. Several works have studied locality in connection with the rank metric. In [31] and [30], rank-metric codes are used as building blocks for the construction of codes with locality properties for DSSs. However, the resulting notion of local recoverability used in these works is a straightforward translation of the classical Hamming locality. A different approach is taken in [18], where locality is formulated for matrix codes. In this framework, a column is locally recoverable if it can be reconstructed by accessing only a small number of other columns. With this point of view, [18] provides a Singleton-like upper bound on the minimum rank distance of rank-LRCs and an optimal construction. More recently, Bastioni et al. [5] proposed new optimal constructions using Drinfeld modules. In this work we introduce a new notion of local recoverability, that is more intrinsic to the rank metric. To establish the analogy, the classical notion of LRCs in the Hamming metric is first recalled. Consider a code C ⊆ Fnq in the Hamming metric. A coordinate i ∈ {1, . . . , n} has locality r ⩾ 1 in C if there exists a subset Ri ⊆ {1, . . . , n}\{i} of size at most r (called helper set) such that the punctured codes C|Ri and C|Ri ∪{i} have the same dimension. This implies that the ith coordinate of any codeword can be recovered via linear operations from the values of the r other coordinates in Ri . A code C ⊆ Fnq is said to be r-locally recoverable if each coordinate i ∈ {1, . . . , n} has locality r in C . In the Hamming metric, the support of a codeword is its set of nonzero coordinates, and its weight is the size of this support. For vector codes, the (column) support of a codeword is the subspace over the base field spanned by its coordinates, and its rank weight is the dimension of this subspace. In the corresponding matrix representation of the code, this support can be identified with the column space of the associated matrix. Since local recoverability is closely related to the notion of support, we propose a new formulation in rank metric that reflects the different nature of the rank support compared to the Hamming one. We therefore define locality at the level of subspaces rather than coordinates/columns. To avoid dependence on the choice of bases, codewords are regarded as linear maps f : U → V between finite-dimensional vector spaces U and V . In this framework, a rank-metric code is a subspace of Hom(U, V ). Roughly speaking, a vector u ∈ U is said to have locality r in a code C ⊆ Hom(U, V ) if, for every f ∈ C , the value f (u) can be recovered from f (S ) alone, where S is an r-dimensional subspace of U that does not contain u. The code C is r-rank locally recoverable if every vector u ∈ U has locality r in C (see Definition 4.26 for more details). This definition matches the nature of supports in the rank metric: a code is rank-locally recoverable with locality r if every element of a codeword’s support can be recovered from a “piece” of that support of size r. It also fits naturally the notion of rank puncturing introduced in [8], which is used to formally define local recoverability as in the Hamming case.

Our contributions The contribution of this paper is threefold. First, we develop a general framework for rank-metric codes whose codewords are linear maps between finite-dimensional vector spaces. In this framework, we reformulate the notions of puncturing and shortening previously introduced for matrix codes in [8] and [7] and for vector codes in [22]. This formulation avoids any dependence on the choice of bases and allows us to treat matrix codes and vector codes in a unified way. Second, we introduce a new notion of local recoverability for rank-metric codes. Rather than defining locality on coordinates, as in the Hamming metric, we define it for every nonzero vector in the domain of the code. As explained above, this definition is coordinate-free, and it is consistent with both the subspace nature of rank-support and the notion of rank puncturing. We characterize locality in terms of the dual code and extend the classical notion of an information set to the rank-metric setting through the notion of information space. Third, we prove a Singleton-like bound for Fq -linear rank-metric codes with locality. We provide constructions of rank locally recoverable codes achieving the bound and show that our construction recovers [4, Construction 1] as a particular case. 2

2 Preliminaries Let q be a prime power, Fq be a finite field of order q and Fqm be the extension field of Fq of degree m. In this paper, vectors over the extension field Fqm are represented by lowercase bold letters: x, y . Matrices are represented by uppercase letters M, G, H . We also denote the space of m × n matrices over a field F as Fm×n . For a positive integer n, the set {1, . . . , n} is denoted by [n]. Let U and V be Fq -vector spaces of dimension n and m. Throughout this paper, we fix bases BU = (u1 , . . . , un ) and BV = (v1 , . . . , vm ) of U and V , respectively. We endow U and V with the unique (nondegenerate) symmetric bilinear forms βU and βV for which BU and BV are orthonormal, i.e., βU (ui , uj ) = δi,j and βV (vℓ , vk ) = δℓ,k , i, j ∈ [n], k, ℓ ∈ [m]. These are the standard inner products on U and V with respect to the chosen bases. They are nondegenerate, i.e., any nonzero u ∈ U (resp. v ∈ V ) gives rise to a nonzero map βU (u, −) (resp. βV (v, −)). However they may (and here will) be nondefinite, i.e., there may exist a nonzero u ∈ U (resp. v ∈ V ) such that βU (u, u) = 0 (resp. βV (v, v ) = 0). We denote by Hom(U, V ) the space of Fq -linear maps from U to V . If U = V , the associated algebra is denoted by End(U ). We also denote by GL(U ) and GLn (Fq ) the group of inversible endomorphisms over U and over Fnq , respectively.

2.1 Adjoint of a homomorphism In this section, we recall some classical notions of linear algebra that we will use throughout this paper. Most of the results of this section are taken from [28]. Definition 2.1 (Adjoint of a linear map) Let f ∈ Hom(U, V ). The adjoint of f is the map f † ∈ Hom(V, U ) such that βV (f (u), v) = βU (u, f † (v)), ∀u ∈ U, ∀v ∈ V.

The image and the kernel of a linear map and its adjoint are related via the orthogonal complement operation. Definition 2.2 (Orthogonal complement) Let W ⊆ U . The orthogonal complement of W in U is def

W ⊥ = {u ∈ U | βU (u, w) = 0, ∀w ∈ W }.

The following results follow from the correspondence between the dual and the adjoint maps (see [28, §10]) and properties of the dual map (namely [28, Theorems 3.20 and 3.22]). Theorem 2.3 Let f ∈ Hom(U, V ). Then, • ker(f † ) = im(f )⊥ , • im(f † ) = ker(f )⊥ , • rk(f † ) = rk(f ), • f is surjective if and only if f † is injective (and vice versa).

The following lemma relates the matrix representations of a linear map and its adjoint. Lemma 2.4 Let BU , BV be two orthonormal bases of U and V . For every f ∈ Hom(U, V ), we have MatBV ,BU (f † ) = MatBU ,BV (f )⊤ .

2.2 Rank-metric codes In this section, we recall basic definitions and results on rank-metric codes. We first introduce rankmetric codes as spaces of Hom(U, V ). This viewpoint provides a unified framework, from which the classical matrix and vector representations of rank-metric codes, commonly used in rank-metric literature, can be recovered. We then introduce support spaces related to a linear map, defined in terms of the image and the kernel of the adjoint of a linear map. This will allow us to recover the classical notions of row and column support in the matrix setting. 3

2.2.1 Representations of rank-metric codes In this section, we briefly recall the basic notions of rank metric, rank-metric codes in their different representations, as well as code equivalence and duality.

Rank-metric codes with homomorphisms Given f, g ∈ Hom(U, V ), the rank distance between f and g is def

dR (f, g ) = rk(f − g ). This function defines a metric on Hom(U, V ). The rank weight of f ∈ Hom(U, V ) is defined as def

wR (f ) = dR (f, 0) = rk(f ). Definition 2.5 (Rank-metric codes) A rank-metric code C is an Fq -linear subspace of Hom(U, V ) endowed with the rank metric. The dimension of this code is its dimension as an Fq -vector space. Its minimum rank distance (shortly minimum distance) is def

dR (C) =

min

f ∈C\{0}

wR (f ).

The notion of equivalence of rank-metric codes is defined in terms of Fq -linear isometry, which we now recall. Definition 2.6 (Fq -linear isometry) An Fq -linear isometry φ between Hom(U, V ) and Hom(U ′ , V ′ ) is an Fq linear homomorphism φ : Hom(U, V ) → Hom(U ′ , V ′ ) such that wR (φ(f )) = wR (f ) for every f ∈ Hom(U, V ). Definition 2.7 (Equivalent rank-metric codes) Two rank-metric codes C ⊆ Hom(U, V ) and D ⊆ Hom(U ′ , V ′ ) are equivalent if there exists an Fq -linear isometry φ such that φ(C) = D. Remark 2.8 We recall that every Fq -linear isometry is induced by compositions with invertible linear maps acting on the domain and the codomain [20, Proposition III.15]. In particular, if dimFq (U ) ̸= dimFq (V ), then every Fq -linear isometry φ is of the form φ(f ) = β ◦ f ◦ α, (1) for some invertible maps α ∈ Hom(U ′ , U ) and β ∈ Hom(V, V ′ ). Note that if dimFq (U ) = dimFq (V ), then isometries of the form φ(f ) = α ◦ f † ◦ β must also be considered.

If two rank-metric codes C ⊆ Hom(U, V ) and D ⊆ Hom(U ′ , V ′ ) are such that φ(C ) = D for Fq -linear isometries φ of the form (1), we say they are left-right-equivalent.

Duality We now observe that the bilinear forms on U and V defined in the previous section allow us to define the following nondegenerate symmetric bilinear form on Hom(U, V ), def

βHom(U,V ) (f, g ) = Tr(f ◦ g † ),

∀f, g ∈ Hom(U, V ),

where Tr denotes the usual trace map of the endomorphism f ◦ g † ∈ End(V ). We can now define the notion of duality of rank-metric codes. Definition 2.9 (Dual code) Let C ⊆ Hom(U, V ) be a rank-metric code. The dual code of C is defined as C ⊥ = {h ∈ Hom(U, V ) | Tr(h ◦ f † ) = 0, ∀f ∈ C}.

4

Matrix rank-metric codes Fix a basis BU = (u1 , . . . , un ) of U and a basis BV = (v1 , . . . , vm ) of V , then every map f ∈ Hom(U, V ) can be represented by a matrix MatBU ,BV (f ) ∈ Fm×n . Indeed for each basis vector uj , we can write q f (uj ) =

m X

ai,j vi ,

i=1

and the matrix associated to f is MatBU ,BV (f ) = (ai,j ) ∈ Fm×n . This correspondence defines an Fq q isomorphism between Hom(U, V ) and Fm×n . Under this isomorphism, the rank of f ∈ Hom(U, V ) q coincides with the rank of the matrix MatBU ,BV (f ), independently of the choice of bases BU and BV . This allows us to identify Hom(U, V ) with Fm×n equipped with the rank metric. Rank-metric codes q then correspond to matrix rank-metric codes (shortly matrix codes ), i.e., linear subspaces of Fm×n q endowed with the rank metric, as introduced by Delsarte [9]. Remark 2.10 Let f, g ∈ Hom(U, V ) and let F = MatBU ,BV (f ) and G = MatBU ,BV (g) the corresponding matrices. Since the bases BU and BV are orthonormal, Lemma 2.4 implies βHom(U,V ) (f, g) = Tr(F G⊤ ).

(2)

Therefore, the dual code previously defined corresponds to the classical Delsarte dual code for rank-metric codes, i.e., C ⊥ = {H ∈ Fm×n | Tr(HF ⊤ ) = 0, ∀F ∈ C}. (3) q

Vector rank-metric codes The set Fnqm of vectors with entries in the extension field Fqm can also be endowed with the rank metric. Given a basis Γ = (γ1 , . . . , γm ) of Fqm over Fq and a vector x = (x1 , . . . , xn ) ∈ Fnqm , we denote by Γ(x) ∈ Fm×n the matrix whose i-th column is the coordinate vector of xi with respect to Γ. In q this setting, the rank weight of a vector c = (c1 , . . . , cn ) ∈ Fnqm is defined equivalently as def

wR (c) = dimFq (⟨c1 , . . . , cn ⟩Fq ) = rk(Γ(c)). Therefore, every Fq -linear subspace C of Fnqm corresponds, via the basis Γ, to a matrix rank-metric code in Fm×n , that we denote by Γ(C ). We can make these codes fit within the language of morphisms q by associating to each codeword c = (c1 , . . . , cn ) ∈ Fnqm a morphism fc ∈ Hom(U, Fqm ) defined by fc (ui ) = ci . In the literature, there is a particular interest on subspaces of Fnqm that are not only Fq -linear but also Fqm -linear. More precisely, according to [10], we consider vector rank-metric code defined as follows. Definition 2.11 An Fqm -vector rank-metric code C is an Fqm -linear subspace of Fn q m endowed with the rank distance. Its dimension k is dimFqm (C) and its minimum rank distance is defined as def

dR (C) =

min c∈C\{0}

wR (c).

A vector rank-metric code of dimension k and minimum rank-distance d is called an [n, k, d]qm vector rankmetric code (shortly vector code).

The next proposition clarifies the correspondence between Fqm -vector codes and matrix codes. Proposition 2.12 [12, Proposition 1.5] If C ⊆ Fn q m is a vector rank-metric code of dimension k over Fq m and Γ is an Fq -basis of Fqm , then Γ(C) is an Fq -linear rank-metric code of dimension mk over Fq .

Therefore an [n, k, d]qm vector rank-metric code gives rise to an [m×n, mk, d]q matrix rank-metric code.

5

Remark 2.13 Despite the correspondence described above, some caution is required regarding the duals of these codes [12]. The dual of an Fqm -vector rank-metric code C (with respect to the standard inner product of Fn q m ) is thus defined as ) ( n def X ⊥ n xi ci = 0, ∀c = (c1 , . . . , cn ) ∈ C . (4) C = x = (x1 , . . . , xn ) ∈ Fqm ⟨x, c⟩ = i=1 ⊥

In general, the matrix code associated to C (with respect to the bilinear form on Fn q m defined above) via the basis Γ does not coincide with the dual of the matrix code Γ, i.e., Γ(C ⊥ ) ̸= Γ(C)⊥ . However, Ravagnani [26, Theorem 21] proved that Γ(C ⊥ ) = Γ′ (C)⊥ ′ if Γ = (γ1 , . . . , γm ) and Γ′ = (γ1′ , . . . , γm ) are orthonormal bases of Fqm with respect to the trace bilinear form

Fqm × Fqm → Fq (x, y) 7→ Trqm /q (xy), that is Trqm /q (γi γj′ ) = δi,j for i, j ∈ [m]. Here, Trqm /q : Fqm → Fq denotes the trace map of the field extension Fqm /Fq .

2.2.2 Supports As in the Hamming metric, the notion of support of a code plays a fundamental role in the study of rank-metric codes. In particular, support spaces will be one of the main tools in our study of locality. In this section we define the column and row support for linear maps in Hom(U, V ). These notions rely on the definitions of adjoint maps recalled in Section 2.1, generalizing the notions of column and row support of a matrix code. Definition 2.14 (Column support) The column support of f ∈ Hom(U, V ) is the image of f : def

colsupp(f ) = im(f ) ⊆ V.

As expected, the dimension of the column support of f is the rank of f , that is wR (f ). The notion of row support of a linear map is defined by the image of its adjoint map. By Theorem 2.3, it can equivalently be described in terms of the orthogonal complement of its kernel. Definition 2.15 (Row support) If f ∈ Hom(U, V ), the row support of f is the image of f † , that is def

rowsupp(f ) = im(f † ) = ker(f )⊥ .

Since rk(f † ) = rk(f ), the dimension of the row support of f is the rank of f . def

Remark 2.16 (Row and column supports of matrices) Let f ∈ Hom(U, V ) and let F = MatBU ,BV (f ) be its matrix representation. Then the column and row supports correspond to the classical column and row supports of F . Indeed, the column support of f is generated by vectors f (u1 ), . . . , f (un ), whose coordinates with respect to BV are the columns of F . By Lemma 2.4, the matrix of f † with respect to the dual basis is F ⊤ . Therefore, the row support of f is generated by columns of F ⊤ , i.e., by the rows of F .

We observe that, differently from the row and column supports of a matrix codeword, which depend on a choice of basis BU and BV , the row and column supports of a linear map are intrinsically defined. Therefore, they are invariant under changes of bases of U and V . The following lemma describes the behaviour of the row support (respectively the column support) under composition of linear maps. Lemma 2.17 For every f ∈ Hom(U, V ), for every g ∈ Hom(S, U ), we have • colsupp(f ◦ g) ⊆ colsupp(f ) with equality if g is surjective, • rowsupp(f ◦ g) ⊆ rowsupp(g) with equality if f is injective.

6

Proof We have im(f ◦ g) ⊆ im(f ), and rowsupp(f ◦ g) = im((f ◦ g)† ) = im(g † ◦ f † ) ⊆ im(g † ) = rowsupp(g). If g is surjective, im(f ◦ g) = f (im(g)) = f (U ) = im(f ). If f is injective, then f † is surjective (by Theorem 2.3), and rowsupp(f ◦ g) = im(g † ◦ f † ) = im(g † ). □

As in the Hamming metric, the support of a code is obtained by combining the supports of its codewords. This leads to the following notions of row and column supports for rank-metric codes. Definition 2.18 The support of a code C ⊆ Hom(U, V ) is the sum of the supports of its codewords: def X def X rowsupp(C) = rowsupp(f ) and colsupp(C) = colsupp(f ). f ∈C

f ∈C

If rowsupp(C) ̸= U (resp. colsupp(C) ̸= V ), we say that C is row-degenerated (resp. column-degenerated ). The code C is nondegenerate if rowsupp(C) = U and colsupp(C) = V .

From now on, we only consider nondegenerate codes.

3 Puncturing and shortening In this section we reformulate the notions of puncturing and shortening of rank-metric codes, originally introduced for matrix codes (see [6–8]) to rank-metric codes in Hom(U, V ). Finally, we present some basic properties, that will be used throughout the paper.

3.1 Codes in Hom(U, V ) Given S an Fq -vector space and a map g ∈ Hom(S, U ), we define

πg : Hom(U, V ) → Hom(S, V ) f 7→ f ◦ g Definition 3.1 (Rank puncturing) Let C ⊆ Hom(U, V ) be a rank-metric code. Let S be an Fq -vector space of dimension s ⩽ n. Fix g an injective map in Hom(S, U ). The puncturing of C with respect to g is the set def

πg (C) = {f ◦ g | f ∈ C} ⊆ Hom(S, V ).

Throughout this paper, we will focus on a particular class of puncturing, i.e., the ones defined by canonical inclusions. Notation 3.2 If S is a subspace of U , we use the notation πS to denote the puncturing map πιS , where ιS ∈ Hom(S, U ) is the canonical injective map. In this case, given f ∈ Hom(U, V ), πS (f ) is nothing but the restriction f|S .

The following remark shows that restricting to canonical inclusions is not a loss of generality up to code equivalence. Remark 3.3 Let C ⊆ Hom(U, V ), and g ∈ Hom(S, U ) be an injective map. Up to equivalence, the code def

puncturing πg (C) only depends on C and im(g). More precisely, if we denote T = im(g) ⊆ U , then πg (C) and πT (C) are equivalent rank-metric codes. Indeed, πg (C) = {f ◦ g | f ∈ C} = {f ◦ ιT ◦ ψ | f ∈ C} = πT (C) ◦ ψ where ψ : S → T is an isomorphism such that g = ιT ◦ ψ. Definition 3.4 (Rank shortening) Let C ⊆ Hom(U, V ) be a rank-metric code. Let S be an Fq -vector space of dimension s ⩽ n and g ∈ Hom(S, U ) be an injective map. Let S ′ be a subspace of U of dimension n − s such that im(g) ⊕ S ′ = U . The (domain) shortening of C with respect to g and S ′ is the subspace of Hom(S, V ) defined as def Short(C, g, S ′ ) = {f ◦ g | f ∈ C, f|S ′ = 0} = πg (ker(πS ′ ) ∩ C).

7

Remark 3.5 Puncturing and shortening have already been defined in the literature, both for matrix codes and for vector codes [6, 8, 22]. We now compare our definitions of puncturing and shortening mainly with the recent formulation of [6], which is stated in the setting of matrix codes. For this comparison, we translate our definitions into the language of matrices. Let g ∈ Hom(S, U ) be an injective map as in Definition 3.1 and let def

B = MatBS ,BU (g) ∈ Fn×s be its matrix representation, where s = dimFq S and BS is a basis of S. Since g q is injective, B has full rank. In matrix representation, πg (C) = πB (C) = {M B | M ∈ C}. Up to transposition, this coincides with the puncturing of [8], or with the right puncturing of [6]. Let now S ′ n×(n−s) be a subspace as in Definition 3.4, so that im(g) ⊕ S ′ = U . Choose a basis BS ′ of S ′ , and let B ′ ∈ Fq be the matrix whose j-th column is the coordinate vector of the j-th element of the basis BS ′ , with respect to BU . The assumption im(g) ⊕ S ′ = U is equivalent to the matrix (B | B ′ ) ∈ Fn×n being invertible. Therefore, q in matrix representation, Short(C, g, S ′ ) = Short(C, B, B ′ ) = {M B | M ∈ C, M B ′ = 0}. Again, up to transposition, this is the same matrix operation as the shortening of [8], and it corresponds to the right shortening of [6].

The following lemma introduces some useful properties of puncturing and shortening. In particular, it describes how these operations affect the column and row supports, the minimum distance and the dimension of the code. Lemma 3.6 Let C ⊆ Hom(U, V ) be a rank-metric code. Let g ∈ Hom(S, U ) be an injective map. Then the following properties hold. (i) colsupp(πg (C)) ⊆ colsupp(C) and rowsupp(πg (C)) ⊆ rowsupp(g); (ii) if dim(S) + dR (C) > n, then dR (πg (C)) ⩽ dR (C). (iii) If πg (C) ̸= 0, then dR (C) − (n − dimFq S) ⩽ dR (πg (C)) ⩽ dimFq S. Let S ′ ⊆ U be a subspace such that im(g) ⊕ S ′ = U . Let T be an Fq -vector space and h ∈ Hom(T, U ) be any injective map with im(h) = S ′ . Then, (iv) dimFq (πg (C)) + dimFq (Short(C, h, im(g))) = dimFq (C); (v) if Short(C, g, S ′ ) ̸= 0, then dR (Short(C, g, S ′ )) ⩾ dR (C).

Proof (i) follows from Lemma 2.17. If f ◦ g ̸= 0 for every nonzero f ∈ C, then Lemma 2.17 implies that dR (πg (C)) ⩽ dR (C). But f ◦ g = 0 if and only if im(g) ⊆ ker(f ), which implies that dim(S) ⩽ n − wR (f ) ⩽ n − dR (C). We thus proved (ii) by contraposition. Now, let us prove (iii). First, the upper bound dR (πg (C)) ⩽ dimFq S follows directly from Lemma 2.17 and from the injectivity of g. We now show the lower bound. Let f ◦ g be a nonzero codeword of πg (C), then f ̸= 0 and so, wR (f ) ⩾ dR (C). We recall that if we restrict a linear map to a subspace of the domain, its rank decreases by at most the codimension of that subspace. Thus, since im(f ◦ g) = f (im(g)), we get dimFq (f (im(g))) ⩾ wR (f ) − (n − dimFq (im(g))). So, we have wR (f ◦ g) ⩾ wR (f ) − (n − dimFq S) for every nonzero codeword f and we get the desired inequality. Let us prove (iv). By the rank-nullity theorem, we have dim(C) = dimFq (πg (C)) + dimFq (ker(πg ) ∩ C) . Now notice that for any f ∈ Hom(U, V ), if f ◦ g = 0 and f|S ′ = 0, then f = 0, since im(g) ⊕ S ′ = U . Hence, dimFq (ker(πg ) ∩ C) = dimFq (πh (ker(πg ) ∩ C)) leading to the desired result since Short(C, h, im(g)) = πh (ker(πim(g) ) ∩ C) by definition. Now, it remains to prove (v). Let 0 ̸= φ ∈ Short(C, g, S ′ ). By definition, there exists f ∈ C such that f|S ′ = 0 and φ = f ◦ g. Since im(g) ⊕ S ′ = U and f vanishes on S ′ , then im(f ) = f (im(g)). Now, since f (im(g)) = im(f ◦ g), we have im(f ) = im(f ◦ g) = im(φ) and so wR (φ) = wR (f ). Since φ ̸= 0, also f ̸= 0 and wR (f ) ⩾ dR (C), which proves the result. □

The minimum distance of a rank-metric code can also be related to the dimension of spaces along which puncturings do not make the code smaller. Proposition 3.7 [7, Proposition 7.2] Let C ⊆ Hom(U, V ) of dimension k and minimum rank distance dR (C). For any 2 ⩽ d ⩽ min(m, n), the following statements are equivalent.

8

1. dR (C) ⩾ d; 2. for every Fq -vector space S of dimension s ⩾ n − d + 1, and every injective map g ∈ Hom(S, U ), the punctured code πg (C) has dimension k.

A correspondence between code puncturing and shortening, well known in the Hamming metric [16, Theorem 1.5.7], was also proved in the context of rank-metrix matrix codes ( [8, Theorem 3.5] or [6, Theorem 2.6]). We reformulate these results in the context of linear maps. Proposition 3.8 Let S be an Fq -vector space and let C ⊆ Hom(U, V ) be a rank-metric code. Let g ∈ Hom(S, U ) be an injective map. Let ge ∈ Hom(S, U ) be a map and let Se′ be a subspace of U such that dimFq Se′ = dimFq U − dimFq S. Assume that, ( † g ◦ ge = idS , (5) g †f′ = 0 |S

Then,

πg (C)⊥ = Short(C ⊥ , ge, Se′ ).

Proof By [6, Theorem 2.6] (applied to the transposed code), we have n o πg (C)⊥ = ϕ ◦ ge | ϕ ∈ C ⊥ , rowsupp(ϕ) ⊆ colsupp(g) . By Theorem 2.3, this reformulates as follows. n o πg (C)⊥ = ϕ ◦ ge | ϕ ∈ C ⊥ , im(g)⊥ ⊆ ker(ϕ) . We just have to check that Se′ = ker(g † ) = im(g)⊥ . We first observe that g † is surjective. By the ranknullity theorem, dim ker(g † ) = dim U − dim S. Since, g †f′ = 0, we have Se′ ⊆ ker(g † ). Now, since dimFq Se′ = |S

dimFq U − dimFq S, we get the desired equality.

□

Remark 3.9 Proposition 3.8 is a reformulation, in the language of morphisms, of [6, Theorem 2.6]. We observe that this result is slightly more general than [8, Theorem 3.5]. Indeed, the duality statement of [8, Theorem 3.5] relates the puncturing defined by an invertible matrix A to the shortening defined by (A⊤ )−1 . Informally speaking, this inverse transpose appears because the shortening on the dual side has to be defined with respect to the data dual to those used for puncturing. In our setting, these data are encoded by the adjoint of the puncturing map. More precisely, if B is the matrix of the puncturing map g (see Remark 3.5), then the conditions in (5) become e = Ir e ′ = 0, B⊤B and B⊤B e is the matrix of ge, and the columns of B e ′ span the subspace Se′ . Thus, the matrix (A⊤ )−1 in [8, where B e and B e ′ satisfying these two relations. Theorem 3.5] gives one particular way of producing matrices B

We conclude this section by showing that the matrix interpretation of the definitions of puncturing and shortening (see Remark 3.5) behave well under the usual passage from vector-codes in Fqm to matrix-codes in Fq . n×(n−s)

n×s Lemma 3.10 Let C ⊆ Fn , and for every B ′ ∈ Fq q m . Let Γ be a Fq -basis of Fq m . For every B ∈ Fq ′ such that (B|B ) is invertible, we have

Γ(πB (C)) = πB (Γ(C)), and

Γ(Short(C, B, B ′ )) = Short(Γ(C), B, B ′ ).

Proof Write B = (b1 | · · · | bs ). For every c ∈ C, we have Γ(cB) = (Γ(⟨c, b1 ⟩), . . . , Γ(⟨c, bs ⟩)) = (Γ(c) · b1 , . . . , Γ(c) · bs ) = Γ(c)B, which proves the first equality. For the second equality, remark that for every c ∈ C, since Γ is an isomorphism, cB ′ = 0 if and only if Γ(c)B ′ = 0. □

9

4 Local recovery in rank metric In this section, we introduce and analyse the notion of local recovery for codes endowed with the rank metric. Our goal is to adapt locality constraints that are used in the Hamming metric to rank-dedicated operations and structures (support, puncturing, etc.).

Local recovery seen as partial but efficient erasure decoding In an erasure-channel context, assume that Y = C + E ∈ Fm×n is a received word, where C ∈ q m×n C ⊆ Fm×n is a rank-metric code and E ∈ F is rank-1 erasure, that is, a matrix such that q q W = colspan(E ) is known and has dimension 1. The problem of finding C given Y and W is known as the erasure decoding problem. A typical n×(n−1) way to solve it is to consider a matrix A ∈ Fq of rank n − 1 such that EA = 0 (the knowledge of W is sufficient for this), and to compute Y A = CA + EA = CA. If dim πA (C ) = dim C , then one can recover the codeword C from Y A = CA = πA (C ), for example by using linear algebra. The local recovery problem is somewhat similar to erasure decoding, with two essential modifications: (i) given u ∈ Fnq \ {0}, it is only required to recover the vector Cu and not C entirely, (ii) to do so, we only have access to the image of C on a subspace of Fnq of small dimension. In particular, and in contrast with [18], we believe that the local recovery property must concern any nonzero element of the code domain (U for morphisms, Fnq for matrices), instead of only canonical vectors.

4.1 Locality for rank-metric codes Recall that given a subspace S ⊆ U , the map πS denotes the puncturing associated to the canonical inclusion ιS : S ,→ U (see Notation 3.2). We now define a new notion of locality with respect to the rank metric. Definition 4.1 Let C ⊆ Hom(U, V ) and r ∈ [n]. We say that u ∈ U \ {0} has (rank) locality r in C if there exists S ⊆ U of dimension at most r, such that u ∈ / S and

dimFq πS (C) = dimFq πS⊕⟨u⟩F (C) . q

In this case, the space S is called a helper space for u.

As a consequence of Remark 3.3, we can rewrite the notion of rank locality with more general puncturings. Lemma 4.2 Let C ⊆ Hom(U, V ), and r ∈ [n]. We say that u ∈ U \ {0} has (rank) locality r in C if there exists an Fq -space S of dimension at most r and an injective map g ∈ Hom(S, U ) such that u ∈ / im(g) and

dimFq πg (C) = dimFq πh (C) where h : S × Fq → U (x, λ) 7→ g(x) + λu. Definition 4.3 A code C ⊆ Hom(U, V ) is r-rank locally recoverable if every u ∈ U \ {0} has rank locality r in C.

Proposition 3.7 gives a trivial upper bound on the locality parameter of a code. Proposition 4.4 Let C ⊆ Hom(U, V ) be a rank-metric code of minimum rank distance d ⩾ 2. Then C is (n − d + 1)-rank locally recoverable.

Proof Let u ∈ U \ {0}. Let S ⊆ U of dimension n − d + 1, such that u ∈ / S. By Proposition 3.7, dimFq (πS (C)) = dimFq (C) = dimFq (πS⊕⟨u⟩F (C)), q

and since u ∈ / S, u has locality n − d + 1 in C.

□

10

Lemma 4.2 allows us to give an easy translation of the notion of locality in the context of matrix codes, where the matrix B plays the role of the linear map h. Definition 4.5 (Locality for matrix codes) Let C ⊆ Fm×n , and r ∈ [n]. q ′

n×r • We say that u ∈ Fn of rank r′ ⩽ r such that q \ {0} has (rank) locality r in C if there exists B ∈ Fq u∈ / colsupp(B) and

dimFq πB (C) = dimFq π(B|u) (C) .

• The code C ⊆ Fm×n is r-rank locally recoverable if every u ∈ Fn q q \ {0} has rank locality r in C. Example 4.6 Let m, n ⩾ 1 and consider the matrix code C = {(M |M ) | M ∈ Fm×n } ⊆ Fm×2n q q of dimension mn over Fq . We claim this code has locality r = 1. Indeed, for all nonzero u = (u1 , u2 ) ∈ F2n q (with ui ∈ Fn q ), we have Cu = M (u1 + u2 ), ∀C = (M |M ) ∈ C. As a consequence: • if u2 = 0, then Cu = C(u1 , 0) = M u1 = C(0, u1 ) for all C ∈ C. Denote by B ∈ Fn×1 the column matrix q associated to the vector (0, u1 ) ∈ Fn q ; then one can easily check that π(B|u) (C) and πB (C) have the same dimension over Fq , meaning that colspan(B) = ⟨(0, u1 )⟩Fq is a helper space for u. • if u2 ̸= 0, we also have Cu = C(u1 + u2 , 0) for all C ∈ C. If u1 + u2 = 0, then Cu = 0 for all C ∈ C, hence u has locality 0. Otherwise, denote by B ′ ∈ Fn×1 the column matrix associated to the vector q ′ (u1 + u2 , 0) ∈ Fn . Then dim π (C) = dim π (C) and ⟨(u1 + u2 , 0)⟩Fq is a helper space for u. ′ q Fq (B |u) Fq B

Our definition of locality in the rank metric actually differs from the one given by Kadhe et al. in [18]. We will demonstrate this distinction thanks to upcoming Proposition 4.10, that requires to firstly prove a few elementary facts. To this end, up to the end of the section, we denote by (v1 , . . . , vm ) a basis of V . Notation 4.7 For every u ∈ U and every ℓ ∈ [m], let φℓ [u] ∈ Hom(U, V ) be the rank-one operator defined by def

φℓ [u](x) = βU (u, x)vℓ ,

∀x ∈ U.

Lemma 4.8 For every u ∈ U and every ℓ ∈ [m], we have (i) (φℓ [u])† (v) = βV (vℓ , v)u for all v ∈ V , (ii) rowsupp(φℓ [u]) = ⟨u⟩Fq , (iii) for every f ∈ Hom(U, V ), ⟨f, φℓ [u]⟩ = βV (f (u), vℓ ).

Proof Let u ∈ U and ℓ ∈ [m]. For every x ∈ U and v ∈ V , we have βU ((φℓ [u])† (v), x) = βV (v, φℓ [u](x)) = βV (v, βU (u, x)vℓ ) = βU (u, x)βV (v, vℓ ) = βU (βV (vℓ , v)u, x) , which proves the first item. The second item then follows. To prove the last one, applying (i) we get that, for every f ∈ Hom(U, V ) and i ∈ [m],     βV f ((φℓ [u])† (vi )), vi = βV f (βV (vℓ , vi )u), vi = βV (vℓ , vi ) · βV (f (u), vi ) ( βV (f (u), vi ) if i = ℓ, = 0 otherwise. The last equality holds because the basis BV is orthonormal. Then m   X ⟨f, φℓ [u]⟩ = Tr(f ◦ (φℓ [u])† ) = βV f ((φℓ [u])† (vi )), vi = βV (f (u), vℓ ) i=1

which proves the third item.

□

11

Lemma 4.9 Let S ⊆ U of dimension r. Let f ∈ Hom(U, V ) such that rowsupp(f ) ⊆ S. For every basis (s1 , . . . , sr ) of S, there exists (λji )i∈[r],j∈[m] ∈ Fm×r such that q # " r m X j X λi si . f= φj i=1

j=1

Proof Fix (s1 , . . . , sr ) a basis of S. By hypothesis, im(f † ) ⊆ S. Therefore, there exists (λji )i∈[r],j∈[m] ∈ Fm×r q P such that for every j ∈ [m], f † (vj ) = ri=1 λji si . This implies that for every v ∈ V , f † (v) =

m X

βV (vj , v)f † (vj ) =

j=1

We deduce that f=

m X

(φj [f † (vj )])† (v).

j=1

m X

†

φj [f (vj )] =

j=1

m X j=1

φj

" r X

# λji si

.

i=1

□ Proposition 4.10 Let C ⊆ Hom(U, V ). Let u ∈ U \ {0}, and S ⊆ U of dimension r, with u ∈ / S. The following are equivalent. (i) u has locality r with helper space S (i.e., dimFq (πS (C)) = dimFq (πS⊕⟨u⟩F (C))); q

(ii) P for any basis {s1 , . . . , sr } of S, there exists ψ1 , . . . , ψr ∈ End(V ) such that for all f ∈ C, f (u) = r i=1 ψi (f (si )); (iii) There exist g1 , . . . , gm ∈ Hom(U, V ) such that, for all ℓ ∈ [m], we have rowsupp(gℓ ) ⊆ S and φℓ [u] + gℓ ∈ C ⊥ where the maps φℓ [u] are defined in Notation 4.7.

Proof We are going to prove that (i) ⇔ (ii) ⇔ (iii). Let us consider the map evS : πS⊕⟨u⟩F (C) → V r

(6)

q

f 7→ (f (s1 ), . . . , f (sr ))

By definition, the rank of evS is dimFq πS (C). Then, by the rank-nullity theorem, (i) holds if and only if the map evS is injective. Assume (i) holds. The map evu : πS⊕⟨u⟩F (C) → V q

f 7→ f (u) satisfies that ker evS = {0} ⊆ ker evu . The fundamental theorem on homomorphisms ensures the existence of a map Ψ : V r → V such that evu = Ψ ◦ evS . In other words, for all f ∈ C, f (u) P = Ψ(f (s1 ), . . . , f (sr )), which implies (ii). Conversely, assume (ii) holds. Then, for all f ∈ C, we have f (u) = ri=1 ψi (f (si )). This implies that evS is injective, which implies (i). Let us prove that (ii) implies (iii). By (ii), for all f ∈ C, we have f (u) = to this equality, Lemma 4.8 (iii) gives ⟨f, φℓ [u]⟩ =

r X

Tr(ψi ◦ f ◦ φℓ [si ]† )

i=1

=

r X

Tr(f ◦ φℓ [si ]† ◦ ψi )

i=1

=

r X

Tr(f ◦ (ψi† ◦ φℓ [si ])† )

i=1 r X = ⟨f, ψi† ◦ φℓ [si ]⟩ i=1

= ⟨f,

r X

ψi† ◦ φℓ [si ]⟩.

i=1

12

Pr

i=1 ψi (f (si )). Applying βV (·, vl )

P def Set gℓ = − ri=1 ψi† ◦ φℓ [si ]. By the previous computation, we have φℓ [u] + gℓ ∈ C ⊥ . Moreover for every i ∈ [r], rowsupp(ψi† ◦ φℓ [si ]) ⊆ rowsupp(φℓ [si ]) ⊆ ⟨si ⟩Fq (by Lemma 4.8 (ii) and Lemma 2.17), hence rowsupp(

r X

ψi† ◦ φℓ [si ]) ⊆

i=1

r X

⟨si ⟩Fq = S.

i=1

Now, it remains to prove that (iii) implies (ii). Denote s1 , . . . , sr a basis of S. Let ℓ ∈ [m]. By Lemma 4.9, Pr P j there exists (λji (ℓ))i∈[r],j∈[m] ∈ Fm×r such that gℓ = m q j=1 φj [ i=1 λi (ℓ)si ]. This implies that for all f ∈ C, r X m X

⟨f, φℓ [u]⟩ = ⟨f, −gℓ ⟩ =

−λji (ℓ)⟨f, φj [si ]⟩.

(7)

i=1 j=1

By Lemma 4.8 (iii), f (u) =

Pm

Pm

ℓ=1 βV (f (u), vℓ )vℓ = m X r X m X

f (u) =

=

ℓ=1 i=1 j=1 r X m X m X i=1 ℓ=1

=

r X

ℓ=1 ⟨f, φℓ [u]⟩vℓ . By Equation (7) we have

 −λji (ℓ)⟨f, φj [si ]⟩ vℓ  −λji (ℓ)βV (f (si ), vj ) vℓ

j=1

ψi (f (si )),

i=1

where we define ψi ∈ End(V ) by ψi : x 7→

Pm  Pm ℓ=1

j j=1 −λi (ℓ)βV (x, vj )



vℓ .

□

It will be useful to also consider the translation in the matrix setting of the characterization in Proposition 4.10. Given a code C ⊆ Fm×n , the following are equivalent: q 1. a vector u ∈ Fnq has locality r in C 2. there exist P1 , . . . , Pr ∈ Fm×m and s1 , . . . , sr ∈ Fnq such that u ∈ / ⟨s1 , . . . , sr ⟩Fq , and q

Cu =

r X

Pi Csi ,

∀C ∈ C.

i=1

3. there exist G1 , . . . , Gm ∈ Fm×n , such that dim q

Pm

ℓ=1 rowsupp(Gℓ ) ⩽ r and

Eℓ (u) + Gℓ ∈ C ⊥ ,

∀ℓ ∈ [m],

where Eℓ (u) is the matrix with zeroes everywhere except for the ℓ-th row which is u.

4.2 Constructing new LRCs from others It is clear that, if C, C ′ ⊆ Hom(U, V ) are two r-rank LRCs, then C ∩C ′ is also r-rank locally recoverable. Let us analyse other classical constructions of LRCs from others. Definition 4.11 Let f (1) ∈ Hom(U (1) , V (1) ) and f (2) ∈ Hom(U (2) , V (2) ). We define the following operations. • direct sum:

f (1) ⊕ f (2) :

(1) U (1) × U (2) → V × V (2) 

u = (u(1) , u(2) ) 7→

 f (1) (u(1) ), f (2) (u(2) ) .

• pairing: if U (1) = U (2) = U , (f (1) , f (2) ) : U →  V (1) × V (2) u 7→

 f (1) (u), f (2) (u) .

• copairing: if V (1) = V (2) = V , f (1) + f (2) :

U (1) × U (2) → V u = (u(1) , u(2) ) 7→ f (1) (u(1) ) + f (2) (u(2) ).

13

Remark 4.12 Given M (1) and M (2) the matrices of f (1) and f (2) in some bases, then f (1) ⊕ f (2) , (f (1) , f (2) ) and f (1) + f (2) are respectively represented by the block matrices ! !   M (1) 0 M (1) (1) (2) . , and M M 0 M (2) M (2) Proposition 4.13 Let C (1) ⊆ Hom(U (1) , V (1) ) and C (2) ⊆ Hom(U (2) , V (2) ) be two rank LRCs with locality r(1) and r(2) respectively. (I) The direct sum of the codes n o   def C (1) ⊕ C (2) = f (1) ⊕ f (2) | f (1) ∈ C (1) , f (2) ∈ C (2) ⊆ Hom U (1) × U (2) , V (1) × V (2) is a rank LRC of locality max{r(1) , r(2) }. (II) If V (1) = V (2) = V , the copairing of the codes n o   def C (1) + C (2) = f (1) + f (2) | f (1) ∈ C (1) , f (2) ∈ C (2) ⊆ Hom U (1) × U (2) , V is a rank LRC of locality r(1) + r(2) .

Proof Let us use the characterization (ii) Dof Proposition E4.10 to prove the statement. Let j ∈ {1, 2}. For every (j)

(j)

(j)

nonzero u(j) ∈ U (j) , there exists S (j) = s1 , . . . , sr(j)

(j)

⊆ U (j) not containing u(j) and ψ1 , . . . , ψr(j) ∈

Fq

End(V (j) ) such that for every f (j) ∈ C (j) , we have (j)

f

(j)

(j)

(u

)=

r X

(j)

(j)

ψi f (j) (si ).

(8)

i=1 (1) def

(1) def

We assume without loss of generality that r(1) ⩽ r(2) . If r(1) < r(2) , we set si = 0 and ψi = idV (1) for r(1) < i ⩽ r(2) .   Let us prove (I). Let us take a nonzero u = u(1) , u(2) ∈ U (1) × U (2) . At least one of the u(j) is nonzero. If both are nonzero, then  (1)  r r (2)   X X (1) (1) (2) (2) (1) (2) (1) (1) (2) (2) (1) (2) f ⊕ f (u) = f (u ), f (u ) =  ψ f (s ), ψ f (s ) i

i

i

i=1

i

i=1

(2)

=

r X

  ψi f (1) ⊕ f (2) (si )

i=1

where si =



(1) (2) si , si



(1) (2) and ψi = ψi ⊕ ψi . Then the set S = ⟨s1 , . . . , sr(2) ⟩Fq does not contain u and is a (1) (2) (2) (1) (1)

helper space for u in C ⊕ C . If u = 0 (resp. u = 0), then one can easily check that S × {0} (resp. {0} × S (2) ) is a helper space for u = (u(1) , 0) (resp. u = (0, u(2) )) in C (1) ⊕ C (2) . This completes the proof for (I). For the case (II), take u = (u(1) , u(2) ) be a nonzero vector of U (1) × U (2) such that u(1) ̸= 0 and (1) (1) (2) (2) (2) u ̸= 0. The space S ⊆ U (1) × U (2) generated by the vectors (s1 , 0), . . . , (sr(1) , 0), (0, s1 ), . . . , (0, sr(2) ) has dimension r(1) + r(2) and does not contain u. Moreover, for every f (1) ∈ C (1) and f (2) ∈ C (2) , we have (f (1) + f (2) )(u(1) , u(2) ) = f (1) (u(1) ) + f (2) (u(2) ) (1)

=

r X

(2)

(1) (1) ψi f (1) (si ) +

i=1

=

r (1) X

r X

(2)

(2)

ψi f (2) (si )

i=1 (2)

(1)

(1)

ψi ((f (1) + f (2) )(si , 0)) +

i=1

r X

(2)

(2)

ψi ((f (1) + f (2) )(0, si )).

i=1

So, we can conclude that S is a helper space for u. In conclusion, if u(1) = 0 and u(2) ̸= 0, we may take S = {0} × S (2) , where S (2) is a helper space for u(2) in C (2) . This is a helper space for u in the copairing. The same holds for u(2) = 0 and u(1) ̸= 0. □ Remark 4.14 If U (1) = U (2) = U , the pairing of the two LRCs C (1) and C (2) , defined by   n  o   def C (1) , C (2) = f (1) , f (2) | f (1) ∈ C (1) , f (2) ∈ C (2) ⊆ Hom U, V (1) × V (2)

14

is not necessarily a LRC. It depends on the way the helper spaces S (1) and S (2) for a same u in C (1) and def

C (2) interact. If u does not lie inS = S (1)+ S (2) , then similar computations as for the proof of (II) ensure that S is a helper space for u in C (1) , C (2) . In particular, this holds when C (1) = C (2) = C: if C is an r-rank

LRC, then so is (C, C). is not surprising when compared with the situation in the Hamming metric. The pairing  This situation  C (1) , C (2) consists in “stacking” codewords of C (1) and C (2) , which corresponds to interleaving. In the Hamming metric, the interleaving of two different LRCs is not necessarily locally recoverable.

4.3 Comparison with the definition of Kadhe et al. Kadhe et al. proposed in [18, Definition 2] another definition of locality in the rank metric. They consider that a code C ⊆ Fm×n is r-locally recoverable if every column of a matrix-codeword C ∈ C q can be recovered by accessing at most r other columns. Considering this code in Hom(Fnq , Fm q ), this notion depends on the choice of bases for Fnq and Fm . q Our new definition of locality is coordinate-free and allows efficient recovery of any element in the image of the matrix-codeword, and not only columns of the codeword1 . Both definitions thus differ in two ways: our definition demands that more elements should be recoverable (not only columns of the codewords), but allows much diverse helper spaces (neither only subsets of columns of the codewords). The dependency on the choice of bases in the definition of locality in [18] induces that two equivalent codes may not share the same locality. Indeed, consider the code    a 0 b 0 C= | (a, b) ∈ Fq . 0 a 0 b It is easy to check that C has locality 1 according to the definition of locality in [18]. However, C is equivalent to    a 0 a+b 0 ′ C = | (a, b) ∈ Fq (9) 0 a 0 b whose third column cannot be recovered with only one other column. Hence C ′ has locality at least 2 (actually, exactly 2) according to [18]. On the contrary, according to our definition and to Proposition 4.10, locality is invariant under left-right-equivalence of codes. Lemma 4.15 Let C ∈ Hom(U, V ) and C ′ ∈ Hom(U ′ , V ′ ) be rank-metric codes such that C = β ◦ C ′ ◦ α with ∼ U ′ and β : V ′ −→ ∼ V . Then, the codes C and C ′ share the same locality. α : U −→

def

Proof Assume that C has locality r, and consider u′ ∈ U ′ . Since u = α−1 (u′ ) has locality r, there exist a helper space S = ⟨s1 , . . . , sr ⟩Fq ⊆ U not containing u, and homomorphisms ψ1 , . . . , ψr ∈ End(V ), such that P for all f ∈ C, f (u) = ri=1 ψi (f (si )). def

We now claim that S ′ = α(S) is a helper space for u′ in C ′ . Indeed, we have u′ ∈ / S ′ and, for any f ′ ∈ C ′ ,   f ′ (u′ ) = β −1 (β ◦ f ′ ◦ α)(α−1 (u′ )) {z } | ∈C

= β −1

r X

 ψi ((β ◦ f ′ ◦ α)(si ))

i=1

=

r X i=1

(β −1 ◦ ψi ◦ β)(f ′ (α(si ))) . | {z } ∈End(V ′ )

□

Lemma 4.15 allows us to enlarge Example 4.6 to a broader family of codes. Example 4.16 Let m, n ⩾ 1 and fix A ∈ GLm (Fq ). Then the matrix code CA = {(M |AM ) | M ∈ Fm×n } ⊆ Fm×2n q q 1 Said differently, a code is locally recoverable if we can recover any element of rank 1 in the support of the codeword, given access to at most r independent elements in its support, as it is the case for Hamming-LRCs.

15

has locality 1. Indeed, CA is equivalent to the code C defined in Example 4.6, through the Fq -isometry of Fm×2n given by: q C = (C1 |C2 ) 7→ (C1 |A−1 C2 ) . We will see later that some of the codes in this family are remarkable, since they achieve a Singleton-like bound, see Section 5.

Let us finally point out two examples that illustrate that the definition of locality in [18] is not equivalent to ours. Example 4.17 Let us prove that C ′ defined in Equation (9) has locality 1 for our definition, whereas it has locality 2 for [18] (from previous discussion). Since C ′ and C are equivalent, according to Lemma 4.15, we only have to prove that C (also defined above) has locality 1.   a 0 b 0 ∈ C, we have Cu = Consider a nonzero u = (u1 , u2 , u3 , u4 ) ∈ F4q . For any codeword C = 0 a 0 b   au1 + bu3 . Now, define v = (u2 , u1 , u4 , u3 ). We can easily check that: au2 + bu4   0 1 Cv . Cu = 1 0 Therefore, if u and v are not collinear, then Cu can be recovered by querying only Cv and applying a linear map to it, proving that u has locality 1 according to Proposition 4.10. If u and v are collinear, this means that u can be written as u = [u1 , λu1 , u3 , λu3 ] with λ ∈ Fq such that λ2 = 1. But in that case,     au1 + bu3 1 0 Cu = = Cw λ(au1 + bu3 ) λ 0 with w = (u1 , 0, u3 , 0) ∈ / ⟨u⟩Fq . This also means that Cu can be recovered by a query of rank 1. Example 4.18 Consider now the matrix code of dimension 3 defined as    a c b c D= | (a, b, c) ∈ F32 ⊆ F2×4 . 2 c b c a+c The code D has locality 1 according to [18]: column 1 can be recovered by column 4 (and conversely), and column 2 can be recovered by column 3 (and conversely). However, D is not 1-rank locally recoverable according to our   definition, since the vector u = (1, 1, 0, 0) ∈ a c b c 4 ∈ D, we have F2 does not have locality 1. Indeed, for any C = c b c a+c   a+c Cu = b+c and the 15 other evaluations of Cv, for v ∈ F42 \ {u}, are:                   0 a c b c a+b a+c b+c 0 , , , , , , , , , 0 c b c a+c 0 a b+c a+b+c             b+c a+b+c a a+b+c b a+b , , , , , . a+b+c b a+b a+c a+b a+b+c One can check that none of them allows to recover Cu. Notice that, by Proposition 4.10 (ii), the space generated by u is a helper space for v = (1, 0, 1, 0) (since Cv = ψ(Cu) with ψ(x, y) = (x + y, 0)) and v = (0, 1, 1, 0) (with ψ(x, y) = (y, y)). Indeed, the morphism ψ does not need to be an automorphism, which induces this asymmetry that cannot happen for locality 1 in the Hamming metric (for nondegenerate codes).

4.4 Relations with the Hamming metric It is natural to question whether LRCs in the Hamming metric can help to design LRCs in the rank metric. One way to map Hamming-metric codes to rank-metric codes is to use the following “diagonal” construction. Assume n ⩾ 2, and let CH ⊆ Fnq be a Hamming-metric code of dimension k and minimum distance d. Let also U be a vector space of dimension n over Fq , and denote by (u1 , . . . , un ) a basis of U . We then define def

C = Diag(CH ) = {fc | c ∈ CH } where fc (ui ) = ci ui for every i ∈ [n]. Then C ⊆ Hom(U, U ) is a rank-metric code of dimension k and minimum rank distance d. 16

Lemma 4.19 If CH is locally recoverable with locality r, then C is 1-rank locally recoverable.

Proof Let i ∈ [n]. Recall that since CH is locally recoverable with locality r, there exist Ri ⊆ [n] of size at most r such that i ∈ / Ri and some (αi,j )j∈Ri ∈ Fq such that for every codeword c = (c1 , . . . , cn ) ∈ CH , we have X ci = αi,j cj . (10) j∈Ri Pn n Now, let us consider a general P nonzero u ∈ Fq and write u = j=1 λj uj with λj ∈ Fq . Since n ⩾ 2, there

exists i ∈ [n] such that wi =

j̸=i uj is non-collinear to u. Let ψ ∈ End(U ) such that

( ψ(uj ) = λj uj +

λi αi,j ui 0

if j ∈ Ri , otherwise,

for j ̸= i and ψ(ui ) = 0. Then, for every codeword c = (c1 , . . . , cn ) ∈ CH , we have X X X X ψ ◦ fc (wi ) = ψ ◦ fc (uj ) = cj ψ(uj ) = λj cj uj + λi αi,j cj ui j̸=i

=

X

j̸=i

j̸=i

j∈Ri

λj cj uj + λi ci ui = fc (u),

j̸=i

which means that the 1-dimension space spanned by wi is a helper space for u in C (Proposition 4.10), hence u has locality 1 in C. □

The previous lemma clearly illustrates the difference between the pre-existing notion of local recoverability in the rank metric compared to the one we develop in the present work. We can see the proposition of Kadhe et al. as a straightforward translation of the notion in the Hamming metric: if CH is an LRC, then C is a rank LRC in the sense of [18, Definition 2] with the same locality, in contrast with Lemma 4.19.

4.5 Information spaces for rank-metric codes and locality of MRD codes The goal of this section is to formalize the notion of information spaces of Fq -linear rank-metric codes, in analogy with the notion of information set in Hamming metric. Recall that an information set for a code in the Hamming metric is a minimal set of indices such that every codeword is uniquely determined by its values at the corresponding positions. In other words, the restriction of the code on this set of positions has the same dimension as the code itself. In rank metric, we will translate this idea to subspaces of the code domain. Definition 4.20 Let C ⊆ Hom(U, V ) be a nonzero code. A subspace S ⊆ U is said to be an information space for C if (i) dimFq (πS (C)) = dimFq (C), (ii) and for all S ′ ⊊ S, we have dimFq (πS ′ (C)) < dimFq (C).

Notice that, given a code C ⊆ Hom(U, V ), the set of spaces satisfying (i) is not empty (it contains U ). So it admits an element of minimal dimension. Such an element is an information space of the code C . It is worth mentioning that, when dealing with the tensor representation of k -dimensional matrix codes, the vector space Fkq is sometimes called the information space (e.g., see [7, §4]). Here, the terminology is different: an information space for a k -dimensional code is a subspace of U whose k dimension (over Fq ) is at least m , where m = dimFq (V ). The notion of information space is tightly related to the one of locality. If S is (or contains) an information space for C ∈ Hom(U, V ) then S is a helper space for any u ∈ / S . We thus use this notion to investigate the locality of MRD (Maximum Rank Distance) codes. We recall that MRD codes are the ones achieving the Singleton bound, reformulated for homomorphisms below. Theorem 4.21 [12, Theorem 3.5] Let C ⊆ Hom(U, V ) of dimension k and minimum rank distance d. Then k ⩽ max{m, n}(min{m, n} − d + 1).

For MRD codes, Proposition 3.7 translates into the following result. 17

Proposition 4.22 Let C ⊆ Hom(U, V ) be an MRD code of dimension k and minimum rank distance d ⩾ 2. k Then, every S ⊆ U of dimension n − min(m, n) + max(m,n) contains an information space for C.

Proof First notice that the dimension k of an MRD code C is divisible by max{m, n}. k k In the case where m ⩾ n, the Singleton bound gives m = n − d + 1. Let S ⊆ U of dimension m . By Proposition 3.7, dimFq (πS (C)) = dimFq (C), and S contains an information space for C. k k In the other case (n ⩾ m), the Singleton bound becomes n = m − d + 1. Let s = n − m + n and S ⊆ U of dimension s. Since s ⩾ n−d+1, by Proposition 3.7, dimFq (πS (C)) = dimFq (C), and S contains an information space for C. □

As a consequence, for any MRD code C ⊆ Hom(U, V ) with m ⩾ n, every subspace S ⊆ U of k dimension m is an information space for C . k -rank locally Corollary 4.23 Let C ⊆ Hom(U, V ) of dimension k. If m ⩾ n and if C is MRD, then C is m k recoverable. Besides, for every u ∈ U , every S ⊆ U of dimension m such that u ∈ / S is a helper space for u.

Proposition 4.24 Let C ⊆ Hom(U, V ) of dimension k. If C is MRD, and m ⩾ n, then C cannot be locally k recoverable with locality r < m .

k Proof Since C is MRD, C ⊥ is also MRD (see [12, Theorem 4.13]) and the minimum distance of C ⊥ is m + 1. ⊥ Let u ∈ U . If u has rank-locality r in C, then by Proposition 4.10, there exists x ∈ C such that wR (x) ⩽ r +1. k k + 1 ⩽ r + 1, and therefore m ⩽ r. □ This implies that m

4.6 Locality for Fqm -linear codes In this section, we make explicit the definition of rank-locality in the context of Fqm -linear codes and we give some results of the last section in this context. n Definition 4.25 Let C ⊆ Fn q m and r ∈ [n]. We say that u ∈ Fq \ {0} has (rank) locality r in C if there exist ′

r′ ⩽ r and B ∈ Fn×r of rank r′ , with u ∈ / colsupp(B), such that q

dimFqm πB (C) = dimFqm π(B|u) (C) . In this case, the space S is called a helper space for u. n Definition 4.26 A code C ⊆ Fn q m is r-rank locally recoverable if every u ∈ Fq \ {0} has rank locality r in C.

Proposition 4.27 Let C ⊆ Fn q m . If C is r-rank locally recoverable, then for every basis Γ of Fq m /Fq , the code Γ(C) ⊆ Fm×n is r-rank locally recoverable. q

Proof If dimFqm (πB (C)) = t, then dimFq (Γ(πB (C)) = mt. Therefore, if dimFqm (πB (C)) = dimFqm (π(B|u) (C)), then dimFq (Γ(πB (C))) = dimFq (Γ(π(B|u) (C))), and by Lemma 3.10, dimFq (πB (Γ(C))) = dimFq (π(B|u) (Γ(C))), and Γ(C) is r-rank locally recoverable.

□

In the context of Fqm -linear codes, the characterizations for local recoverability provided by Proposition 4.10 become the following. n Proposition 4.28 Let C ⊆ Fn / S. For every q m . Let also u ∈ Fq , and S ⊆ U of dimension r, with u ∈ n×r B = (b1 , . . . , br ) ∈ Fq such that colsupp(B) = S, the following are equivalent.

(i) dimFqm (πB (C)) = dimFqm (π(B|u) (C)) (ii) There exist λ1 , . . . , λr ∈ Fqm such that for every c ∈ C, ⟨c, u⟩ = (iii)

Pr

⊥ There exists x ∈ Fn q m such that rowsupp(x) ⊆ S and u + x ∈ C .

18

i=1 λi ⟨c, bi ⟩.

Proof Since π(B|u) (C) = {(⟨c, b1 ⟩, . . . , ⟨c, br ⟩, ⟨c, u⟩), c ∈ C}, the equivalence (i) ⇔ (ii) is clear. Suppose now that there exist λ1 , . . . , λr ∈ Fqm such that for every c ∈ C, ⟨c, u⟩ =

r X

λi ⟨c, bi ⟩.

i=1

P Set x := − ri=1 λi bi . Then u + x lies in C ⊥ and rowsupp(x) ⊆ S. This proves that (ii) implies (iii). ⊥ m such that rowsupp(x) ⊆ S and u + x ∈ C . Then, there Conversely, suppose there exists x ∈ Fn Pr q ⊥ m exist Pr λ1 , . . . , λr ∈ Fq such that x = i=1 λi bi . Since u + x ∈ C , we obtain that for all c ∈ C, ⟨c, u⟩ = □ i=1 λi ⟨c, bi ⟩. This proves that (ii) ⇔ (iii).

In the case of an Fqm -vector code C , the previous proposition implies that the endomorphisms ψi from Proposition 4.10 (ii) correspond to companion matrices (matrices of the multiplication by scalars in Fqm ) for the corresponding matrix code Γ(C ). The third items of Propositions 4.10 and 4.28 both give a characterization of local recoverability related to the dual codes. As already mentioned in Remark 2.13, we have Γ(C )⊥ ̸= Γ(C ⊥ ). Therefore, a parity-check equation ⟨c, x⟩ = 0 ∈ Fqm does not necessarily lead to a parity-check equation ⟨Γ(c), Γ(x)⟩ = 0. Since Fm q has dimension m over Fq an equation ⟨c, x⟩ = 0 ∈ Fqm gives rise to m parity-check equations in Fq . This explains why Proposition 4.10 (iii) involves m codewords in the dual of Γ(C ), whereas (iii) of the previous proposition only relies on the existence of one vector (and all its Fm q -multiples). Let us now prove that an Fqm -linear MRD code of dimension k has locality exactly k . To do so, we will study the notion of information space for Fqm -linear codes. n×k of rank Lemma 4.29 Let C ⊆ Fn q m be an Fq m -linear code of dimension k (over Fq m ). There exists B ∈ Fq exactly k, such that dimFqm (πB (C)) = dimFqm (C).

Proof Let G ∈ Fk×n q m be a generator matrix of C. Since rk(G) = k, for every A ∈ GLn (Fq ), rk(GA) = k. Therefore, there exists a set I = {i1 , . . . , ik } ⊆ [n] such that the columns of GA indexed by I form an invertible matrix. Denote AI the matrix obtained from A by keeping its columns indexed by I. We then have dimFqm (πB (C)) = dimFqm (C). □

Remark that if C ⊆ Fnqm has dimension k over Fqm and if dimFq πB (C ) = dimFq (C ) for some B ∈ Fn×r (with r ⩽ n), then we must have k ⩽ r since πB (C ) ⊆ Frqm . This leads us to define q information spaces for Fqm -linear codes in the following way. n Definition 4.30 Let C ⊆ Fn q m with dimFqm (C) = k. A k-dimensional subspace S ⊆ Fq is called an

whose columns span S. information space for C if πB (C) = Fkqm for every B ∈ Fn×k q

Notice that Lemma 4.29 shows that any Fqm -linear code admits at least one information space. We now recall the Singleton bound for vector codes, which follows directly from the matrix framework [12, Theorem 3.5]. Theorem 4.31 (Singleton bound for Fqm -linear vector codes) An [n, k, d]qm vector rank-metric code C satisfies k ⩽ n − d + 1. Codes whose parameters reach this bound are called Maximum Rank Distance (MRD) codes.

The particular case of Fqm -linear MRD codes implies the following results thanks to Proposition 3.7. n Corollary 4.32 Let C ⊆ Fn q m be an MRD code of dimension k. Then every S ⊆ Fq m of dimension k is an information space for C.

Corollary 4.33 Let C ⊆ Fn q m be an MRD code of dimension k. Then, C is k-rank locally recoverable. Besides, for every u ∈ Fn / S is a helper space for u in C. q , every space S of dimension k such that u ∈

19

A last result finally shows that the dimension of helper spaces of MRD Fqm -linear codes must be at least the dimension of the code. Proposition 4.34 Let C ⊆ Fn q m of dimension k over Fq m . If C is MRD, then C cannot be locally recoverable with locality strictly less than k.

Proof Since C is MRD, C ⊥ is also MRD (see [26, Corollary 41]), and the minimum distance of C ⊥ is k + 1. Let ⊥ u ∈ Fn q . If u has rank locality r in C, then by Proposition 4.28, there exists x ∈ C such that wR (x) ⩽ r + 1. This implies that k + 1 ⩽ r + 1, and therefore k ⩽ r. □

5 A Singleton-like bound for rank LRCs This section aims at establishing a Singleton-like bound of rank-metric codes, which involves the locality and the three classical parameters. Such a bound was obtained in the Hamming metric in [11]. Given subspaces S, S ′ ⊆ U such that S ⊕ S ′ = U , we denote by Short(C, S, S ′ ) the shortened code Short(C, ιS , S ′ ) using the canonical inclusion ιS (see Notation 3.2). Lemma 5.1 Let C ⊆ Hom(U, V ) be an r-rank locally recoverable code. Let S, S ′ ⊆ U be subspaces such that S ⊕ S ′ = U . Then, the code Ce = Short(C, S, S ′ ) is r-rank locally recoverable.

Proof Let u ∈ S \ {0}. Let ψ ∈ Hom(S, U ) be an injective map such that ψ † ◦ ιS = idS , and ψ † ◦ ιS ′ = 0. By Proposition 3.8, we have Ce⊥ = Short(C, S, S ′ )⊥ = πψ (C ⊥ ). Since ψ is injective, the map ψ † is surjective (Theorem 2.3). Consider w ∈ U \ {0} such that ψ † (w) = u. Since C is r-rank locally recoverable, w has locality r in C, and by Proposition 4.10, there exist W ⊆ U of dimension ⩽ r with w ∈ / W , and f1 , . . . , fm ∈ Hom(U, V ), such that for all i ∈ [m], rowsupp(fi ) ⊆ W and e ⊥ for every i ∈ [m]. φi [w] + fi ∈ C ⊥ . Since Ce⊥ = πψ (C ⊥ ), we get (φi [w] + fi ) ◦ ψ ∈ C † Let now i ∈ [m]. Remark that (φi [w] + fi ) ◦ ψ = φi [ψ (w)] + fi ◦ ψ = φi [u] + fi ◦ ψ. Besides, rowsupp(fi ) = im(fi† ) = ker(fi )⊥ ⊆ W . This implies that W ⊥ ⊆ ker(fi ). Consider ρ : U → U/W ⊥ the canonical surjection. Then, by the fundamental theorem on homomorphisms, there exists gi ∈ Hom(U/W ⊥ , V ) such that fi = gi ◦ρ. We have rowsupp(fi ◦ ψ) = rowsupp(gi ◦ ρ ◦ ψ) ⊆ rowsupp(ρ ◦ ψ) by Lemma 2.17. Note that dimFq (rowsupp(ρ ◦ ψ)) = dimFq (im(ρ ◦ ψ)) ⩽ dimFq (im(ρ)) = r. To summarize, the subspace T = rowsupp(ρ ◦ ψ) ⊆ U has dimension at most r, and is such that for every i ∈ [m], rowsupp(fi ◦ ψ) ⊆ T . By Proposition 4.10, Ce is r-rank locally recoverable. □

We now derive a Singleton-like upper bound for rank locally recoverable codes. Theorem 5.2 Let C ⊆ Hom(U, V ) be a code of dimension k, and minimum rank distance d. Suppose C is r-rank locally recoverable. Then     k k +2− . (11) d⩽n− m rm A code achieving this bound with equality is called an optimal rank locally recoverable code.

Proof The proof works as follows. We build recursively a sequence of nonzero codes C (j) ⊆ Hom(U (j) , V ) of dimension kj and minimum distance dj satisfying def

(i) nj = dimFq (U (j) ) ⩾ n − j(r + 1), (ii) kj ⩾ k − jrm, k

k (iii) nj − mj ⩽ n − m − j,

(iv) dj ⩾ dj−1 , (v) C (j) is r-rank locally recoverable. Then, we apply the classical Singleton bound on the last code we obtain, and we derive the expected result. Set C (0) = C and U (0) = U . Thus, n0 = n, k0 = k and d0 = d. For j ⩾ 1, if we assume that C (j−1) is a code satisfying hypotheses (i)–(v), we define C (j) in the following way. • Pick a nonzero u(j) ∈ U (j−1) .

20

• Since C (j−1) ⊆ Hom(U (j−1) , V ) is r-rank locally recoverable, there exists Wj ⊆ U (j−1) of dimension rj ⩽ r, such that u(j) ∈ / Wj and     dimFq πWj (C (j−1) ) = dimFq πWj ⊕⟨u(j) ⟩ (C (j−1) ) .

(12)

Fq

 D E  • Finally, set C (j) def = Short C (j−1) , Wj′ , Wj ⊕ u(j) , for some subspace Wj′ ⊆ U (j−1) such that Fq D E Wj′ ⊕ Wj ⊕ u(j) = U (j−1) . Fq

k ⌉ − 1}, the code C (j) indeed satisfies the We will now prove by induction that for every j ∈ {0, . . . , ⌈ rm hypotheses (i)–(v). For j = 0, these properties are clearly satisfied by C (0) = C. k Now, fix j ∈ {1, . . . , ⌈ rm ⌉ − 1} and assume that C (j−1) satisfies the hypotheses. We have

nj = nj−1 − (rj + 1) ⩾ nj−1 − (r + 1).  D E  By Lemma 3.6, the code C (j) = Short C (j−1) , Wj′ , Wj ⊕ u(j) has dimension Fq

kj = kj−1 − dimFq (πWj ⊕⟨u(j) ⟩ (C (j−1) )) Fq

= kj−1 − dimFq (πWj (C

(j−1)

))

⩾ kj−1 − rj m ⩾ kj−1 − rm. where the last inequality follows from dimFq (πWj (C (j−1) )) ⩽ rj m. By induction hypothesis, this proves that (i) and (ii) hold. Moreover, nj −

dimFq (πWj (C kj−1 kj = nj−1 − (rj + 1) − + m m m

(j−1)

))

⩽ nj−1 −

kj−1 − 1, m

since dimFq (πWj (C (j−1) )) ⩽ rj m. By induction hypothesis, this proves (iii). The code C (j) being a shortening of C (j−1) , Lemma 3.6 ensures that dj ⩾ dj−1 , which proves (iv). Finally, (v) is a direct consequence of Lemma 5.1. Now, we apply the Singleton bound to the last nonzero code of the sequence of codes (C (j) )j . By j (ii),kwe have kj ⩾ 1 whenever j ⩽ k−1 rm . Then, the largest integer jmax satisfying this condition is jmax = l m (jmax ) k . rm − 1. Therefore, we can iterate this procedure at least until we build the code C

k−1 rm

=

We now apply the Singleton bound, as well as (iii) and (iv), to C (jmax ) , in order to get the desired result. If m ⩾ njmax , we directly get   kj k k k d ⩽ djmax ⩽ njmax − max + 1 ⩽ n − − jmax + 1 = n − − + 2. m m m rm Therefore, since d is an integer,         k k k k d⩽ n− − +2 =n− +2− . m rm m rm k

k

Suppose now m ⩽ njmax . The Singleton bound gives djmax ⩽ m − njjmax + 1. Notice now that m − njjmax ⩽ max

max

k

max njmax − jm whenever m ⩽ njmax and kjmax ⩽ njmax m, which is satisfied in our context. Hence, we get the expected bound in the same way as for m ⩾ njmax . □

k , the bound (11) becomes the classical Singleton bound, as it is the case in Remark 5.3 If m ⩾ n and r = m k the Hamming metric. Hence, optimal rank LRC codes with locality r = m are MRD codes. Kadhe et al. proved a Singleton-like bound for their definition of rank locality [18, Theorem 1]. In their case, they assume that m divides k, in which case Theorem 5.2 gives the exact same bound. Their bound is a direct consequence of the Singleton bound for LRCs in the Hamming metric: a rank-LRC codes C gives rise to a code CH in the Hamming metric with the same locality. The relation between our notion of locality and the one in the Hamming metric is not as straightforward (see Lemma 4.19, for instance). This is why Theorem 5.2 has to be proved from scratch.

A subfamily of codes given in Example 4.16 reaches the Singleton-like bound of Theorem 5.2.

21

Example 5.4 Recall that the codes CA , defined as CA = {(M |AM ) | M ∈ Fm×n } ⊆ Fm×2n q q for n, m ⩾ 1 and A ∈ GLm (Fq ), have dimension mn and locality 1. The Singleton-like bound of Theorem 5.2 hence ensures that lnm + 2 = 2. dR (CA ) ⩽ 2n − n − 1 Some of these codes (e.g., if A is the identity matrix) have minimum rank-distance 1. Let us exhibit subfamilies with minimum rank-distance 2. For this sake, fix λ ∈ Fq and assume that λ is not a square in Fq . Fix A ∈ Fm×m such that A2 = λIm , where Im ∈ Fm×m is the identity matrix. q q Let us now prove that any C = (M |AM ) ∈ CA has rank ⩾ 2. If rk(M ) ⩾ 2 this is clear, so assume rk(M ) = 1. Let v ∈ Fm q be a nonzero column of M . Since A is invertible, it suffices to prove that v and Av are not collinear. If they were, the vector v would be an eigenvector of A, and the corresponding eigenvalue would be a root of the minimal polynomial X 2 − λ of A. But λ is not a square in Fq , so this leads to a contradiction.

In the Fqm -linear case, we then obtain the following bound. Corollary 5.5 Let C ⊆ Fn q m be an Fq m -linear code of dimension k, and minimum rank distance d. Suppose C is r-rank locally recoverable. Then   k d⩽n−k+2− . r

Proof By Proposition 2.12, by fixing any basis Γ of Fqm /F q, one can associate to C a code Γ(C) ⊆ m Hom(Fn K = km, and distance d. This code is also r-LRC, so by Proposition 5.2, q , Fq ) of dimension l m l minimum m d⩽n− K m +2−

K rm

=n−k+2−

k r

.

□

Remark 5.6 As in the Hamming metric, if r = k we recover the classical Singleton bound, and optimal rank LRC codes with locality r = k are MRD codes.

6 Rank-metric analogues of Tamo-Barg optimal LRCs In this section, we provide a construction of optimal rank-LRC inspired by Tamo and Barg’s construction [32] in the Hamming metric. Their construction heavily relies on polynomials and Reed–Solomon codes. Likewise, ours will use q -polynomials and Gabidulin codes. We recall these notions, describe our construction and provide one instantiation.

6.1 q-polynomials and Gabidulin codes Definition 6.1 (Ore polynomials) Let m ⩾ 2. We denote by Fqm {τ } the noncommutative ring of Ore polynomials (also known as skew polynomials, or twisted polynomials) over Fqm defined as ( n ) def X Fqm {τ } = ci τ i n ⩾ 0, ci ∈ Fqm , i=0

endowed with the classical additive law, and the multiplication defined by τ a = aq τ for every a ∈ Fqm .

In the previous definition, the letter τ is just a formal variable, without further signification. However, it should be understood as the q -Frobenius endomorphism and Ore polynomials then correspond to polynomials in the q -Frobenius. This motivates the following terminology. P Definition 6.2 For f = i ai τ i ∈ Fqm {τ }, we define the q-degree of f as the largest integer i such that ai ̸= 0 and we denote it by degq (f ).

By [23], the ring Fqm {τ } is both left and right-Euclidean. Regarding τ as an endomorphism of Fqm , we can map Ore polynomials onto endomorphisms of Fqm . More precisely, since τ m = idFqm , two Ore polynomials induce the same endomorphism of Fqm if and only if they are congruent modulo τ m − id. In particular, every Fq -linear endomorphism of Fqm is represented by a unique Ore polynomial of q -degree less than m. For f ∈ Fqm {τ }, let f denote its unique representative modulo τ m − 1 of q -degree smaller than m. 22

Proposition 6.3 Let f ∈ Fqm {τ } be such that f ̸= 0. Then, dimFq ker f ⩽ degq (f ).

The above proposition is a standard property of linearized polynomials, see for instance [19, Theorem 3.50]. For every Fq -linear subspace U of Fqm , a family of q -polynomials defines a rank-metric code in Hom(U, Fqm ) as follows. Definition 6.4 (q-polynomial code) Let U be an Fq -linear subspace of Fqm and F be an Fq -linear subspace of Fqm {τ }. The q-polynomial code associated to F over U is of the form  πU (F) = f ◦ ιU | f ∈ F ⊆ Hom(U, Fqm ).

If F is an Fqm -linear subspace of Fqm {τ }, then πU (F ) is naturally an Fqm -linear code. For spaces of q -polynomials of sufficiently small q -degree, the previous proposition implies that the restriction map P 7→ P ◦ ιU is injective and determines a lower bound on the minimum distance of the associated code. Lemma 6.5 Let U be an Fq -linear subspace of Fqm of dimension n, and F be an Fq -linear subspace of  def Fqm {τ }. Assume δ = max degq (f ), f ∈ F < n. Then, πU (F) has the same Fq -dimension as F, and its minimum rank distance is at least n − δ.

Proof Since δ < n ⩽ m, the map f 7→ πU (f ) is injective over F by Proposition 6.3. This proves the equality of dimensions. The lower bound on the minimum rank distance comes from the rank-nullity theorem and Proposition 6.3. □

The most typical examples of q -polynomial codes are Gabidulin codes, originally introduced by Delsarte [9] and Gabidulin [10]. For a positive integer k , we denote by Fqm {τ }<k the vector space of q -polynomials of q -degree less than k . Definition 6.6 For an Fq -linear subspace U of Fqm of dimension n ⩽ m, the associated Gabidulin code of dimension k ⩽ n is
def Gabk (U ) = πU Fqm {τ }<k .

Gabidulin codes are rank-metric analogues of Reed–Solomon codes. By Lemma 6.5, they are MRD codes, so they share with Reed–Solomon codes the remarkable property of being optimal with respect to the Singleton bound. Besides, for every Fq -linear subspace U of Fqm of dimension n ⩽ m, the code Gabk (U ) (with k < n) is k -rank locally recoverable thanks to Corollary 4.33. In particular, for every nonzero u ∈ U , every k -dimensional subspace S of U such that u ∈ / S is a helper space for u.

6.2 Construction We build the rank-metric analogue of the general construction of optimal r-LRCs in the Hamming metric given by Tamo and Barg in [32, §A]. This seminal construction consists in designing an evaluation domain A = A1 ∪ · · · ∪ At ⊆ Fq , with pairwise disjoint subsets Ai of size r + 1, along with polynomials f ∈ Fq [x] that evaluate like polynomials of degree less than r on each of the Ai . For any of these polynomials f , the vector of evaluations of f over Ai lies in a Reed–Solomon code of dimension r, therefore each of its coordinates can be recovered by polynomial interpolation. Tamo and Barg’s trick to design such polynomials is to rely on a so-called good polynomial for the partition (Ai )i∈[t] : aPpolynomial g of degree r +1, that is constant on each of the Ai . Then polynomials f of the form f = j⩾0 fj g j with deg(fj ) < r have the desired property. We mimic this idea in the context of q -polynomials. Now, the evaluation domain is an Fq -vector space U . Given a “partition” of U in (r + 1)-dimensional subspaces Ui (more precisely an r-spread of the projectivized space PG(U )), we aim to design a family of q -polynomials that evaluate as q polynomials of degree less than r on each Ui . This way, we are able to recover their values at some u ∈ Ui thanks to any subspace S ⊆ Ui such that Ui = S ⊕ ⟨u⟩Fq . To do so, we also rely on a good q -polynomial as described in the next theorem.

23

Theorem 6.7 Let U ⊆ Fqm of dimension n and V = Fqm . Let r be a positive integer such that r + 1 divides n. Assume there exist n S (a) a family U of t = qqr+1−1 F -subspaces U1 , . . . , Ut of U of dimension r + 1 such that U = ti=1 Ui (so −1 q Ui ∩ Uj = {0} for every i ̸= j), (b) a q-polynomial g of degree r + 1 such that for every i ∈ [t], there exists λi ∈ Fqm such that g|Ui = λi idUi . Let k < n such that r divides k and k + kr − 2 < n. Define  k −1   rX def j fj ◦ g fj ∈ Fqm {τ }<r . F =   j=0

Then, the Tamo–Barg-like code def

TB(U, g, k) = πU (F) ⊆ Hom(U, Fqm ) is an optimal rank r-locally recoverable code of dimension k over Fqm .

Proof It is clear that dimFqm F ⩽ kr · r = k. Now, by unicity of the right-division in Fqm {τ } by g, we get dimFqm F = k. Moreover, all the q-polynomials in F have q-degree bounded from above by   k k def δ = r−1+ − 1 (r + 1) = k + − 2 < n. r r Therefore, by Lemma 6.5, the code TB(U, g, k) has dimension k and its minimum distance satisfies dR (TB(U , g, k)) ⩾ n − δ = n − k − kr + 2, which matches the Singleton bound for Fqm -linear LRCs (Corollary 5.5). It thus remains to prove that TB(U, g, k) is indeed an r-rank LRC. Take u ∈ F∗qm . The hypothesis (a) ensures there exists a unique i ∈ [t] such that u ∈ Ui . By (b), there exists λi ∈ Fqm such that for every f ∈ TB(U, g, k), we have k r −1

k r −1

f|Ui =

X

j

fj ◦ g ◦ ιUi =

j=0

X

fj ◦ (λji idUi ).

j=0

Therefore πUi (TB(U, g, k)) ⊆ Gabr (Ui ). Moreover, as the q-polynomials fj run in the whole space of polynomials of q-degree less than r, we have πUi (TB(U, g, k)) = Gabr (Ui ). The latter code being MRD, Corollary 4.32 ensures that any subspace S ⊆ Ui of dimension r such that Ui = S ⊕ ⟨u⟩Fq is an information space for Gabr (Ui ), i.e., dimFqm (πS (Gabr (Ui ))) = dimFqm (Gabr (Ui )). Then πS (TB(U, g, k)) = πS (πUi (TB(U, g, k))) = πS (Gabr (Ui )) has the same dimension as πUi (TB(U, g, k)), which means that S is a helper space for u in TB(U, g, k). □ Remark 6.8 Note that for every Ui ∈ U, we have Ui = ker(g − λi id), since the right-hand side has dimension at most r + 1, and dimFq (Ui ) = r + 1. Then λi ̸= λj for i ̸= j. Remark 6.9 The set of good q-polynomials (that satisfy (b)) is an Fqm -vector space. Actually, good qpolynomials are tightly related to good polynomials for the original Tamo-Barg construction [32]. Indeed, seen as classical polynomials via the identification τ = X q , q-polynomials are always divisible by X. Then, if g satisfies (b), the polynomial g(X)/X (of degree q r+1 − 1) is a good polynomial in the sense of [32, §A] for def

the partition U ∗ = {Ui \ {0} , Ui ∈ U}.

We instantiate this construction using a Desarguesian spread, leaving the existence of alternative constructions as an open question. Example 6.10 Take U = Fqm and α1 , . . . , αt some representatives of the classes of F∗qm /F∗qr+1 . Then, the n o def family U = Ui = αi Fqr+1 | i ∈ [t] satisfies the condition (a) of Theorem 6.7. Fix η, ν ∈ Fqm . On each Ui , the q-polynomial g = ητ r+1 + νid satisfies the condition (b) of Theorem 6.7: for every i ∈ [t] and x ∈ Fqr+1 , we have r+1 r+1
g(αi x) = ηαiq x + ναi x = ηαiq −1 + ν αi x = λi αi x.

24

Note that a q-polynomial g satisfying the condition (b) with respect to U implies that it is L-q r+1 -partially scattered (of index 0) in the sense of [3], that is for any y, z ∈ F∗qm , g(y) g(z) y = =⇒ ∈ Fqr+1 . y z z By [3, Proposition 3.1], since r + 1 divides m, a monomial of the form τ t is L-q r+1 -partially scattered of index 0 if and only if t | r + 1. This indicates that the only good q-polynomials with respect to U are the ones considered above. Note that we recover [18, Construction 1] with η = 1 and ν = 0. As discussed in Section 4.3, the notion of local recoverability studied in [18] is not the same as ours. Nevertheless, this specific construction gives an optimal LRC for both notions. Remark 6.11 The construction of Theorem 6.7 shares some analogies with the one of [5, §3.1], which provides optimal LRCs in the sense of [18]. The main difference lies in the fact that the partition of the condition (a) is replaced by a decomposition as a direct sum U = U1 ⊕ · · · ⊕ Us

(13)

of (r+1)-dimensional subspaces and that a good q-polynomial for such a direct sum satisfies that g|Ui = λi idUi for an homothety factor λi ∈ Fq (instead of Fqm as in (b)). In other words, the endomorphism associated to g is diagonalizable on U . In this case, with a basis of U formed by the union of bases of the eigenspaces Ui , the value of any q-polynomial of F at a basis vector can be recovered by its restriction on a given Ui , which lies in the Gabidulin code Gabr (Ui ). In [5, §3.1], the good polynomial is the q-polynomial ϕT associated to a Drinfeld module ϕ of rank r + 1. Note that these codes are not rank r-locally recoverable for our definition. The relaxed condition (13) does not allow the recoverability of any nonzero of U with a helper space of dimension r, but only of the ones which lie in one of the Ui ’s.

Acknowledgements The authors warmly thank Gianira Alfarano for her inputs regarding the use of the Desarguian spread in Example 6.10. This work was supported by a Research AAP from University Paris 8, allowing the authors to meet there. CG is financially supported by the Military French Ministry – Defense and Innovation Agency (DGA-AID). JN is supported by the French government Investissements d’Avenir program ANR-11LABX-0020-01.

References [1] Alexander Barg, Kathryn Haymaker, Everett W. Howe, Gretchen L. Matthews, and Anthony Várilly-Alvarado. Locally recoverable codes from algebraic curves and surfaces. In Everett W. Howe, Kristin E. Lauter, and Judy L. Walker, editors, Algebraic Geometry for Coding Theory and Cryptography, pages 95–127, Cham, 2017. Springer International Publishing. [2] Alexander Barg, Itzhak Tamo, and Serge Vlăduţ. Locally recoverable codes on algebraic curves. In 2015 IEEE International Symposium on Information Theory (ISIT), page 1252–1256. IEEE, June 2015. [3] Daniele Bartoli, Giovanni Zini, and Ferdinando Zullo. Investigating the exceptionality of scattered polynomials. Finite Fields and Their Applications, 77:101956, 2022. [4] Hannes Bartz, Lukas Holzbaur, Hedongliang Liu, Sven Puchinger, Julian Renner, and Antonia Wachter-Zeh. Rank-metric codes and their applications. Foundations and Trends® in Communications and Information Theory, 19(3):390–546, 2022. [5] Luca Bastioni, Mohamed O. Darwish, and Giacomo Micheli. Optimal rank-metric codes with rank-locality from drinfeld modules, 2024. [6] Martino Borello and Martin Scotti. Rank-metric intersecting codes. In Proceedings of the Fourteenth International Workshop on Coding and Cryptography, Paris, France, June 2026. WCC 2026, extended abstract. [7] Eimear Byrne, Alessandro Neri, Alberto Ravagnani, and John Sheekey. Tensor representation of rank-metric codes. SIAM Journal on Applied Algebra and Geometry, 3(4):614–643, 2019. [8] Eimear Byrne and Alberto Ravagnani. Covering radius of matrix codes endowed with the rank metric. SIAM Journal on Discrete Mathematics, 31(2):927–944, 2017. [9] Philippe Delsarte. Bilinear forms over a finite field, with applications to coding theory. Journal of combinatorial theory, Series A, 25(3):226–241, 1978. 25

[10] Ernest Mukhamedovich Gabidulin. Theory of codes with maximum rank distance. Problemy Peredachi Informatsii, 21(1):3–16, 1985. [11] Parikshit Gopalan, Cheng Huang, Huseyin Simitci, and Sergey Yekhanin. On the locality of codeword symbols. IEEE Trans. Inf. Theor., 58(11):6925–6934, November 2012. [12] Elisa Gorla. Rank-metric codes. In Concise Encyclopedia of Coding Theory, pages 227–250. Chapman and Hall/CRC, 2021. [13] Junsheng Han and Luis Alfonso Lastras-Montano. Reliable memories with subline accesses. In 2007 IEEE International Symposium on Information Theory, pages 2531–2535, 2007. [14] Kathryn Haymaker, Beth Malmskog, and Gretchen L. Matthews. Locally recoverable codes with availability t⩾2 from fiber products of curves. Adv. Math. Commun., 12(2):317–336, 2018. [15] Cheng Huang, Minghua Chen, and Jin Li. Pyramid codes: Flexible schemes to trade space for access efficiency in reliable data storage systems. In Sixth IEEE International Symposium on Network Computing and Applications (NCA 2007), pages 79–86, 2007. [16] William Cary Huffman and Vera Pless. Fundamentals of Error-Correcting Codes. Cambridge University Press, 2010. [17] Lingfei Jin, Liming Ma, and Chaoping Xing. Construction of optimal locally repairable codes via automorphism groups of rational function fields. IEEE Transactions on Information Theory, 66(1):210–221, 2020. [18] Swanand Kadhe, Salim El Rouayheb, Iwan Duursma, and Alex Sprintson. Codes with locality in the rank and subspace metrics. IEEE Trans. Inf. Theor., 65(9):5454–5468, September 2019. [19] Rudolf Lidl and Harald Niederreiter. Finite Fields. Encyclopedia of Mathematics and its Applications. Cambridge University Press, 2 edition, 1996. [20] Katherine Morrison. Equivalence for rank-metric and matrix codes and automorphism groups of Gabidulin codes. IEEE Transactions on Information Theory, 60(11):7035–7046, 2014. [21] Carlos Munuera, Wanderson Tenório, and Fernando Torres. Locally recoverable codes from algebraic curves with separated variables. Adv. Math. Commun., 14(2):265–278, 2020. [22] Alessandro Neri. Algebraic theory of rank-metric codes : representations, invariants and density results. PhD thesis, University of Zurich, 2019. [23] Oystein Ore. On a special class of polynomials. Transactions of the American Mathematical Society, 35(3):559–584, 1933. [24] Dimitris S. Papailiopoulos and Alexandros G. Dimakis. Locally repairable codes. In 2012 IEEE International Symposium on Information Theory Proceedings, pages 2771–2775, 2012. [25] N. Prakash, Govinda M. Kamath, V. Lalitha, and P. Vijay Kumar. Optimal linear codes with a local-error-correction property. In 2012 IEEE International Symposium on Information Theory Proceedings, pages 2776–2780, 2012. [26] Alberto Ravagnani. Rank-metric codes and their duality theory. Designs, Codes and Cryptography, 80:197–216, 2015. [27] Ankit Singh Rawat, Onur Ozan Koyluoglu, Natalia Silberstein, and Sriram Vishwanath. Optimal locally repairable and secure codes for distributed storage systems. IEEE Transactions on Information Theory, 60(1):212–236, 2014. [28] Steven Roman. Advanced Linear Algebra. Springer-Verlag, New York, NY, third edition, 2007. [29] Cecilia Salgado, Anthony Várilly-Alvarado, and Jose Felipe Voloch. Locally recoverable codes on surfaces. IEEE Transactions on Information Theory, 67(9):5765–5777, 2021. [30] Natalia Silberstein, Ankit Singh Rawat, O. Ozan Koyluoglu, and Sriram Vishwanath. Optimal locally repairable codes via rank-metric codes. In 2013 IEEE International Symposium on Information Theory, pages 1819–1823, 2013. [31] Natalia Silberstein, Ankit Singh Rawat, and Sriram Vishwanath. Error-correcting regenerating and locally repairable codes via rank-metric codes. IEEE Transactions on Information Theory, 61(11):5765–5778, 2015. [32] Itzhak Tamo and Alexander Barg. A family of optimal locally recoverable codes. IEEE Transactions on Information Theory, 60(8):4661–4676, August 2014. [33] Itzhak Tamo, Alexander Barg, Sreechakra Goparaju, and Robert Calderbank. Cyclic LRC codes, binary LRC codes, and upper bounds on the distance of cyclic codes. International Journal of Information and Coding Theory, 3(4):345, 2016. [34] Itzhak Tamo, Dimitris S. Papailiopoulos, and Alexandros G. Dimakis. Optimal locally repairable codes and connections to matroid theory. IEEE Transactions on Information Theory, 62(12):6661–6671, 2016.

26