AFFINE GRASSMANN CODES

PETER BEELEN, SUDHIR R. GHORPADE, AND TOM HØHOLDT

Abstract. We consider a new class of linear codes, called affine Grassmann codes. These can be viewed as a variant of generalized Reed-Muller codes and are closely related to Grassmann codes. We determine the length, dimension, and the minimum distance of any affine Grassmann code. Moreover, we show that affine Grassmann codes have a large automorphism group and determine the number of minimum weight codewords.

1. Introduction

Reed-Muller codes are among the most widely studied classes of linear error correcting codes. Numerous generalizations and variants of Reed-Muller codes have also been considered in the literature. (See, for example, [2], [12, Ch. 13–15], [14, Ch. 1, §13; Ch. 11, §3.4.1; Ch. 16, §3; Ch. 17, §4] and the relevant references therein). In this paper we introduce a class of linear codes that appears to be a genuinely distinct variant of Reed-Muller codes. As explained in Section 7, this new class of codes is intimately related to the so-called Grassmann codes, which have been of much current interest (see, for example, [6, 7, 9, 13] and the relevant references therein), and with this in view we call these the affine Grassmann codes. Roughly speaking, affine Grassmann codes are obtained by evaluating linear polynomials in the minors of a generic ℓ × ℓ′ matrix at all points of the corresponding affine space over a finite field. Evidently, when ℓ = 1, this gives the first order generalized Reed-Muller code RM(1, ℓ′). However, in general, the resulting code is distinct from higher order generalized Reed-Muller codes and determination of several of its properties appears to be rather nontrivial. Our main results include the determination of the minimal distance (Theorem 16) and a characterization as well as an explicit enumeration of the minimum weight codewords (Theorems 28 and 32). Further, we show that affine Grassmann codes have a large automorphism group (Theorem 21); this result could be viewed as an extension of the work of Delsarte, Goethals and MacWilliams [2, Thm. 2.3.1], Knörr and Willems [11] as well as Berger and Charpin [1] on the automorphisms of Reed-Muller codes. In geometric terms, some of our results could be viewed as a generalization of elementary facts about hyperplanes over finite fields to “determinantal hyperplanes”. (See Remark 11 for greater details.) The auxiliary results obtained in the course of proving the main theorems and the techniques employed may also be of some independent interest.

2. Preliminaries

Denote, as usual, by 𝔽_{q} the finite field with q elements. Fix positive integers ℓ and ℓ′ and a ℓ × ℓ′ matrix X = (X_{ij}) whose entries are algebraically independent indeterminates over 𝔽_{q}. By 𝔽_{q}[X] we denote the polynomial ring in the ℓℓ′ indeterminates X_{ij} (1 ≤ i ≤ ℓ, 1 ≤ j ≤ ℓ′) with coefficients in 𝔽_{q}. For convenience, we introduce the following notation for the rows and columns of the matrix X:

Date: October 8, 2009; Revised: June 10, 2010. To appear in the IEEE Transactions of Information Theory, Vol. 56, No. 7 (July 2010).

X_{i} = (X_{i1} ⋯ X_{iℓ′}) for 1 ≤ i ≤ ℓ and X^{j} = ( X_{1j} ; ⋮ ; X_{ℓj} ) for 1 ≤ j ≤ ℓ′.

Recall that by a minor of X of order i we mean the determinant of an i×i submatrix of X. A minor of X of order i is sometimes referred to as an i × i minor of X. But in any case, it should be remembered that the minors of X are not matrices, but are elements of the polynomial ring 𝔽_{q}[X].

We are primarily interested in the linear space generated by all the minors of X. This is unchanged if we replace X by its transpose. With this in view, we shall always assume that ℓ ≤ ℓ′. Further, we set

m = ℓ + ℓ′ and δ = ℓℓ′.

For 0 ≤ i ≤ ℓ, we let Δ_{i}(ℓ, m) be the set of all i × i minors of X, where, as per standard conventions, the only 0 × 0 minor of X is 1. We define

Δ(ℓ, m) = ⋃_{i=0}^{ℓ} Δ_{i}(ℓ, m).

Definition 1. The linear space F(ℓ, m) over 𝔽_{q} is the subspace of 𝔽_{q}[X] generated by Δ(ℓ, m).

For example, if ℓ = ℓ′ = 2, then m = 4, δ = 4, and Δ_{0}(2, 4) = {1}, while

Δ_{1}(2, 4) = {X_{11}, X_{12}, X_{21}, X_{22}} and Δ_{2}(2, 4) = {X_{11}X_{22} − X_{12}X_{21}}.

Thus a typical element of F(2, 4) looks like

(1)  a + b_{1}X_{11} + b_{2}X_{12} + b_{3}X_{21} + b_{4}X_{22} + c (X_{11}X_{22} − X_{12}X_{21})

where a, b_{1}, b_{2}, b_{3}, b_{4}, c ∈ 𝔽_{q}. Observe that #Δ(2, 4) = 6, where for a finite set D, we denote by #D the cardinality of D. In general, we have the following.

Lemma 2. The cardinality of Δ(ℓ, m) is \binom{m}{ℓ}.

Proof. Since the entries of X are indeterminates, the number of minors of X of order i is the number of i×i submatrices of X. An i×i submatrix of X is obtained by choosing i rows among the ℓ rows and i columns among the ℓ′ columns. Thus

#Δ_{i}(ℓ, m) = \binom{ℓ}{i}\binom{ℓ′}{i} for 0 ≤ i ≤ ℓ.

Consequently,

#Δ(ℓ, m) = ∑_{i≥0} \binom{ℓ}{ℓ − i}\binom{ℓ′}{i} = \binom{m}{ℓ},

where the last equality follows from the so-called Chu–Vandermonde summation (see e.g. [8, Sec. 5.1, (5.27)]). □

We remark that an alternative proof of the above lemma can be obtained by observing that the minors of X (of arbitrary orders) are in a natural one-to-one correspondence with the ℓ×ℓ minors of the ℓ×m matrix (X|I) obtained by adjoining to X a ℓ × ℓ identity matrix.

The following basic result can be viewed as a very special case of the standard basis theorem or the straightening law of Doubilet, Rota and Stein (cf. [3], [5, Thm. 4.2]). In the case we are interested in, a much simpler proof can be given and this is included below.

Lemma 3. The elements of Δ(ℓ, m) are linearly independent. In particular,

dim_{𝔽_{q}} F(ℓ, m) = \binom{m}{ℓ}.

Proof. Suppose there is a linear dependence relation ∑_{M∈Δ(ℓ,m)} a_{M}M = 0, where a_{M} ∈ 𝔽_{q} for M ∈ Δ(ℓ, m). We will show by finite induction on i (0 ≤ i ≤ ℓ) that a_{M} = 0 for all M ∈ Δ_{i}(ℓ, m). First, by specializing all the variables to zero (i.e., by substituting X_{rs} = 0 for all r ∈ {1, …, ℓ} and s ∈ {1…. , ℓ′} in the linear dependence relation), we see that the desired assertion holds when i = 0. Next, suppose i > 0 and a_{M} = 0 for all M ∈ Δ_{j}(ℓ, m) and all j < i. Pick a minor M ∈ Δ_{i}(ℓ, m). By specializing all the variables except the ones occurring in M to zero, we obtain a_{M} = 0. Repeating this procedure for each i × i minor, we obtain the induction step. This proves that the elements of Δ(ℓ, m) are linearly independent. Consequently, dim_{𝔽_{q}} F(ℓ, m) = #Δ(ℓ, m) = \binom{m}{ℓ}. □

Thanks to Lemma 3, every element of F(ℓ, m) is a unique 𝔽_{q}-linear combination of the elements of Δ(ℓ, m). With this in view, we make the following definition.

Definition 4. Given f = ∑_{M∈Δ(ℓ,m)} a_{M}M ∈ F(ℓ, m), where a_{M} ∈ 𝔽_{q} for every M ∈ Δ(ℓ, m), the support of f is the set

supp(f) := {M ∈ Δ(ℓ, m) : a_{M} ≠ 0}.

Note that the the support of f is the empty set if and only if f is the zero polynomial.

We shall denote the space of all ℓ × ℓ′ matrices with entries in 𝔽_{q} by 𝔸^{δ} (𝔽_{q}), or simply by 𝔸^{δ}. Indeed, for fixed positive integers ℓ and ℓ′, this space can be readily identified with the δ-dimensional affine space over 𝔽_{q}, where δ = ℓℓ′, as before. It is clear that for any f ∈ 𝔽_{q}[X] (and in particular, any f ∈ F(ℓ, m)) and P ∈ 𝔸^{δ}, the element f(P) of 𝔽_{q} is well-defined. Now let us fix an enumeration P_{1}, P_{2}, …, P_{q^{δ}} of 𝔸^{δ}.

Definition 5. The evaluation map of 𝔽_{q}[X] is the map

Ev : 𝔽_{q}[X] → 𝔽_{q}^{q^{δ}} defined by Ev(f) := (f(P_{1}), …, f(P_{q^{δ}})) .

