arXiv:1710.02067v1 [] 5 Oct 2017

Codes Endowed With the Rank Metric

Elisa Gorla
Institut de Mathématiques
Université de Neuchâtel, Switzerland
elisa.gorla@unine.ch
Alberto Ravagnani
Department of Electrical and Computer Engineering
University of Toronto, Canada
ravagnani@ece.utoronto.ca

Abstract
We review the main results of the theory of rank-metric codes, with emphasis on their combinatorial properties. We study their duality theory and MacWilliams identities, comparing
in particular rank-metric codes in vector and matrix representation. We then investigate the
combinatorial structure of MRD codes and optimal anticodes in the rank metric, describing
how they relate to each other.

Introduction
A q-ary rank-metric code is a set of matrices over Fq equipped with the rank distance, which
measures the rank of the difference of a pair of matrices. Rank-metric codes were first studied
in [3] by Delsarte for combinatorial interest.
More recently, codes endowed with the rank metric have been re-discovered for error correction in the context of linear network coding, and featured prominently in the coding theory
literature.
In linear network coding, a source attempts to transmit information packets to multiple
destinations via a network of intermediate nodes. The nodes compute and forward in the
direction of the sinks linear functions of the received packets, rather than simply routing them.
In [1, 9] it was shown that linear network coding achieves the optimal multicast throughput
over sufficiently large alphabets.
Rank-metric codes were proposed in [8, 18] for end-to-end error correction in noisy and
adversarial networks. In this context, as shown in [17], the correction capability of a rankmetric code is measured by a fundamental parameter, called the minimum rank distance of
the code.

1

In this work we survey the main results of the mathematical theory of rank-metric codes,
with emphasis on their combinatorial structure.
In Section 1 we introduce the most important parameters of a rank-metric code, namely,
the minimum distance, the weight distribution, and the distance distribution. We then define
the trace-dual of a linear rank-metric code, and compare the duality theories of codes in matrix
and vector representation. In particular, we show that the former generalizes the latter.
Section 2 is devoted to the duality theory of codes endowed with the rank metric. We
study how combinatorial properties of a linear code relate to combinatorial properties of the
dual code. In particular, we show that the weight distribution of a linear code and the weight
distribution of its dual code determine each other via a MacWilliams-type transformation. We
also show an application of the MacWilliams identities for the rank metric to an enumerative
combinatorics problem.
In Section 3 we study codes that have the largest possible cardinality for their parameters.
These are called Maximum Rank Distance codes (MRD in short) and have very remarkable
properties. We first show the existence of linear MRD codes for all choices of the parameters
and of the field size. Then we prove that the dual of a linear MRD code is MRD. Finally, we
show that the distance distribution of a (possibly non-linear) rank-metric code is completely
determined by its parameters.
Section 4 is devoted to rank-metric anticodes, i.e., sets of matrices where the distance
between any two of them is bounded from above by a given integer. We study how codes and
anticodes relate to each other, deriving in particular an upper bound for the cardinality of any
anticode of given parameters. We conclude the section showing that the dual of an optimal
linear anticode is an optimal anticode.

1

Rank-metric codes

In the sequel q denotes a fixed prime power, and Fq the finite field with q elements. Moreover,
k and m denote positive integers with k ≤ m without loss of generality, and Fqk×m is the space
of k × m matrices over Fq . Finally, for given integers a, b ∈ N we denote by
 
a
b q
the q-ary binomial coefficient of a and b, which counts the number of b-dimensional subspaces
of an a-dimensional space over Fq . See e.g. [19, Section 1.7] for details.
Definition 1. The rank distance is the function d : Fqk×m ×Fqk×m → N defined by d(M, N ) =
rk(M − N ) for all M, N ∈ Fqk×m .
It is easy to check that d is indeed a distance function on Fqk×m .
Definition 2. A (rank-metric) code over Fq is a non-empty subset C ⊆ Fqk×m . When
|C| ≥ 2, the minimum distance of C is the positive integer
d(C) = min{d(M, N ) | M, N ∈ C, M 6= N }.
A code C is linear if it is an Fq -linear subspace of Fqk×m . In this case its dual code is defined
as
C ⊥ = {N ∈ Fqk×m | Tr(M N t ) = 0 for all M ∈ C} ⊆ Fqk×m ,
where Tr(·) denotes the trace of a square k × k matrix.
The map (M, N ) → Tr(M N t ) ∈ Fq is a scalar product on Fqk×m , i.e., it is symmetric,
bilinear and non-degenerate. In particular, the dual of a linear code is a linear code of
dimension
dim(C ⊥ ) = km − dim(C).
Other fundamental parameters of a rank-metric code are the following.

2

Definition 3. The weight distribution and the distance distribution of a code C are
the collections {Wi (C) | i ∈ N} and {Di (C) | i ∈ N} respectively, where
Di (C) = 1/|C| · |{(M, N ) ∈ C 2 | d(M, N ) = i}|

Wi (C) = |{M ∈ C | rk(M ) = i}|,
for all i ∈ N.

If C is a linear code, then for all P ∈ C there are precisely |C| pairs (M, N ) ∈ C 2 such that
M − N = P . Therefore
X
Di (C) = 1/|C| ·
|{(M, N ) ∈ C 2 | M − N = P }| = Wi (C)
P ∈C
rk(P )=i

