Optimum distance flag codes from spreads via perfect matchings in graphs

Abstract

In this paper, we study flag codes on the vector space ${{\mathbb {F}}}_q^n$, being q a prime power and ${{\mathbb {F}}}_q$ the finite field of q elements. More precisely, we focus on flag codes that attain the maximum possible distance (optimum distance flag codes) and can be obtained from a spread of ${{\mathbb {F}}}_q^n$. We characterize the set of admissible type vectors for this family of flag codes and also provide a construction of them based on well-known results about perfect matchings in graphs. This construction attains both the maximum distance for its type vector and the largest possible cardinality for that distance.

1 Introduction

Random network coding is introduced in [1] as a new method for attaining a maximum information flow by using a channel modelled as an acyclic-directed multigraph with possibly several senders and receivers. In this model, intermediate nodes are allowed to perform random linear combinations of the received vectors instead of simply routing them, as it happens when using classical channels of communication. This process is specially vulnerable to error dissemination, and, as a solution to this problem, in [13], Koetter and Kschischang introduce the concept of subspace codes as adequate error-correction codes in random network coding. These codes are families of subspaces of an n-dimensional vector space over the finite field ${\mathbb {F}}_q$ endowed with a specific distance. If the dimension of all the subspaces in a code is fixed, we say that it is a constant dimension code.

In coding theory, the distance of a code is closely related to its error-correction capability. More precisely, a code with distance d can detect $d-1$ errors and correct up to $\lfloor \frac{d-1}{2}\rfloor$. The size of a code is also an important parameter, since it determines the amount of different messages that can be encoded. Hence, one of the main problems in this area is the construction of codes with the largest possible size with a given minimum distance or codes with the largest minimum distance for a given size. In the particular context of network coding, this fact motivates the search for subspace codes having the largest possible distance and the best size for that distance.

Spreads are objects coming from finite geometry, introduced by Segre in [25]. A k-dimensional spread (or k-spread) of ${{\mathbb {F}}}_q^n$ is just a collection of k-dimensional subspaces that pairwise intersect trivially and cover the space ${{\mathbb {F}}}_q^n$. It is well known that k-spreads exist if, and only if, k divides n. In the network coding setting, k-spread codes are optimal codes in the previous sense: they attain the best distance for their dimension, and their cardinality is as large as possible.

When using subspace codes, every codeword (a subspace) is sent in a single use of the channel. In contrast, in [23, 24], Nobrega and Uchôa-Filho present the notion of multishot codes, where codewords are sequences of r subspaces of ${\mathbb {F}}_q^n$ and need r successive uses of the channel (shots) to be sent. This approach allows to construct codes with good parameters without modifying neither the field size q nor the dimension n. As a particular case of multishot codes, we have the class of flag codes. A flag on ${{\mathbb {F}}}_q^n$ is just a sequence $\mathcal {F}=(\mathcal {F}_1, \dots , \mathcal {F}_r)$ of nested subspaces of ${{\mathbb {F}}}_q^n$. The vector $(\dim (\mathcal {F}_1), \dots , \dim (\mathcal {F}_r))$ is called type of the flag $\mathcal {F}$. Now, given integers $0<t_1<\dots<t_r<n$, a flag code of type $(t_1, \dots , t_r)$ on ${{\mathbb {F}}}_q^n$ is a nonempty collection of flags of this type. Flag codes in network coding appear for the first time in [19]. Later on, in [2], a study of flag codes attaining the best possible distance (optimum distance flag codes) is undertaken. In that work, these codes are characterized in terms of the constant dimension codes used in different shots (the projected codes). Moreover, it was also shown that the presence of a spread code among the projected codes leads to constructions of optimum distance flag codes that also reach the largest possible size.

In particular, in [2], the authors build optimum distance flag codes with a k-spread as a projected code fixing the full type vector, that is, $(1,\dots , n-1)$. They conclude that such codes exist just if $n=2k$ or $n=3$ and $k=1$. On the other hand, in this paper, we deal with the converse problem: given n and a divisor k of n, we look for conditions on the type vector of an optimum distance flag code on ${{\mathbb {F}}}_q^n$ having a k-spread as a projected code. We show that not every type vector $(t_1, \dots , t_r)$ is allowed for this purpose, only those satisfying

$$\begin{aligned} k \in \{t_1,\dots ,t_r\} \subseteq \{1,\dots ,k,n-k,\dots ,n-1\} \end{aligned}$$

are admissible.

Observe that, for $n=2k$ or $n=3$ and $k=1$, any full type vector is admissible. In fact, for $n=2k$, we have $k=n-k$. However, this equality does not hold for an arbitrary divisor k of n, and to overcome the gap between dimensions k and $n-k$, we need to provide suitable nested subspaces of these dimensions. We solve this problem by using classical combinatorial results about the existence of perfect matchings on bipartite regular graphs. Finally, for any given admissible type vector, we get a construction of flag codes with the maximum distance and the largest cardinality among optimum distance flag codes of the corresponding type.

The paper is organized as follows: In Sect. 2, we recall some background on finite fields, constant dimension codes, flag codes and graphs. In Sect. 3, we determine the set of admissible type vectors for a flag code to attain the maximum possible distance and to have a k-spread as a projected code. Then, for those type vectors, we undertake the construction of such codes in several stages. First, we consider the type $(1, n-1)$ and construct optimum distance flag codes from the spread of lines, exploiting the existence of perfect matchings in bipartite regular graphs. Then, using the field reduction map, we translate the previous construction into the type $(k, n-k)$. Finally, by taking advantage of some properties satisfied by the mentioned map, we finish with the full admissible type $(1,\dots , k,n-k,\dots , n-1)$ and any other admissible type vector. Our codes have the best size for the given admissible type vector and the associated maximum distance. We complete this section with an example of our construction for the admissible type (2, 4) on ${{\mathbb {F}}}_2^6$ having a 2-spread as the subspace code used at the first shot.

2 Preliminaries

We devote this section to recall some background we will need along this paper. This background involves finite fields, subspace and flag codes and graph theory.

2.1 Results on finite fields

Most of the following definitions and results about finite fields as well as the corresponding proofs can be found in [18].

Let q be a prime power and ${{\mathbb {F}}}_q$ the finite field with q elements. Consider $f(x) \in {{\mathbb {F}}}_q[x]$ a monic irreducible polynomial of degree k and $\alpha \in {{\mathbb {F}}}_{q^k}$ a root of f(x). Then, we have that ${{\mathbb {F}}}_{q^k} \cong {{\mathbb {F}}}_q[\alpha ]$, which allows us to realize the field ${{\mathbb {F}}}_{q^k}$ as ${{\mathbb {F}}}_q[\alpha ]$. If $f(x)=x^k+\sum _{i=0}^{k-1}a_ix^i \in {{\mathbb {F}}}_q[x]$, the following square matrix

$$\begin{aligned} P= \begin{pmatrix} 0 &{} 1 &{} 0 &{} \dots &{} 0\\ 0 &{} 0 &{} 1 &{} \dots &{} 0\\ \vdots &{} \vdots &{} \vdots &{} \ddots &{} \vdots \\ 0 &{} 0 &{} 0 &{} \dots &{} 1\\ -a_0 &{} -a_1 &{} -a_2 &{} \dots &{} -a_{k-1} \end{pmatrix} \end{aligned}$$

is called the companion matrix of f(x) and satisfies that ${{\mathbb {F}}}_q[\alpha ] \cong {{\mathbb {F}}}_q[P]$. Then, ${{\mathbb {F}}}_q[P]$ is a field with $q^k$ elements. We also have the natural field isomorphism