It is clear that the evaluation map Ev defined above is a surjective linear map. Also, it is well-known that the kernel of Ev is the ideal of 𝔽_{q}[X] generated by {X_{ij}^{q} − X_{ij} : 1 ≤ i ≤ ℓ, 1 ≤ j ≤ ℓ′}, and that this kernel contains no nonzero polynomial having degree < q in each of the variables. (See, for example, [10, p. 11].) In particular, if 0 ≠ f ∈ F(ℓ, m), then f cannot be in the kernel of Ev because deg_{X_{ij}}(f) ≤ 1 for each variable X_{ij}. Thus the restriction of the evaluation map Ev to F(ℓ, m) is injective. We are now ready to define the codes that are studied in the remainder of this paper.

Definition 6. The affine Grassmann code C^{𝔸}(ℓ, m) is the image of F(ℓ, m) under the evaluation map Ev. The minimum distance of C^{𝔸}(ℓ, m) := Ev (F(ℓ, m)) will be denoted by d(ℓ, m).

Recall that a code C is said to be degenerate if there exists a coordinate position i such that c_{i} = 0 for all c ∈ C. It turns out that affine Grassmann codes are nondegenerate and their length and dimension are easily determined.

Lemma 7. The affine Grassmann code C^{𝔸}(ℓ, m) is a nondegenerate linear code of length q^{δ} and dimension \binom{m}{ℓ}.

Proof. It is obvious that C^{𝔸}(ℓ, m) is a linear code of length q^{δ} = #𝔸^{δ}(𝔽_{q}). Moreover, since the constant polynomial 1, being the only element of Δ_{0}(ℓ, m), is in F(ℓ, m), and since Ev(1) = (1, …, 1), it follows that C^{𝔸}(ℓ, m) is nondegenerate. Finally, since the evaluation map is injective on F(ℓ, m), it follows from Lemma 3 that the dimension of C^{𝔸}(ℓ, m) is \binom{m}{ℓ}. □

Example 8. Suppose ℓ = ℓ′ = 2. Then m = δ = 4 and the elements of F(2, 4) are of the form (1). The affine space 𝔸^{δ} consists of the 2 × 2 matrices with entries in 𝔽_{2} = {0, 1}. There are 16 such matrices and, upon letting e_{ij} denote the 2 × 2 matrix with 1 in (i, j)^{th} position and 0 elsewhere, 𝔸^{δ}(𝔽_{2}) may be enumerated as 0, e_{11}, e_{12}, e_{21}, e_{22}, e_{11} + e_{12}, e_{11} + e_{21}, e_{11} + e_{22}, e_{12} + e_{21}, e_{12} + e_{22}, e_{21} + e_{22}, e_{11} + e_{12} + e_{21}, e_{11} + e_{12} + e_{22}, e_{11} + e_{21} + e_{22}, e_{12} + e_{21} + e_{22}, e_{11} + e_{12} + e_{21} + e_{22}, where 0 denotes the 2 × 2 zero matrix. Accordingly, the codewords of C^{𝔸}(2, 4) consist of the elements of 𝔽_{2}^{16} of the form a1 + v, where 1 denotes the 16-tuple all of whose coordinates are 1, whereas v denotes the 16-tuple given by (0, b_{1}, b_{2}, b_{3}, b_{4}, b_{1} + b_{2}, b_{1} + b_{3}, b_{1} + b_{4} + c, b_{2} + b_{3} + c, b_{2} + b_{4}, b_{3} + b_{4}, b_{1} + b_{2} + b_{3} + c, b_{1} + b_{2} + b_{4} + c, b_{1} + b_{3} + b_{4} + c, b_{2} + b_{3} + b_{4} + c, b_{1} + b_{2} + b_{3} + b_{4} + c). Here a, b_{1}, b_{2}, b_{3}, b_{4}, c vary over 𝔽_{2}. As such, there are 2^{6} = 64 codewords, and it is clear that the code is nondegenerate and its dimension is 6; indeed, a 𝔽_{2}-basis of C^{𝔸}(2, 4) is obtained by setting exactly one of a, b_{1}, b_{2}, b_{3}, b_{4}, c to be 1 and the others to be 0. Further, by listing the 64 codewords, it is easily seen that every nonzero codeword is of (Hamming) weight ≥ 6, and the codeword corresponding a = b_{1} = b_{2} = b_{3} = b_{4} = 0 and c = 1 is of weight 6. Thus, at least in the binary case, C^{𝔸}(2, 4) is a [16, 6, 6]-code.

We end this section by giving two lemmas on determinants that will be useful in the sequel.

Lemma 9. Let Y = (Y_{ij}) be a ℓ × ℓ matrix whose entries are independent indeterminates over 𝔽_{q} and let B = (b_{ij}) be a ℓ × ℓ matrix with entries in 𝔽_{q}. Then there is h ∈ F(ℓ, 2ℓ) such that

det(Y +B) = det(Y)+ ∑_{1≤i,j≤ℓ}(−1)^{i+j}b_{ij} det(Y^{ij})+h with supp(h) ⊆ ⋃_{i=0}^{ℓ−2} Δ_{i}(ℓ, 2ℓ),

where Y^{ij} denotes the (ℓ − 1) × (ℓ − 1) matrix obtained from Y by deleting the i-th row and the j-th column.

Proof. For a subset S of {1, …, ℓ}, denote by (Y, B)_{S} the matrix obtained from Y by replacing for all j ∈ S, the j-th column of Y by the j-th column of B. By the multilinearity of the determinant, we readily see that

det(Y + B) = ∑_{S} det((Y, B)_{S}),

where the sum is over all subsets S of {1, …, ℓ}. Observe that if S is the empty set, then det((Y, B)_{S}) = det(Y). Moreover, if S is singleton, say S = {j}, where 1 ≤ j ≤ ℓ, then by developing the determinant along the j-th column we find that

det((Y, B)_{S}) = ∑_{i=1}^{ℓ}(−1)^{i+j}b_{ij} det(Y^{ij}).

Finally, if S ⊆ {1, …, ℓ} with #S = s ≥ 2, then using Laplace expansion along the columns indexed by the elements of S, we see that det((Y, B)_{S}) is a 𝔽_{q}-linear combination of minors in Δ_{ℓ−s}(ℓ, 2ℓ). This yields the desired result. □

We will also need the following well-known result whose proof can be found, for example, in [4, Ch. I, §2].

Lemma 10 (Cauchy-Binet). Let r and s be positive integers such that r ≤ s, and let A be a r × s matrix and B a s × r matrix with entries in a commutative ring. For a subset I of {1, …, s} with #I = r, denote by A^{I} the r × r submatrix of A formed by the j-th columns of A for j ∈ I, and denote by B_{I} the r × r submatrix of B formed by the i-th rows of B for i ∈ I. Then

det(AB) = ∑_{I} det(A^{I}) det(B_{I}),

where the sum is over all subsets I of {1, …, s} of cardinality r.

Remark 11. As a warm-up for the results of the subsequent section, let us consider the case of ℓ = 1 even though it is rather trivial. Here F(1, m) corresponds to the space of linear polynomials in ℓ′ variables of the form h = a_{0} +a_{1}X_{11} +⋯+a_{ℓ′}X_{1ℓ′}. For any such h, the Hamming weight of the corresponding codeword Ev(h) amounts to finding the the number of 𝔽_{q}-rational points on a hyperplane in 𝔸^{ℓ′}. Indeed, assuming that Ev(h) is nonzero, or equivalently that not all a_{0}, a_{1}, …, a_{ℓ′} are zero, it is readily seen that

w_{H} (Ev(h)) = #𝔸^{ℓ′}(𝔽_{q}) − #H = \begin{cases}q^{ℓ′} & if a_{1} = ⋯ = a_{ℓ′} = 0, \\ q^{ℓ′} − q^{ℓ′−1} & otherwise, \end{cases}

where H denotes the affine hyperplane {P ∈ 𝔸^{ℓ′}(𝔽_{q}) : h(P) = 0}. It follows that the minimum distance of C^{𝔸}(1, m) is q^{ℓ′−1}(q−1), and also that the number of minimum weight codewords is (q^{ℓ′+1} − q). In a similar manner, the general case corresponds to finding the maximum number of points on a “determinantal hyperplane”, i.e., the zero-set of an arbitrary nonzero element of F(ℓ, m), and finding the minimum weight codewords corresponds to finding those determinantal hyperplanes where the maximum is attained.

3. Minimum distance

In this section we will compute the minimum distance d(ℓ, m) of the affine Grassmann code C^{𝔸}(ℓ, m). We start by determining the Hamming weight of a maximal minor, obtaining thereby an upper bound for d(ℓ, m). As usual we denote by w_{H}(c) the Hamming weight of a codeword c.

Lemma 12. Let M ∈ Δ_{ℓ}(ℓ, m). Then

w_{H}(Ev(M)) = q^{δ−ℓ^{2}} ∏_{i=0}^{ℓ−1}(q^{ℓ} − q^{i}).

In particular,

d(ℓ, m) ≤ q^{δ−ℓ^{2}} ∏_{i=0}^{ℓ−1}(q^{ℓ} − q^{i}).

Proof. Without loss of generality we shall assume that M is the leading maximal minor, i.e., M = det((X_{ij})_{1≤i,j≤ℓ}). Let P ∈ 𝔸^{δ} (𝔽_{q}) and let (p_{ij})_{1≤i≤ℓ, 1≤j≤ℓ′} be the ℓ×ℓ′ matrix with entries in 𝔽_{q} corresponding to P. It is clear that M(P) ≠ 0 if and only if the ℓ×ℓ submatrix (p_{ij})_{1≤i,j≤ℓ} is nonsingular. This happens for exactly ∏_{i=0}^{ℓ−1}(q^{ℓ} − q^{i}) values of p_{ij} with 1 ≤ i, j ≤ ℓ. The remaining ℓℓ′ − ℓ^{2} values p_{ij} with j > ℓ do not play any role in the evaluation of M at P. Hence w_{H}(Ev(M)) = q^{(δ−ℓ^{2})} ∏_{i=0}^{ℓ−1}(q^{ℓ} − q^{i}). This implies the desired inequality for d(ℓ, m). □