for all i ∈ N. Moreover, if |C| ≥ 2 then d(C) = min{rk(M ) | M ∈ C, M 6= 0}.
In [5], Gabidulin proposed independently a different notion of rank-metric code, in which
the codewords are vectors with entries from an extension field Fqm rather than matrices over
Fq .
Definition 4. The rank of a vector v = (v1 , ..., vk ) ∈ Fkqm is the dimension of the linear
spaces generated over Fq by its entries, i.e., rkG (v) = dimFq hv1 , ..., vk i. The rank distance
between vectors v, w ∈ Fkqm is dG (v, w) = rkG (v − w).
One can check that dG is a distance function on Fkqm .
Definition 5. A vector rank-metric code over Fqm is a non-empty subset C ⊆ Fkqm . When
|C| ≥ 2, the minimum distance of C is the positive integer
dG (C) = min{dG (v, w) | v, w ∈ C, v 6= w}.
The code C is linear if it is an Fqm -linear subspace of Fkqm . In this case the dual of C is
defined as
)
(
k
X
⊥
k
vi wi = 0 for all v ∈ C ⊆ Fkqm .
C = w ∈ Fq m |
i=1

The map (v, w) 7→ vi wi is an Fqm -scalar product on Fkqm . Therefore for all linear vector
rank-metric codes C ⊆ Fkqm we have
P

dimFqm (C ⊥ ) = k − dimFqm (C).
Definition 6. The weight distribution and the distance distribution of a vector rankmetric code C are the integer vectors (Wi (C) | i ∈ N) and (Di (C) | i ∈ N) respectively,
where
Wi (C) = |{v ∈ C | rkG (v) = i}|,

Di (C) = 1/|C| · |{(v, w) ∈ C 2 | dG (v, w) = i}|

for all i ∈ N.
There exists a natural way to associate to a vector rank-metric code a code in matrix
representation with the same cardinality and metric properties.
Definition 7. Let Γ = {γ1 , ..., γm } be a basis of Fqm over Fq . The matrix associated to a
vector v ∈ Fkqm with respect to Γ is the k × m matrix Γ(v) with entries in Fq defined by
vi =

m
X

Γ(v)ij γj

for all i = 1, ..., k.

j=1

The rank-metric code associated to a vector rank-metric code C ⊆ Fkqm with respect to Γ is
Γ(C) = {Γ(v) | v ∈ C} ⊆ Fqk×m .

3

Notice that in the previous definition the i-th row of Γ(v) is the expansion of the entry vi
over the basis Γ.
The proof of the following result is standard and left to the reader.
Proposition 8. For every Fq -basis Γ of Fqm the map v 7→ Γ(v) is an Fq -linear bijective
isometry (Fkqm , dG ) → (Fqk×m , d).
In particular, if C ⊆ Fkqm is a vector rank-metric code, then Γ(C) has the same cardinality,
rank distribution and distance distribution as C. Moreover, if |C| ≥ 2 then dG (C) = d(Γ(C)).
In the remainder of the section we compare the duality theories of matrix and vector rankmetric codes, showing that the former generalizes the latter. The following results appear
in [12].
Given an Fqm -linear vector rank-metric code C ⊆ Fkqm and a basis Γ of Fqm over Fq , it is
natural to ask whether the codes Γ(C ⊥ ) and Γ(C)⊥ coincide or not. The answer is negative
in general, as we show in the following example.
Example 9. Let q = 3, k = m = 2 and F32 = F3 [η], where η is a root of the irreducible
primitive polynomial x2 + 2x + 2 ∈ F3 [x]. Let ξ = η 2 , so that ξ 2 + 1 = 0. Set α = (ξ, 2),
and let C ⊆ F232 be the 1-dimensional vector rank-metric code generated by α over F32 . Take
Γ = {1, ξ} as basis of F32 over F3 . One can check that Γ(C) is generated over F3 by the two
matrices




0 1
−1 0
Γ(α) =
,
Γ(ξα) =
.
2 0
0 2
Let β = (ξ, 1) ∈ F232 . We have α1 β1 + α2 β2 = 1 6= 0, and so β ∈
/ C ⊥ . It follows Γ(β) ∈
/ Γ(C ⊥ ).
On the other hand,


0 1
Γ(β) =
,
1 0
and it is easy to see that Γ(β) is trace-orthogonal to both Γ(α) and Γ(ξα). Therefore Γ(β) ∈
Γ(C)⊥ , hence Γ(C)⊥ 6= Γ(C ⊥ ).
Although the duality notions for matrix and vector rank-metric codes do not coincide,
there is a simple relation between them via orthogonal bases of finite fields.
m−1
for all
Let Trace : Fqm → Fq be the map defined by Trace(α) = α + αq + · · · + αq
′
} of Fqm over Fq are called orthogonal
α ∈ Fqm . Bases Γ = {γ1 , ..., γm } and Γ′ = {γ1′ , ..., γm
if Trace(γi′ γj ) = δij for all i, j ∈ {1, ..., m}. It is well-known that every basis Γ of Fqm over Fq
has a unique orthogonal basis Γ′ (see [10], page 54).
Theorem 10. Let C ⊆ Fkqm be an Fqm -linear vector rank-metric code, and let Γ, Γ′ be
orthogonal bases of Fqm over Fq . We have
Γ′ (C ⊥ ) = Γ(C)⊥ .
In particular, C has the same weight distribution as Γ(C), and C ⊥ has the same weight
distribution as Γ(C)⊥ .
′
}. Let M ∈ Γ′ (C ⊥ ) and N ∈ Γ(C). There
Proof. Write Γ = {γ1 , ..., γm } and Γ′ = {γ1′ , ..., γm
⊥
′
exist α ∈ C and β ∈ C such that M = Γ (α) and N = Γ(β). By Definition 7 we have

0 =

k
X

αi βi =

i=1

m
k X
X
i=1 j=1

Mij γj′

m
X

Nit γt =

t=1

m
m X
k X
X

Mij Nit γj′ γt .

i=1 j=1 t=1

Applying the function Trace : Fqm → Fq to both sides of equation (10) we obtain


k X
m X
m
k X
m X
m
X
X
0 = Trace 
Mij Nit Trace(γj′ γt ) = Tr(M N t ).
Mij Nit γj′ γt  =
i=1 j=1 t=1

i=1 j=1 t=1

4

(1)

Therefore Γ′ (C ⊥ ) ⊆ Γ(C)⊥ . Proposition 8 implies that Γ′ (C ⊥ ) and Γ(C)⊥ have the same
dimension over Fq . Hence the two codes are equal. The second part of the statement follows
from Proposition 8.
Theorem 10 shows that the duality theory of Fq -linear rank-metric codes in matrix representation can be regarded as a generalization of the duality theory of Fqm -linear vector
rank-metric codes. For this reason, in the sequel we only treat rank-metric codes in matrix
representation.

2

MacWilliams identities for the rank metric

This section is devoted to the duality theory of codes endowed with the rank metric. We
concentrate on linear rank-metric codes, and show that the weight distributions of a code
C and its dual code C ⊥ determine each other via a MacWilliams-type transformation. This
result was established by Delsarte in [3, Theorem 3.3] using the machinery of association
schemes, and may be regarded as the rank-analogue of a celebrated theorem by MacWilliams
on the weight distribution of linear codes endowed with the Hamming metric (see [11]). In
this section we present a lattice-theoretic proof inspired by [13, Theorem 27].
Notation 11. We denote by colsp(M ) ⊆ Fkq the Fq -space generated by the columns of a
matrix M ∈ Fqk×m . Given a code C ⊆ Fqk×m and an Fq -subspace U ⊆ Fkq , we let
C(U ) = {M ∈ C | colsp(M ) ⊆ U } ⊆ Fqk×m
be the set of matrices in C whose columnspace is contained in U .
Note that for all M, N ∈ Fqk×m we have colsp(M + N ) ⊆ colsp(M ) + colsp(N ). As a
consequence, if U ⊆ Fkq is an Fq -linear subspace and C ⊆ Fqk×m is a linear code, then C(U ) is
a linear code as well.
We start with a series of preliminary results. In the sequel we denote by U ⊥ the orthogonal
(or dual) of an Fq -vector space U ⊆ Fkq with respect to the standard inner product of Fkq . It
will be clear from context if by “⊥” we denote the trace-dual in Fqk×m or the standard dual
in Fkq .
Lemma 12. Let U ⊆ Fkq be a subspace. The following hold.
1. dim(Fqk×m (U )) = m · dim(U ).
2. Fqk×m (U )⊥ = Fqk×m (U ⊥ ).
Proof.
1. Let s = dim(U ) and V = {(x1 , ..., xk ) ∈ Fkq | xi = 0 for i > s} ⊆ Fkq . There exists
an Fq -isomorphism g : Fkq → Fkq that maps U to V . Let G ∈ Fqk×k be the invertible
matrix associated to g with respect to the canonical basis {e1 , ..., ek } of Fkq , i.e.,
g(ej ) =

k
X

Gij ei

for all j = 1, ..., k.

i=1

The map M 7→ GM is an Fq -isomorphism Fqk×m (U ) → Fqk×m (V ). Property 1 of the
lemma now directly follows from the definition of Fqk×m (V ).
2. Let N ∈ Fqk×m (U ⊥ ) and M ∈ Fqk×m (U ). Using the definition of trace-product one
Pm
sees that Tr(M N t ) = i=1 hMi , Ni i, where h·, ·i is the standard inner product of Fkq ,
and Mi , Ni denote the i-th column of M and N (respectively). Each column of N
belongs to U ⊥ , and each column of M belongs to U . Therefore Tr(M N t ) = 0, hence
Fqk×m (U ⊥ ) ⊆ Fqk×m (U )⊥ . By property 1, the two spaces Fqk×m (U ⊥ ) and Fqk×m (U )⊥ have
the same dimension over Fq . Therefore they are equal.

5

The following result is [12, Lemma 28].
Proposition 13. Let C ⊆ Fqk×m be a linear code, and let U ⊆ Fkq be a subspace of dimension
u over Fq . Then
|C|
|C(U )| = m(k−u) |C ⊥ (U ⊥ )|.
q
Proof. We have C(U )⊥ = (C ∩ Fqk×m (U ))⊥ = C ⊥ + Fqk×m (U )⊥ = C ⊥ + Fqk×m (U ⊥ ), where the
last equality follows from part 2 of Lemma 12. Therefore
|C(U )| · |C ⊥ + Fqk×m (U ⊥ )| = q km .

(2)

On the other hand, part 1 of Lemma 12 gives
dim(C ⊥ + Fqk×m (U ⊥ )) = dim(C ⊥ ) + m · dim(U ⊥ ) − dim(C ⊥ (U ⊥ )).
As a consequence,
q km · q m(k−u)
.
|C| · |C ⊥ (U ⊥ )|
Combining equations (2) and (3) one obtains the proposition.
|C ⊥ + Fqk×m (U ⊥ )| =

(3)

We will also need the following preliminary lemma, which is an explicit version of the
Möbius inversion formula for the lattice of subspaces of Fkq . We include a short proof for
completeness. See [19, Sections 3.7 – 3.10] for details.
Lemma 14. Let P(Fkq ) be the set of all Fq -subspaces of Fkq , and let f : P(Fkq ) → Z be
P
any function. Define g : P(Fkq ) → Z by g(V ) = U⊆V f (U ) for all V ⊆ Fkq . Then for all
i ∈ {0, ..., k} and for any subspace V ∈ P(Fkq ) with dim(V ) = i we have
f (V ) =

i
X

i−u
2

(−1)i−u q (

)

u=0

X

g(U ).

U⊆V
dim(U)=u

Proof. Fix an integer i ∈ {0, ..., k} and a vector space V ∈ P(Fkq ) with dim(V ) = i. We
inductivelyPdefine a function µ : {U ∈ P(Fkq ) | U ⊆ V } → Z by µ(U ) = 1 if U = V , and
µ(U ) = − U(S⊆V µ(S) if U ( V . By definition of g we have
X
X
X
X
X
µ(U )g(U ) =
µ(U )
f (S) =
f (S)
µ(U ) = f (V ),
U⊆V

U⊆V

S⊆U

S⊆V

S⊆U⊆V

where the last equality immediately follows from the definition of µ. Therefore it suffices to
show that for all U ⊆ V we have
µ(U ) = (−1)i−u q (

i−j
2

),

(4)

where u = dim(U ). We proceed by induction on i − u. If i = u then equation (4) is trivial.
Now assume i > u. By definition of µ and the induction hypothesis we have


i
X
X
i−j
i−s i−s
µ(U ) = −
µ(S) = −
(−1) q ( 2 )
s−u q
s=u+1

U(S⊆V

=

−

i
X

i−s

(−1)

s=u+1

=

−

i−u
X
s=0

=

i−s
2

q(



) i−u
i−s q



s
i−u
i−u i−u
)
(
2
(−1) q
+ (−1) q ( 2 )
s q

i−u

(−1)

s

i−u
2

q(

),

where the last equality follows from the q-Binomial Theorem (see [19], page 74).

6

We can now prove the main result of this section, first established by Delsarte in [3,
Theorem 3.3]. A proof for the special case of Fqm -linear vector rank-metric codes using
different techniques can be found in [6].
Theorem 15 (MacWilliams identities for the rank metric). Let C ⊆ Fqk×m be an linear
rank-metric code. For all i ∈ {0, ..., k} we have
Wi (C ⊥ ) =


 

k
k
X
i−u
1 X
k−u
k−j
i−u
Wj (C)
(−1) q mu+( 2 )
.
k−i q
u q
|C| j=0
u=0

Proof. For all subspaces V ⊆ Fkq define
f (V ) = |{M ∈ C ⊥ | colsp(M ) = V }|,

g(V ) =

X

f (U ) = |C ⊥ (V )|.

U⊆V

By Lemma 14, for any i ∈ {0, ..., k} and for any vector space V ⊆ Fkq of dimension i we have
f (V ) =

i
X

(−1)i−u q (

i−u
2

)

u=0

=

i
X

|C ⊥ (U )|

U⊆V
dim(U)=u
i−u

(−1)

q(

)

i−u
2

u=0

=

X

X

|C ⊥ (T ⊥ )|

T ⊆Fk
q
T ⊇V ⊥
dim(T )=k−u

i
i−u
1 X
i−u
(−1) q mu+( 2 )
|C| u=0

X

|C(T )|,

T ⊆Fk
q
⊥

T ⊇V
dim(T )=k−u

where the last equality follows from Proposition 13. Now observe that
X
f (V )
Wi (C ⊥ ) =
V ⊆Fk
q
dim(V )=i

=

=

=

i
i−u
1 X
(−1)i−u q mu+( 2 )
|C| u=0

i
i−u
1 X
i−u
(−1) q mu+( 2 )
|C| u=0

X

X

⊆Fk
q

V
dim(V )=i

|C(T )|

T ⊆Fk
q
⊥

T ⊇V
dim(T )=k−u

X

T ⊆Fk
q
dim(T )=k−u



i
i−u
1 X
k−u
i−u
(−1) q mu+( 2 )
i−u q
|C| u=0

X

|C(T )|

⊆Fk
q
⊥

V
V ⊇T
dim(V )=i

X

|C(T )|.

T ⊆Fk
q
dim(T )=k−u

On the other hand,
X

|C(T )| =

X

T ⊆Fk
q

T ⊆Fk
q

dim(T )=k−u

dim(T )=k−u

k−u
X
j=0

7

X

S⊆T
dim(S)=j

|{M ∈ C | colsp(M ) = S}|

(5)

k−u
X

=

X

j=0

|{M ∈ C | colsp(M ) = S}|

S⊆Fk
q

T ⊆Fk
q

dim(S)=j

T ⊇S
dim(T )=k−u

k−u
X

=

X

j=0

k−j
u



Wj (C).

(6)

q

Combining equations (5) and (6) one obtains the desired result.
Example 16. Let q = 2, k = 2, m = 3. Let
generated over F5 ∼
= Z/5Z by the matrices


1 0 2
,
0 2 4

C ⊆ Fqk×m be the 2-dimensional linear code


2
1


3 0
.
4 0

We have W0 (C) = 1, W1 (C) = 8 and W2 (C) = 16. Applying Theorem 15 one can easily
compute W0 (C ⊥ ) = 1, W1 (C ⊥ ) = 65 and W2 (C) = 560. Observe that C ⊥ has dimension
6 − 2 = 4, and that 1 + 64 + 560 = 625 = 54 , as expected.
We now present a different formulation of the MacWilliams identities for the rank metric.
The following result is [12, Theorem 31].
Theorem 17. Let C ⊆ Fqk×m be a linear code. For all 0 ≤ ν ≤ k we have
k−ν
X
i=0



ν
|C| X
k−j
⊥
Wj (C )
.
ν−j q
q mν j=0




k−i
Wi (C)
=
ν q

Proof. Proposition 13 gives
X

|C(U )|

|C|
q mν

=

U⊆Fk
q

|C(U )| =

|C ⊥ (U )|.

(7)

U⊆Fk
q
dim(U)=ν

dim(U)=k−ν

Observe that
X

X

|{(U, M ) | U ⊆ Fkq , dim(U ) = k − ν, M ∈ C, colsp(M ) ⊆ U }|

U⊆Fk
q
dim(U)=k−ν

=

X

|{U ⊆ Fkq , dim(U ) = k − ν, colsp(M ) ⊆ U }|

M∈C

=

k
X

X

|{U ⊆ Fkq , dim(U ) = k − ν, colsp(M ) ⊆ U }|

rk(M)=i

k
X

X



i=0

=

i=0

M∈C

M∈C
rk(M)=i




k−ν
X
k−i
k−i
Wi (C)
.
=
ν q
k−ν −i q

(8)

i=0

Using the same argument with C ⊥ and k − ν one shows that
X

U⊆Fk
q
dim(U)=ν

⊥

|C (U )| =

k−ν
X
j=0



k−j
Wj (C )
ν −j
⊥

The result now follows combining equations (7), (8) and (9).

8



q

.

(9)

Remark 18. The two formulations of the MacWilliams identities for the rank metric given in
Theorems 15 and 17 are equivalent. See [6, Corollary 1 and Proposition 3] and [12, Theorem
61] for details.
The next theorem is [2, Theorem 27], and shows that the weight distribution of a linear
code is determined by its parameters, together with the number of codewords of small weight.
We state it without proof. An application of this result will be given in Section 3 (see
Corollary 30).
Theorem 19. Let C ⊆ Fqk×m be a linear code with 1 ≤ dim(C) ≤ km − 1, minimum distance
d = d(C), and dual minimum distance d⊥ = d(C ⊥ ). Let ε = 1 if C is MRD, and ε = 0
otherwise. For all 1 ≤ i ≤ d⊥ we have
k−d
X  u  u − d⊥ + i − 1
i
Wk−d⊥ +i (C) = (−1)i q (2)
Wk−u (C)
d⊥ − i q
i−1
q
⊥
u=d

+



k
d⊥ − i



i−1−ε
X

q u=0


 

u
⊥
k − d⊥ + i
)
(
2
q dim(C)−m(d −i+u) − 1 .
(−1) q
u
q
u

In particular, k, m, t, d, d⊥ and Wd (C), . . . , Wk−d⊥ (C) completely determine the weight
distribution of C.
We conclude this section showing how MacWilliams identities for the rank metric can be
employed to solve certain enumerative problems of matrices over finite fields. The following
result is [13, Corollary 52].
Corollary 20. Let I ⊆ {(i, j) ∈ {1, ..., k} × {1, ..., m} | i = j} be a set of diagonal entries.
For all 0 ≤ r ≤ k the number of k × m matrices M over Fq having rank r and Mij = 0 for all
(i, j) ∈ I is
q −|I|



 

k
k 
X
X
r−u
|I|
k−u
k−t
(q − 1)t
(−1)r−u q mu+( 2 )
.
k−r q
u q
t
u=0
t=0

Proof. Define the linear code C = {M ∈ Fqk×m | Mij = 0 for all (i, j) ∈
/ I} ⊆ Fqk×m . Then
dim(C) = |I|, Wt (C) = 0 for |I| < t ≤ k, and
 
|I|
t
Wt (C) =
(q − 1)
t
for 0 ≤ t ≤ |I|. Moreover, C ⊥ = {M ∈ Fqk×m | Mij = 0 for all (i, j) ∈ I}. Therefore the
number of matrices M ∈ Fqk×m having rank r and Mij = 0 for all (i, j) ∈ I is precisely
Wr (C ⊥ ). The corollary now follows from Theorem 15.

3

MRD codes

In this section we study rank-metric codes that have the largest possible cardinality for their
parameters. We start with a Singleton-type bound for the cardinality of a rank-metric code
of given minimum distance. A code is called MRD if it attains the bound. We then show
that for any admissible choice of the parameters there exists a linear MRD code with those
parameters.
In the second part of the section we study general structural properties of MRD codes.
We first prove in Theorem 26 that the dual of a linear MRD code is MRD. Then we show in
Theorem 28 that the weight distribution of a possibly non-linear MRD code C ⊆ Fqk×m with
0 ∈ C is determined by k, m and d(C). As a corollary, we prove that these three parameters
completely determine the distance distribution of any MRD code. Our proofs are inspired by
the lattice-theory approach to the weight functions of coding theory proposed in [14] and [13].

9

Theorem 21 (Singleton-like bound). Let C ⊆ Fqk×m be a rank-metric code with |C| ≥ 2 and
minimum distance d. Then |C| ≤ q m(k−d+1) .
(k−d+1)×m

denote the projection on the last k − d + 1 rows. Since C has
Proof. Let π : C → Fq
minimum distance d, the map π is injective. Therefore
|C| = |π(C)| ≤ q m(k−d+1) .

A code is MRD if its parameters attain the Singleton-like bound.
Definition 22. We say that C ⊆ Fqk×m is an MRD code if |C| = 1, or |C| ≥ 2 and |C| =
q m(k−d+1) , where d = d(C).
We now prove that for any choice of q, k, m and d there exists a linear rank-metric code
C ⊆ Fqk×m that attains the bound of Theorem 21. This result was first shown by Delsarte in
[3], and rediscovered independently by Gabidulin in [5] and by Kötter and Kschischang in [8]
in the context of linear network coding.
Theorem 23. For all 1 ≤ d ≤ k there exists an Fqm -linear vector rank-metric code C ⊆ Fkqm
with dG (C) = d and dimFqm (C) = k − d + 1. In particular, there exists a linear MRD code
C ⊆ Fqk×m with d(C) = d.
We include an elegant proof for Theorem 23 from [8]. Recall that a linearized polynomial p over Fqm is a polynomial of the form
s

2

p(x) = α0 x + α1 xq + α2 xq + · · · + αs xq ,

αi ∈ Fqm , i = 0, ..., s.

The degree of p, denoted by deg(p), is the largest integer i ≥ 0 such that αi 6= 0. The Fqm vector space of linearized polynomials over Fqm of degree at most s is denoted by Linq (m, s).
It is easy to see that dimFqm (Linq (m, s)) = s + 1.
Remark 24. The roots of a linearized polynomial p over Fqm form an Fq -vector subspace of
Fqm (see [10], Theorem 3.50), which we denote by V (p) ⊆ Fqm in the sequel. Clearly, for any
non-zero linearized polynomial p we have dimFq V (p) ≤ deg(p) by the Fundamental Theorem
of Algebra.
Proof of Theorem 23. Let E = {β1 , ..., βk } ⊆ Fqm be a set of Fq -independent elements. These
elements exist as k ≤ m by assumption. Define the Fqm -linear map
evE : Linq (m, k − d) → Fkqm ,

evE (p) = (p(β1 ), ..., p(βk )) for p ∈ Linq (m, k − d).

We claim that C = evE (Linq (m, k − d)) ⊆ Fkqm is a vector rank-metric code with the desired
properties.
Clearly, C is Fqm -linear. Now let p ∈ Linq (m, k − d) be a non-zero linearized polynomial,
and let W ⊆ Fqm denote the space generated over Fq by the evaluations p(β1 ), ..., p(βk ).
The polynomial p induces an Fq -linear evaluation map p : hβ1 , ..., βk iFq → Fqm . The image
of p is W , and therefore by the rank-nullity theorem we have dimFq (W ) = k − dimFq V (p).
By Remark 24 we conclude dimFq (W ) ≥ k − (k − d) = d. This shows that dG (C) ≥ d. In
particular, as d ≥ 1, the map evE is injective, and the dimension of C is dimFqm (C) = k−d+1.
Combining Proposition 8 and Theorem 21 we obtain dG (C) = d.
The second part of the theorem immediately follows from Proposition 8.
The MRD code construction in the proof of Theorem 23 was later generalized by Sheekey
in [15], introducing a new class of MRD codes.
The reminder of the section is devoted to the structural properties of MRD codes. We
start with a preliminary result from [14, Chapter 7].

10

Lemma 25. Let C ⊆ Fqk×m be an MRD code with |C| ≥ 2 and minimum distance d. For all
subspaces U ⊆ Fkq with u = dim(U ) ≥ d − 1 we have
|C(U )| = q m(u−d+1) .
Proof. As in Lemma 12, define the space V = {(x1 , ..., xk ) ∈ Fkq | xi = 0 for i > u} ⊆ Fkq .
Let g : Fkq → Fkq be an Fq -isomorphism with f (U ) = V . Denote by G ∈ Fqk×k the matrix
associated to g with respect to the canonical basis of Fkq . Define the rank-metric code D =
GC = {GM | M ∈ C}. Clearly, D has the same dimension and minimum distance as C. In
particular, it is MRD. Observe moreover that C(U ) = D(V ).
Now consider the maps
π

π

2
1
,
−→
F(k−u)×m
F(k−d+1)×m
D −→
q
q

where π1 is the projection on the last k − d + 1 coordinates, and π2 is the projection on
the last k − u coordinates. Since d(D) = d, π1 is injective. Since D is MRD, we have
logq (|D|) = m(k − d + 1). Therefore π1 is bijective. The map π2 is Fq -linear and surjective.
Therefore
(k−u)×m
|π2−1 (0)| = |π2−1 (M )| = q m(u−d+1) for all M ∈ Fq
.
Since π1 is bijective and π2 is surjective, the map π = π2 ◦ π1 is surjective. Moreover,
(k−u)×m

|π −1 (0)| = |π −1 (M )| = q m(u−d+1) for all M ∈ Fq

.

The lemma now follows from the identity C(U ) = D(V ) = π −1 (0).
We can now show that the dual of a linear MRD code is MRD. The next fundamental
result is [13, Theorem 5.5].
Theorem 26. Let C ⊆ Fqk×m be a linear MRD code. Then C ⊥ is MRD.
Proof. The result is immediate if dim(C) ∈ {0, km}. Assume 1 ≤ dim(C) ≤ km − 1, and let
d = d(C), d⊥ = d(C ⊥ ). Applying Theorem 21 to C and C ⊥ we obtain
dim(C ⊥ ) ≤ m(k − d⊥ + 1).

dim(C) ≤ m(k − d + 1),

Therefore km = dim(C) + dim(C ⊥ ) ≤ 2mk − m(d + d⊥ ) + 2m, i.e.,
d + d⊥ ≤ k + 2.

(10)

Let U ⊆ Fkq be any Fq -subspace with dim(U ) = k − d + 1. By Proposition 13 we have
|C ⊥ (U )| =

|C ⊥ |
q m(d−1)

|C(U ⊥ )|.

(11)

Since dim(U ⊥ ) = d − 1, by Lemma 25 we have |C(U ⊥ )| = |C|/q m(k−d+1) = 1, where the last
equality follows from the fact that C is MRD. Therefore (11) becomes
|C ⊥ (U )| =

|C ⊥ |
q m(d−1)

=

q km /q m(d−1)
= 1.
q m(d−1)

Since U is arbitrary with dim(U ) = k − d + 1, this shows d⊥ ≥ k − d + 2. Using (10) we
conclude d⊥ = k − d + 2. The theorem now follows from
dim(C ⊥ ) = km − dim(C) = km − m(k − d + 1) = m(k − d⊥ + 1).

11

The proof of Theorem 26 also shows the following useful characterization of linear MRD
codes in terms of their minimum distance and dual minimum distance.
Proposition 27. Let C ⊆ Fqk×m be a linear code with 1 ≤ dim(C) ≤ km − 1. The following
are equivalent.
1. C is MRD,
2. C ⊥ is MRD,
3. d(C) + d(C ⊥ ) = k + 2.
In the remainder of the section we concentrate on the weight and distance distributions of
(possibly non-linear) MRD codes. We start with a result on the weight distribution of MRD
codes containing the zero vector (see [14, Theorem 7.46]).
Theorem 28. Let C be an MRD code with |C| ≥ 2 and 0 ∈ C. Let d = d(C). Then W0 (C) = 1,
Wi (C) = 0 for 1 ≤ i ≤ d − 1, and
Wi (C) =

d−1
X

i−u

(−1)

u=0

   
   
i
X
i−u
k
i
i
i−u (i−u
+m(u−d+1) k
(
)
)
2
2
q
+
(−1) q
i q u q
i q u q
u=d

for d ≤ i ≤ k.
Proof. Since 0 ∈ C, we have W0 (C) = 1 and Wi (C) = 0 for 1 ≤ i ≤ d − 1. For all subspaces
V ⊆ Fkq define
f (V ) = |{M ∈ C | colsp(M ) = V }|,

g(V ) =

X

f (U ) = |C(V )|.

U⊆V

Fix 0 ≤ i ≤ k and a vector space V ⊆ Fkq of dimension i. By Lemma 14 we have
f (V ) =

i
X

i−u

(−1)

q(

i−u
2

)

u=0

X

g(U ).

U⊆V
dim(U)=u

Using Lemma 25 and the fact that C is MRD with 0 ∈ C we obtain

1
if 0 ≤ dim(U ) ≤ d − 1,
g(U ) =
q m(u−d+1) if d ≤ dim(U ) ≤ k.
Therefore
f (V ) =

d−1
X

u=0

i−u

(−1)

 
 
i
X
i−u
i
i−u (i−u
+m(u−d+1) i
)
(
)
2
2
+
(−1) q
.
q
u q
u q
u=d

The result now follows from the identity
Wi (C) =

X

f (V ).

⊆Fk
q

V
dim(V )=i

Different formulas for the weight distribution of linear MRD codes were obtained in [4]
using elementary methods.
Theorem 28 implies the following [3, Theorem 5.6], which states that the distance distribution of any MRD code is determined by its parameters.

12

Corollary 29. Let C ⊆ Fqk×m be an MRD code with |C| ≥ 2 and minimum distance d. We
have D0 (C) = 1, Di (C) = 0 for 1 ≤ i ≤ d − 1, and
Di (C) =

d−1
X

(−1)i−u q (

u=0

   
   
i
X
i−u
i
k
i
) k
+
(−1)i−u q ( 2 )+m(u−d+1)
i q u q
i q u q

i−u
2

u=d

for d ≤ i ≤ k.
Proof. Fix an i with d ≤ i ≤ k. For N ∈ C define C − N = {M − N | M ∈ C}. By definition
of distance distribution we have
X
|C| · Di (C) = |{(M, N ) ∈ C 2 | rk(M − N ) = i}| =
Wi (C − N ).
N ∈C

For all N ∈ C the code C − N is MRD. Moreover, 0 ∈ C − N . The result now easily follows
from Theorem 28.
Corollary 29 shows in particular that the weight distribution of a linear MRD code is
determined by k, m and d(C). Recall from Proposition 27 that an MRD code C ⊆ Fqk×m is
characterized by the property d(C)+d(C ⊥ ) = k +2. We now prove that the weight distribution
of a linear code C with d(C) + d(C ⊥ ) = k + 1 is determined by k, m and dim(C). The following
result is [2, Corollary 28].
Corollary 30. Let C ⊆ Fqk×m be a linear rank-metric code with 1 ≤ dim(C) ≤ km − 1 and
d(C) + d(C ⊥ ) = k + 1. Then
dim(C) 6≡ 0

mod m

d(C) = k − ⌈dim(C)/m⌉ + 1.

and

Moreover, for all d ≤ i ≤ k we have
 
k
Wi (C) =
i q

i−d(C)

X

u=0

  

u
i
)
(
2
(−1) q
q dim(C)−m(k+u−i) − 1 .
u q
u

Proof. Assume by contradiction that dim(C) = αm for some α. Applying Theorem 21 to C
and C ⊥ we obtain
d(C) ≤ k − α + 1,
d(C ⊥ ) ≤ α + 1.
(12)
By Proposition 27, the two inequalities in (12) are either both equalities, or both strict inequalities. Since d(C) + d(C ⊥ ) = k + 1 by assumption, they must be both strict inequalities.
Therefore
d(C) ≤ k − α,
d(C ⊥ ) ≤ α,
hence d(C) + d(C ⊥ ) ≤ k, a contradiction. This shows that dim(C) 6≡ 0 mod m.
Now write dim(C) = αm + β with 1 ≤ β ≤ m − 1. Applying again Theorem 21 to C and
C ⊥ one finds




km − αm − β
αm + β
⊥
+ 1 = k − α,
d(C ) ≤ k −
= α + 1.
d(C) ≤ k −
m
m
Since d(C) + d(C ⊥ ) = k + 1, we must have




dim(C)
αm + β
+1=k−
+ 1,
d(C) = k −
m
m
as claimed. The last part of the statement follows from Theorem 19.

13

4

Rank-metric anticodes

This section is devoted to rank-metric anticodes, i.e., rank-metric codes in which the distance
between any two matrices is bounded from above by a given integer δ.
In Theorem 33 we give a bound for the cardinality of a (possibly non-linear) anticode,
using a code-anticode-type bound. We also characterize optimal anticodes in terms of MRD
codes. Then we show that the dual of an optimal linear anticode is an optimal linear anticode.
The main results of this section appear in [12] and [14].
Definition 31. Let 0 ≤ δ ≤ k be an integer. A (rank-metric) δ-anticode is a non-empty
subset A ⊆ Fqk×m such that d(M, N ) ≤ δ for all M, N ∈ A. We say that A is linear if it is
an Fq -linear subspace of Fqk×m .
Example 32. Any A ⊆ Fqk×m with |A| = 1 is a 0-anticode. The ambient space Fqk×m is a
k-anticode. The vector space of k × m matrices over Fq whose last k − δ rows are zero is a
linear δ-anticode of dimension mδ.
In the sequel we work with a fixed integer 0 ≤ δ ≤ k. Moreover, for A, C ⊆ Fqk×m we set
A + C = {M + N | M ∈ A, N ∈ C}.
Theorem 33. Let A ⊆ Fqk×m be a δ-anticode. Then |A| ≤ q mδ . Moreover, if δ ≤ k − 1 then
the following are equivalent.
1. |A| = q mδ .
2. A + C = Fqk×m for some MRD code C with d(C) = δ + 1.
3. A + C = Fqk×m for all MRD codes C with d(C) = δ + 1.
Proof. Let C ⊆ Fqk×m be any MRD code with d(C) = δ + 1. Such a code exists by Theorem 23.
For all M ∈ A let [M ] = M + C = {M + N | N ∈ C}. Then [M ] ∩ [M ′ ] = ∅ for all M, M ′ ∈ A
with M 6= M ′ . Moreover, by definition of MRD code we have |[M ]| = |C| = q m(k−δ) for all
M ∈ A, hence
|Fqk×m | ≥

[

M∈A

[M ] =

X

|[M ]| = |A| · |C| = |A| · q m(k−δ) .

M∈A

Therefore |A| ≤ q mδ , and equality holds if and only if
[
Fqk×m =
[M ] = A + C.
M∈A

A similar argument shows that properties 1, 2 and 3 are equivalent.
Definition 34. We say that a δ-anticode A is (cardinality)-optimal if it attains the bound
of Theorem 33.
Remark 35. Example 32 shows the existence of optimal linear δ-anticodes for all choices of
the parameter δ.
In the remainder of the section we prove that the dual of an optimal linear δ-anticode
is an optimal (k − δ)-anticode. The result may be regarded as the analogue of Theorem 26
in the context of rank-metric anticodes. We start with a preliminary result on the weight
distribution of MRD codes.
Lemma 36. Let C ⊆ Fqk×m be an MRD code with 0 ∈ C, |C| ≥ 2 and d(C) = d. Then
Wd+ℓ (C) > 0 for all 0 ≤ ℓ ≤ k − d.

14

Proof. By Theorem 28, we shall prove the lemma for a given MRD code C ⊆ Fqk×m of our
choice with |C| ≥ 2, minimum distance d, and 0 ∈ C. We will first produce a convenient MRD
code with the prescribed properties.
Let C ⊆ Fkqm be the vector rank-metric code constructed in the proof of Theorem 23, with
evaluation set E = {β1 , ..., βk } and evaluation map evE . Let Γ be a basis of Fqm over Fq . By
Proposition 8, the set C = Γ(C) ⊆ Fqk×m is a linear code with dim(C) = m(k − d + 1) and the
same weight distribution as C. In particular, C is a non-zero linear MRD code of minimum
distance d.
Now we prove the lemma for the MRD code C constructed above. Fix ℓ with 0 ≤ ℓ ≤ k − d.
Define t = k − d − ℓ, and let U ⊆ Fqm be the Fq -subspace generated by {β1 , ..., βt }. If t = 0
we set U to be the zero space. By [10], Theorem 3.52,
Y
pU =
(x − γ)
γ∈U

is a linearized polynomial over Fqm of degree t = k − d − ℓ ≤ k − d, i.e., pU ∈ Linq (n, k − d).
Therefore by Proposition 8 it suffices to prove that evE (pU ) = (pU (β1 ), ..., pU (βk )) has rank d+
ℓ = k −t. Clearly, V (pU ) = U . In particular we have evE (pU ) = (0, ..., 0, pU (βt+1 ), ..., pU (βk )).
We will show that pU (βt+1 ), ..., pU (βk ) are linearly independent overFq . Assumethat there
Pk
Pk
exist at+1 , ..., ak ∈ Fq with i=t+1 ai pU (βi ) = 0. Then we have pU
i=t+1 ai βi = 0, i.e.,
Pk
Pt
i=t+1 ai βi ∈ V (pU ) = U . It follows that there exist a1 , ..., at ∈ Fq such that
i=1 ai βi =
Pk
Pt
Pk
i=t+1 ai βi , i.e.,
i=1 ai βi −
i=t+1 ai βi = 0. Since β1 , ..., βk are independent over Fq ,
we have ai = 0 for all i = 1, ..., k. In particular ai = 0 for i = t + 1, ..., k. Hence
pU (βt+1 ), ..., pU (βk ) are linearly independent over Fq , as claimed.
The following proposition characterizes optimal linear anticodes in terms of their intersection with linear MRD codes.
Proposition 37. Assume 0 ≤ δ ≤ k−1, and let A ⊆ Fqk×m be a linear code with dim(C) = mδ.
The following are equivalent.
1. A is an optimal δ-anticode.
2. A ∩ C = {0} for all non-zero MRD linear codes C ⊆ Fqk×m with d(C) = δ + 1.
Proof. By Theorem 33, it suffices to show that if A ∩ C = {0} for all non-zero MRD linear
codes C ⊆ Fqk×m with d(C) = δ + 1, then A is a δ-anticode.
By contradiction, assume that A is not a δ-anticode. Since A is linear, by definition of
δ-anticode there exists N ∈ C with rk(N ) ≥ δ + 1. Let D be a non-zero linear MRD code with
d(D) = δ + 1 (see Theorem 23 for the existence of such a code). By Lemma 36 there exists
M ∈ D with rk(M ) = rk(N ). There exist invertible matrices A and B of size k × k and m× m,
resp., such that N = AM B. Define C = ADB = {AP B | P ∈ D}. Then C ⊆ Fqk×m is a nonzero linear MRD code with d(C) = δ + 1 and such that N ∈ A ∩ C. Since rk(N ) ≥ δ + 1 ≥ 1,
N is not the zero matrix. Therefore A ∩ C 6= {0}, a contradiction.
We conclude the section showing that the dual of an optimal linear anticode is an optimal
linear anticode.
Theorem 38. Let A ⊆ Fqk×m be an optimal linear δ-anticode. Then A⊥ is an optimal linear
(k − δ)-anticode.
Proof. Let A ⊆ Fqk×m be an optimal linear δ-anticode. If δ = k then the result is trivial.
From now on we assume 0 ≤ δ ≤ k − 1. By Definition 34 we have dim(A) = mδ, hence
dim(A⊥ ) = m(k − δ). Therefore by Proposition 37 it suffices to show that A⊥ ∩ C = {0} for
all non-zero linear MRD codes C ⊆ Fqk×m with d(C) = k − δ + 1. Let C be such a code. Then
dim(C) = m(k − (k − δ + 1) + 1) = mδ < mk.

15

Combining Theorem 26 and Proposition 27 one shows that C ⊥ is a linear MRD code with
d(C ⊥ ) = k − (k − δ + 1) + 2 = δ + 1. By Proposition 37 we have A ∩ C ⊥ = {0}. Since
dim(A) + dim(C ⊥ ) = mδ + m(k − (δ + 1) + 1) = mk, we have A ⊕ C ⊥ = Fqk×m . Therefore
{0} = (Fqk×m )⊥ = (A ⊕ C ⊥ )⊥ = A⊥ ∩ C. This shows the theorem.

References
[1] R. Ahlswede, N. Cai, S.-Y.R. Li, R.W. Yeung, Network information flow. IEEE Transactions on Information Theory 46 (2000), 4, pp. 1204 – 1216.
[2] J. De la Cruz, E. Gorla, H. H. López, A. Ravagnani, Rank distribution of Delsarte codes.
Designs, Codes and Cryptography (to appear).
[3] P. Delsarte, Bilinear forms over a finite field, with applications to coding theory. Journal
of Combinatorial Theory A, 25 (1978), 3, pp. 226 – 241.
[4] J. G. Dumas, R. Gow, G. McGuire, J. Sheekey, Subspaces of matrices with special rank
properties. Linear Algebra and Its Applications, 433 (2010), pp. 191 – 202.
[5] E. Gabidulin Theory of codes with maximum rank distance. Problems of Information
Transmission, 1 (1985), 2, pp. 1 – 12.
[6] M. Gadouleau, Z. Yan MacWilliams Identities for Codes with the Rank Metric.
EURASIP Journal on Wireless Communications and Networking, 2008.
[7] E. Gorla, A. Ravagnani, Subspace codes from Ferrers diagrams. Journal of Algebra and
Its Applications, 16 (2017), 7.
[8] R. Kötter, F. R. Kschischang, Coding for Errors and Erasures in Random Network
Coding. IEEE Transactions on Information Theory, 54 (2008), 8, pp. 3579 – 3591.
[9] S.-Y.R. Li, R.W. Yeung, N. Cai, Linear network coding. IEEE Transactions on Information Theory, 49 (2003), 2, pp. 371 – 381.
[10] R. Lidl, H. Niederreiter, Finite Fields. Addison-Wesley Publishing Company (1983).
[11] F. J. MacWilliams, A Theorem on the Distribution of Weights in a Systematic Code.
Bell System Technical Journal, 42 (1963), 1, pp. 79 – 94.
[12] A. Ravagnani, Rank-metric codes and their duality theory. Designs, Codes and Cryptography, 80 (2016), 1, pp. 197 – 216.
[13] A. Ravagnani, Duality of codes supported on regular lattices, with an
application
to
enumerative
combinatorics.
Submitted.
Online
preprint:
https://arxiv.org/abs/1510.02383.
[14] A. Ravagnani, Properties and Constructions of Codes with the Rank and the Subspace
Metric. PhD thesis, Université de Neuchâtel, 2016.
[15] J. Sheekey, A New Family of MRD Codes. Advances in Mathematics of Communications,
10 (2016), 3.
[16] D. Silva, F. R. Kschishang, On metrics for error correction in network coding. IEEE
Transactions on Information Theory, 55 (2009), 12, pp. 5479 – 5490.
[17] D. Silva, F. R. Kschischang, On metrics for error correction in network coding. IEEE
Transactions on Information Theory, 55 (2009), 12, pp. 5479 – 5490.
[18] D. Silva, E. S. Rogers, F. R. Kschishang, R. Koetter, A Rank-Metric Approach to Error Control in Random Network Coding. IEEE Transactions on Information Theory, 54
(2008), 9, pp. 3951 – 3967.
[19] P. Stanley, Enumerative Combinatorics, vol. 1, Cambridge Stud. Adv. Math., vol. 49.
Cambridge University Press (2012).

16

