{'fraction_non_alphanumeric': 0.05865393557987414, 'fraction_numerical': 0.026474873670831137, 'mean_word_length': 3.4231454819690113, 'pattern_counts': {'":': 0, '<': 5, '<?xml version=': 0, '>': 8, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 19, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Construction of Subspace Codes through Linkage

A construction is presented that allows to produce subspace codes of long length using subspace codes of shorter length in combination with a rank metric code. The subspace distance of the resulting code, called linkage code, is as good as the minimum subspace distance of the constituent codes. As a special application, the construction of the best known partial spreads is reproduced. Finally, for a special case of linkage, a decoding algorithm is presented which amounts to decoding with respect to the smaller constituent codes and which can be parallelized.


Introduction
In [22] Koetter and Kschischang developed an approach to random network coding where the encoded information is represented as subspaces of a given ambient space. This accounts for the unknown network topology by assuming that any linear combination of packets may occur at the nodes of the network.
This approach has led to the area of subspace codes and specifically to intensive research efforts on constructions of subspace codes with large subspace distance [23,21,25,10,14,9,16,12,15,11,24,29,17]. Most of the research focuses on constant-dimension codes (CDC's), that is, codes where all subspaces have the same dimension.
One direction for constructing CDC's is based on so-called cyclic orbit codes [23,9,24,29,17], which are orbits of a subspace in the F q -vector space F q n under the natural action of F * q . While the resulting codes have very beneficial algebraic structure, they do not have large cardinality in general. Taking unions of such codes leads to cyclic subspace codes which still have nice structure, but it remains an open problem how to take unions of cyclic orbit codes without decreasing the distance.
A second major research direction is based on rank-metric codes as introduced and studied earlier by Delsarte [6] and Gabidulin [13]. Lifting rank-metric codes [26] is a very simple construction which results in subspace codes where the reduced row echelon form of each subspace has its identity matrix in the leftmost position. While these codes are asymptotically good [21], they can still be improved upon. Through a careful study of general reduced row echelon forms, Etzion and Silberstein [10] could enlarge lifted rank-metric codes. This is known as the echelon-Ferrers construction (or multilevel construction) and has led to the best codes known at that time. In the same paper it is also demonstrated how to decode these codes. In [11] the same authors could enlarge their codes even further by making use of the pending dot construction initiated by Trautmann/Rosenthal [30]. A different way of enlarging lifted rank-metric codes has been presented by Skachek in [27], where for a specific case of the resulting codes also a decoding algorithm is developed.
A slightly different approach is taken in [12,Sec. III] by Etzion/Vardy and [19] by Gorla/Ravagnani. Therein, the authors focus on CDC's with the best theoretical distance. This distance is achieved when any two distinct subspaces of the code intersect trivially. In [12,19] the authors present constructions of such codes with large cardinality (in fact, the same cardinality). In finite projective geometry, collections of pairwise trivially intersecting subspaces are known as partial spreads, or as spreads if the subspaces also cover the entire ambient space. The cardinalities obtained in [12,19] have also been achieved via constructions based on finite geometry [1,7].
In this paper we will present a surprisingly simple construction of subspace codes of long length by linking matrix representations of subspace codes of shorter length and making use of a rank-metric code. The distance of the resulting subspace code, called a linkage code, is the minimum of the distances of the involved subspace codes and the related lifted rank-metric code.
By way of an example we will compare our construction to the echelon-Ferrers construction [10] and its improvement [11] as well as to the best codes found by sophisticated computer search. We will see that our codes improve upon those constructed in [10,11] and for lengths where no computer search has been conducted, it leads to the best codes known so far.
In Section 3 we show that specific instances of linkage reproduce the constructions of partial spreads given in [12,19], and thus linkage may be considered as a generalization of the latter. In fact, those constructions, which on first sight appear to be quite different, can be nicely presented in a unified way with the aid of linkage. Using an optimal binary partial spread of dimension 3 and length 8, which was found only recently by El-Zanati et al. [8], we can improve upon the constructions in [12,19] for the binary case in dimension 3 and when the length has remainder 2 modulo 3. This reproduces results derived in [8].
Finally, in Section 4 we show that for a specific choice of the seed codes, decoding of linkage codes can be reduced to decoding of the seed codes. Making use of Gabidulin codes and lifted Gabidulin codes, for which an efficient decoding algorithm has been derived by Silva et al. [26], we obtain linkage codes that can be decoded by an efficient parallelizable algorithm.

A Linkage Construction for Subspace Codes
Let us first recall some basic facts about subspace codes and rank-metric codes. Throughout we fix a finite field F = F q . A subspace code of length n is simply a non-empty collection of subspaces in F n . The code is called a constant-dimension code if all subspaces have the same dimension. The subspace distance of a subspace code C is defined as d S (C) := min{d S (V, W) | V, W ∈ C, V = W}, where the distance between two subspaces is It is a metric on the space of all subspaces, see [22,Lem. 1]. (2.1) If the code C consist of a single subspace of dimension k, we define d S (C) := min{2k, 2(n−k)}. A constant-dimension code of length n, dimension k, cardinality N will be called an (n, N, k)-code, and it is a (n, N, k, d)-code if its subspace distance is d.
A k × m rank-metric code is a non-empty subset of F k×m , endowed with the rank metric d R (A, B) := rk(A − B) (which is indeed a metric, see [13]). The rank distance of a rank-metric code C is defined in the usual way as d R (C) := min{rk(A − B) | A, B ∈ C, A = B}. If C consists of single matrix, we define d R (C) := min{k, m}. It is well known (see [6,Thms. 5.4,6.3] and [13, p. 2]) that if m ≥ k and C is a rank-metric code in F k×m q with rank distance d, then Moreover, there exist rank-metric codes of distance d and size q m(k−d+1) , and such codes can even be constructed as linear subspaces of F k×m q . They are called MRD codes. The best known class of linear MRD codes are the Gabidulin codes, derived by Gabidulin in [13]. Just recently, other constructions of MRD codes were found by de la Cruz et al. [5] and Hernandez/Sison [20]. However, as opposed to Gabidulin codes so far no decoding algorithm is known for the latter codes.
If C ⊆ F k×m is an MRD code, then the subspace code is called a lifted MRD code. Here the notation im(M ) stands for the row space of the matrix M and I k denotes the k × k-identity matrix. If d R (C) = d, then d S ( C) = 2d, see [26,Prop. 4], and therefore C is a (k + m, q m(k−d+1) , k, 2d)-code.
The following specific class of MRD codes will be used in the next section when studying partial spreads.
Remark 2.1. There is a simple construction of MRD codes in F k×m of rank distance k. Let W ∈ F k×m be any matrix of rank k and M ∈ GL m (F) be the companion matrix of a primitive polynomial in F[x] of degree m. Define Since F[M ] ∼ = F q m and |M | = q m − 1, the code C is a linear rank-metric code of size q m and rank distance k. Hence C is an MRD code. In fact, it can be shown that C is a Gabidulin code.
In order to present our linkage construction we need to work with matrix representations of subspaces. The following terminology will be convenient. For example, the rank-metric code C in Remark 2.1 forms an SC-representing set of a cyclic orbit code in the sense of [24,29,17]. Any set of full row rank matrices in reduced row echelon form is an SC-representing set. In general, an SC-representing set is simply a subset of orbit representatives of the action of GL k (F) on F k×n via left multiplication.
The linkage construction in the following theorem links subspace codes with the aid of a rank-metric code and results in a subspace code of longer length without compromising the distance. It makes use of representing matrices. The theorem generalizes a former construction in [17,Thm. 5.1].
Furthermore, let C R ⊆ F k×n 2 be a linear rankmetric code with rank distance d R (C R ) = d R and cardinality |C R | = N R . Define the subspace code C of length n := n 1 + n 2 as C :=C 1 ∪C 2 ∪C 3 , wherẽ Then C is a (n, N, k, d)-code, where N = N 2 + N 1 N R and d = min{d 1 , d 2 , 2d R }. We write C = C 1 * C R C 2 for the resulting linkage code and call C the code obtained by linking C 1 and C 2 through C R .
The notation C = C 1 * C R C 2 has to be used with care because the code C depends on the representing sets M 1 and M 2 and not only on the codes C 1 and C 2 . Thus the notation M 1 * C R M 2 is actually the accurate one, but we prefer the former because the properties of the linkage that we are interested in are associated to the subspace codes C 1 , C 2 . The sets M 1 , M 2 are mere technicalities in our context, and the notation C 1 * C R C 2 will not lead to any confusion.
However, in order to illustrate the dependence on the SC-representing sets for C 1 and C 2 we will present, after the proof, an example showing that different choices lead in general to different distance distributions of the linkage code.
Proof. The cardinality of C is clear because the three setsC i are pairwise disjoint. Furthermore, it is obvious that d S (C i ) = d S (C i ) for i = 1, 2. Moreover, it is clear that each subspace inC 2 intersects trivially with each subspace inC 1 andC 3 . Thus d S (W 1 , W 2 ) = 2k for all W 1 ∈C 2 and W 2 ∈C 1 ∪C 3 .
Next, let U = im(U | 0) ∈C 1 and V = im(U ′ | M ) ∈C 3 . Thus U, U ′ ∈ M 1 and M ∈ C R \{0}. Then rk(M ) ≥ d R by linearity of the code C R and so dim ker for some x, y ∈ F k and thus y ∈ ker M and xU = yU ′ ∈ im(U ) ∩ im(U ′ ). Since the maps from U ∩ V mapping x(U | 0) to xU and y(U ′ | M ) to y are both injective, this yields This concludes the proof.
The following example shows that different choices of the SC-representing sets for C 1 and C 2 lead to different distance distributions of the linkage code. Since we will not further study the distance distribution of linkage codes, we continue to use the notation C 1 * C R C 2 for the linkage. Example 2.5. We aim at constructing a constant-dimension code over F 2 of length 13, dimension k = 3, and distance 4. Let n 1 = 7 and n 2 = 6. The largest known codes of dimension 3 and length 7 (resp. 6) with distance 4 have cardinality 329 (resp. 77), see [3, Tables I and II] by Braun/Reichelt as well as [28] by Honold et al., where it is shown that 77 is actually the largest possible size for length 6. We choose these codes for C 1 and C 2 , respectively, and an MRD code C R in F 3×6 2 with rank distance d R = 2 and thus cardinality N R = 2 6(3−2+1) = 2 12 due to (2.2). The resulting linkage code has therefore cardinality 77 + 2 12 · 329 = 1, 347, 661. This is lower than the cardinality of the best known code with the same parameters, which is 1, 597, 245, see [3,App.]. But the latter has been found by extended computer search, whereas the linkage code is readily available once C 1 and C 2 have been found. The linkage code beats the codes that have been found by Etzion/Silberstein with the aid of the multilevel construction [10] where the best such code has cardinality 1, 192, 587, see [23]. It also beats the modified multilevel construction [11] by Etzion/Silberstein, where the best such code has size 1, 221, 296. This particular construction is a refinement of the pending dot construction appearing first in [30] by Trautmann/Rosenthal. The following table presents the cardinality of further linkage constructions for q = 2, k = 3, d S = 4 and various lengths n. We make use of the best codes found in [3, Table II] for lengths 6, . . . , 9 and an MRD code C R ⊆ F 3×n 2 with rank distance 2. Thus N R = 2 2n 2 thanks to (2.2). We also show the largest size obtained via the modified multilevel (MML) construction [11,Thm. 17] (which always beats the multilevel construction in [10]) as well as the largest size known so far. For n ≤ 14 the latter has been found by computer search [3, Tables I and II], while for n = 15 no such search has been conducted yet and linkage with n 1 = 9, n 2 = 6 results in the largest known code. Note that for all n shown in the table, every partition into n = n 1 + n 2 leads to a linkage code that is larger than the MML construction. This is probably due to the fact that the MML construction leads to subspace codes that contain a lifted MRD code. This restriction also restricts the size of these codes. It is worth pointing out that for length n = 13 the largest known cardinality 1, 597, 245 is actually the optimum by the anticode bound, and the existence of a code with that size has been established by Braun et al. in [2] via a 2-analogue of a Steiner triple system.
Example 2.6. Let us consider Theorem 2.3 for the case where C 1 is a lifted MRD code and C R is an MRD code. For C 2 we may choose a lifted MRD code or an arbitrary subspace code. Let us consider the case where C 2 is a lifted MRD code. Thus, let n = n 1 + n 2 , where n i ≥ 2k for i = 1, 2, and C i be the lifting of an MRD code in F k×(n i −k) with rank distance d. Then . By Theorem 2.3 the linkage code C 1 * C R C 2 has subspace distance 2d and cardinality q (n 2 −k)(k−d+1) + q (n−k)(k−d+1) . Note that the second term is the cardinality of a lifted MRD code in F n with subspace distance 2d. Thus, linkage always results in a better code than lifting. In fact, with our choice the codeC 1 ∪C 3 in Theorem 2.3 is a lifted MRD code and thus the cardinality of the linkage code is clearly larger than that of a lifted MRD code. Furthermore we observe that only the first term depends on the partition n = n 1 + n 2 , and that the cardinality of C 1 * C R C 2 is largest when n 2 is largest. The following table shows the size of the linkage construction for q = 2, k = 3, d S = 4 and various lengths. In each case, C 1 is a lifted MRD code of distance 4 and C R is an MRD code of rank distance 2. Each given length n is split into n = n 1 + n 2 such that n 2 is maximal subject to n i ≥ 2k for i = 1, 2. In the column denoted by "Link largest " we present the cardinality of the linkage code where we use the largest known subspace code for C 2 . In the column "Link MRD " we use a lifted MRD code for C 2 . For comparison we also show the size, 2 2(n−3) , of a lifted MRD code of length n.
It should be noted that the linkage codes are smaller than the codes obtained from the MML construction; see the previous table. This is explained by the fact that the MML construction is a careful design to create additional subspaces without compromising the distance. It may be regarded as a replacement of the codeC 2 in Theorem 2.3 by a larger set, where the zero block matrix is replaced by suitable matrices. In the column "Extended Lifted MRD" we illustrate that our codes are slightly smaller than those constructed in [27] by Skachek 1 , which are also subspace codes containing a lifted MRD code (and are smaller than the MML codes).
n n 1 n 2 Link largest Link MRD Lifted MRD Extended Lifted MRD 12 6  We will return to these codes in Theorem 4.6 when we investigate decoding.
The linkage construction can be viewed as a generalization of two specific constructions that can be found in the literature. We will discuss the details in the next section, where we turn to subspace codes with largest possible distance.

Partial Spreads
With the aid of Theorem 2.3 we can construct optimal partial spreads for certain cases. Recall that a partial spread in F n is a collection of subspaces that pairwise intersect trivially. If all subspaces have the same dimension, say k, then this is simply a constant-dimension code of dimension k and distance 2k, and we call the code a partial k-spread. It is well known that if k divides n, then an optimal partial k-spread (i.e., a partial k-spread of maximum cardinality) is a k-spread, i.e., the spaces intersect trivially and cover the entire F n . In this case a simple counting argument shows that the cardinality is (q n − 1)/(q k − 1), where F = F q . Several constructions of k-spreads are known. For later reference we provide the following two options. If k does not divide n, then the maximum size of a partial k-spread in F n q is in general not known -with one exception which will be considered below in further detail. The following result can be found in [ Constructions of partial k-spreads and cardinality were presented in [1,Thms. 4.2] as well as [12,Thm. 11] and [19,Thm. 13]. Hence for c ∈ {0, 1} these partial spreads have maximum possible cardinality. The latter two constructions are special cases of our linkage and will be described in our terminology in the following examples. Consider the F q -vector space F q n 1 × F q n 2 . In F q n 1 choose the k-spread C 1 given by the orbit of the subfield F q k under the action of the cyclic group F * q n 1 ; see Remark 3.1(a). Furthermore, let β be a primitive element of F q n 2 and set C 2 = span F {1, β, . . . , β k−1 } . Note that this is trivially a partial k-spread in F q n 2 of maximal possible cardinality because k > n 2 /2. Consider the coordinate map w.r.t. the basis {1, β, . . . , β n 2 −1 } of F q n 2 , that is, Using the identification ϕ, the code C 2 simply translates into C 2 = {im(I k | 0 k×c )}. Finally, in F k×n 2 choose the rank-metric code where M is the companion matrix of the minimal polynomial of β over F q . Note that the matrix (I k | 0 k×c )M j consist exactly of the rows ϕ(β j ), . . . , ϕ(β j+k−1 ). By Remark 2.1, C R is an MRD code of rank distance k. Identifying F q n 1 with F n 1 q , the linkage code C 1 * C R C 2 is exactly the partial k-spread constructed in [12,Thm. 11]. It has cardinality 1 + q n 2 (q n 1 − 1)/(q k − 1), and this is m(n, k).
Example 3.4. Essentially the same construction as in Example 3.3 but with different specifications of the constituent codes is used by Gorla/Ravagnani in [19,Thm. 13]. Again, let n = lk + c and set n 1 = k(l − 1) and n 2 = k + c. Then the code constructed in [19,Thm. 13] is the linkage C 1 * C R C 2 with the following specifications: C 1 is a Desarguesian k-spread in F n 1 (see Remark 3.1) while C 2 is the subspace code {im(0 k×c | I k )} and C R is an MRD code in F k×n 2 as in Remark 2.1 with matrix W = (0 | I k ), thus the nonzero matrices in C R are the last k rows of the matrices M l . In addition to the construction, the authors also present a decoding algorithm for their partial spreads by making explicit use of the structure of the Desarguesian spread; see [19,Sec. 5]. In contrast, no decoding algorithm is given in [12] for the partial spreads constructed therein.
Instead of partitioning n into n 1 + n 2 with the specific choice of n 2 = k + c as in the previous examples, we may use any other splitting n = lk + n 2 . This will be summarized in the next result where we also address maximality of the partial spread. A partial k-spread in F n is called maximal if it is maximal with respect to inclusion, that is, it is not properly contained in any other partial k-spread. The following result shows, among other things, that linking a k-spread and a maximal partial k-spread through an MRD code leads to a maximal partial k-spread. Theorem 3.5. Let n = lk + n 2 , where l ≥ 1 and n 2 ≥ k. Let C 1 be a k-spread in F lk and C 2 be a partial k-spread in F n 2 . Furthermore, let C R be a linear MRD code in F k×n 2 with rank distance k and thus cardinality q n 2 . Finally, let C = C 1 * C R C 2 be the resulting linkage code as in Theorem 2.3. (a) If |C 2 | = m(n 2 , k), then |C| = m(n, k). (b) If C 2 is a maximal partial k-spread then so is C.
Proof. (a) Theorem 2.3 tells us that |C| = q n 2 m(lk, k) + m(n 2 , k). But this is easily seen to be m(n, k). (b) Let (W 1 | W 2 ) ∈ F k×(n 1 +n 2 ) be of rank k and set W := im(W 1 | W 2 ). We have to show that there exists a subspace V ∈ C such that W ∩ V = {0}, for then C is a maximal partial k-spread. Assume first that W 1 = 0. Then there exists (x, y) ∈ W such that x = 0. Since C 1 is a spread of F lk , the vector x is in exactly one subspace of C 1 , say im(U 1 ). Let x = αU 1 , where α ∈ F k \{0}. Since C R is a linear rank-metric code with rank distance k, we have αM = αM ′ for all distinct M, M ′ ∈ C R . This shows that the set {αM | M ∈ C R } has cardinality |C R | = q n 2 and therefore equals F n 2 . As a consequence, y = αM for some M ∈ C R . Hence (x, y) = α(U 1 | M ) and W ∩ V = {0} for the subspace V = im(U 1 | M ) ∈ C. Assume now W = im(0 | W 2 ). Then rk(W 2 ) = k and the maximality of C 2 implies W ∩V = {0} for some subspace V = im(0 | U 2 ) ∈ C. All of this shows that C is a maximal partial k-spread in F n .
The following is an immediate consequence of Examples 3.3 and 3.4 because in both cases the chosen code C 2 is trivially a maximal partial k-spread.
In Theorem 3.2 we have seen that the maximum cardinality of a partial k-spread in F n is known whenever n (mod k) ∈ {0, 1}. There is one more case where the cardinality is known, and that is if q = 2 and k = 3. The following result covers all remainders of n modulo 3.
We call a partial 3-spread with this cardinality a maximum partial 3-spread.
Note that for c ∈ {0, 1} the result is simply a special case of Theorem 3.5, whereas for c = 2 the cardinality m(n, k) in (3.1) is one below the maximum. As a consequence, the constructions in [12,Thm. 11] and [19,Thm. 13] are just one subspace short of being maximum.
The proof of Theorem 3.7 is based on a concrete example for n = 8 and an extension construction for n > 8. It makes use of a result in [4,Lem. 4], which establishes a partition of F n q into subspaces of two distinct dimensions. Below we will provide an alternative extension, where we will also make use of the maximum 3-spread in F 8 2 .

Example 3.8 ([8, Ex. 2]
). There exists a partial 3-spread in F 8 2 with cardinality 34. Hence the spread is maximum. It has been found by computer search and is explicitly given in [8].
Now we can provide a simple construction of maximum partial 3-spreads in F n 2 for any n ≥ 10. Note that, due to the previous example and earlier discussions, a maximum partial 3-spread in F n 2 is available for the values n ∈ {6, 7, 8, 9}. Corollary 3.9. Let n ≥ 10 and write n = 3l + n 2 for some l ≥ 1 and n 2 ∈ {6, 7, 8}. Choose a 3-spread C 1 in F 3l 2 and a maximum partial 3-spread C 2 in F n 2 2 . Finally, let C R be an MRD code with rank distance 3 in F 3×n 2 2 . Then C 1 * C R C 2 is a maximum partial 3-spread in F n 2 .
Proof. The resulting code is certainly a partial spread. Let n (mod 3) = c, thus n 2 (mod 3) = c. By Theorems 3.7 and 2.3 the cardinality of C 1 * C R C 2 is given by and this is the maximum value due to Theorem 3.7.

Decoding of Linkage Codes
In this section we turn to decodability of the linkage codes from Theorem 2.3. Of course, one aims at reducing decoding of C 1 * C R C 2 to decoding of the smaller codes C 1 , C 2 , C R . We will show first that this strategy does not work if one utilizes the rank metric for the code C R . Instead one has to employ the subspace distance for all codes involved. We will show that if we use suitable MRD codes and liftings thereof, then decoding can indeed be reduced to decoding of the constituent codes. Since lifted Gabidulin codes can be efficiently decoded, as proven by Silva et al. [26], this leads to an efficient decoding algorithm for a particular instance of linkage codes. The following terminology is standard.
Since the subspace distance is a metric on the set of all subspaces in F n (see [22,Lem. 1]), a decodable subspace has a unique closest codeword in C.
The following simple fact will be useful later.
Remark 4.2. Let C be a constant-dimension code in F n with dimension k and subspace distance d. Suppose V ⊆ F n is a decodable K-dimensional subspace and U ∈ C is the unique closest codeword. Then dim(U ∩ V) > K/2 and dim(U + V) < k + K/2.
We start with an example illustrating that the rank distance of the code C R cannot be used in the natural way for decoding the linkage code C 1 * C R C 2 .
Throughout this section we call a matrix V ∈ F K×n a matrix representation of the subspace V ⊆ F n if V = im(M ) := {xM | x ∈ F K }. We explicitly allow dim(V) < K. In particular, V is decodable. Note that V ⊆ U (i.e., only erasures occurred during the transmission). One can check straightforwardly that there exists no matrix representation ( Even worse, for all matrix representations (V 1 | V 2 ) ∈ F 4×16 of V for which the matrix V 2 has a unique closest matrix in C R with respect to the rank distance, this unique closest matrix is the zero matrix and therefore does not lead to the correct decoding U . The fact that the "obvious decoding" does not work may be explained by the fact that the subspaces represented by the nonzero matrices in C R , i.e., im(I | 0), im(M | 0), im(I + M | 0), all coincide. This causes the rank-metric code C R to be of little help with decoding.
The example can be generalized. We introduce the following notation. Define the projections π 1 : F n 1 +n 2 −→ F n 1 , (a, b) −→ a and π 2 : F n 1 +n 2 −→ F n 2 , (a, b) −→ b. (4.1) Proposition 4.4. Let C be as in Theorem 2.3 and assume d ≥ d R + 2. Then there exists a subspace U = im(U 1 | U 2 ) ∈ C and a received word In other words, it is not possible to decode V by making use of the rank metric for the code C R .
Proof. Let d ≥ d R + 2. Since d ≤ d 1 ≤ 2k, we have r := k − ⌈ d R 2 ⌉ ≥ 1 2 , and thus r ≥ 1 because it is an integer. We construct now subspaces U and V as stated in the proposition. First choose a subspace U = im(U 1 | U 2 ) ∈ C with (U 1 | U 2 ) ∈ F k×n such that rk(U 2 ) ≥ k − r = ⌈ d R 2 ⌉. By definition of C such an element does indeed exist. Next, there exists a matrix X ∈ GL k (F) such that and where U 22 ∈ F (k−r)×n 2 has rank k − r and and im( Then dim(V) = r because the rows of (U 1 | U 2 ) are linearly independent. Moreover, V ⊆ U and therefore This establishes (a) and (b). For (c) consider now all matrices V 2 in F k×n 2 whose row space is π 2 (V). These matrices can be written as The matrix X −1 does not change the row space, and we include it only to simplify the next step. Indeed, for each such matrix V 2 we have The rightmost matrix has full row rank, k − r. Indeed, suppose u(M 2 U 21 − U 22 ) = 0. Then uM 2 U 21 = uU 22 ∈ im(U 21 ) ∩ im(U 22 ). Since this intersection is trivial, we obtain uU 22 = 0, which in turn implies u = 0. All of this shows that rk( for all matrix representations of π 2 (V).
The last observation suggests to modify the linkage construction by simply replacing the rank-metric code C R by matrix representations of a subspace code. This results in a code that is decodable if its constituent codes are decodable. But since these codes are considerably smaller than the original linkage codes, we will not follow that path.
Instead, we will show now how to decode linkage codes C 1 * C R C 2 for the case where C 1 and C R are (lifted) MRD codes. We need the following lemma.
With the aid of Remark 4.2 we obtain Hence dim V 1 = rk(V 1 ) < K/2.
Note that the implication "⇐=" of the last lemma is in general not true for U 2 and V 2 because the matrices in C R may not have rank k. Now we are in the position to discuss decoding of the linkage codes from Theorem 2.3. We consider the following situation which is a special case of the general linkage construction. It may also be regarded as an extension of the codes considered in Example 2.6. Theorem 4.6. For i = 1, 2 let n i ≥ k and let M i ⊆ F k×n i be a linear MRD code with rank distance d, thus |M i | = q n i (k−d+1) . Moreover, let M 3 ⊆ F k×n 1 and M 4 ⊆ F k×n 2 be SC-representing sets of constant-dimension codes with subspace distance 2d. Consider the code Then C is an (n, N, k, 2d)-code, where n = k + n 1 + n 2 and N = q (n 1 +n 2 )(k−d+1) + |M 3 | + |M 4 |.
Proof. This is a simple application of Theorem 2.3 : C =C 1 * C RC 2 with the codesC 1 = {im(I k )}, Note that if M 4 represents a lifted MRD code, then Hence the code is of the form as discussed in Example 2.6, and in Theorem 4.6 we improve upon the codes in that example by the size of M 3 . In the column "Link MRD " of the table in Example 2.6 we listed, for a specific choice of parameters, the largest codes of the form C ′ ∪ C ′′′ above. As we saw already, the largest size is attained when n 2 is largest subject to n = k + n 1 + n 2 with n 1 + k ≥ 2k and n 2 ≥ 2k (now n 1 + k takes the role of n 1 from that example), thus for n 1 = k and n 2 = n − 2k. But in that case |M 3 | = 1 and thus we improve upon the codes in that table by exactly one subspace.
We now turn to decoding of the codes in Theorem 4.6. As we show next this can be reduced to decoding of the constituent codes.  (b) rk(V 0 | V 2 ) < K/2. In this case the unique closest codeword in C is in C ′′ and given by U = im(0 | M | 0), where M ∈ M 3 is the unique matrix such that d S (im(M ), im(V 1 )) ≤ (2d−1)/2. (c) rk(V 0 ) > K/2. In this case the unique closest codeword in C is in C ′ and given by U = im( Proof. First of all, the uniqueness of the matrices M and M i in (a) -(c) is guaranteed since the subspace codes C(M 3 ), C(M 4 ) and the lifted MRD codes C i all have subspace distance 2d. Let us denote by U = im(U 0 | U 1 | U 2 ) the unique codeword in C closest to V. We will use the notation U i = im(U i ) and V i = im(V i ) for i = 0, 1, 2.
(b) The case rk(V 0 | V 2 ) < K/2 is analogous. (c) Let rk(V 0 ) > K/2. Then Lemma 4.5 applied toC 1 * C RC 2 (see proof of Theorem 4.6) implies (U 0 ) = 0. Thus U ∈ C ′ . In particular, we may assume U 0 = I k . For i = 1, 2 let V ′ i := im(V 0 | V i ) and U ′ i := im(I k | U i ). Then U ′ i ∈ C i for i = 1, 2, where C i = {im(I k | M ) | M ∈ M i } is the lifting of the MRD code M i for i = 1, 2. Consider the projections ψ i : F k+n 1 +n 2 −→ F k+n i , (a 0 , a 1 , a 2 ) −→ (a 0 , a i ) Then (ψ i )| U is injective and thus dim(U ∩ V) ≤ dim(U ′ i ∩ V ′ i ). As in (a) this implies d S (U ′ i , V ′ i ) ≤ d S (U , V) ≤ (2d − 1)/2 for i = 1, 2. Hence V ′ i can be uniquely decoded w.r.t. C i and the closest codeword is given by U ′ i . Using the unique matrix representations (I | U i ), U i ∈ M i , of the spaces U i , we arrive at the correct decoding of V.
We summarize the result in the following algorithm. Data: decode im(V 0 | V 1 ) in C 1 to im(I k | U 1 ); decode im(V 0 | V 2 ) in C 2 to im(I k | U 2 ); return U = im(I k | U 1 | U 2 ).
One should observe that in the last case of the algorithm, the two decoding steps can be performed in parallel. A similar, but not identical, form of parallelizing decoding is also used for the spread codes in [19]; recall Example 3.4 for the relation to our linkage codes.
Clearly, the construction in Theorem 4.6 and its decoding can easily be generalized to more than 3 blocks. Remark 4.9. A very efficient decoding is obtained when we use Gabidulin codes for M 1 and M 2 and lifted Gabidulin codes for M 3 and M 4 (thus n i > k). In this case, all codes relevant for decoding in the previous proof are lifted Gabidulin codes, and the decoding algorithm derived by Silva et al. [26] may be employed. If n i >> k, then even better efficiency is obtained by using direct products of Gabidulin codes as the MRD codes and the lifting of such a code for M 3 and M 4 ; see [26, Sec. VI.E]. In fact, our code C ′ in Theorem 4.6 (or rather its generalization to more than 3 blocks) is of the form proposed in [26] and with the above we have shown how to enlarge the code without compromising its properties. In this sense, our results put the considerations in [26, Sec. VI.E] in a broader context.