We will show that the upper bound for d(ℓ, m) in the above lemma gives, in fact, the true minimum distance. To this end, the specialization maps defined below will be useful.

Definition 13. Let i, j be integers satisfying 1 ≤ i ≤ ℓ and 1 ≤ j ≤ ℓ′, and let a = (a_{1}, …, a_{ℓ′}) ∈ 𝔽_{q}^{ℓ′} and b = (b_{1}, …, b_{ℓ}) ∈ 𝔽_{q}^{ℓ}. The row-wise specialization map relative to a and i is the map

s_{a}^{(i)} : F(ℓ, m) → F(ℓ − 1, m − 1) defined by s_{a}^{(i)}(f) := f |_{X_{i}=a},

i.e., s_{a}^{(i)}(f) is the element of F(ℓ−1, m−1) obtained by substituting (X_{i1}, …, X_{iℓ′}) = (a_{1}, …, a_{ℓ′}) in f (X_{11}, …, X_{ℓℓ′}). Further, if ℓ′ > ℓ, then the column-wise specialization map relative to b and j is the map

t_{b}^{(j)} : F(ℓ, m) → F(ℓ, m − 1) defined by t_{b}^{(j)}(f) := f |_{X^{j}=b},

i.e., t_{b}^{(j)}(f) is the element of F(ℓ, m − 1) obtained by substituting (X_{1j}, …, X_{ℓj}) = (b_{1}, …, b_{ℓ}) in f. It may be noted that s_{a}^{(i)} and t_{b}^{(j)} are 𝔽_{q}-linear maps.

Lemma 14. Let f ∈ F(ℓ, m) and let i, j be integers satisfying 1 ≤ i ≤ ℓ and 1 ≤ j ≤ ℓ′. Then

(2)  w_{H}(Ev(f)) = ∑_{a∈𝔽_{q}^{ℓ′}} w_{H}(Ev(s_{a}^{(i)}(f))).

Moreover, if ℓ′ > ℓ, then

(3)  w_{H}(Ev(f)) = ∑_{b∈𝔽_{q}^{ℓ}} w_{H}(Ev(t_{b}^{(j)}(f))).

Proof. Given any a ∈ 𝔽_{q}^{ℓ′}, the specialization s_{a}^{(i)}(f) is in F(ℓ − 1, m − 1) and hence the codeword Ev(s_{a}^{(i)}(f)) has q^{δ−ℓ′} coordinates; each of these coordinates can be computed by evaluating f at those points P = (p_{ij}) of 𝔸^{δ} (𝔽_{q}) satisfying (p_{i1}, …, p_{iℓ′}) = a. As a varies over 𝔽_{q}^{ℓ′}, all the q^{δ} coordinates of Ev(f) will be accounted for. Thus the codeword Ev(f) can be partitioned into shorter codewords Ev(s_{a}^{(i)}(f)), a ∈ 𝔽_{q}^{ℓ′}. This implies (2). The proof of (3) is similar. □

We shall now consider the special case ℓ = ℓ′, i.e., m = 2ℓ. In this case, X has a unique maximal minor and whenever it occurs in a polynomial in F(ℓ, 2ℓ), all the submaximal minors occurring in that polynomial can be killed by a translation.

Lemma 15. Let f ∈ F(ℓ, 2ℓ) be such that det(X) ∈ supp(f) and the coefficient of det(X) in f equals 1. Then there exists a unique ℓ × ℓ matrix A with entries in 𝔽_{q} such that

f = det(X + A) + h, where h ∈ F(ℓ, 2ℓ) with supp(h) ⊆ ⋃_{i=0}^{ℓ−2} Δ_{i}(ℓ, 2ℓ).

Proof. If ℓ = 1, then the desired result holds trivially with h = 0. Assume that ℓ ≥ 2. For 1 ≤ i, j ≤ ℓ, let X^{ij} denote the (ℓ − 1) × (ℓ − 1) submatrix of X obtained by deleting the i-th row and the j-th column, and let b_{ij} denote the coefficient of det(X^{ij}) in f. Then there is h_{1} ∈ F(ℓ, 2ℓ) such that

f = det(X) + ∑_{1≤i,j≤ℓ} b_{ij} det(X^{ij}) + h_{1} and supp(h_{1}) ⊆ ⋃_{i=0}^{ℓ−2} Δ_{i}(ℓ, 2ℓ).

Now define a_{ij} = (−1)^{i+j}b_{ij} for 1 ≤ i, j ≤ ℓ and let A denote the ℓ × ℓ matrix (a_{ij})_{1≤i,j≤ℓ}. By Lemma 9, there is h_{2} ∈ F(ℓ, 2ℓ) such that

det(X + A) = det(X) + ∑_{1≤i,j≤ℓ} b_{ij}X^{ij} + h_{2} and supp(h_{2}) ⊆ ⋃_{i=0}^{ℓ−2} Δ_{i}(ℓ, 2ℓ).

Thus f = det(X + A) + h, where h := h_{1} − h_{2}, and we have the desired result. □

We are now ready to prove the main result of this section.

Theorem 16. The minimum distance d(ℓ, m) of the code C^{𝔸}(ℓ, m) is given by

(4)  d(ℓ, m) = q^{δ−ℓ^{2}} ∏_{i=0}^{ℓ−1}(q^{ℓ} − q^{i}).

Proof. We prove the theorem by induction on m. Note that m ≥ 2 since 1 ≤ ℓ ≤ ℓ′. If m = 2, then ℓ = ℓ′ = 1 and δ = 1, and so (4) follows from the observations in Remark 11 in this case. Now suppose m > 2 and the theorem is true for all codes C^{𝔸}(ℓ, m−1), with 1 ≤ ℓ ≤ ⌊(m−1)/2⌋. We will prove (4) by considering separately the cases ℓ < ℓ′ and ℓ = ℓ′.

Case 1: ℓ < ℓ′. Let f ∈ F(ℓ, m) and suppose f ≠ 0. Then supp(f) is nonempty. Choose a minor M ∈ supp(f) of the maximum possible order, say r, in the sense that M ∈ Δ_{r}(ℓ, m) and Δ_{s}(ℓ, m) ∩ supp(f) = ∅ for all s > r. Since r ≤ ℓ < ℓ′, there exists a column X^{j} of X such that the variables X_{1j}, …, X_{ℓj} do not occur in M. In particular, t_{b}^{(j)}(M) = M for any b ∈ 𝔽_{q}^{ℓ}. Since M is of maximum order in supp(f), this implies that t_{b}^{(j)}(f) is not the zero polynomial and therefore the codeword Ev(t_{b}^{(j)}(f)) is nonzero for any b ∈ 𝔽_{q}^{ℓ}. Consequently, by Lemma 14 and the induction hypothesis, we see that

w_{H}(Ev(f)) = ∑_{b∈𝔽_{q}^{ℓ}} w_{H}(Ev(t_{b}^{(j)}(f)))
≥ q^{ℓ}d(ℓ, m − 1)
= q^{ℓ}q^{(ℓ′−1)ℓ−ℓ^{2}} ∏_{i=0}^{ℓ−1}(q^{ℓ} − q^{i})

= q^{δ−ℓ^{2}} ∏_{i=0}^{ℓ−1}(q^{ℓ} − q^{i}).

Since the above holds for any nonzero f ∈ F(ℓ, m), we obtain

d(ℓ, m) ≥ q^{δ−ℓ^{2}} ∏_{i=0}^{ℓ−1}(q^{ℓ} − q^{i}).

This inequality together with Lemma 12 establishes the induction step.

Case 2: ℓ = ℓ′. In this case m = 2ℓ and X has only one ℓ × ℓ minor, namely L := det(X). Let f ∈ F(ℓ, 2ℓ) be a nonzero polynomial. We will distinguish two subcases depending on whether or not the ℓ × ℓ minor L occurs in f.

Subcase 1: L ∉ supp(f). In this event, by a similar reasoning as in Case 1, there exists a row, say the i-th row, such that s_{a}^{(i)}(f) ≠ 0 for all a ∈ 𝔽_{q}^{ℓ}. Consequently, by Lemma 14 and the induction hypothesis, we see that

w_{H}(Ev(f)) = ∑_{a∈𝔽_{q}^{ℓ}} w_{H}(Ev(s_{a}^{(i)}(f)))
≥ q^{ℓ}d(2ℓ − 1, ℓ − 1)
= q^{ℓ}q^{(ℓ−1)ℓ−(ℓ−1)^{2}} ∏_{i=0}^{ℓ−2}(q^{ℓ−1} − q^{i})

= q^{ℓ} ∏_{i=0}^{ℓ−2}(q^{ℓ} − q^{i+1})

> ∏_{i=0}^{ℓ−1}(q^{ℓ} − q^{i}).

Thus from Lemma 12, we conclude that Ev(f) cannot be a minimum weight codeword of C^{𝔸}(ℓ, m) if det(X) ∉ supp(f).

