{'fraction_non_alphanumeric': 0.06304381805866723, 'fraction_numerical': 0.01083728442661387, 'mean_word_length': 3.672346640701071, 'pattern_counts': {'":': 0, '<': 4, '<?xml version=': 0, '>': 0, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 13, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Support Constrained Generator Matrices of Gabidulin Codes in Characteristic Zero

Gabidulin codes over fields of characteristic zero were recently constructed by Augot et al., whenever the Galois group of the underlying field extension is cyclic. In parallel, the interest in sparse generator matrices of Reed-Solomon and Gabidulin codes has increased lately, due to applications in distributed computations. In particular, a certain condition pertaining the intersection of zero entries at different rows, was shown to be necessary and sufficient for the existence of the sparsest possible generator matrix of Gabidulin codes over finite fields. In this paper we complete the picture by showing that the same condition is also necessary and sufficient for Gabidulin codes over fields of characteristic zero. Our proof builds upon and extends tools from the finite field case, combines them with a variant of the Schwartz-Zippel lemma over automorphisms, and provides a simple randomized construction algorithm whose probability of success can be arbitrarily close to one. In addition, potential applications for low-rank matrix recovery are discussed.


I. INTRODUCTION
Over finite fields, Gabidulin codes [1], [2] can be seen as a rank-metric equivalent of Reed-Solomon codes, where instead of evaluating ordinary polynomials, one uses linearized polynomials (i.e., whose only nonzero coefficients are for monomials whose degree is a nonnegative integer power of the field characteristic). To properly generalize this definition to fields of characteristic zero, it was recently suggested in [3] to employ θ-polynomials, which are linear combinations of compositions of a generator θ of the underlying Galois group of the field extension (that must be cyclic).
Independently, there has been a surge of interest lately in constructing sparsest generator matrices for Reed-Solomon and Gabidulin codes [4], [5], [6], [7], [8], for several applications in distributed computing. Since the rows of a generator matrix are codewords, each row cannot contain more than k−1 zeros according to the Singleton bound, where k is the dimension of the code. The so called GM-MDS conjecture, posed by [5] and solved by [7] and [8], asserts that this maximum number of zeros at every row is attainable, as long as a certain condition regarding the position of zeros is satisfied. Specifically, this condition requires the zero-entries at every set of rows to intersect in at most k minus the number of rows in the intersection.
In this paper we complete the picture by showing that the same condition is necessary and sufficient for the existence of sparse generator matrices for Gabidulin codes over fields of characteristic zero. We note that while the proof of the equivalent condition for Reed-Solomon codes is identical for finite fields and fields of characteristic zero, for Gabidulin codes this is not the case, and the proof from [4] fails over the latter fields. However, by adopting notions from the Reed-Solomon equivalent (the "Simplified GM-MDS conjecture" [7,Thm. 3]), and combining with a variant of the well-known Schwartz-Zippel lemma, we are able to resolve the problem over fields of characteristic zero. Moreover, our proof also provides a randomized construction algorithm whose probability of success can be arbitrarily high; similar randomized construction algorithms exist for the finite variants of the problem, but their probability of success is lower.
Beyond their application in network coding [9], spacetime codes [10], and cryptography [11], Gabidulin codes have applications in low rank matrix recovery [12] (LRMR), which is normally performed over fields of characteristic zero. In this problem, one reconstructs a low-rank matrix from a given set of linear measurements. If these linear measurements are given by multiplication of the unknown matrix by a paritycheck matrix of a Gabidulin code, this problem reduces to syndrome decoding of the respective zero codeword. Since the parity-check matrix of a Gabidulin code has a similar structure to that of the generator matrix [3,Prop. 8], our results imply that when performing LRMR with Gabidulin codes, one may employ linear measurements that depend on a small number of entries of the unknown matrix.
The problem is formally stated in Section II, alongside necessary mathematical background. Our main results are summarized in Section III, and proved in Section V by using auxiliary claims given in Section IV.

A. Notations
Let [n] = {1, 2, . . . , n}. Denote the dimension of a subspace V over a field F by dim F V and the span of the elements in a set S over the field F by span F S. The (total) degree of a (multivariate) polynomial f is denoted by deg f (e.g. deg(x 2 y 2 + x 3 ) = 4). For an m × n matrix X and I ⊆ [m], J ⊆ [n], X I,J is the submatrix with the rows and columns indexed in I and J respectively. Let X I,: = X I, [n] and X :,J = X [m],J and when I or J has a single element, we sometimes write the element only instead of the set.

II. PROBLEM SETUP
In this section we will first provide a brief background on cyclic Galois extensions. Then, we will define rank metric codes and Gabidulin codes. Finally, we will define our problem, namely, finding Gabidulin codes with support constrained generator matrices over a field of characteristic zero.

A. Field extensions
Let E/F be a field extension of finite degree, i.e. the dimension of E as a vector space over F is finite, and let dim F E = m. The automorphism group of E/F, Aut(E/F), is the set of automorphisms of E that fix F, i.e.
with the group operation of function composition •. If |Aut(E/F)| = m, E/F is called a Galois extension, in which case, Aut(E/F) is also denoted by Gal(E/F) and is called the Galois group of E/F.
In this paper, we will focus on cyclic Galois extensions, whose Galois group is a cyclic group of order m: where the automorphism θ is the generator and θ i+1 = θ • θ i for every i ≥ 0. Notice that θ m = θ 0 is the identity automorphism.
For example, for finite fields, when F = F q and E = F q m , the Galois group is cyclic of order m with the generator automorphism θ(x) = x q : For infinite fields, when F = Q is the set of rational numbers and E = Q(ζ n ), where ζ n is the n'th root of unity, Q(ζ n )/Q is a Galois extension of degree ϕ(n), where ϕ(n) is the Euler's phi function (Q(ζ n ) is called the n'th cyclotomic field and an interested reader can refer to [13]). Its Galois group is isomorphic to the multiplicative group Z * n of integers modulo n. Since Z * n is cyclic for n = p a , 2p a [14], where p is any odd prime and a is any positive integer, it follows that for these values of n we have that Q(ζ n ) is a cyclic Galois extension of degree m = ϕ(n) = p a−1 (p − 1). It is also possible to define cyclic extensions of Q for any degree m by considering subfields of Q(ζ p ) for an odd prime p such that p − 1 is divisible by m.

B. Rank metric codes
where c 1 , . . . , c n ∈ E represent the entries of c ∈ E n . By fixing an ordered basis of E over F, the elements of E can be considered as vectors in F m , and then the codewords (i.e. the elements of C ⊂ E n ) can be viewed as m × n matrices over F. Then, this definition of the rank distance in (1) is equivalent to the minimum of the rank of the matrix representation of a nonzero codeword. Notice that by definition in (1), the rank distance of C can be upper bounded by the Hamming distance, d H (C) min 0 =c∈C c 0 , where c 0 is the number of nonzero entries of c. Therefore, the Singleton bound can be written for the rank distance as well: The codes with d R (C) = n − k + 1 are called maximum rank distance (MRD), for which we write [n, k] E/F by omitting d.
A generator matrix for an [n, k, d] E/F code C is a k × n matrix over E whose rows form a basis for C.

C. Gabidulin codes
Gabidulin codes are defined as the row space of the k × n matrix where θ ∈ Aut(E/F) and x 1 , . . . , x n ∈ E are F-linearly independent (notice that this requires n ≤ m = dim F E). Note that Gabidulin codes can be seen as evaluation codes of the socalled θ-polynomials; a θ-polynomial is a function f : and every codeword in a Gabidulin code is the evaluations of some θpolynomial of θ-degree at most k − 1. Note also that the generator matrix can be chosen as the product of any k × k invertible matrix over E and the matrix in (3).
Originally, this was defined by Delsarte [1] and Gabidulin [2] for the finite fields, when F = F q , E = F q m , and θ(x) = x q , as the first general constructions of MRD codes over finite fields. Later [3], it was extended to fields of characteristic zero and it was shown that when E/F is a cyclic Galois extension and θ is the generator of Gal(E/F), this extension of Gabidulin codes also gives an [n, k] E/F MRD code [3]. In the rest of the paper, we will assume that E/F is a cyclic Galois extension of order m and F is of characteristic zero.

D. Problem definition
We consider the problem of finding an [n, k] E/F MRD code whose generator matrix G ∈ E k×n has support constraints. We describe the support constraints through the subsets The same condition also appears in the GM-MDS conjecture for MDS codes (i.e. d H = n − k + 1, see [5], and also [15], [6]) which was proven in [7] and [8].
Over infinite fields, the fact that (5) is necessary can be shown similar to [7], since MRD codes are also MDS (2), and since the proof in [7] applies to both finite and infinite fields. However, a similar proof to [4] cannot be applied to show that (5) is sufficient when F has characteristic zero. The reason is that in finite fields, since the generator matrix in (3) consists of entries in the form of polynomials in the x i 's, which, in one step of the proof, allows to reduce the problem to a similar one with a smaller parameter, whereas in the characteristic zero, the entries are in the form of θ-polynomials (defined in [3]) and applying the same step turns the problem into one of a different kind. Hence, in this paper, we will show that (5) is sufficient for the existence of [n, k] E/F MRD codes under the support constraints on the generator matrix given in (4) when F has characteristic zero.

III. MAIN RESULTS
In this section, we present our main results on the existence of MRD codes in characteristic zero (see Theorem 1) and the best achievable rank distance for the cases where there does not exist any (see Corollary 1). Also, we will give a randomized algorithm for the code construction. The proofs of the theorems will be given in Section V. Theorem 1. Let E/F be a cyclic Galois extension of degree m such that F has characteristic zero. For some k ≤ n ≤ m, let Z 1 , . . . , Z k ⊂ [n] satisfy (5). Then, there exists an [n, k] E/F Gabidulin code with a generator matrix satisfying the constraints in (4).
If the Z i do not satisfy (5), then as given in [4] and [7], i∈Ω Z i + |Ω| < n−k+1 and hence, an MRD code does not exist. For this case, Corollary 1 below (which is the analog of [4, Thm. 2]) shows that this upper bound is achievable by the subcodes (i.e., the subspaces) of Gabidulin codes.

A. Code Construction
Fix an F-basis {b 1 , . . . , b m } for E and assume that the conditions for the Z i in Theorem 1 are satisfied, i.e. Z 1 , . . . , Z k ⊂ [n] satisfy (5). Then, each Z i has at most k − 1 elements by applying (5) with |Ω| = 1. In [5,Thm. 2] and [4,Corollary 3], it is shown that one can keep adding elements to these sets from [n] without violating any of the inequalities in (5) until each Z i has exactly k − 1 elements. Note that adding elements to these sets will only put more zero constraints on the generator matrix. Therefore, without loss of generality, we can assume that |Z i | = k − 1 for all i along with (5). Then, we construct a generator matrix for a rank metric code in a randomized manner as described below: Inputs: A finite nonempty set S ⊂ F and subsets Z 1 , . . . , Z k ⊂ [n] satisfying (5). Steps: • Add elements to the Z i 's from [n] (if necessary) by following the algorithm given in [5,Thm. 2] so that they all have exactly k − 1 elements and still satisfy (5).
where e j is the column vector with 1 at the jth entry and 0's elsewhere (Note that |Z i | = k − 1). Output: The generator matrix G = T · A ∈ E k×n . By Lemma 1 below, G in the above construction is guaranteed to satisfy (4) for any inputs. Lemma 1. Let Z 1 , . . . , Z k ⊂ [n] be subsets of size k − 1. For a given k × n matrix A, a k × k matrix T (over the same field as A) satisfying (T · A) ij = 0 for every j ∈ Z i and i ∈ [k] can be given as in (7).
Proof. For a fixed i ∈ [k], the statement (T · A) ij = 0 for every j ∈ Z i is equivalent to the equation T i,: · A :,Zi = 0. A solution T i,: to this equation can be described in terms of the adjugate of the k × k square matrix P = 0 k×1 A :,Zi . Recall that adj P is the transpose of the cofactor matrix (−1) i+j det(P [k]\{i},[k]\{j} ) i,j∈[k] and satisfies adj(P)P = det(P)I k×k . Since P has an all zero column, we have det P = 0, which implies adj(P)P = 0. Furthermore, due to the zero column in P, the entries of adj P are zero except the first row, whose entries are for j ∈ Since (adj P) 1,: · P = 0 and (adj P) 1,: · A :,Zi = 0, the row vector T i,: = (adj P) 1,: satisfies T i,: · A :,Zi = 0.
Furthermore, if x 1 , . . . , x n are F-linearly independent and the matrix T is invertible (i.e. det T = 0), then the code generated by G is an [n, k] E/F Gabidulin code since the row spaces of A and G = T · A are identical. In Theorem 2, we give a lower bound on the probability of this construction giving an MRD code.
Theorem 2. If the conditions in Theorem 1 are satisfied, then, the generator matrix G randomly constructed as described above will satisfy (4) and generate an [n, k] E/F Gabidulin code with probability at least 1 − n+k(k−1) |S| .
Since F is infinite, S can be arbitrarily large. Therefore, the probability of constructing an MRD code can be arbitrarily close to 1.
Furthermore, if the Z i do not satisfy (5), then by following the proof of Corollary 1, we can construct a rank metric code achieving the largest possible rank distance for the given support constraints.

IV. MORE ON CYCLIC GALOIS EXTENSIONS
Before moving to the proofs of the theorems, in this section, we will give some useful properties of the automorphisms in Gal(E/F) = {θ 0 , θ 1 , . . . , θ m−1 }.

A. Linear independence of the elements in E
Lemma 2 below lists some equivalent conditions to the F-linear dependence of the elements of E in terms of the automorphisms in Gal(E/F). The first two of these conditions can be also seen as a special case of [3,Prop. 5], where the authors give equivalent rank metrics for the elements of E n , whereas Lemma 2 only claims these rank metrics simultaneously declare rank deficiency (i.e. returns a rank less than n) for a given element of E n . It is worth noting, as shown by Augot et al. [3], that the assumption that the extension E/F is cyclic plays an important role in Lemma 2. This is since its proof relies on the fact that θ fixes only the elements of F (i.e. for any x ∈ E, θ(x) = x if and only if x ∈ F), which is the case for the cyclic extensions. Proof. If x i = 0 for some i then the claim is trivial, and hence assume that x i = 0 for every i.
(ii) =⇒ (i): Let ℓ be the minimum number of columns of M that are E-linearly dependent and w.l.o.g. assume that If the top n × n minor of M is zero, then there exists ℓ ≤ n such that the ℓ'th row of M is in the Espan of the first ℓ − 1 rows. By induction, it can be shown that for any i ≥ ℓ, the i'th row is in the span of the first ℓ − 1 rows. To see how, assume for some β 1 , . . . , β ℓ−1 ∈ E, Then, by applying θ to both sides, it follows that the (i + 1)'th row is a linear combination of the first ℓ rows; hence it is also in the span of the first ℓ − 1 rows. As a result, rank M ≤ ℓ − 1 < n, which implies (ii).
(i) =⇒ (iii): Assume that n i=1 β i x i = 0 for some β i ∈ F. Then, for any j, applying θ j to both sides yields

B. Schwartz-Zippel Lemma for automorphisms
Recall the Schwartz-Zippel Lemma, which states that for a nonzero multivariate polynomial f in n variables over a field, a point uniformly chosen at random from S n , where S is a nonempty finite subset of this field, will be a root of f with probability at most deg f |S| . In this section, we will give an extension of Schwartz-Zippel Lemma for a special type of functions from E n to E. More precisely, for a given multivariate polynomial f over E in mn variables (seen as an m × n matrix), we will consider the function g(x 1 , . . . , [n] ) and give a bound on the probability of a randomly chosen point being a zero of g. Later, this will help us to derive the bound on the probability given in Theorem 2.
where we use θ i−1 (Γ tj ) = Γ tj since Γ tj ∈ F. Now, applying the Schwartz-Zippel Lemma to the polynomial f ′ gives V. PROOFS OF THEOREM 1 AND THEOREM 2 First of all, notice that it is sufficient to prove Theorem 2 since it implies Theorem 1 when S is chosen sufficiently large. Assume x 1 , . . . , x n are chosen as described in Theorem 2. We know that the code with the generator matrix T · A, which satisfies (4)  Therefore, it is sufficient to show that P(det T · det M [n],: In order to show this, we will appeal to Lemma 3. Define the multivariate polynomial f (X) = det det e j X [k],Zi i,j∈[k] · det X [n],: (9) for the variables X ij , i ∈ [m], j ∈ [n] seen as an m × n matrix X. Then, it suffices to show that P(f (M) = 0) ≤ n+k(k−1) |S| . Hence, by Lemma 3, all we need to show is that f is a nonzero polynomial with total degree at most n+k(k−1).
To show the bound on the degree of f , recall the Leibniz formula for the determinant of an n × n square matrix Z, which is det Z = π∈Sn sgn(π) n i=1 Z π(i),i , where S n is the permutation group of size n and sgn(π) is the sign of the permutation π. Thus, when the entries of Z are polynomials, we can write  1).
To show that f is a nonzero polynomial, we will use the simplified GM-MDS conjecture of Dau et al. [5], which was proved in [7] and [8].
Notice that the i'th row of P in (11) consists of the coefficients of the polynomial j∈Zi (X − α j ) = k j=1 P ij X j−1 (12) in the variable X. We will also show that P can be written in the form of (7). To see how, define the m × n Vandermonde matrix V = α i−1 j i∈[m],j∈ [n] . Fix i ∈ [k] and consider the determinant of the k × k Vandermonde matrix W = v V [k],Zi , where v is a column vector whose j'th entry is X j−1 for j ∈ [k]: det W = c i j∈Zi (X − α j ) (12) = c i j∈ [k] P ij X j−1 where c i = j1<j2∈Zi (α j1 − α j2 ) = 0. On the other hand, by the linearity of the determinant in the first column, we can write det e j V [k],Zi X j−1 , since v = j∈[k] e j X j−1 . As a result, the entries of P satisfy Now, let us evaluate f in (9) at V, which will give a multivariate polynomial in the variables α j : = det [c i P ij ] i,j∈[k] · det V [n],: By Lemma 4, det P is a nonzero polynomial. Furthermore, we have that c i = 0 and det V [n],: = j1<j2∈[n] (α j1 − α j2 ) = 0. Hence, f (V) is not the zero polynomial in the variables α j . Therefore, f (X) itself cannot be the zero polynomial in the variables X ij .