Degenerate flag varieties in network coding (Q6167303): Difference between revisions

To transmit information over network channels, network coding considers the packets of information as vectors in a given vector space $V$ (over some field $K$) and the packets are sent through the nodes of the network where each node forwards linear combinations of the received packets (with randomly selected coefficients). For the problem of error and erasure correction in large networks, where the information is encoded in a subspace of a vector space $V$ (over some field $K$) that contains the packets of information as vectors, in [\textit{R. Koetter} and \textit{F. R. Kschischang}, IEEE Trans. Inf. Theory 54, No. 8, 3579--3591 (2008; Zbl 1318.94111)] and in [IEEE Trans. Inf. Theory 54, No. 9, 3951--3967 (2008; Zbl 1318.94119)] \textit{D. Silva} et al. proposed a new solution observing that information that is preserved after being linearly transformed by the network is the subspace $U\subseteq V$ spanned by the input vectors. In other words, $U$ is a point in some Grassmannian $\text{Gr}_{\ell}(V)$, for a fixed dimension $\ell<\dim_KV$. \textit{D. Liebhold} et al. [Des. Codes Cryptography 86, No. 2, 269--284 (2018; Zbl 1412.94254)] propose encoding the information using (partial) flags and their stabilizers in the general linear group of $V$. For the set of all flags in $V$, a simplicial complex known as the spherical building of the general linear group of $V$, [loc. cit.] introduce a new distance on flags, the \textit{Grassmann distance} $$d(U,U')=\frac{1}{2}\big(\dim(U+U')-\dim(U\cap U')\big)\text{ for }U,U'\in\mathrm{Gr}_{\ell}(V),$$ which is more appropriate to measure errors and erasures in the transmission of flags through the network and it is easier to compute than the commonly used gallery distance. In this method, the information is encoded in a sequence of vectors $u_1,\ldots,Un$ such that the vector subspaces $U_i=\langle u_1,\ldots, u_i\rangle$ form a flag $U_1\subseteq U_2\subseteq \cdots\subseteq U_n$ in a corresponding partial flag variety ${\mathfrak Fl}(V)$ with the sum of the Grassmann distances as metric in ${\mathfrak Fl}(V)$. For the partition into cells of the flag variety ${\mathfrak Fl}(V)$, each cell is a regular orbit under the action of certain unipotent subgroups of $\text{GL}(V)$, typically non abelian. The main contribution of the paper under review is a variant of the linear flag coding of [Liebhold et al, loc. cit] by using degenerate flags, more precisely, flag degenerations induced the natural filtration of the universal enveloping algebra of the Lie algebra of the algebraic group $\text{GL}_{n+1}(K)=\text{GL}(V)$. Thus, the PBW degenerated flag variety ${\mathfrak Fl}^{(a)}(V)$ is the highest weight orbit of an abelian algebraic group acting on the corresponding $\text{GL}_{n+1}(K)$-module. One key advantage is that the cells of the degenerate flag variety ${\mathfrak Fl}^{(a)}(V)$ are affine spaces, more closely related to linear subspace coding than working with the usual flags. Another advantage is that the transformations by the network nodes use less additions compared to linear subspace coding and flag coding. Moreover, since the largest of the degenerate flag variety ${\mathfrak Fl}^{(a)}(V)$ is a regular orbit of the Borel space of upper triangular matrices and the translations preserve the Grassmann metric, the distance in ${\mathfrak Fl}^{(a)}(V)$ becomes a generalized flag rank metric. Thus, the information set is a metric affine space isometric to the space of upper triangular matrices endowed with the flag rank metric. As applications of the general constructions, the authors introduce flag rank metric codes and a network coding scheme using degenerate flags.