Subcase 2: L ∈ supp(f). In this event, by Lemma 15 there exists a ℓ × ℓ matrix A with entries in 𝔽_{q} such that f = det(X + A) + h, where h is a 𝔽_{q}-linear combination of i × i minors of X with 0 ≤ i ≤ ℓ − 2. If h = 0, then f = det(X + A) and since Ev(f) is obtained by evaluating f at all points of 𝔸^{δ} (𝔽_{q}), we see that w_{H}(Ev(det(X + A))) = w_{H}(Ev(det(X))); hence, by Lemma 12, we then find that w_{H}(Ev(det(X + A))) = ∏_{i=0}^{ℓ−1}(q^{ℓ} − q^{i}) = d(ℓ, 2ℓ). Now suppose h ≠ 0. Then ℓ ≥ 2 and as in Case 1, we can choose a minor M ∈ supp(h) of maximum order, say r with r ≤ ℓ − 2, and find an integer i with 1 ≤ i ≤ ℓ such that s_{a}^{(i)}(M) = M for all a ∈ 𝔽_{q}^{ℓ}. Since M is of maximum order in supp(h), we see that s_{a}^{(i)}(h) ≠ 0 for all a ∈ 𝔽_{q}^{ℓ}. Also, since r ≤ ℓ − 2, the nonzero polynomial s_{a}^{(i)}(h) is of (total) degree at most ℓ − 2. On the other hand, by developing the resulting determinant along the i-th row, we see that s_{a}^{(i)}(det(X + A)) is either the zero polynomial or a nonzero polynomial in 𝔽_{q}[X] of degree ℓ − 1. It follows that s_{a}^{(i)}(f) ≠ 0 for all a ∈ 𝔽_{q}^{ℓ}. Now, proceeding as in Subcase 1, we see that w_{H}(Ev(f)) > ∏_{i=0}^{ℓ−1}(q^{ℓ} − q^{i}), and so from Lemma 12 we conclude that Ev(f) cannot be a minimum weight codeword.

Thus we have shown that d(ℓ, 2ℓ) = ∏_{i=0}^{ℓ−1}(q^{ℓ} − q^{i}) and therefore established the induction step in Case 2. This completes the proof. □

Using the q-factorial function [d]_{q}! := ∏_{i=1}^{d}(q^{i} − 1), the formula (4) for the minimum distance of C^{𝔸}(ℓ, m) can be more compactly written as follows.

(5)  d(ℓ, m) = q^{δ−\binom{ℓ+1}{2}}[ℓ]_{q}!.

Note that if ℓ = 1, then the formula (4) as well as (5) for d(ℓ, m) is in agreement with the observations in Remark 11.

Remark 17. By analyzing the proof of Theorem 16 in greater detail, one can show that if ℓ = ℓ′, then the minimum weight codewords of C^{𝔸}(ℓ, m) arise precisely from nonzero constant multiples of translates of the unique maximal minor, i.e., from polynomials of the form λ det(X + A), with 0 ≠ λ ∈ 𝔽_{q} and A an ℓ × ℓ matrix with entries in 𝔽_{q}. Consequently, the number of minimum weight codewords in C^{𝔸}(ℓ, 2ℓ) is equal to (q − 1)q^{ℓ^{2}}. A more general version of these results will be proved in Sections 5 and 6.

4. Automorphisms

Recall that the (permutation) automorphism group Aut(C) of a code C ⊆ 𝔽_{q}^{n} is the set of all permutations σ of {1, …, n} such that (c_{σ(1)}, …, c_{σ(n)}) ∈ C for all c = (c_{1}, …, c_{n}) ∈ C. Evidently, Aut(C) is a subgroup of the symmetric group on {1, …, n}. In this section, we shall show that the automorphism groups of affine Grassmann codes are large; more precisely, we shall show that Aut (C^{𝔸}(ℓ, m)) contains a subgroup of order

(6)  q^{δ} ∏_{i=0}^{ℓ−1}(q^{ℓ} − q^{i}) = n ∏_{i=0}^{ℓ−1}(q^{ℓ} − q^{i}) = q^{ℓ^{2}}d(ℓ, m),

where n and d(ℓ, m) denote the length and the minimal distance of C^{𝔸}(ℓ, m).

Denote, as usual, by GL_{r}(𝔽_{q}) the set of all invertible r×r matrices with entries in 𝔽_{q} and by M_{r×s}(𝔽_{q}) the set of all r×s matrices with entries in 𝔽_{q}. Let A ∈ GL_{ℓ′}(𝔽_{q}) and u ∈ M_{ℓ×ℓ′}(𝔽_{q}). Define

ϕ_{u,A} : 𝔸^{δ} (𝔽_{q}) → 𝔸^{δ} (𝔽_{q})

to be the linear transformation given by

ϕ_{u,A}(P) = P A^{−1} + u for P = (p_{ij})_{1≤i≤ℓ, 1≤j≤ℓ′} ∈ 𝔸^{δ} (𝔽_{q}) ,

It is clear that the transformation ϕ_{u,A} gives a bijection of 𝔸^{δ} = 𝔸^{δ} (𝔽_{q}) onto itself, and hence (f(ϕ_{u,A}(P)))_{P ∈𝔸^{δ}} will be a permutation of (f(P))_{P ∈𝔸^{δ}} for any f ∈ 𝔽_{q}[X]; we shall denote this permutation σ_{u,A}.

Lemma 18. Let A ∈ GL_{ℓ′}(𝔽_{q}) and u ∈ M_{ℓ×ℓ′}(𝔽_{q}). Then σ_{u,A} ∈ Aut (C^{𝔸}(ℓ, m)).

Proof. Let r be any integer with 0 ≤ r ≤ ℓ. In view of Lemma 9, a r × r minor of XA^{−1} + u is a 𝔽_{q}-linear combination of i × i minors of X, where 0 ≤ i ≤ r. Consequently, if f = f(X) ∈ F(ℓ, m), then f(XA^{−1} + u) ∈ F(ℓ, m). Moreover,

σ_{u,A} (Ev(f)) = (f(ϕ_{u,A}(P)))_{P ∈𝔸^{δ}(𝔽_{q})} = Ev (f(XA^{−1} + u)) .

It follows that σ_{u,A} ∈ Aut(C), where C = C^{𝔸}(ℓ, m) = Ev (F(ℓ, m)). □

Observe that ϕ_{0,I} is the identity transformation of 𝔸^{δ}, where 0 denotes the zero matrix in M_{ℓ×ℓ′}(𝔽_{q}) and I the identity matrix in GL_{ℓ′}(𝔽_{q}). Moreover, given any A, B ∈ GL_{ℓ′}(𝔽_{q}) and u, v ∈ M_{ℓ×ℓ′}(𝔽_{q}), we have

(7)  ϕ_{u,A} ∘ ϕ_{v,B} = ϕ_{w,AB} and ϕ_{u,A}^{−1} = ϕ_{u′,A^{−1}},

where w := vA^{−1} + u and u′ = −uA. This leads to the following observation-cum-definition.

Definition 19. The set {ϕ_{u,A} : A ∈ GL_{ℓ′}(𝔽_{q}) and u ∈ M_{ℓ×ℓ′}(𝔽_{q})} forms a group with respect to composition of maps and this group will be denoted by 𝔊(ℓ, m).

We determine the group structure of 𝔊(ℓ, m) in the following proposition.

Proposition 20. As a group 𝔊(ℓ, m) is isomorphic to the semidirect product M_{ℓ×ℓ′}(𝔽_{q}) ⋊_{θ} GL_{ℓ′}(𝔽_{q}), where the homomorphism θ : GL_{ℓ′}(𝔽_{q}) → Aut(M_{ℓ×ℓ′}(𝔽_{q})) is defined by θ(A)(B) := BA^{−1}.

Proof. Recall that if G and H are any groups, and if θ : H → Aut(G) is any group homomorphism, then the semidirect product G ⋊_{θ} H of G and H relative to θ is the group whose underlying set is G × H and whose group operation is defined by (g, h)(g′, h′) = (gθ(h)(g′), hh′). In our case, G is the additive group M_{ℓ×ℓ′}(𝔽_{q}) and H is the multiplicative group GL_{ℓ′}(𝔽_{q}), while θ : H → Aut(G) is given by θ(A)(u) := uA^{−1}. Now observe that θ(A) ∈ Aut(G) for all A ∈ H and θ(A_{1}A_{2}) = θ(A_{1})θ(A_{2}) for all A_{1}, A_{2} ∈ H. So θ is indeed a homomorphism of H into Aut(G).

Moreover, in view of (7), the group operation (u, A)(v, B) = (u + vA^{−1}, AB) in G ⋊_{θ} H is consistent with the group operation in 𝔊(ℓ, m). Thus (u, A) ↦ ϕ_{u,A} gives an isomorphism of M_{ℓ×ℓ′}(𝔽_{q}) ⋊_{θ} GL_{ℓ′}(𝔽_{q}) onto 𝔊(ℓ, m). □

Theorem 21. The automorphism group of the affine Grassmann code C^{𝔸}(ℓ, m) contains a subgroup isomorphic to 𝔊(ℓ, m). In particular, #Aut (C^{𝔸}(ℓ, m)) is greater than or equal to the quantity in (6).