$$\begin{aligned} \phi :{{\mathbb {F}}}_{q^k}\rightarrow {{\mathbb {F}}}_q[P], \qquad \sum _{i=0}^{k-1}v_i\alpha ^i \mapsto \sum _{i=0}^{k-1}v_i P^i. \end{aligned}$$

(1)

For any positive integer n, we denote by $\mathcal {P}_q(n)$ the set of all vector subspaces of ${{\mathbb {F}}}_q^n$. The Grassmann variety $\mathcal {G}_q(k,n)$ is the set of all k-dimensional subspaces of ${{\mathbb {F}}}_q^n$. Any subspace $\mathcal {U}\in \mathcal {G}_q(k,n)$ can be generated by the rows of some full-rank matrix $U \in {{\mathbb {F}}}_q^{k\times n}$. In that case, we write $\mathcal {U}={\mathrm {rowsp}{(}}U)$ and say that U is a generator matrix of $\mathcal {U}$. By taking the generator matrix in reduced row echelon form (RREF), we get uniqueness in the matrix representation of the subspace $\mathcal {U}$.

Let us take $n=ks$ with $k>1$. The field isomorphism $\phi$ provided by (1), in turn, naturally induces a map $\varphi$ between $\mathcal {P}_{q^k}(s)$ and $\mathcal {P}_q(ks)$ given by:

$$\begin{aligned} \begin{array}{rccc} {\varphi }: &{} \qquad \mathcal {P}_{q^k}(s) &{} \longrightarrow &{} \mathcal {P}_q(ks)\\ &{} &{} &{} \\ &{} \mathrm {rowsp}\begin{pmatrix} x_{11}&{}\dots &{}x_{1s}\\ \vdots &{}\ddots &{} \vdots \\ x_{m1}&{}\dots &{}x_{ms} \end{pmatrix} &{} \longmapsto &{} \mathrm {rowsp}\begin{pmatrix} \phi (x_{11})&{}\dots &{}\phi (x_{1s})\\ \vdots &{}\ddots &{} \vdots \\ \phi (x_{m1})&{}\dots &{}\phi (x_{ms}) \end{pmatrix}. \end{array} \end{aligned}$$

(2)

This map is known as field reduction since it maps subspaces over ${{\mathbb {F}}}_{q^k}$ into subspaces over the subfield ${{\mathbb {F}}}_q$ (see [8, 17, 21, 22]). Let us recall some useful properties of the map $\varphi$ pointed out in [17] that we will use in Sect. 3.2.2.

Proposition 2.1

The map $\varphi$ defined in (2) satisfies the following:

• (1) $\varphi$ is injective.

• (2) For any pair of subspaces $\mathcal {U}, \mathcal {V}$ of ${\mathbb {F}}_{q^k}^s$, we have $\varphi (\mathcal {U}\cap \mathcal {V})=\varphi (\mathcal {U}) \cap \varphi (\mathcal {V})$.

• (3) Given $\mathcal {U}, \mathcal {V}$ subspaces of ${{\mathbb {F}}}_{q^k}^s$ with $\mathcal {U}\subseteq \mathcal {V}$, then $\varphi (\mathcal {U}) \subseteq \varphi (\mathcal {V})$.

• (4) For any $m\in \{1,\dots ,s-1\}$, it holds that $\varphi (\mathcal {G}_{q^k}(m,s))\subseteq \mathcal {G}_{q}(mk,sk)$.

2.2 Constant dimension codes

The Grassmannian $\mathcal {G}_q(k,n)$ can be considered as a metric space with the subspace distance defined as:

$$\begin{aligned} d_S(\mathcal {U}, \mathcal {V})= \dim (\mathcal {U}+\mathcal {V})-\dim (\mathcal {U}\cap \mathcal {V})=2(k-\dim (\mathcal {U}\cap \mathcal {V})), \end{aligned}$$

(3)

for all $\mathcal {U}, \mathcal {V}\in \mathcal {G}_q(k,n)$ (see [13]).

A constant dimension (subspace) code of dimension k and length n is any nonempty subset $\mathcal {C}\subseteq \mathcal {G}_q(k,n)$. The minimum subspace distance of the code $\mathcal {C}$ is defined as

$$\begin{aligned} d_S(\mathcal {C})=\min \{ d_S(\mathcal {U}, \mathcal {V}) \ | \ \mathcal {U}, \mathcal {V}\in \mathcal {C}, \ \mathcal {U}\ne \mathcal {V}\} \end{aligned}$$

(see [26] and references therein, for instance). It follows that the minimum distance of a constant dimension code $\mathcal {C}$ is upper-bounded by:

$$\begin{aligned} d_S(\mathcal {C})\leqslant \left\{ \begin{array}{lll} 2k &{}\quad \text {if} &{} 2k\leqslant n, \\ 2(n-k) &{}\quad \text {if} &{} 2k > n. \end{array} \right. \end{aligned}$$

(4)

Constant dimension codes $\mathcal {C}\subseteq \mathcal {G}_q(k,n)$ in which the distance between any pair of different codewords is $d_S(\mathcal {C})$ are said to be equidistant. For such codes, there exists some value $c<k$ such that, given two different subspaces $\mathcal {U}, \mathcal {V}\in \mathcal {C}$, it holds that $\dim (\mathcal {U}\cap \mathcal {V})=c$. Hence, the minimum distance of the code is precisely $d_S(\mathcal {C})=2(k-c)$, and $\mathcal {C}$ is also called an equidistant c-intersecting constant dimension code. In case the value c is the minimum possible dimension of the intersection between k-dimensional subspaces of ${{\mathbb {F}}}_q^n$, that is,

$$\begin{aligned} c=\left\{ \begin{array}{lll} 0 &{}\quad \text {if} &{} 2k\leqslant n, \\ 2k-n &{}\quad \text {if} &{} 2k > n, \end{array} \right. \end{aligned}$$

equidistant c-intersecting codes attain the bound given in (4). In particular, for dimensions $k \leqslant \lfloor \frac{n}{2}\rfloor$, we have that these codes are 0-intersecting codes known as partial spreads. The cardinality of any partial spread $\mathcal {C}$ in $\mathcal {G}_q(k,n)$ always satisfies

$$\begin{aligned} |\mathcal {C}| \leqslant \left\lfloor \frac{q^n-1}{q^k-1} \right\rfloor \end{aligned}$$

(5)

(see [9, Lemma 7]). Partial spread codes and equidistant codes have been studied in [6, 9, 10]. Whenever k divides n, the previous bound is attained by the so-called spread codes (or k-spreads) of ${{\mathbb {F}}}_q^n$. Notice that a k-spread $\mathcal {S}$ is a subset of $\mathcal {G}_q(k,n)$ whose elements give a vector space partition of ${{\mathbb {F}}}_q^n$. Spreads are classical objects coming from finite geometry (see [25], for instance). For further information related to spreads in the network coding framework, we refer the reader to [8, 21, 22, 26].

The following spread is due to Segre [25]. In the network coding setting, it was presented for the first time in [21] as a construction of spread code. Denote by $GL_k(q)$ the general linear group of degree k over the field ${{\mathbb {F}}}_q$. Let $P \in GL_k(q)$ be the companion matrix of a monic irreducible polynomial in ${{\mathbb {F}}}_q[x]$. We will write $I_k$ and $\mathrm {0}_k$ to denote the identity matrix and the zero matrix of size $k\times k,$ respectively. Take $s \in {{\mathbb {N}}}$ such that $n=sk$. Then, the following family of k-dimensional subspaces is a spread code:

$$\begin{aligned} \mathcal {S}(s,k,P)=\{{\mathrm {rowsp}{(}}S)\mid S\in \Sigma \} \subseteq \mathcal {G}_q(k,n), \end{aligned}$$

(6)

where $\Sigma$ is the set of $k\times ks$ matrices

$$\begin{aligned} \Sigma =\{( A_1 | A_{2} | \dots | A_s)\,\big |\, A_i \in {{\mathbb {F}}}_q[P]\} \end{aligned}$$

(7)

with the first nonzero block from the left equal to $I_k$.

Remark 2.2

Notice that the matrices in $\Sigma$ are in reduced row echelon form and it is clear that the field reduction map $\varphi$ defined in (2) gives a bijection between the Grassmannian of lines $\mathcal {G}_{q^k}(1,s)$ and the spread code $\mathcal {S}(s,k,P)$

(8)

We will come back to this fact in Sect. 3.2.2.

Given a constant dimension code $\mathcal {C}\subseteq \mathcal {G}_q(k,n)$, the dual code of $\mathcal {C}$ is the subset of $\mathcal {G}_q(n-k,n)$ given by

$$\begin{aligned} \mathcal {C}^\perp =\{ \mathcal {U}^\perp \ | \ \mathcal {U}\in \mathcal {C}\}, \end{aligned}$$

where $\mathcal {U}^\perp$ is the orthogonal of $\mathcal {U}$ with respect to the usual inner product in ${{\mathbb {F}}}_q^n$. In [13], it was proved that $\mathcal {C}$ and $\mathcal {C}^\perp$ have both the same cardinality and minimum distance. Notice that the dual of a partial spread of dimension $k\leqslant \lfloor \frac{n}{2}\rfloor$ is an equidistant $(n-2k)$-intersecting code of dimension $n-k$ and conversely.

2.3 Flag codes

Subspace codes were introduced for the first time in [13] as error-correction codes in random network coding. In that paper, the authors propose a suitable network channel with a single transmitter and several receivers that is used just once, so that subspace codes can be considered as one-shot codes. The use of the channel more than once was suggested originally in [23] and gave rise to the so-called multishot codes as a generalization of subspace codes. We call any nonempty subset $\mathcal {C}$ of $\mathcal {P}_q(n)^r$ a multishot code of length $r\geqslant 1$, or just r-shot code. In particular, if codewords in $\mathcal {C}$ are sequences of nested subspaces, we say that $\mathcal {C}$ is a flag code. Flag codes were first studied as orbits of group actions in [19], and, in [16], the reader can find a study of bounds on the cardinality of full flag codes with a prescribed distance. Let us recall some concepts in the setting of flag codes.

A flag of type $(t_1, \dots , t_r)$, with $0<t_1<\dots<t_r<n$, on the vector space ${\mathbb {F}}_q^n$ is a sequence of subspaces $\mathcal {F}=(\mathcal {F}_1,\dots , \mathcal {F}_r)$ in $\mathcal {G}_q(t_1,n) \times \dots \times \mathcal {G}_q(t_r,n) \subseteq \mathcal {P}_q(n)^r$ such that

$$\begin{aligned} \{0\}\subsetneq \mathcal {F}_1 \subsetneq \dots \subsetneq \mathcal {F}_r \subsetneq {\mathbb {F}}_q^n. \end{aligned}$$

With this notation, $\mathcal {F}_i$ is said to be the i-th subspace of $\mathcal {F}$. In case the type vector is $(1, 2, \dots , n-1),$ we say that ${\mathcal {F}}$ is a full flag.

The space of flags of type $(t_1, \dots , t_r)$ on ${\mathbb {F}}_q^n$ is denoted by $\mathcal {F}_q((t_1,...,t_r),n)$ and can be endowed with the flag distance $d_f$ that naturally extends the subspace distance defined in (3): given two flags $\mathcal {F}=(\mathcal {F}_1,\dots , \mathcal {F}_r)$ and $\mathcal {F}'=(\mathcal {F}'_1,\dots , \mathcal {F}'_r)$ in $\mathcal {F}_q( (t_1, \dots , t_r),n)$, the flag distance between them is

$$\begin{aligned} d_f(\mathcal {F},\mathcal {F}')= \sum _{i=1}^r d_S(\mathcal {F}_i, \mathcal {F}'_i). \end{aligned}$$

A flag code of type $(t_1, \dots , t_r)$ on ${{\mathbb {F}}}_q^n$ is defined as any non-empty subset $\mathcal {C}\subseteq \mathcal {F}_q((t_1, \dots , t_r), n)$. The minimum distance of a flag code $\mathcal {C}$ of type $(t_1, \dots , t_r)$ on ${{\mathbb {F}}}_q^n$ is given by

$$\begin{aligned} d_f(\mathcal {C})=\min \{d_f(\mathcal {F},\mathcal {F}')\ |\ \mathcal {F},\mathcal {F}'\in \mathcal {C}, \ \mathcal {F}\ne \mathcal {F}'\}. \end{aligned}$$

Given a type vector $(t_1, \dots , t_r)$, for every $i=1, \dots , r$, we define the i-projection to be the map

$$\begin{aligned} \begin{array}{rccc} {p_i}: &{} \mathcal {F}_q((t_1, \dots , t_r), n) &{} \longrightarrow &{} \mathcal {G}_q(t_i,n) \\ &{} &{} &{}\\ &{} \mathcal {F}=(\mathcal {F}_1,\dots ,\mathcal {F}_r) &{} \longmapsto &{} p_i(\mathcal {F})= \mathcal {F}_i. \end{array} \end{aligned}$$

(9)

The i-projected code of $\mathcal {C}$ is the set $\mathcal {C}_i=\{p_i(\mathcal {F})\,| \,\mathcal {F}\in \mathcal {C}\}$. By definition, this code $\mathcal {C}_i$ is a constant dimension code in the Grassmannian $\mathcal {G}_q(t_i, n)$ and its cardinality satisfies $\vert \mathcal {C}_i\vert \leqslant \vert \mathcal {C}\vert$. We say that $\mathcal {C}$ is a disjoint flag code if $|\mathcal {C}_1|=\dots =|\mathcal {C}_r|=|\mathcal {C}|$, that is, the i-projection $p_i$ is injective for any $i \in \{1, \dots , r\}$.

The distance of a flag code $\mathcal {C}$ of type $(t_1, \dots , t_r)$ is upper-bounded by:

$$\begin{aligned} d_f(\mathcal {C}) \leqslant 2 \left( \sum _{t_i\leqslant \lfloor \frac{n}{2} \rfloor } t_i + \sum _{t_i > \lfloor \frac{n}{2} \rfloor } (n-t_i) \right) . \end{aligned}$$

(10)

In particular, if $\mathcal {C}$ is a full flag code, we have that (10) becomes

$$\begin{aligned} d_f(\mathcal {C})\leqslant \left\{ \begin{array}{lccc} \dfrac{n^2}{2}, &{} \text {for} &{} n &{} \text {even}, \\ &{} &{} &{} \\ \dfrac{n^2-1}{2}, &{} \text {for} &{} n &{} \text {odd}. \end{array} \right. \end{aligned}$$

2.4 Matchings in graphs

Now we introduce some basic concepts and results on graphs in order to use them in the construction of a specific family of flag codes with the maximum distance in Sect. 3. All these definitions and results together with their proofs can be found in [3].

A graph $G=(V,E)$ consists of a vertex set V and an edge set $E\subset V \times V$ where an edge is an unordered pair of vertices. Two vertices $v,v'\in V$ are adjacent if $(v,v') \in E$. Also, we say that $(v,v')$ is an incident edge with v and $v'$. Two edges are adjacent if they have a common vertex. Given a vertex $v \in V$ we call the degree of v to the number of incident edges with v. A graph G is said to be k-regular, if each vertex in G has degree k.

On the other hand, a set of vertices (or edges) is independent if it does not contain adjacent elements. A set $M\subseteq E$ of independent edges of a graph $G=(V,E)$ is called a matching. A matching M matches $S \subseteq V$ if every vertex in S is incident with an edge in M and M is perfect if it matches V.

A graph G is bipartite if the vertex set can be partitioned into two sets $V=A\cup B$ such that there is no pair of adjacent vertices neither in A nor in B. For this class of graphs, perfect matchings are just bijections between A and B given by a subset of edges of the graph connecting each vertex in A with another vertex in B. The following classic result, whose proof can be found in [3] (pages 37–38), states the existence of perfect matchings in a family of graphs:

Theorem 2.3

Any k-regular bipartite graph admits a perfect matching.

The search for maximum matchings in bipartite graphs is a classical problem in graph theory that started in the 1930s with the works of König and of Egerváry (see [5, 14]). Later, Kuhn and M. Hall tackled this problem and presented the first formal algorithms to find perfect matchings in bipartite graphs (see [11, 15]). This type of algorithms is known as “Hungarian Method”. Finding matchings in non-bipartite graphs is a more difficult problem, and the first (efficient) algorithm in this direction was provided by Edmonds in 1965 (see [4]). For further information on matching theory, see [20] and references inside.

We will use the previous Theorem through Sect. 3 in order to give perfect matchings of a particular regular bipartite graph of our interest. Such matchings will allow us to construct disjoint flag codes of a specific type as we will show later.

3 Optimum distance flag codes from spreads

Flag codes attaining the bound in (10) are called optimum distance flag codes and can be characterized in terms of their projected codes in the following way:

Theorem 3.1

(see [2]) Let $\mathcal {C}$ be a flag code of type $(t_1, \dots , t_r)$. The following statements are equivalent:

• (i) $\mathcal {C}$ is an optimum distance flag code.

• (ii) $\mathcal {C}$ is disjoint, and every projected code $\mathcal {C}_i$ attains the maximum possible subspace distance.

As a consequence, the i-projected codes of an optimum distance flag code have to be partial spreads if $t_i \leqslant \lfloor \frac{n}{2} \rfloor$ and equidistant $(2t_i-n)$-intersecting subspace codes for dimensions $t_i> \lfloor \frac{n}{2} \rfloor$.

As mentioned in Sect. 2.2, whenever k divides n, k-spread codes are partial spread codes (constant dimension codes with maximum distance) with the best size. This good property of spreads naturally gives rise to the question of finding optimum distance flag codes having a spread as their i-projected code when the dimension $t_i$ is a divisor of n. Note that, due to the disjointness property, we could have at most one spread among the projected codes. In [2], it was proved that having a spread as a projected code makes optimum distance flag codes attain the maximum possible size as well.

Theorem 3.2

[2, Theorem 3.12] Let k be a divisor of n and assume that $\mathcal {C}$ is an optimum distance flag code of type $(t_1, \dots , t_r)$ on ${{\mathbb {F}}}_q^n$. If some $t_i=k$, then $|\mathcal {C}|\leqslant \frac{q^n-1}{q^k-1}$ and equality holds if, and only if, the i-projected code $\mathcal {C}_i$ is a k-spread of ${{\mathbb {F}}}_q^n$.

In the same paper, it is shown that, for the full type vector $(1,\dots ,n-1)$, it is possible to find optimum distance full flag codes having a spread as a k-projected code only if either $n=2k$ or $n=3$ and $k=1$. Observe that there, the authors always work with full flag codes (the full type vector is fixed) and then provide conditions on n and k. Now, we deal with the inverse problem: given n and a divisor k of n, we look for conditions on the type vector of an optimum distance flag code on ${{\mathbb {F}}}_q^n$ having a k-spread as a projected code. We conclude that not all the type vectors are allowed. Let us describe the admissible ones and provide a construction of optimum distance flag codes for them, based on the existence of perfect matchings in a specific graph.

3.1 Admissible type vectors

This paper is devoted to explore the existence of optimum distance flag codes of a general type vector $(t_1,\dots ,t_r)$, not necessarily the full type, having a spread as their i-projected code when $t_i$ is a divisor of n. The next result states the necessary conditions that the type vector $(t_1,\dots ,t_r)$ must satisfy.

Theorem 3.3

Let $\mathcal {C}$ be an optimum distance flag code of type $(t_1, \dots , t_r)$on ${{\mathbb {F}}}_q^n$. Assume that some dimension $t_i=k$ divides n and the associated projected code $\mathcal {C}_i$ is a k-spread. Then, for each $j\in \{1, \dots , r\}$, either $t_j\leqslant k$ or $t_j \geqslant n-k$.

Proof

Notice that in case $i=r$, clearly $t_j\leqslant t_r=k$, for every $j=1, \dots , r$. Suppose that $i<r$. Let us show that $t_{i+1}\geqslant n-k$.

Since $t_i=k$ divides n, we can write $n=sk$, for some $s\geqslant 2$. If $s=2$, we have that $n-k=k$ and the result trivially holds. In case $s>2$, then $s<2(s-1)$ and we have that $2k< n < 2(s-1)k=2(n-k)$. We deduce that $k \leqslant \lfloor \frac{n}{2} \rfloor < n-k$. Now, by contradiction, assume that $t_{i+1}< n-k$. We distinguish two possibilities:

• (1) If $k < t_{i+1} \leqslant \lfloor \frac{n}{2}\rfloor$, since $\mathcal {C}$ is an optimum distance flag code, by Theorem 3.1, its projected code $\mathcal {C}_{i+1}$ must be a partial spread of dimension $t_{i+1}$ and cardinality $\vert \mathcal {C}_{i+1}\vert =\vert \mathcal {C}_{i}\vert =\frac{q^{n}-1}{q^{k}-1}$. Contradiction with (5).

• (2) If $\lfloor \frac{n}{2}\rfloor< t_{i+1} <n-k$, the projected code $\mathcal {C}_{i+1}$ has to be an equidistant $(2t_{i+1}-n)$-intersecting constant dimension code. In other words, the subspace distance of $\mathcal {C}_{i+1}$ is $2(n-t_{i+1})$. Hence, its dual code $\mathcal {C}_{i+1}^{\perp }$ is a partial spread of dimension $n-t_{i+1}>n-k>k$ and cardinality $\vert \mathcal {C}_{i+1}\vert =\vert \mathcal {C}_{i}\vert =\frac{q^{n}-1}{q^{k}-1}$, which again contradicts (5).

We conclude that $t_{i+1} \geqslant n-k$.

Remark 3.4

This result provides a necessary condition on the type vector of any optimum distance flag code on ${{\mathbb {F}}}_q^n$ having a k-spread as a projected code. According to this, we say that a type vector is admissible if it satisfies the conditions in Theorem 3.3. In other words, if

$$\begin{aligned} k \in \{ t_1, \dots , t_r\} \subseteq \{1, \dots , k, n-k, \dots , n-1\}. \end{aligned}$$

Notice that every type vector containing the dimension k is admissible when $n=2k$ since, in that case, it holds $k=n-k$. This particular case has been already studied in [2], where it was proved that optimum distance flag codes of any type vector containing the dimension k can be constructed from a k-spread (planar spread). Moreover, those codes were shown to attain the maximum possible cardinality as well. In the next subsection, we tackle the problem of constructing flag codes attaining the maximum distance and having a k-spread as their projected code for any admissible type vector in the general case $n=ks$, for $s\geqslant 3$.

3.2 A construction based on perfect matchings

This part is devoted to describe a specific construction of optimum distance flag codes on ${{\mathbb {F}}}_q^n$ from a k-spread of a given admissible type vector $(t_1, \dots , t_r)$. By means of Theorem 3.3, if such codes exist, their type vector must satisfy $k \in \{t_1, \dots , t_r\} \subseteq \{1, \dots , k, n-k, \dots , n-1\}$. For the sake of simplicity, we undertake this construction in several phases: we consider first the admissible type vector $(1,n-1)$, that is, the construction of optimum distance flag codes from the spread of lines. Secondly, by using the field reduction map defined in Sect. 2.1, we properly translate the construction in the first step to get optimum distance flag codes of type vector $(k,n-k)$ having the k-spread $\mathcal {S}$ introduced in (6) as its first projected code. Then, taking advantage of certain properties of the k-spread $\mathcal {S}$, we extend the construction in the second step to obtain optimum distance flag codes of the full admissible type, that is, $(1, \dots , k, n-k, \dots , n-1)$. Finally, this last construction gives optimum distance flag codes of any admissible type vector after a suitable puncturing process. Let us explain in detail all these stages.

3.2.1 The type vector $(1,n-1)$: starting from the spread of lines

Take $n\geqslant 3$. In this section, we provide a construction of optimum distance flag codes on ${{\mathbb {F}}}_q^n$ from the spread of lines, that is, having the Grassmannian $\mathcal {G}_q(1, n)$ as a projected code. By Theorem 3.3, the only admissible type vector in this case is $(1,n-1)$. In other words, to give an optimum distance flag code from the spread of lines of ${{\mathbb {F}}}_q^n,$ we have to provide a family of $|\mathcal {G}_q(1, n)|$ pairwise disjoint flags of length two, all of them consisting of a line contained in a hyperplane. To do so, we translate this problem to the one of finding perfect matchings in bipartite regular graphs, using the results given in Sect. 2.4. Let us precise this.

Consider the graph $G=(V, E)$, with set of vertices $V=\mathcal {G}_q(1,n) \cup \mathcal {G}_q(n-1,n)$ and set of edges E defined by

$$\begin{aligned} E=\{(l,H)\in \mathcal {G}_q(1,n) \times \mathcal {G}_q(n-1,n) \ | \ l\subset H \}. \end{aligned}$$

Notice that the set of vertices in G consists of the lines and hyperplanes of ${{\mathbb {F}}}_q^n$. An edge (l, H) of G exists if, and only if, the line l is contained in the hyperplane H. With this notation, the next result holds.

Proposition 3.5

The graph $G=(V, E)$ is bipartite and $\frac{q^{(n-1)}-1}{q-1}$-regular.

Proof

It is clear that G is a bipartite graph by definition. Moreover, the number of hyperplanes containing a fixed line coincides with the number of lines lying on a given hyperplane. This number is precisely $\frac{q^{(n-1)}-1}{q-1}$. Then, the degree of any vertex in G coincides with this value, and then, G is $\frac{q^{(n-1)}-1}{q-1}$-regular.

Note that the problem of giving a family of flags with the desired conditions can be seen as the combinatorial problem of giving a perfect matching in G. Since G is a regular bipartite graph, we can use Theorem 2.3 to conclude that there exist perfect matchings in G. More precisely, there exists a subset $M\subset E$ that matches V, that is, each edge in M has an extremity in $\mathcal {G}_q(1,n)$ and the other one in $\mathcal {G}_q(n-1,n)$. In particular, the set M has a number of edges equal to $|\mathcal {G}_q(1,n)|$. This matching M induces naturally a bijection, also denoted by M, between the set of lines and the set of hyperplanes in ${\mathbb {F}}_q^n$. Moreover, by the definition of E, we have that the map $M : \mathcal {G}_q(1,n) \rightarrow \mathcal {G}_q(n-1,n)$ satisfies that $l\subset M(l)$ for any $l\in \mathcal {G}_q(1,n)$. This fact allows us to construct a family of flags of type $(1,n-1)$ on ${{\mathbb {F}}}_q^n$ in the following way:

$$\begin{aligned} \widetilde{\mathcal {C}}=\widetilde{\mathcal {C}}_M=\{ (l,M(l)) \ | \ l \in \mathcal {G}_q(1,n) \}. \end{aligned}$$

(11)

Let us see that the family $\widetilde{\mathcal {C}}$ is a flag code with projected codes $\widetilde{\mathcal {C}}_1=\mathcal {G}_q(1,n)$ and $\widetilde{\mathcal {C}}_2=\mathcal {G}_q(n-1,n)$ satisfying the desired conditions.

Theorem 3.6

Given $n\geqslant 3$, the code $\widetilde{\mathcal {C}}$ defined in (11) is an optimum distance flag code of type $(1,n-1)$ on ${{\mathbb {F}}}_q^n$ with the spread of lines as a projected code.

Proof

Since the map M defined above is bijective, the code $\widetilde{\mathcal {C}}$ must be a disjoint flag code with projected codes $\widetilde{\mathcal {C}}_1=\mathcal {G}_q(1,n)$ and $\widetilde{\mathcal {C}}_2=\mathcal {G}_q(n-1,n).$ In particular, as $d_S(\widetilde{\mathcal {C}}_1)=d_S(\widetilde{\mathcal {C}}_2)=2$ is the maximum possible distance for constant dimension codes of dimension 1 and $n-1$ in ${{\mathbb {F}}}_q^n$, by Theorem 3.1, we have that $\widetilde{\mathcal {C}}$ is an optimum distance flag code with $\mathcal {G}_q(1,n)$ as a projected code.

Remark 3.7

Observe that, by means of Theorem 3.2, our code $\widetilde{\mathcal {C}}$ defined as above attains the maximum possible cardinality for flag codes of type $(1,n-1)$ and distance 4, which is

$$\begin{aligned} |\widetilde{\mathcal {C}}| = \dfrac{q^n-1}{q-1}= q^{n-1}+q^{n-2}+\dots + q+1. \end{aligned}$$

For the particular case $n=3$, the previous bound was given in [16], where the author studied bounds for the cardinality of full flag codes with a given distance. Observe that this is the only case in which optimum distance full flag codes with a spread as a projected code can be constructed, apart from the case $n=2k$, as it was explained in [2].

Note that, despite the fact that Theorem 2.3 guarantees the existence of perfect matchings in regular bipartite graphs, in order to provide a concrete construction of optimum distance flag codes of type $(1,n-1)$ on ${{\mathbb {F}}}_q^n$, we need to get a precise matching in G. As said in Sect. 2, this can be done by using known algorithms (see [7, 11, 12, 15], for instance). In Sect. 3.3, we exhibit an optimum distance flag code of type (2, 4) constructed as a perfect matching obtained with GAP.

3.2.2 The type vector $(k,n-k)$

Take $n=ks$ a natural number with $k\geqslant 2$ and $s\geqslant 3$. In order to construct optimum distance flag codes of type $(k, n-k)$ on ${{\mathbb {F}}}_q^{n}$, we will use the construction of optimum distance flag codes of type $(1,s-1)$ on ${{\mathbb {F}}}_{q^k}^s$ given in Sect. 3.2.1 together with the field reduction map defined in Sect. 2.1. Let us explain this construction.

Let $M : \mathcal {G}_{q^k}(1,s) \rightarrow \mathcal {G}_{q^k}(s-1,s)$ be a bijection such that $l\subset M(l)$ for any $l\in \mathcal {G}_{q^k}(1,s)$. By Theorem 3.6, we know that the code

$$\begin{aligned} \widetilde{\mathcal {C}}=\widetilde{\mathcal {C}}_M=\{ (l,M(l)) \ | \ l \in \mathcal {G}_{q^k}(1,s) \} \end{aligned}$$

is an optimum distance flag of type $(1, s-1)$ on ${{\mathbb {F}}}_{q^k}^s$. In particular, the code $\widetilde{\mathcal {C}}$ is disjoint. On the other hand, given $P \in GL_k(q)$ the companion matrix of a monic irreducible polynomial of degree k in ${{\mathbb {F}}}_q[x]$, the associated field isomorphism $\phi :{{\mathbb {F}}}_{q^k}\rightarrow {{\mathbb {F}}}_q[P]$ induces the field reduction ${\varphi }: \mathcal {P}_{q^k}(s) \longrightarrow \mathcal {P}_q(ks)$ as in (2). Notice that, by Proposition 2.1, we have that for any $m\in \{1,\dots ,s-1\}$, it holds that $\varphi (\mathcal {G}_{q^k}(m,s))\subseteq \mathcal {G}_{q}(mk,sk)$. Moreover, given $\mathcal {U}, \mathcal {V}$ subspaces of ${{\mathbb {F}}}_{q^k}^s$ with $\mathcal {U}\subseteq \mathcal {V}$, then $\varphi (\mathcal {U}) \subseteq \varphi (\mathcal {V})$. As a consequence, if $(l, M(l)) \in \widetilde{\mathcal {C}}$, then $(\varphi (l),\varphi (M(l)))$ is a flag of type $(k, n-k)$ on ${{\mathbb {F}}}_{q}^n$. This fact allows us to define a family of flags over ${{\mathbb {F}}}_{q}^n$ as follows

$$\begin{aligned} \widehat{\mathcal {C}}=\{ (\varphi (l),\varphi (M(l))) \ | \ l \in \mathcal {G}_{q^k}(1,s) \}. \end{aligned}$$

(12)

By Remark 2.2, we know that $\varphi$ gives a bijection between $\mathcal {G}_{q^k}(1,s)$ and the k-spread $\mathcal {S}=\mathcal {S}(s,k,P)$ defined in (6). Hence, the family $\widehat{\mathcal {C}}$ is a flag code with projected codes

$$\begin{aligned} \widehat{\mathcal {C}}_1=\varphi (\mathcal {G}_{q^k}(1,s))=\mathcal {S}, \, \widehat{\mathcal {C}}_2=\varphi (\mathcal {G}_{q^k}(s-1,s)) \end{aligned}$$

and the following result holds:

Theorem 3.8

The code $\widehat{\mathcal {C}}$ defined in (12) is an optimum distance flag code of type $(k,n-k)$ on ${{\mathbb {F}}}_q^n$ having the spread $\mathcal {S}$ as a projected code.

Proof

Since $\widehat{\mathcal {C}}_1=\varphi (\mathcal {G}_{q^k}(1,s))=\mathcal {S}$, we have $|\widehat{\mathcal {C}}|=|\widehat{\mathcal {C}}_1|=|\varphi (\mathcal {G}_{q^k}(1,s))|=|\mathcal {G}_{q^k}(1,s)|$. Furthermore, by the injectivity of $\varphi$ (see Proposition 2.1), we also have that $|\widehat{\mathcal {C}}_2|=|\varphi (\mathcal {G}_{q^k}(s-1,s))|=|\mathcal {G}_{q^k}(s-1,s)|$. As $|\mathcal {G}_{q^k}(1,s)|=|\mathcal {G}_{q^k}(s-1,s)|$, we conclude that $|\widehat{\mathcal {C}}|=|\widehat{\mathcal {C}}_1|=|\widehat{\mathcal {C}}_2|$ and $\widehat{\mathcal {C}}$ is disjoint. Let us now prove that the projected codes of $\widehat{\mathcal {C}}$ are constant dimension codes with the maximum possible distance. Since the projected code $\widehat{\mathcal {C}}_1$ is a spread, it is enough to check this property for $\widehat{\mathcal {C}}_2$. Given any two different subspaces $\varphi (H), \varphi (H') \in \widehat{\mathcal {C}}_2=\varphi (\mathcal {G}_{q^k}(s-1,s))$, by means of Proposition 2.1, we have that $H, H'$ are different hyperplanes. Moreover, since the intersection of any two hyperplanes in ${\mathbb {F}}_{q^k}^s$ is a $(s-2)$-dimensional subspace of ${{\mathbb {F}}}_{q^k}^s$ we have that

$$\begin{aligned} \dim (\varphi (H)\cap \varphi (H')) = \dim (\varphi (H\cap H')) =k(s-2)=n-2k. \end{aligned}$$

Notice that $n-2k= 2(n-k)-n$ is the minimum among the possible dimensions of the intersection of subspaces in $\mathcal {G}_q(n-k,n)$. Hence, $\widehat{\mathcal {C}}_2$ is an equidistant $(n-2k)$-intersecting constant dimension code and, by applying Theorem 3.1, we are done.

3.2.3 The full admissible type vector

In this subsection, we finally tackle the construction of optimum distance flag codes of the full admissible type, that is, of type $(1, \dots , k, n-k, \dots , n-1)$ on ${{\mathbb {F}}}_q^{n}$ having the k-spread $\mathcal {S}$ defined in (6) as a projected code. To do this, we start from the optimum distance flag code $\widehat{\mathcal {C}}$ of type $(k,n-k)$ defined in (12). Recall that the construction of this code depends on the choice of a bijection $M : \mathcal {G}_{q^k}(1,s) \rightarrow \mathcal {G}_{q^k}(s-1,s)$ such that $l\subset M(l)$ for any $l\in \mathcal {G}_{q^k}(1,s)$.

Let us fix an order in the set of lines of ${{\mathbb {F}}}_{q^k}^s$ and write $\mathcal {G}_{q^k}(1,s)=\{l_1, l_2, \dots , l_L\}$, where $L=|\mathcal {G}_{q^k}(1,s)|$. This order in $\mathcal {G}_{q^k}(1,s)$ naturally induces respective orders in the sets $\mathcal {G}_{q^k}(s-1,s)$, $\mathcal {S}$ and $\mathcal {H}=\varphi (\mathcal {G}_{q^k}(s-1,s))$ as follows:

$$\begin{aligned} H_i=M(l_i), \, \mathcal {S}_i=\varphi (l_i), \mathcal {H}_i=\varphi (H_i) \end{aligned}$$

for $i=1,\dots , L$. Denote also by $\mathrm {S}_i$ the RREF generator matrix of $\mathcal {S}_i$. Notice that $\mathrm {S}_i \in \Sigma$ where $\Sigma$ is the set defined in (7), and $\mathrm {S}_i=(\phi (x_{i1})| \dots | \phi (x_{is})),$ where $(x_{i1}, \dots , x_{is})\in {{\mathbb {F}}}_{q^k}^s$ is the RREF matrix generating the line $l_i$.

Now, given a hyperplane $H_i=M(l_i)$ of ${{\mathbb {F}}}_{q^k}^s$, we can write

$$\begin{aligned} H_i = l_{i} \oplus l_{i_2} \oplus \dots \oplus l_{i_{s-1}}, \end{aligned}$$

for $l_{i_2}, \dots , l_{i_{s-1}}$ some lines of ${{\mathbb {F}}}_{q^k}^s.$ By the properties of the field reduction $\varphi$ described in Proposition 2.1, we have that

$$\begin{aligned} \mathcal {H}_i=\varphi (H_i)=\mathcal {S}_{i}\oplus \mathcal {S}_{i_2}\oplus \dots \oplus \mathcal {S}_{i_{s-1}}. \end{aligned}$$

So, any subspace $\mathcal {H}_i \in \mathcal {H}$ can be decomposed as a direct sum of subspaces in $\mathcal {S}$. This representation is not unique since $H_i$ can be written as direct sum of different collections of lines. Moreover, given that for any line $l_{i_s}$ in ${{\mathbb {F}}}_{q^k}^s \setminus H_i$, it holds that $H_i\oplus l_{i_s}={{\mathbb {F}}}_{q^k}^s$, by using Proposition 2.1 again, we conclude that $\mathcal {H}_i \oplus \mathcal {S}_{i_s}={{\mathbb {F}}}_q^{n}$. As a consequence, the rows of the matrix

$$\begin{aligned} \mathrm {W}_i= \left( \begin{array}{l} \mathrm {S}_i\\ \mathrm {S}_{i_2}\\ \vdots \\ \mathrm {S}_{i_{s-1}}\\ \mathrm {S}_{i_s}\\ \end{array} \right) \end{aligned}$$

(13)

form a basis of ${{\mathbb {F}}}_q^{n}$. Moreover, any collection of $j\leqslant n$ rows of $\mathrm {W}_i$ generates a j-dimensional subspace of ${{\mathbb {F}}}_q^{n}$.

Denote by $\mathrm {W}_i^{(j)}$ the submatrix of $\mathrm {W}_i$ given by its first j rows. We also denote by $\mathcal {W}_i^{(j)}={\mathrm {rowsp}{(}}\mathrm {W}_i^{(j)})$. With this notation, it is clear that $\mathcal {W}_i^{(k)}=\mathcal {S}_i$ and $\mathcal {W}_i^{(n-k)}=\mathcal {H}_i$. In addition, for any $1\leqslant j_1 < j_2 \leqslant n$, it holds that $\mathcal {W}_i^{(j_1)} \subsetneq \mathcal {W}_i^{(j_2)}$. This fact allows us to define $\mathcal {F}_{\mathrm {W}_i}$ the flag of type $(1, \dots , k, n-k, \dots , n-1)$ associated with $\mathrm {W}_i$ in the following way:

$$\begin{aligned} \mathcal {F}_{\mathrm {W}_i}=\left( \mathcal {W}_i^{(1)}, \dots , \mathcal {W}_i^{(k-1)}, \mathcal {S}_i, \mathcal {H}_i, \mathcal {W}_i^{(n-k+1)}, \dots , \mathcal {W}_i^{(n-1)}\right) . \end{aligned}$$

(14)

Finally, given the family of matrices $\{\mathrm {W}_i\}_{i=1}^L$, we define the family of associated flags of type $(1,\dots ,k,n-k,\dots ,n-1)$:

$$\begin{aligned} \mathcal {C}=\{ \mathcal {F}_{\mathrm {W}_i} \ | \ i=1, \dots , L \}. \end{aligned}$$

(15)

Let us see that $\mathcal {C}$ is an optimum distance flag code. To do so, we analyze the structure of its projected codes:

$$\begin{aligned} \mathcal {C}_j=\left\{ \mathcal {W}_i^{(j)} \ | \ i=1, \dots , L \right\} \end{aligned}$$

(16)

and

$$\begin{aligned} \mathcal {C}_{k+j}=\left\{ \mathcal {W}_i^{(n-k+j-1)} \ | \ i=1, \dots , L \right\} , \end{aligned}$$

(17)

for all $j=1, \dots , k.$

Proposition 3.9

Given the flag code $\mathcal {C}$ defined as above, for each $j=1, \dots , k$ the following is satisfied:

• (1) The code $\mathcal {C}_j$ is a partial spread in $\mathcal {G}_q(j, n)$ with cardinality $L=\frac{q^n-1}{q^k-1}$.

• (2) The code $\mathcal {C}_{k+j}$ is an equidistant $(n-2k+2(j-1))$-intersecting constant dimension code in $\mathcal {G}_q(n-k+j-1, n)$ with cardinality $L=\frac{q^n-1}{q^k-1}$. As a consequence, $\mathcal {C}_{k+j}$ is a constant dimension code of maximum distance.

In particular, we have that $\mathcal {C}_k=\mathcal {S}$ and $\mathcal {C}_{k+1}=\mathcal {H}$.

Proof

By construction, it is clear that $\mathcal {C}_k=\mathcal {S}$ and $\mathcal {C}_{k+1}=\mathcal {H}$. Now, for any $1\leqslant j\leqslant k$, given two different indices $i_1,i_2\in \{ 1, \dots , L\}$, we have that

$$\begin{aligned} \mathcal {W}_{i_1}^{(j)} \cap \mathcal {W}_{i_2}^{(j)} \subset \mathcal {S}_{i_1} \cap \mathcal {S}_{i_2} = \{0\}. \end{aligned}$$

Hence, $\mathcal {C}_j$ is a partial spread in the Grassmannian $\mathcal {G}_q(j,n)$ with $|\mathcal {C}_j|=L$.

To prove (2), consider subspaces $\mathcal {W}_{i_1}^{(n-k+j-1)}, \mathcal {W}_{i_2}^{(n-k+j-1)} \in \mathcal {C}_{k+j}$. We know that $\dim (\mathcal {H}_{i_1} \cap \mathcal {H}_{i_2})=(s-2)k=n-2k$, and then, the subspace sum $\mathcal {H}_{i_1} +\mathcal {H}_{i_2}$ is the whole space ${{\mathbb {F}}}_q^{n}$. As a consequence,

$$\begin{aligned} n = \dim (\mathcal {H}_{i_1} +\mathcal {H}_{i_2}) \leqslant \dim \left( \mathcal {W}_{i_1}^{(n-k+j-1)}+\mathcal {W}_{i_2}^{(n-k+j-1)}\right) \leqslant n \end{aligned}$$

and then it follows that

$$\begin{aligned} \begin{array}{ccl} n &{} = &{} \dim \left( \mathcal {W}_{i_1}^{(n-k+j-1)} + \mathcal {W}_{i_2}^{(n-k+j-1)}\right) \\ &{} = &{} 2(n-k+j-1)-\dim \left( \mathcal {W}_{i_1}^{(n-k+j-1)} \cap \mathcal {W}_{i_2}^{(n-k+j-1)}\right) . \end{array} \end{aligned}$$

Hence, we obtain

$$\begin{aligned} \begin{array}{ccl} \dim \left( \mathcal {W}_{i_1}^{(n-k+j-1)} \cap \mathcal {W}_{i_2}^{(n-k+j-1)}\right) &{} = &{} 2(n-k+j-1)-n \\ &{} = &{} n-2k+2(j-1), \end{array} \end{aligned}$$

which is the minimum possible dimension of the intersection between subspaces of dimension $n-k+j-1$ of ${{\mathbb {F}}}_q^{n}$. Thus, we conclude that $\mathcal {C}_{k+j}$ is an equidistant $(n-2k+2(j-1))$-intersecting constant dimension code with exactly L elements. In particular, we have that $d_S(\mathcal {C}_{k+j})= 2(k-(j-1))$ and $\mathcal {C}_{k+j}$ is a constant dimension code with the maximum distance.

Theorem 3.10

The flag code $\mathcal {C}$ defined in (15) is an optimum distance flag code of type $(1, \dots , k, n-k, \dots , n-1)$ on ${{\mathbb {F}}}_q^{n}$ with the k-spread $\mathcal {S}$ as a k-projected code. This code has cardinality $|\mathcal {C}|=L=\frac{q^n-1}{q^k-1}$ and distance $d_f(\mathcal {C})=2k(k+1)$.

Proof

By means of Proposition 3.9, we conclude that $\mathcal {C}$ is a disjoint flag code of cardinality L with projected codes attaining the maximum distance for their corresponding dimensions. Then, by Theorem 3.1, $\mathcal {C}$ is an optimum distance flag code, that is, $d_f(\mathcal {C})=2k(k+1)$.

Remark 3.11

The code $\mathcal {C}$ defined in (15) attains the maximum possible distance for flag codes of type $(1, \dots , k, n-k, \dots , n-1)$ on ${{\mathbb {F}}}_q^{n}$. Furthermore, by means of Theorem 3.2, it also has the best possible size among the optimum distance flag codes of the full admissible type vector on ${{\mathbb {F}}}_q^n$.

3.2.4 The general case

Finally, in order to get an optimum distance flag code of any admissible type vector with a k-spread as a projected code, we apply a puncturing process to the code $\mathcal {C}$ defined in (15). This process was already used in [2] to get optimum distance flag codes having a planar spread as a projected code. Let us recall it. Fix an admissible type vector $(t_1, \dots , t_r)$, that is, a type vector such that $k \in \{t_1,\dots , t_r\}\subseteq \{1,\dots , k, n-k,\dots , n-1\}$. Consider a flag $\mathcal {F}_{\mathrm {W_i}}$ in the code $\mathcal {C}$ in (15). The punctured flag of type $(t_1, \dots , t_r)$ associated with $\mathcal {F}_{\mathrm {W_i}}$ is the sequence

$$\begin{aligned} \left( \mathcal {W}_i^{(t_1)}, \dots , \mathcal {W}_i^{(t_r)}\right) . \end{aligned}$$

(18)

The punctured flag code of type $(t_1, \dots , t_r)$ associated with $\mathcal {C}$ is the code given by

$$\begin{aligned} \mathcal {C}_{(t_1, \dots , t_r)}= \left\{ \left( \mathcal {W}_i^{(t_1)}, \dots , \mathcal {W}_i^{(t_r)}\right) \ | \ i=1, \dots , L\right\} . \end{aligned}$$

(19)

Observe that the projected codes of $\mathcal {C}_{(t_1, \dots , t_r)}$ are, in particular, projected codes of $\mathcal {C}$. Hence, the next result follows straightforwardly from this fact, together with Theorem 3.2.

Theorem 3.12

Given n and a divisor k of n, for every admissible type vector $(t_1, \dots , t_r)$, the code $\mathcal {C}_{(t_1, \dots , t_r)}$ defined as above is an optimum distance flag code on ${{\mathbb {F}}}_q^n$ with the spread $\mathcal {S}$ as a projected code. Its cardinality, which is $L=\frac{q^n-1}{q^k-1}$, is maximum for optimum distance flag codes of this type.

3.3 Example

We conclude the paper with an example of our construction of an optimum distance flag code of type (2, 4) on ${{\mathbb {F}}}_2^6$ having a 2-spread as its first projected code. To do this, we follow the steps given in Sect. 3.2.

Consider the bipartite graph $G=(V, E)$ where $V=\mathcal {G}_4(1,3) \cup \mathcal {G}_4(2,3)$ and E is the set of pairs $(l,H) \in \mathcal {G}_4(1,3)\times \mathcal {G}_4(2,3)$ with $l\subset H$. Take $\alpha \in {{\mathbb {F}}}_4$ with $\alpha \ne 0,1$. Then, we have that ${{\mathbb {F}}}_4=\{0,1,\alpha , \alpha ^2\}$. By using the package GRAPE of GAP and following the process described in [3], we have obtained the next perfect matching of V. The induced bijection $M : \mathcal {G}_4(1,3) \rightarrow \mathcal {G}_4(2,3)$ is explicitly given by:

Observe that every line $l\in \mathcal {G}_4(1,3)$ is a subspace of the (hyper)plane M(l). Even more, we have expressed every subspace M(l) as the rowspace of a $2\times 3$ matrix whose the first row is precisely a generator of the line l. In this way, we obtain the optimum distance flag code of type (1, 2) on ${\mathbb {F}}_4^3$

$$\begin{aligned} \widetilde{\mathcal {C}}=\{(l, M(l))\mid l \in \mathcal {G}_4(1,3)\}. \end{aligned}$$

Now, let $f(x)= x^2+x+1$ be the minimal polynomial of $\alpha$ and consider its companion matrix $P=\begin{pmatrix} 0 &{}\quad 1 \\ 1 &{}\quad 1 \end{pmatrix}.$ If $\phi$ is the field isomorphism in (1), we have that $\phi (0)={\mathrm {0}}_2$, $\phi (1)=I_2$ and $\phi (\alpha )=P$. Taking the previous matching M and the field reduction $\varphi$ induced by $\phi$ (2), we define the following optimum distance flag code of type (2, 4) on ${\mathbb {F}}_2^6$

$$\begin{aligned} \widehat{\mathcal {C}}=\{(\varphi (l), \varphi (M(l))) \mid l \in \mathcal {G}_4(1,3)\}. \end{aligned}$$

If we take $l=\langle (0,1,\alpha )\rangle$, for instance, the corresponding element on $\widehat{\mathcal {C}}$ is the flag

$$\begin{aligned} \mathcal {F}= \begin{array}{c} \left( \text {rowsp} \begin{pmatrix} {\mathrm {0}}_2 &{}\quad I_2&{}\quad P \end{pmatrix}, \, \text {rowsp} \begin{pmatrix} {\mathrm {0}}_2 &{}\quad I_2&{}\quad P \\ I_2 &{}\quad {\mathrm {0}}_2 &{}\quad P \end{pmatrix}\right) . \end{array} \end{aligned}$$

Note that $\widehat{\mathcal {C}}_1=\mathcal {S}(3,2,P)=\mathcal {S}$. Also, for every $\varphi (l) \in \mathcal {S}$ with $l \in \mathcal {G}_4(1,3)$, we have that $\varphi (M(l))$ is a 4-dimensional subspace over ${{\mathbb {F}}}_2$ that contains $\varphi (l)$. Moreover, $\varphi (M(l))$ is the vector space generated by the rows of a $4\times 6$ full-rank matrix, whose two first rows span $\varphi (l)$.

4 Conclusions and future work

In this paper, we have addressed the problem of obtaining flag codes of general type $(t_1,\dots ,t_r)$ on a space ${\mathbb {F}}_q^n$ with the maximum possible distance and the property of having a k-spread as a projected code whenever k divides n. Firstly, we have showed that the existence of such codes might be not possible for an arbitrary type vector and have characterized the admissible ones. They have to satisfy the condition: $k \in \{t_1,\dots , t_r\} \subseteq \{1,\dots , k,n-k,\dots , n-1\}$.

Given an admissible type vector, we have proved the existence of optimum distance flag codes of such a type with a spread as a projected code by describing a gradual construction starting from type $(1, n-1)$, following with type $(k, n-k)$, to finish with the full admissible type $\{1,\dots , k,n-k,\dots , n-1\}$. This construction is mainly based on two ideas: on the one side, we exploit the existence of perfect matchings in the bipartite graph with set of vertices given by the lines and the hyperplanes of ${\mathbb {F}}_q^n$ and edges given by the containment relation. On the other hand, we use the properties of the field reduction map that allow us to translate the spread of lines to a k-spread and to build our code from it. Our construction provides codes with the best possible size among optimum distance flag codes of any arbitrary admissible type vector.

In future work, we investigate the algebraic structure and features of this family of codes and explore other possible constructions. We also study the family of flag codes from spreads not necessarily having the maximum distance as well as the existence and performance of decoding algorithms for them.