1 Introduction and motivation
Rank-metric codes are linear spaces of matrices of given size, with entries in a finite field
\(\mathbb {F}_q\). The set of
\(n\times m\) matrices over a field is a metric space when endowed with the rank metric: The distance between two matrices is the rank of their difference. Rank-metric codes were introduced by Delsarte in [
6]. Gabidulin [
9] and Roth [
16] later independently rediscovered the family of rank-metric codes, which are linear over the field extension
\(\mathbb {F}_{q^m}\). The study of rank-metric codes is motivated by their applications to linear network coding, code-based cryptography, and distributed storage.
The mathematical theory of rank-metric codes includes the study of code invariants and their bounds. Beyond the size of its elements, also called codewords, and its dimension, two basic invariants of a rank-metric code are its minimum distance and maximum rank. The minimum distance of a nonzero rank-metric code is the least rank of a nonzero matrix in the code, while its maximum rank is the maximum rank of an element of the code. The Singleton bound involves the dimension of a rank-metric code and its minimum distance, while the Anticode bound involves the dimension of a code and its maximum rank. Codes which meet the Singleton bound go under the name of Maximum Rank Distance codes (MRD codes) and were first studied by Delsarte in [
6]. Codes attaining the Anticode bound were studied by Meshulam in [
13], with a different motivation and terminology. Within coding theory, they are known as optimal anticodes. While MRD codes are of direct applied interest, optimal anticodes are mostly of theoretical interest. For example, they can be used to define the generalized weights, a family of code invariants. This was done in [
14], where the properties of optimal anticodes are studied.
For a fixed minimum distance
d, MRD codes are the rank-metric codes which have minimum distance
d and the largest dimension according to the Singleton bound. Conversely, one could fix a dimension
k and ask what are the codes of dimension
k and largest minimum distance. It turns out that, if
k is divisible by the maximum between
n and
m, these are the MRD codes. Else, they are a different family of codes, called quasi MRD codes. This last family of codes was introduced and studied in [
3].
Something similar happens for the Anticode bound: The optimal anticodes are the rank-metric codes of largest dimension, among those with a fixed maximum rank. Similarly to the case of MRD codes, the dimension of optimal anticodes is divisible by the maximum between n and m, say m. Moreover, for a fixed k divisible by m, optimal anticodes are the codes with least maximum rank, among those of dimension k. In this paper, we study the family of rank-metric codes whose dimension is not divisible by m and whose maximum rank is the least possible for codes of that dimension, according to the Anticode bound. As these are not optimal anticodes, we call them quasi optimal anticodes (qOACs).
The paper is organized as follows: In Sect.
3 we define qOACs and dually qOACs. We give a complete structural classification of dually qOACs and a partial one of qOACs. In Sect.
4 we study the generalized weights of dually qOACs and of a family of qOACs. In Sect.
5 we study their the weight distribution, while in Sect.
6 we compute the associated
q-polymatroids.
2 Preliminaries
In this section we give an introduction to rank-metric codes and state some results that we will need throughout the paper. Let q a prime power and \(\mathbb {F}_q^{ \, n \times m }\) the linear space of \(n \times m\) matrices with entries in the finite field \(\mathbb {F}_q\). Up to transposition, we may assume without loss of generality that \(n \le m\). Throughout the paper, we denote by \(e_1,\ldots ,e_\ell \) the canonical basis of \(\mathbb {F}_q^\ell \), i.e., \(e_i\) is the vector whose coordinates are all zero, except for a one in position i.
Two rank-metric codes are equivalent if there is a linear rank-preserving homomorphism mapping one code into the other.
Linear isometries of
\(\mathbb {F}_q^{ \, n \times m }\) are classified in [
11] for odd characteristic and in [
19] for characteristic equal to 2.
Further we define the dual of a rank-metric code \({\mathcal {C}}\) using the standard scalar product for matrices.
For a matrix \(M\in \mathbb {F}_q^{ \, n \times m }\) \(\text{ colsp }(M)\subseteq \mathbb {F}_q^n\) denotes the \(\mathbb {F}_q\)-linear space generated by the columns of M and \(\text{ rowsp }(M) \subseteq \mathbb {F}_q^m\) the \(\mathbb {F}_q\)-linear space generated by the rows of M.
Notice that whenever we want to refer to the matrix space supported by a certain row space we will consider the transposed version of the support given in Definition
2.5.
An important role in the motivation of this paper is taken by deriving bounds on rank-metric codes. In the sequel we give two of the most relevant inequalities, one relating the minimum distance and one relating the maximum rank to the dimension of a rank-metric code.
The
Singleton-like bound for rank-metric codes was presented by Delsarte in [
6]. It is the rank-metric version of the well-known Singleton bound in the Hamming metric. Codes meeting bound (
1) are known as
Maximum Rank Distance Codes (MRD codes) and have been extensively studied.
We shall present now an upper bound on the dimension involving the maximum rank, instead of the minimum distance as seen in (
1). A classical theorem by Flanders in [
8] states that the dimension of a linear space of matrices whose rank is less than or equal to a given
\(r \le n\) is upper bounded by
mr. The results in [
8] are proved under the assumption that the cardinality of the base field is strictly greater than
r and that the characteristic differs from 2. Atkinson and Lloyd in [
1] obtained the same result with the assumption only on the field size. The square case with
\(r = n-1\) for an arbitrary field size was proved by Dieudonné in [
7]. Finally, Meshulam in [
13] showed that the assumptions on the rank and on the field size are unnecessary for deriving the bound on the dimension. In fact, the next bound was proved in [
13] and goes under the name of
Anticode bound.
The classification of matrix spaces with least possible maximum rank for a given dimension follows the same history as the derivation of the Anticode Bound and is presented in the next theorem.
Some fundamental properties of optimal anticodes are stated in [
15], for instance that
\({\mathcal {C}}\) is an optimal anticode if and only if
\(\mathcal {C}^\perp \) is an optimal anticode.
In the end we want to introduce q-polymatroids, which are the q-analogue of polymatroids.
3 Quasi optimal and dually quasi optimal anticodes
It is well-known that the dual of an optimal anticode is an optimal anticode. However, this is not the case for qOACs. In the next example, we produce dually qOACs, as well as qOACs which are not dually qOACs.
The next proposition relates the maximum rank of a code with that of its dual. It also provides us with a simple characterization of dually qOACs.
A first classification of large matrix spaces of bounded rank appears in [
1], where Atkinson and Lloyd study linear spaces of dimension close to
mr over fields of large cardinality. Their classification was extended to all fields and matrices of arbitrary size by de Seguins Pazzis in [
4]. As a direct consequence of the results by de Seguins Pazzis, we can characterize the qOACs whose dimension is at least
\(\alpha (m-1)+n\).
Using Theorem
3.5, we can classify dually qOAs.
Theorems
3.5 and
3.6 provide us with many examples of codes which are qOACs but not dually qOACs. In fact, any code as in Theorem
3.5 which is not one of the codes in Theorem
3.6 is of this kind. We now give some concrete examples of qOACs which are not dually qOACs. These examples are covered by Theorem 2.5, unless
\(m=n\) and
\(\rho =n-\alpha -1\).
If
\(\mathcal {C}\) is a qOAC of dimension
\(\dim ({\mathcal {C}}) = \alpha m + \rho \) and
\(\text{ maxrk }(\mathcal {C})=\alpha +1\), then
\(\mathcal {C}\) cannot be equivalent to a subspace of
\(\text{ Mat }(\langle e_1,\ldots ,e_s\rangle )+\text{ Mat }(\langle e_1,\ldots ,e_k\rangle )^t\) for any
\(s,k\ge 0\) with
\(s+k\le \alpha \). Lemma 1 in [
8] shows that, up to equivalence,
\(\mathcal {C}\) is contained in
\(\text{ Mat }(\langle e_1,\ldots ,e_{\alpha +1}\rangle )+\text{ Mat }(\langle e_1,\ldots ,e_{\alpha +1}\rangle )^t\). Theorems
3.5 and
3.8 prove that, under some assumptions on
\(\rho \),
\(\mathcal {C}\) is equivalent to a subspace of
\(\text{ Mat }(\langle e_1,\ldots ,e_s\rangle )+\text{ Mat }(\langle e_1,\ldots ,e_{\alpha +1-s}\rangle )^t\). In the next example, we exhibit a code which does not satisfy the assumptions of Theorems
3.5 or
3.8 and which is not equivalent to a subspace of
\(\text{ Mat }(\langle e_1,\ldots ,e_s\rangle )+\text{ Mat }(\langle e_1,\ldots ,e_{\alpha +1-s}\rangle )^t\) for any
\(0\le s\le \alpha +1\). The example is based on [
13, Remark on pg. 228].
In the sequel, we concentrate on linear spaces of the form \(\text{ Mat }(\langle e_1,\ldots ,e_s\rangle )+\text{ Mat }(\langle e_1,\ldots ,e_k\rangle )^t\), as well as some of their linear subspaces.
In the rest of the paper, we compute the invariants of the codes from Definition
3.10. In the next proposition, we characterize which codes of the form
\({\mathcal {C}}_{s,h,k}\) are qOACs. Together with Theorem
3.6, Proposition
3.12 yields examples of qOACs which are not dually qOACs, beyond those of Example
3.7. Some examples of this kind are given in Example
3.13.
In the following sections, we compute the invariants of the codes from Definition
3.10. We always assume that
\(n=s+h\), since this does not affect the computation of the invariants. This amounts to considering the codes
\(C_{s,k,n-s}=\text{ Mat }(\langle e_1,\ldots ,e_s\rangle )+\text{ Mat }(\langle e_1,\ldots ,e_k\rangle )^t\).
4 Generalized weights
In this section we compute the generalized weights of codes of the form
\(\text{ Mat }(\langle e_1,\ldots ,e_s\rangle )+\text{ Mat }(\langle e_1,\ldots ,e_k\rangle )^t\). All dually qOACs and almost all qOACs are of this form by Theorems
3.5 and
3.6. We start by recalling the definition of generalized weights.
Generalized weights were defined in [
14], where some of their basic properties were also established. A different, but related, definition of generalized weights was given in [
12].
We start with a simple result, which will be used in the proof of Theorem
4.3.
We are now ready to state the main theorem of this section. This theorem computes the generalized weights of all dually qOACs and of almost all qOACs.
6 Associated q-polymatroids
q-polymatroids are the
q-analogs of polymatroids. They were introduced indipendently by Shiromoto in [
17] and by Gorla, Jurrius, López Valdez, and Ravagnani in [
10]. In this section we compute the rank functions of the
q-polymatroids associated to codes of the form
\(\text{ Mat }(\langle e_1,\ldots ,e_s\rangle )+\text{ Mat }(\langle e_1,\ldots ,e_k\rangle )^t\). By Lemma
6.4 this determines the
q-polymatroids associated to all dually qOACs and to certain qOACs.
We start by recalling the relevant definitions. The fact that the functions
\(\rho _c\) and
\(\rho _r\) define
q-polymatroids is shown in [
10, Theorem 5.3].
The next proposition follows directly from the definition of the rank functions.
The next lemmas will be used in the proof of Theorem
6.5.
The proof of the next lemma is immediate.
The next theorem is the main result of this section. We compute the rank functions of the q-polymatroids associated to a quasi-optimal anticode.
Publisher's Note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.