Proof. In view of Lemma 18, ϕ_{u,A} ↦ σ_{u,A} gives a natural map from 𝔊(ℓ, m) into Aut (C^{𝔸}(ℓ, m)). It is readily seen that this map is a group homomorphism. So it suffices to show that this homomorphism is injective. To this end, suppose σ_{u,A} is the identity permutation for some A ∈ GL_{ℓ′}(𝔽_{q}) and u ∈ M_{ℓ×ℓ′}(𝔽_{q}). Then σ_{u,A}(Ev(f)) = Ev(f) for all f ∈ F(ℓ, m), i.e.,

f(P A^{−1} + u) = f(P) for all f ∈ F(ℓ, m) and all P ∈ 𝔸^{δ} (𝔽_{q}).

By choosing P to be the zero matrix and letting f vary over all possible 1 × 1 minors, we find that u = 0. Further, by choosing P = e_{ij}, i.e., P to be the ℓ × ℓ′ matrix with 1 in (i, j)-th position and 0 elsewhere, and again letting f vary over all possible 1 × 1 minors, we see that A^{−1} is the identity matrix I. Hence A = I. □

We leave the question of the complete determination of the automorphism group Aut(C^{𝔸}(ℓ, m)) open for future investigation.

5. Characterization of minimum weight codewords

In Section 3, we have calculated the minimum distance d(ℓ, m) of the affine Grassmann code C^{𝔸}(ℓ, m). In this section, we will give an explicit characterization of all of its codewords of weight d(ℓ, m). One of the tools utilized will be a concept involving the specialization function s_{a}^{(i)} from Definition 13, which is defined below.

Definition 22. Let f ∈ F(ℓ, m) and let i be an integer between 1 and ℓ. The i-th row-vanishing locus of f is the set

V_{f}^{(i)} := {a ∈ 𝔽_{q}^{ℓ′} : s_{a}^{(i)}(f) = 0}.

It turns out that if a polynomial in F(ℓ, m) is changed by a translation of the underlying matrix X to X + u, then its i-th row-vanishing locus is a translate of the corresponding locus of the transformed polynomial by the i-th row of u.

Lemma 23. Let f ∈ F(ℓ, m) and let i be an integer between 1 and ℓ. Then

V_{f}^{(i)} = u_{i} + V_{ϕ_{u,I}(f)}^{(i)} for every u ∈ M_{ℓ×ℓ′}(𝔽_{q}),

where I denotes the identity matrix in GL_{ℓ′}(𝔽_{q}).

Proof. Let u ∈ M_{ℓ×ℓ′}(𝔽_{q}) and let g := ϕ_{u,I}(f). Suppose a ∈ V_{f}^{(i)}. Define b ∈ 𝔽_{q}^{ℓ′} by the relation a = u_{i} + b. Note that

(8)  s_{b}^{(i)} (g) = g(X)|_{X_{i}=b} = f(X + u)|_{X_{i}=b}.

Now s_{a}^{(i)}(f) = f|_{X_{i}=a} = 0. In particular, the polynomial f|_{X_{i}=a} evaluates to 0 for every specialization of the rows X_{1}, …, X_{i−1}, X_{i+1}, …, X_{ℓ} to arbitrary vectors in 𝔽_{q}^{ℓ′}. Since translations by a fixed vector in 𝔽_{q}^{ℓ′} give a bijection of 𝔽_{q}^{ℓ′} into itself, this implies that g|_{X_{i}=b} evaluates to 0 for every specialization of the rows X_{1}, …, X_{i−1}, X_{i+1}, …, X_{ℓ} to arbitrary vectors in 𝔽_{q}^{ℓ′}. Hence by the injectivity of

the evaluation map Ev : F(ℓ − 1, m − 1) → 𝔽_{q}^{(ℓ−1)ℓ′}, we see that g|_{X_{i}=b} is the zero polynomial. Thus, in view of (8), b ∈ V_{g}^{(i)}, i.e., a ∈ u_{i} + V_{f}^{(i)}. This proves that

V_{f}^{(i)} ⊆ u_{i} + V_{g}^{(i)}. The reverse inclusion is proved similarly. □

Corollary 24. Let f ∈ F(ℓ, m) and let i be an integer between 1 and ℓ. Then the i-th row-vanishing locus is either empty or an affine linear space over 𝔽_{q}, i.e., either V_{f}^{(i)} = ∅ or V_{f}^{(i)} = a + V for some a ∈ 𝔽_{q}^{ℓ′} and a 𝔽_{q}-linear space V.

Proof. Suppose V_{f}^{(i)} ≠ ∅. Then there exists some a ∈ V_{f}^{(i)}. Let u ∈ M_{ℓ×ℓ′}(𝔽_{q}) be such that u_{i} = a and u_{j} = 0 for 1 ≤ j ≤ ℓ with j ≠ i. Also let g := ϕ_{u,I}(f). Then by Lemma 23, V_{f}^{(i)} = a + V_{g}^{(i)}. It remains to show that V_{g}^{(i)} is a subspace of

𝔽_{q}^{ℓ′}. To this end, first note that 0 ∈ V_{g}^{(i)}, thanks to the choice of a. Now observe that for any minor M ∈ Δ(ℓ, m), we have s_{0}^{(i)}(M) = 0 if M involves the i-th row and s_{0}^{(i)}(M) = M otherwise. Since s_{0}^{(i)}(g) = 0, Lemma 3 implies that g is a 𝔽_{q}-linear combination of minors of X that involve the i-th row. Hence using the multilinearity of the determinant, we readily see that V_{g}^{(i)} is closed under addition and scalar multiplication. □

The following result is an analogue of Lemma 23 for homogeneous linear transformations of the underlying matrix.

Lemma 25. Let f ∈ F(ℓ, m) and let i be an integer between 1 and ℓ. Then

V_{ϕ_{0,A}(f)}^{(i)} = V_{f}^{(i)}A := {aA : a ∈ V_{f}^{(i)}} for every A ∈ GL_{ℓ′}(𝔽_{q}),

where 0 denotes the zero matrix in M_{ℓ×ℓ′}(𝔽_{q}).

Proof. Let A ∈ GL_{ℓ′}(𝔽_{q}). Consider h := ϕ_{0,A}(f)., i.e., h ∈ F(ℓ, m) given by h(X) = f(XA^{−1}). Observe that if, as before, X_{1}, …, X_{ℓ} denote the row vectors of X, then X_{1}A^{−1}, …, X_{ℓ}A^{−1} are the row-vectors of XA^{−1}. Thus the specialization X_{i} = aA in h corresponds to the specialization X_{i} = a in f. The rest of the proof is similar to that of Lemma 23. □

Using the row-vanishing locus, one can obtain a useful estimate for the Hamming weight of a codeword from C^{𝔸}(ℓ, m).

Proposition 26. Let f ∈ F(ℓ, m) and let i be an integer between 1 and ℓ. Suppose t = #V_{f}^{(i)}. Then

(9)  w_{H}(Ev(f)) ≥ \frac{q^{ℓ′} − t}{q^{ℓ′} − q^{ℓ′−ℓ}} d(ℓ, m).

Proof. In view of Lemma 14 and the definition of V_{f}^{(i)}, we see that

(10) w_{H}(Ev(f)) = ∑_{a∈𝔽_{q}^{ℓ′} \V_{f}^{(i)}} w_{H}(Ev(s_{a}^{(i)}(f))) ≥ (q^{ℓ′} − t)d(ℓ − 1, m − 1).

On the other hand, by Theorem 16,

d(ℓ, m) = q^{ℓ(ℓ′−ℓ)} ∏_{i=0}^{ℓ−1}(q^{ℓ} − q^{i}) and d(ℓ − 1, m − 1) = q^{(ℓ−1)(ℓ′−ℓ)} ∏_{j=0}^{ℓ−2}(q^{ℓ−1} − q^{j}).

Hence, by a direct computation, d(ℓ, m)/d(ℓ − 1, m − 1) = q^{ℓ′} − q^{ℓ′−ℓ}. Combining this with (10), we obtain the desired result. □

Proposition 26 has the following important corollary for minimum weight codewords, which will be the key to our characterization of minimum weight codewords.

Corollary 27. Let f ∈ F(ℓ, m). If Ev(f) is a minimum weight codeword of C^{𝔸}(ℓ, m), then #V_{f}^{(i)} ≥ q^{ℓ′−ℓ} for all i ∈ {1, …, ℓ}.

Proof. If #V_{f}^{(i)} < q^{ℓ′−ℓ} for some i ∈ {1, …, ℓ}, then by Proposition 26, we obtain w_{H}(Ev(f)) > d(ℓ, m). □

We are now ready to formulate and prove a characterization of minimum weight codewords of C^{𝔸}(ℓ, m). Recall that if Y = (Y_{ij}) is any ℓ × ℓ′ matrix and, as before, ℓ ≤ ℓ′, then the leading maximal minor of Y is the minor formed by the first ℓ columns of Y, namely, det ( (Y_{ij})_{1≤i,j≤ℓ} ).

Theorem 28. Let f ∈ F(ℓ, m). Then f is a minimum weight codeword of C^{𝔸}(ℓ, m) if and only if f is in the 𝔊(ℓ, m)-orbit of the leading maximal minor of X. In other words, w_{H}(Ev(f)) = d(ℓ, m) if and only if f is the leading maximal minor of Y, where Y = XA^{−1} + u for some A ∈ GL_{ℓ′}(𝔽_{q}) and u ∈ M_{ℓ×ℓ′}(𝔽_{q}).

Proof. Let L := det ( (X_{ij})_{1≤i,j≤ℓ} ) denote the leading maximal minor of X. Suppose f is in the 𝔊(ℓ, m)-orbit of L. Then, as noted in Section 4, the codewords Ev(f) and Ev(L) differ from each other by a permutation of the coordinates. Hence w_{H}(Ev(f)) = w_{H}(Ev(L)) = d(ℓ, m), thanks to Lemma 12.

To prove the converse, suppose w_{H}(Ev(f)) = d(ℓ, m). Then f must be a nonzero polynomial since d(ℓ, m) < q^{δ}. Further, since ℓ′ − ℓ ≥ 0, Corollary 27 implies that V_{f}^{(i)} is nonempty for each i ∈ {1, …, ℓ}. Choose u_{i} ∈ V_{f}^{(i)} for 1 ≤ i ≤ ℓ. Let u ∈ M_{ℓ×ℓ′}(𝔽_{q}) be the ℓ × ℓ′ matrix whose i-th row vector is u_{i} for 1 ≤ i ≤ ℓ, and let g := ϕ_{u,I}(f). Then g is in the 𝔊(ℓ, m)-orbit of f and by Lemma 23,

V_{f}^{(i)} = u_{i} + V_{g}^{(i)} and 0 ∈ V_{g}^{(i)} for each i ∈ {1, …, ℓ}.

Thus, s_{0}^{(i)}(g) = 0 for each i ∈ {1, …, ℓ}. Now observe that for any M ∈ Δ(ℓ, m) and any i ∈ {1, …, ℓ}, we have s_{0}^{(i)}(M) = 0 if M involves the i-th row of X and s_{0}^{(i)}(M) = M otherwise. Consequently, if g = ∑_{M∈Δ(ℓ,m)} a_{M}M, where a_{M} ∈ 𝔽_{q} for M ∈ Δ(ℓ, m), then by Lemma 3, we see that a_{M} = 0 for all M ∈ ∪_{i=0}^{ℓ−1}Δ_{i}(ℓ, m). This proves that g is a 𝔽_{q}-linear combination of ℓ × ℓ minors of X. In particular, if ℓ′ = ℓ, then L being the only ℓ × ℓ minors of X, we obtain g = cL for some c ∈ 𝔽_{q} with c ≠ 0. Since L = ϕ_{0,D}(cL), where D denotes the ℓ′ ×ℓ′ diagonal matrix diag (c, 1, …, 1) in GL_{ℓ′}(𝔽_{q}), we see that f is in the 𝔊(ℓ, m)-orbit of L when ℓ′ = ℓ.

Now suppose ℓ < ℓ′. Consider the first row-vanishing space V_{g}^{(1)}. In view of Corollary 24 and the fact that 0 ∈ V_{g}^{(1)}, we see that V_{g}^{(1)} is a linear space over 𝔽_{q}. Moreover, Corollary 27 implies that the dimension of V_{g}^{(1)} is at least ℓ′ − ℓ. Hence we can choose linearly independent vectors b_{1}, …, b_{ℓ′−ℓ} ∈ V_{g}^{(1)}. Let b be the (ℓ′ − ℓ) × ℓ′ matrix whose i-th row vector is b_{i} for 1 ≤ i ≤ ℓ′ − ℓ. Since b has full rank, there exists an invertible matrix A ∈ GL_{ℓ′}(𝔽_{q}) such that

bA = (0_{(ℓ′−ℓ)×ℓ} | I_{ℓ′−ℓ}) = ( \begin{matrix}0 & ⋯ & 0 & 1 & 0 & … & 0 \\ 0 & ⋯ & 0 & 0 & 1 & … & 0 \\ ⋮ & & ⋮ & ⋮ & & ... & ⋮ \\ 0 & ⋯ & 0 & 0 & 0 & … & 1 \end{matrix} ) .

Indeed, the matrix on the right is essentially the reduced column-echelon form of b. We now consider the function h = h(X) = ϕ_{0,A}(g(X)) = g(XA^{−1}). Clearly, h is in the 𝔊(ℓ, m)-orbit of g and hence of f; in particular, w_{H}(Ev(h)) = d(ℓ, m) and h is a nonzero polynomial. By the multilinearity of the determinant, it can, just as g, be written as a 𝔽_{q}-linear combination of ℓ × ℓ minors of X. For 1 ≤ j ≤ ℓ′, let e_{j} denote the vector in 𝔽_{q}^{ℓ′} with 1 in the j-th position and 0 elsewhere. Observe that if M ∈ Δ_{ℓ}(ℓ, m) is the minor formed by the columns of X indexed by j_{1}, …, j_{ℓ}, where 1 ≤ j_{1} < ⋯ < j_{ℓ} ≤ ℓ′, then s_{e_{j}}^{(1)}(M) = 0 if j ∉ {j_{1}, …, j_{ℓ}}, whereas s_{e_{j}}^{(1)}(M) is a nonzero polynomial (and, in fact, ±M_{1}, where M_{1} is a (ℓ − 1) × (ℓ − 1) minor of X) if j ∈ {j_{1}, …, j_{ℓ}}. Now by the choice of A and by Lemma 25, we have that e_{j} ∈ V_{h}^{(1)} for all j such that ℓ < j ≤ ℓ′. Consequently, if h = ∑_{M∈Δ_{ℓ}(ℓ,m)} a_{M}M, where a_{M} ∈ 𝔽_{q} for M ∈ Δ_{ℓ}(ℓ, m), then by Lemma 3, we see that a_{M} = 0 for all those M in Δ_{ℓ}(ℓ, m) that involve the j-th column of X for some j > ℓ. But the only ℓ × ℓ minor of X that does not involve the j-th column of X for some j > ℓ is L. Hence h = cL for some c ∈ 𝔽_{q} with c ≠ 0. It follows that f is in the 𝔊(ℓ, m)-orbit of L. □

In case ℓ′ = ℓ, the above theorem simplifies to the statement in Remark 17.

6. Enumeration of minimum weight codewords

In this section, we let d = d(ℓ, m) denote the minimum distance of C^{𝔸}(ℓ, m) and A_{d} the number of minimum weight codewords of C^{𝔸}(ℓ, m). Having characterized the codewords of weight d in the previous section, we now proceed to compute A_{d}. Equivalently, we determine the number of polynomials f ∈ F(ℓ, m) giving rise to minimum weight codewords. We have seen in Section 4 that the finite group 𝔊(ℓ, m) acts naturally on F(ℓ, m). With this in view, we can use standard group theory together with Theorem 28 to obtain the following.

Lemma 29. Let L = det ((X_{ij})_{1≤i,j≤ℓ}) be the leading maximal minor of X. Then

A_{d} = \frac{#𝔊(ℓ, m)}{#Stab(L)},

where Stab(L) denotes the stabilizer of the minor L.

Proof. By Theorem 28, the cardinality of the 𝔊(ℓ, m)-orbit of L is equal to A_{d}. On the other hand, for any finite group acting on a finite set, the cardinality of the orbit of an element is equal to the index of its stabilizer. □

Thanks to Lemma 29, the computation of A_{d} reduces to the problem of finding the cardinality of the stabilizer of L := det ((X_{ij})_{1≤i,j≤ℓ}). To this end, let us begin by observing that if f ∈ F(ℓ, m) is in the 𝔊(ℓ, m)-orbit of L, i.e., if f = ϕ_{u,A}(L) for some A ∈ GL_{ℓ′}(𝔽_{q}) and u ∈ M_{ℓ×ℓ′}(𝔽_{q}), then

(11) f = det(XM + m) for some M ∈ M_{ℓ′×ℓ}(𝔽_{q}) of rank ℓ and m ∈ M_{ℓ×ℓ}(𝔽_{q}).

Indeed, it suffices to take M to be the ℓ′ × ℓ matrix formed by the first ℓ columns of A^{−1} and m to be the ℓ × ℓ matrix formed by the first ℓ columns of u, and observe that rank(M) = ℓ since A is nonsingular and that the leading maximal minor of the ℓ × ℓ′ matrix XA^{−1} + u is det(XM + m). We shall now analyze when a polynomial f given by (11) is in the stabilizer of L. As usual, we denote by SL_{ℓ}(𝔽_{q}) the special linear group of ℓ × ℓ matrices over 𝔽_{q}, viz., SL_{ℓ}(𝔽_{q}) := {A ∈ GL_{ℓ}(𝔽_{q}) : det A = 1}.

Lemma 30. Let L = det ((X_{ij})_{1≤i,j≤ℓ}) be the leading maximal minor of X. Also let M ∈ M_{ℓ′×ℓ}(𝔽_{q}) be of rank ℓ and m ∈ M_{ℓ×ℓ}(𝔽_{q}). Then L = det(XM + m) if and only if m = 0 and there exists E ∈ SL_{ℓ}(𝔽_{q}) such that the first ℓ rows of ME form the ℓ × ℓ identity matrix, while the last ℓ′ − ℓ rows are zero. In this case, the matrix E in SL_{ℓ}(𝔽_{q}) is uniquely determined by M.

Proof. We start by showing the uniqueness of the matrix E. Suppose

ME_{1} = ( \begin{matrix}I_{ℓ} \\ 0 \end{matrix} ) = ME_{2} for some E_{1}, E_{2} ∈ SL_{ℓ}(𝔽_{q}),

where I_{ℓ} denotes the ℓ × ℓ identity matrix and 0 the (ℓ′ − ℓ) × ℓ zero matrix. Then M(E_{2} − E_{1}) = 0. Since M has full rank, this can only happen if E_{1} = E_{2}.

To prove the equivalence, first suppose there exists E ∈ SL_{ℓ}(𝔽_{q}) such that

(12)  ME = ( \begin{matrix}I_{ℓ} \\ 0 \end{matrix} ) ,

and also suppose m = 0. Then

det(XM + m) = det(XM) = det(XME) = det (X ( \begin{matrix}I_{ℓ} \\ 0 \end{matrix} )) = L.

Conversely, suppose L = det(XM + m). Since M has full rank, there exists N ∈ M_{ℓ′×ℓ}(𝔽_{q}) such that NM = m. Hence L = det(XM + m) = det((X + N)M). Using Cauchy-Binet formula (Lemma 10) and the notation therein, we now find

(13)  L = ∑_{I} det((X + N)^{I}) det(M_{I}),

where the sum is over all subsets I of {1, …, ℓ′} of cardinality ℓ. For any such I, Lemma 9 implies that det((X + N)^{I}) is the sum of det(X^{I}) and a 𝔽_{q}-linear combination of minors of X^{I} of order < ℓ. Hence, comparing terms of total degree ℓ in (13), we obtain

(14)  L = det(X^{I^{∗}}) = ∑_{I} det(X^{I}) det(M_{I}), where I^{∗} := {1, …, ℓ}.

Consequently, in view of Lemma 3, det(M_{I^{∗}}) = 1, while det(M_{I}) = 0 for every I ⊆ {1, …, ℓ′} with #I = ℓ and I ≠ I^{∗}. Define E := M_{I^{∗}}^{−1}. It is clear that E ∈ SL_{ℓ}(𝔽_{q}). Moreover, by the choice of E, the first ℓ rows of ME form the ℓ × ℓ identity matrix I_{ℓ}. We claim that for any i > ℓ, the i-th row ME_{i} of ME is zero. To see this, write ME_{i} = (b_{1}, …, b_{ℓ}). Choose any j ∈ I^{∗} and let I := (I^{∗} ∪ {i}) \ {j}. Then I ⊆ {1, …, ℓ′} with #I = ℓ and det(M_{I}) = 0 since I ≠ I^{∗}. On the other hand, det(M_{I}) = det(M_{I}E). Now, since the first ℓ−1 elements of I are contained in {1, …, ℓ}, the first ℓ − 1 rows of the matrix M_{I}E form the matrix obtained from I_{ℓ} by deleting its j-th row. This implies that 0 = det(M_{I}E) = ±(M_{I}E)_{ℓj} = ±(ME)_{ij}. By varying j over I^{∗}, we obtain ME_{i} = (0, …, 0). This proves the claim. It remains to show that m = 0. We have noted earlier that there is N ∈ M_{ℓ×ℓ′}(𝔽_{q}) such that m = NM. Hence

L = det(XM+m) = det((X+N)M) = det((X+N)ME) = det((X_{ij}+N_{ij})_{1≤i,j≤ℓ}),

where the penultimate equality follows since E ∈ SL_{ℓ}(𝔽_{q}) and the last equality follows since ME satisfies (12). Using Lemma 9 together with Lemma 3, by comparing the coefficients of (ℓ − 1) × (ℓ − 1) minors, we find N_{ij} = 0 for 1 ≤ i, j ≤ ℓ. But then mE = N(ME) = (N_{ij})_{1≤i,j≤ℓ} = 0, thanks to (12). Since E is invertible, this implies that m = 0. □

We are now ready to compute the cardinality of the stabilizer of the leading maximal minor.

Lemma 31. Let L = det ((X_{ij})_{1≤i,j≤ℓ}) be the leading maximal minor of X. Then

#Stab(L) = \frac{q^{ℓ(ℓ′−ℓ)}}{q − 1} ∏_{i=ℓ}^{ℓ′−1}(q^{ℓ′} − q^{i}) ∏_{j=0}^{ℓ−1}(q^{ℓ} − q^{i}).

Proof. Let A ∈ GL_{ℓ′}(𝔽_{q}) and u ∈ M_{ℓ×ℓ′}(𝔽_{q}). Suppose ϕ_{u,A}(L) = L. First we write A = (M | R) where M ∈ M_{ℓ′×ℓ}(𝔽_{q}) and R ∈ M_{ℓ′×(ℓ′−ℓ)}(𝔽_{q}) are matrices formed, respectively, by the first ℓ columns of A and the remaining ℓ′ − ℓ columns of A.

Similarly, we write u = (m | r). Then, as in (11), L = det(XM + m). Hence by Lemma 30, m = 0 and moreover, there exists a unique E ∈ SL_{ℓ}(𝔽_{q}) such that

(15)  A ( \begin{matrix}E & 0 \\ 0 & I_{ℓ′−ℓ} \end{matrix} ) = A (M | R) = ( \frac{I_{ℓ}}{0} R ) ,

where 0 denotes the zero matrix of an appropriate size and, as before, I_{ℓ} denotes the ℓ × ℓ identity matrix. The matrices R and r do not have any effect on ϕ_{u,A}(L) and can therefore be chosen freely. However, R has to be chosen in such a way that the matrix on the right hand side of (15) has full rank. This means that the last ℓ′ − ℓ rows of R must be linearly independent. It follows that #Stab(L) is the product of #SL_{ℓ}(𝔽_{q}) and the following terms:

q^{ℓ(ℓ′−ℓ)},  for the choice of r,
q^{ℓ(ℓ′−ℓ)},  for the choice of the first ℓ rows of R, and
∏_{i=0}^{ℓ′−ℓ−1}(q^{ℓ′−ℓ} − q^{i}), for the choice of the last ℓ′ − ℓ rows of R.

Since #SL_{ℓ}(𝔽_{q}) = (q − 1)^{−1} ∏_{j=0}^{ℓ−1}(q^{ℓ} − q^{j}), the lemma is proved. □

We now obtain the main result of this section concerning the number of codewords of C^{𝔸}(ℓ, m) of weight d(ℓ, m). The result is best formulated using the Gaussian binomial coefficient defined, for any integers k and n with 1 ≤ k ≤ n, as follows.

(16)  \left[{n \atop k}\right]_{q} := \frac{[n]_{q}!}{[k]_{q}![n − k]_{q}!} = \frac{(q^{n} − 1)(q^{n} − q) … (q^{n} − q^{k−1})}{(q^{k} − 1)(q^{k} − q) … (q^{k} − q^{k−1})}.

It is well-known that (16) is a monic polynomial in q of degree k(n − k) with nonnegative integral coefficients. In particular, \left[{n \atop n}\right]_{q} = 1.

Theorem 32. The number A_{d} of codewords of weight d(ℓ, m) of the affine Grassmann code C^{𝔸}(ℓ, m) is given by

A_{d} = (q − 1)q^{ℓ^{2}} \left[{ℓ′ \atop ℓ}\right]_{q}.

Proof. Using Proposition 20 we see that

#𝔊(ℓ, m) = #M_{ℓ×ℓ′}(𝔽_{q}) · #GL_{ℓ′}(𝔽_{q}) = q^{ℓℓ′} ∏_{i=0}^{ℓ′−1}(q^{ℓ′} − q^{i}).

Hence the desired result follows from Lemmas 29 and 31. □

For ℓ = 1, we obtain A_{d} = q(q^{ℓ′}−1), whereas for ℓ′ = ℓ, we obtain A_{d} = (q−1)q^{ℓ^{2}}. This is in agreement with Remarks 11 and 17, respectively.

7. Connection with Grassmann codes

Grassmann codes, denoted by C(ℓ, m), are [n, k]_{q}-linear codes defined for any positive integers ℓ, m satisfying 1 ≤ ℓ ≤ m, where

n := \left[{m \atop ℓ}\right]_{q} := \frac{(q^{m} − 1)(q^{m} − q) … (q^{m} − q^{ℓ−1})}{(q^{ℓ} − 1)(q^{ℓ} − q) … (q^{ℓ} − q^{ℓ−1})} and k := \binom{m}{ℓ}.

The case ℓ = m is trivial and in general, there is a natural equivalence between C(ℓ, m) and C(m − ℓ, m). With this in view, we shall assume 1 ≤ ℓ < m and that m − ℓ ≥ ℓ. Thus, if we set ℓ′ := m − ℓ, then we have 1 ≤ ℓ ≤ ℓ′ and ℓ + ℓ′ = m, exactly as in the basic set-up of Sections 2 through 6.

A quick way to define C(ℓ, m) is to say that these are linear codes associated to the projective system obtained from the Plücker embedding of the Grassmann variety G_{ℓ,m} in the projective space ℙ^{k−1} over 𝔽_{q}. Recall that the Grassmann variety (also known as the Grassmannian) G_{ℓ,m} over 𝔽_{q} is the space of all ℓ-dimensional subspaces of the m-dimensional vector space 𝔽_{q}^{m} over 𝔽_{q}. The Plücker embedding maps G_{ℓ,m}(𝔽_{q}) into ℙ^{k−1} = ℙ(∧^{ℓ}𝔽_{q}^{m}) by sending a ℓ-dimensional subspace W spanned by w_{1}, …, w_{ℓ} to the class of w_{1} ∧ ⋯ ∧ w_{ℓ}. To obtain this a little more concretely, one can proceed as follows. Let

I(ℓ, m) = {α = (α_{1}, …, α_{ℓ}) ∈ ℤ^{ℓ} : 1 ≤ α_{1} < ⋯ < α_{ℓ} ≤ m}

be an indexing set [ordered, say, lexicographically] for the points of ℙ^{k−1}(𝔽_{q}). Given any α ∈ I(ℓ, m) and any ℓ × m matrix A = (a_{ij}), let

p_{α}(A) = determinant of the α-th submatrix of A := det (a_{iα_{j}})_{1≤i,j≤ℓ} .

Now, for any W ∈ G_{ℓ,m}(𝔽_{q}), we can find a ℓ × m matrix A_{W} whose rows give a basis of W, and then

p(W) = (p_{α}(A_{W}))_{α∈I(ℓ,m)} ∈ ℙ^{k−1}

is called the Plücker coordinate of W. It is easy to see that this depends only on W and not on the choice of A_{W}. Moreover, The map W ↦ p(W) of G_{ℓ,m}(𝔽_{q}) → ℙ^{k−1} is precisely the Plücker embedding; it is well-known that this is injective and its image equals the zero locus of certain quadratic polynomials. Henceforth, we shall identify W with p(W). The definition of C(ℓ, m) as the codes corresponding to the projective system in ℙ^{k−1} given by G_{ℓ,m}(𝔽_{q}) amounts to the following.

Let G(ℓ, m) = (∧^{ℓ}𝔽_{q}^{m})^{∗} denote the space of linear forms on ∧^{ℓ}𝔽_{q}^{m} [this can be identified with (∧^{m−ℓ}𝔽_{q}^{m})] and let {Q_{1}, …, Q_{n}} be (arbitrary, but fixed, lifts of) points in ∧^{ℓ}𝔽_{q}^{m} corresponding to the elements of G_{ℓ,m}(𝔽_{q}) in ℙ^{k−1}. Now the evaluation map

Ev : G(ℓ, m) → 𝔸^{n}(𝔽_{q}) defined by Ev(g) := (g(Q_{1}), …, g(Q_{n}))

is injective (since the Plücker embedding is nondegenerate) and its image is precisely the Grassmann code C(ℓ, m).

To relate C(ℓ, m) to C^{𝔸}(ℓ, m), let us first note that the projective space ℙ^{k−1} is covered by affine spaces U_{α} ≃ 𝔸^{k−1}, where U_{α} := {p ∈ ℙ^{k−1} : p_{α} = 1} and α varies over I(ℓ, m). It is a classical fact that the intersection B_{α} := G_{ℓ,m}∩U_{α} is isomorphic to an affine space of dimension δ := ℓℓ′ = ℓ(m − ℓ). This isomorphism is described explicitly by the Basic Cell Lemma of [6]. In effect, if W ∈ B_{α}, then the ℓ × m matrix A_{W} associated to W can be chosen in such a way that the α-th submatrix of A_{W} is the identity matrix. Now if B_{W} denotes the ℓ×ℓ′ matrix formed by removing from A_{W} its α-th submatrix, then the entries of B_{W} can be viewed as variables. Moreover, the k-tuple p(W) formed by the ℓ × ℓ minors of A_{W} corresponds to the k-tuple formed by arbitrary sized minors of B_{W}. Thus, evaluating linear forms at points of the affine open cell B_{α} of G_{ℓ,m} corresponds to evaluating linear forms in arbitrary sized minors of B_{W} at the points of the δ-dimensional affine space over 𝔽_{q}. In other words, the evaluation map Ev : G(ℓ, m) → 𝔸^{n} reduces to the evaluation map on F(ℓ, m) considered in Section 2.

Remark 33. We hope that the above discussion clarifies the genesis of the terminology affine Grassmann for the codes C^{𝔸}(ℓ, m) studied in this paper. Indeed, this terminology arises from the fact that in essence, we consider an affine open piece of the Grassmann variety instead of the full Grassmann variety. However, this terminology should not be confused with the so called affine Grassmannian, which is usually an infinite dimensional object obtained from the Laurent power series valued points of an algebraic group. Indeed, it appears unlikely that interesting and efficient codes could be built from the infinite dimensional affine Grassmannian, and hence there does not seem to be any harm in calling the codes C^{𝔸}(ℓ, m) as affine Grassmann codes.

It may be worthwhile to compare the basic parameters of C(ℓ, m) and C^{𝔸}(ℓ, m). This is done in Figure 1 below. While the results for C^{𝔸}(ℓ, m) are proved in the previous sections, those for C(ℓ, m) can be found, for example, in [13] and [6].

C(ℓ, m)  C^{𝔸}(ℓ, m)
Length  \left[{m \atop ℓ}\right]_{q} = q^{δ} + q^{δ−1} + 2q^{δ−2} + ⋯ q^{δ}

Dimension \binom{m}{ℓ}  \binom{m}{ℓ}

Minimum  q^{δ}  q^{δ−ℓ^{2}} ∏_{i=0}^{ℓ−1}(q^{ℓ} − q^{i})
distance  = q^{δ} − q^{δ−1} − q^{δ−2} + ⋯

Number of (q − 1)\left[{m \atop ℓ}\right]_{q}  (q − 1)q^{ℓ^{2}} \left[{m−ℓ \atop ℓ}\right]_{q}
min. weight = O(q^{δ+1}) = O(q^{δ+1})

codewords

Figure 1. A comparison of Grassmann and affine Grassmann codes

It may be noted that the two classes of codes are comparable. While the affine Grassmann codes are shorter than Grassmann codes and have a better rate, the Grassmann codes fare better in terms of the minimum distance and also the relative distance. In spite of the connection between the two codes indicated above, there does not seem to be a straightforward way to deduce the properties of one code directly from that of the other. However, the growing literature on Grassmann codes can provide pointers for further research on affine Grassmann codes, whereas the analogy of affine Grassmann codes with Reed-Muller codes and results obtained in this paper concerning their automorphisms may provide further impetus for the study of Grassmann codes.

Acknowledgments

The second named author would like to thank the Department of Mathematics of the Technical University of Denmark for its warm hospitality during his visits in June 2008 and April 2009 when some of this work was carried out.

References

[1] T. P. Berger and P. Charpin, “The automorphism group of generalized Reed-Muller codes”, Discrete Math., vol. 117, pp. 1–17, 1993.

[2] P. Delsarte, J. M. Goethals, and F. J. MacWilliams, “Generalized Reed-Muller codes and their relatives”, Inf. Control, vol.16, pp. 403–442, 1974.

[3] P. Doubilet, G. C. Rota, and J. Stein, “Foundations of Combinatorics IX: Combinatorial Methods in Invariant Theory”, Stud. Appl. Math., vol. 53, pp. 185–216, 1974.

[4] F.R. Gantmacher, The Theory of Matrices, vol. 1, New York: Chelsea, 1960.

[5] S. R. Ghorpade, “Abhyankar’s work on Young tableaux and some recent developments”, in Algebraic Geometry and its Applications (West Lafayette, 1990), New York: Springer-Verlag, 1994, pp. 233–265.

[6] S. R. Ghorpade and G. Lachaud, “Higher weights of Grassmann codes”, in Coding Theory, Cryptography and Related Areas (Guanajuato, 1998), Berlin/Heidelberg: Springer-Verlag, 2000, pp. 122–131.

[7] S. R. Ghorpade, A. R. Patil and H. K. Pillai, “Decomposable subspaces, linear sections of Grassmann varieties, and higher weights of Grassmann codes”, Finite Fields Appl., vol. 15, pp. 54–68, 2009.

[8] R. L. Graham, D. E. Knuth and O. Patashnik, Concrete Mathematics, Reading: Addison-Wesley, 1989.

[9] J. P. Hansen, T. Johnsen, and K. Ranestad, “Grassmann codes and Schubert unions”, in Arithmetic, Geometry and Coding Theory (Luminy, 2005), Séminaires et Congrès, vol. 21, Paris: Soc. Math. France, 2009, pp. 103–121.

[10] J.-R. Joly, “Équations et variétés algébraiques sur un corps fini”, Enseign. Math., vol. 19, pp. 1–117, 1973.

[11] R. Knörr and W. Willems, “The automorphism groups of generalized Reed-Muller codes”, Astérisque, vol. 181–182, pp. 195–207, 1990.

[12] F. J. MacWilliams and N. J. A. Sloane, The Theory of Error Correcting Codes, New York: Elsevier, 1977.

[13] D. Yu. Nogin, “Codes associated to Grassmannians”, in Arithmetic, Geometry and Coding Theory (Luminy, 1993), Berlin: Walter de Gruyter, 1996, pp. 145–154.

[14] V. Pless and W. C. Huffman (Eds.), Handbook of Coding Theory, Vols. I and II, Amsterdam: Elsevier, 1998.

Department of Mathematics, Technical University of Denmark, DK 2800, Lyngby, Denmark.

E-mail address: p.beelen@mat.dtu.dk

Department of Mathematics, Indian Institute of Technology Bombay, Powai, Mumbai 400076, India.

E-mail address: srg@math.iitb.ac.in

Department of Mathematics, Technical University of Denmark, DK 2800, Lyngby, Denmark.

E-mail address: T.Hoeholdt@mat.dtu.dk