arXiv:1609.08265v2 [] 15 Sep 2017

MINIMUM DISTANCE AND THE MINIMUM WEIGHT
CODEWORDS OF SCHUBERT CODES
SUDHIR R. GHORPADE AND PRASANT SINGH
Abstract. We consider linear codes associated to Schubert varieties in Grassmannians. A formula for the minimum distance of these codes was conjectured
in 2000 and after having been established in various special cases, it was proved
in 2008 by Xiang. We give an alternative proof of this formula. Further,
we propose a characterization of the minimum weight codewords of Schubert
codes by introducing the notion of Schubert decomposable elements of certain
exterior powers. It is shown that codewords corresponding to Schubert decomposable elements are of minimum weight and also that the converse is true
in many cases. A lower bound, and in some cases, an exact formula, for the
number of minimum weight codewords of Schubert codes is also given. From a
geometric point of view, these results correspond to determining the maximum
number of Fq -rational points that can lie on a hyperplane section of a Schubert
variety in a Grassmannian with its nondegenerate embedding in a projective
subspace of the Plücker projective space, and also the number of hyperplanes
for which the maximum is attained.

1. Introduction
Fix a prime power q and positive integers ℓ, m with ℓ ≤ m. Let Fq denote the
finite field with q elements and let V be a vector space over Fq of dimension m. To
the Grassmannian Gℓ,m of all ℓ-dimensional linear subspaces of V , one can associate
in a natural way an [n, k]q -code, i.e., a q-ary linear code of length n and dimension
k, where
 
 
m
m
(q m − 1)(q m − q) · · · (q m − q ℓ−1 )
and
k
=
.
(1)
n=
:=
(q ℓ − 1)(q ℓ − q) · · · (q ℓ − q ℓ−1 )
ℓ
ℓ q
This code is denoted by C(ℓ, m) and is called Grassmann code. The study of
Grassmann codes goes back to the work of Ryan [15, 16, 18] in the late 1980’s and
was continued by Nogin [13] and several authors (see, e.g., [6, 7, 10, 5, 2] and the
Date: September 18, 2017.
2010 Mathematics Subject Classification. 94B05, 94B27, 14M15, 14G50.
The first named author was partially supported by Indo-Russian project INT/RFBR/P114 from the Department of Science & Technology, Govt.
12IRAWD009 from IIT Bombay.

of India and IRCC Award grant

The second named author was partially supported by a doctoral fellowship from the Council
of Scientific and Industrial Research, India.
1

2

SUDHIR R. GHORPADE AND PRASANT SINGH

references therein). It is now known that Grassmann codes possess a number of
interesting properties. For instance, their minimum weight is known and is given
by the following beautiful formula of Nogin [13]:
(2)

d (C(ℓ, m)) = q δ

where δ := ℓ(m − ℓ).

Furthermore, several generalized Hamming weights are known, the automorphism
group has been determined and is known to be fairly large, the duals of Grassmann
codes have a very low minimum distance (namely, 3) and the minimum weight
codewords of C(ℓ, m)⊥ generate C(ℓ, m)⊥ . In fact, as the results of [2, 14] show,
Grassmann codes can be regarded as regular LDPC codes and also as a Tanner
codes with a small component code, namely, C(1, 2).
Schubert codes are a natural generalization of Grassmann codes and were introduced in [6] around the turn of the last century. These are linear codes Cα (ℓ, m)
associated to Schubert subvarieties Ωα (ℓ, m) of the Grassmannian Gℓ,m and are indexed by ℓ-tuples α = (α1 , . . . , αℓ ) of positive integers with 1 ≤ α1 < · · · < αℓ ≤ m.
The Grassmann codes are a special case where αi = m − ℓ + i for i = 1, . . . , ℓ. It
was shown in [6] that the minimum distance of Cα (ℓ, m) satisfies the inequality
(3)

d (Cα (ℓ, m)) ≤ q δ(α)

where

δ(α) :=

ℓ
X

(αi − i).

i=1

Further, it was conjectured in [6] that the inequality in (3) is, in fact, an equality.
We will refer to this conjecture as the Minimum Distance Conjecture, or in short,
the MDC. When αi = m − ℓ + i for i = 1, . . . , ℓ, we have δ(α) = δ and so the MDC
holds, thanks to (2). In the case ℓ = 2, the MDC was proved in the affirmative by
Chen [3] and, independently, by Guerra and Vincenti [9]. An explicit formula for
the length nα and dimension kα of Cα (ℓ, m) in the case ℓ = 2 was also given in [3],
while [9] gave a general, even if complicated, formula for nα for arbitrary ℓ. Later,
in [8], the MDC was established for Schubert divisors (i.e., in the case δ(α) = δ − 1)
and general formulas for nα and kα were obtained, namely,


X
αj − j + 1
δ(β)
(4)
nα =
q
and kα = det
,
1≤i,j≤ℓ
i−j+1
β≤α

where the above summation is over all ℓ-tuples β = (β1 , . . . , βℓ ) of integers satisfying
Pℓ
1 ≤ β1 < · · · < βℓ ≤ m and βi ≤ αi for i = 1, . . . , ℓ and δ(β) := i=1 (βi − i). An
affirmative answer to the MDC was eventually proposed by Xiang [19], where an
alternative proof of the inequality in (3) is given and a clever and rather involved
proof of the other inequality is also given. While one doesn’t doubt the veracity
of Xiang’s proof, it has been felt that a cleaner and more transparent proof of the
MDC would be desirable. With this in view, we give in this paper an alternative
coordinate-free argument to establish the MDC in the general case. Further, we
take up the problem of characterizing the minimum weight codewords of Schubert

MINIMUM WEIGHT CODEWORDS OF SCHUBERT CODES

3

codes and determining their number. In the case of Grassmann codes, there is a
nice characterization that was given already by Nogin [13]. To explain this, let
us note that the codewords of C(ℓ, m) are indexed by elements f of the exterior
Vℓ
V and may be denoted by cf . In fact, cf = (f ∧ P1 , . . . , f ∧ Pn ), where
power
V
P1 , . . . , Pn is a fixed set of representatives in m−ℓ V of (the Fq -rational points of)
Vm−ℓ
Gℓ,m . The map
V → C(ℓ, m) given by f 7→ cf is a linear bijection. The
characterization is simply that cf is a minimum weight codeword C(ℓ, m) if and
only if f is decomposable, i.e., f = f1 ∧ . . . ∧ fm−ℓ for some linearly independent
f1 , . . . , fm−ℓ ∈ V . The Schubert code Cα (ℓ, m) can be viewed as a puncturing of the
Grassmann code C(ℓ, m) at the complement of Ωα (ℓ, m) in Gℓ,m . The codewords of
Vm−ℓ
V and are given by (f ∧ P1 , . . . , f ∧ Pnα ),
Cα (ℓ, m) can still be indexed by f ∈
Vm−ℓ
V of (the Fq -rational
where P1 , . . . , Pnα is a fixed set of representatives in
points of) Ωα (ℓ, m); we will continue to denote these by cf . However, in general,
V
the map f 7→ cf of m−ℓ V → Cα (ℓ, m) is surjective, but not injective. This makes
the case of Schubert codes more difficult and a straightforward generalization of the
characterization of minimum weight codewords of Grassmann codes does not hold
for Schubert codes. It turns out that one needs here a stronger and more subtle
notion of decomposability that we call Schubert decomposability. We propose a
new conjecture that the minimum weight codewords of Cα (ℓ, m) are precisely those
Vm−ℓ
V . We prove several
that correspond to Schubert decomposable elements of
aspects of this conjecture. Thus we show that codewords indexed by Schubert
Vm−ℓ
V are minimum weight codewords of Cα (ℓ, m)
decomposable elements of
and we also show that if cf ∈ Cα (ℓ, m) is a minimum weight codeword for some
Vm−ℓ
decomposable f ∈
V , then f is Schubert decomposable. What remains to
be seen is whether every minimum weight codeword of Cα (ℓ, m) can be indexed by
Vm−ℓ
a decomposable element of
V . We show that this is indeed the case when
ℓ = 2 or when α is “completely non-consecutive”, i.e., when αi − αi−1 ≥ 2 for all
i = 1, . . . , ℓ. Thus, the new conjecture is established in these cases. We also give
an explicit lower bound for the number of minimum weight codewords of Cα (ℓ, m),
and observe that it gives the exact value if our new conjecture is true. Of course in
the completely non-consecutive case or when ℓ = 2, this becomes an unconditional
result. We also show that unlike Grassmann codes, the minimum weight codewords
of a Schubert code do not, in general, generate the code. On the other hand, one
knows from the recent work of Piñero [14] that the duals of Schubert codes have
the same low minimum distance as that of C(ℓ, m)⊥ and moreover, the minimum
weight codewords of Cα (ℓ, m)⊥ generate Cα (ℓ, m)⊥ .
The results of this paper have a geometric interpretation that may be of independent interest. Indeed, Ωα (ℓ, m) admits a nondegenerate embedding in Pkα −1 and
using the language of projective systems (see, e.g., [17, §1.1]), we see that determining the minimum distance d(Cα (ℓ, m)) is equivalent to determining the maximum

4

SUDHIR R. GHORPADE AND PRASANT SINGH

number of Fq -rational points in sections of Ωα (ℓ, m) by hyperplanes in Pkα −1 since
mα := max{|(Ωα (ℓ, m) ∩ H) (Fq )| : H hyperplane in Pkα −1 } = nα − d(Cα (ℓ, m)).
Furthermore, if Mα is the number of minimum weight codewords of Cα (ℓ, m), then

Mα = H : H hyperplane in Pkα −1 with |(Ωα (ℓ, m) ∩ H) (Fq )| = mα .
2. Preliminaries
In this section, we recall some basic notions and set the notations and terminology used in the rest of this paper. As in the Introduction, a prime power q and
integers ℓ, m with 1 ≤ ℓ ≤ m will be kept fixed throughout this paper. We have
frequently used the notation A := B to mean that A is defined to be equal to B.
2.1. Linear Codes. Let n, k be positive integers. By an [n, k]q -code we mean a
linear k-dimensional subspace of Fnq . Let C be an [n, k]q -code. The parameters n
and k are called the length and the dimension of C, respectively, whereas elements
of C are usually referred to as codewords. Given a codeword c = (c1 , . . . , cn ) of C,
the Hamming weight of c will be denoted by wt(c); this is simply the number of
i ∈ {1, . . . , n} for which ci 6= 0. The minimum distance of C is denoted by d(C)
and can be defined as min{wt(c) : c ∈ C with c 6= 0}. Elements c ∈ C satisfying
wt(c) = d(C) are called the minimum weight codewords of C.
2.2. Grassmann and Schubert Varieties. Let F be a field (later we will mainly
take F = Fq , but for now it can be an arbitrary field) and V be an m-dimensional
Vd
V denote the dth
vector space over F. For a nonnegative integer d, we let

exterior power of V ; this is a vector space over F of dimension m
. Fixing a basis
d
Vd
Vm
V with F. Also the dual ( V )∗ is canonically
of V , we can (and will) identify
Vm−d
Vd
identified with
V . An element f of
V is said to be decomposable if f 6= 0
Vd
and f = f1 ∧ · · · ∧ fd for some f1 , . . . , fd ∈ V . In general, elements of
V are
V
F-linear combinations of decomposable elements. The annihilator of any f ∈ d V
is the subspace of V denoted by Vf and defined by
Vf := {x ∈ V : f ∧ x = 0}.
Evidently, f = 0 if and only if dim Vf = m. Now suppose d < m. Then the
following characterization is well-known; see, e.g., [11, Thm. 1.1]:
(5)

f is decomposable ⇐⇒ dim Vf = d.

Note that if f is decomposable and f = f1 ∧ · · · ∧ fd , then {f1 , . . . , fd } is a basis of
Vf . And if {g1 , . . . , gd } is an arbitrary basis of Vf , then f = λ(g1 ∧ · · · ∧ gd ) where
λ ∈ F is a nonzero scalar given by the determinant of the change-of-basis matrix.
As in the Introduction, the Grassmannian Gℓ,m = Gℓ (V ) may be defined by
Gℓ,m := {L : L is a ℓ-dimensional subspace of V }.

MINIMUM WEIGHT CODEWORDS OF SCHUBERT CODES

5

Vℓ 
Elements of Gℓ,m can be identified with the points of the projective space P
V
via the Plücker embedding, which associates to a subspace L ∈ Gℓ,m with F-basis
Vℓ
{v1 , . . . , vℓ } the class [v1 ∧ . . . ∧ vℓ ] of v1 ∧ . . . ∧ vℓ ∈
V . It is well-known that this
is a well-defined embedding under which Gℓ,m corresponds to a projective algebraic
V 
variety in P ℓ V defined by the vanishing of certain quadratic homogeneous
polynomials with integer coefficients. Moreover, the embedding is nondegenerate,
V 
i.e., Gℓ,m is not contained in any hyperplane of P ℓ V . One can also view Gℓ,m
as a quotient of GLm (F). Indeed, the group GL(V ) of invertible linear maps of
V → V acts transitively on Gℓ,m and so Gℓ,m can be viewed as the homogeneous
space GL(V )/Pℓ , where Pℓ is the parabolic subgroup given by the stabilizer of a
fixed ℓ-dimensional subspace of V . As this indicates, Gℓ,m is a nonsingular variety
of dimension δ := ℓ(m−ℓ). When ℓ = m, the Grassmannian is a particularly simple
object, namely the singleton set {V }, or the projective space P0 consisting of a single
point. Thus, to avoid trivialities, we shall henceforth assume that 1 ≤ ℓ < m.
Now let us fix a partial flag A1 ⊂ · · · ⊂ Aℓ of nonzero subspaces of V . Let αi :=
dim Ai for i = 1, . . . , ℓ. We sometimes refer to α := (α1 , . . . , αℓ ) as the dimension
sequence of the partial flag A1 ⊂ · · · ⊂ Aℓ . Note that 1 ≤ α1 < · · · < αℓ ≤ m.
The Schubert variety corresponding to this partial flag depends essentially on the
dimension sequence α and is defined by
(6)

Ωα (ℓ, m) := {L ∈ Gℓ,m : dim(L ∩ Ai ) ≥ i for all i = 1, . . . , ℓ}.

With respect to the Plücker embedding of Gℓ,m , the Schubert variety Ωα (ℓ, m)
Vℓ 
V given by the intersection of Gℓ,m with a bunch
corresponds to a subset of P
of Plücker coordinate hyperplanes. As such Ωα (ℓ, m) is indeed a projective variety
that is known to be nondegenerately embedded in Pkα −1 , where kα is as in (4).
Note that the elements of Ωα (ℓ, m) are precisely those L ∈ Gℓ,m for which there is
a basis of the form {v1 , . . . , vℓ } with the property vi ∈ Ai for i = 1, . . . , ℓ. Thus,
Ωα (ℓ, m) = {[v1 ∧ . . . ∧ vℓ ] : v1 , . . . , vℓ ∈ V linearly independent and vi ∈ Ai ∀ i}.
We shall use either of the above two descriptions of Ωα (ℓ, m). Moreover, we shall
often reverse the order so as to write [v1 ∧ . . . ∧ vℓ ] as [vℓ ∧ . . . ∧ v1 ].
Now note that α can be divided into consecutive blocks as
α = (α1 , . . . , αp1 , αp1 +1 , . . . , αp2 , . . . , αpu−1 +1 , . . . , αpu , αpu +1 , . . . , αℓ )
so that 1 ≤ p1 < · · · < pu < ℓ and αpi +1 , . . . , αpi+1 are consecutive for 0 ≤ i ≤ u,
where p0 = 0 and pu+1 = ℓ, by convention. If we further require that αpi +1 −αpi ≥ 2
for i = 1, . . . , u, then the nonnegative integer u and the “jump spots” p1 , . . . , pu
are uniquely determined by α. For example, if ℓ = 7 and α = (1, 2, 4, 5, 6, 8, 10),
then u = 3 and (p1 , p2 , p3 ) = (2, 5, 6). It is an easy consequence of the dimension
formula (see, e.g., [8, Lemma 2]) that if the dimension condition in (6) holds at the

6

SUDHIR R. GHORPADE AND PRASANT SINGH

“jump spots”, then it holds everywhere else; in other words,
(7)

Ωα (ℓ, m) = {L ∈ Gℓ (Aℓ ) : dim(L ∩ Api ) ≥ pi for all i = 1, . . . , u}.

Hereafter, u and p0 , p1 , . . . , pu , pu+1 will denote the unique integers satisfying
(8) p0 := 0 < p1 < · · · < pu < pu+1 := ℓ,

and αpi +1 − αpi ≥ 2 for 1 ≤ i ≤ u,

and moreover, αpi−1 +1 , . . . , αpi are consecutive for 1 ≤ i ≤ u + 1, that is,
αpi −j = αpi − j

(9)

for 1 ≤ i ≤ u + 1 and 1 ≤ j < pi − pi−1 .

In particular, if α is completely consecutive, i.e., if u = 0, then (7) shows that
Ωα (ℓ, m) coincides with the Grassmannian Gℓ (Aℓ ) of all ℓ-dimensional subspaces of
Aℓ . The other extreme is u = ℓ − 1, which means αi+1 − αi ≥ 2 for i = 1, . . . , ℓ − 1,
and we will refer to such α as completely non-consecutive. We now define a notion
that will play an important role in the sequel.
Vm−ℓ
Definition 2.1. An element f of
V is said to be Schubert decomposable
(with respect to the Schubert variety Ωα (ℓ, m)) if f is decomposable, i.e., f 6= 0
and f = f1 ∧ · · · ∧ fm−ℓ for some f1 , . . . , fm−ℓ ∈ V , and moreover,
dim(Vf ∩ Api ) = αpi − pi

(10)

for all i = 1, . . . , u.

Note that if α is completely consecutive, then u = 0 and condition (10) is
vacuously true. Thus, in this case the notions of decomposable and Schubert decomposable elements are identical. However, in general, a decomposable element
need not be Schubert decomposable.
2.3. Grassmann Codes and Schubert Codes. Here, and hereafter, we will
assume that the base field F is the finite field Fq . Then Gℓ,m and Ωα (ℓ, m) are
finite and the number of (Fq -rational) points in these varieties are n and nα , which
were given explicitly in (1) and (4), respectively. Fix an ordering L1 , . . . , Lnα of
Vℓ
V such that each Pi
the elements of Ωα (ℓ, m) and representatives P1 , . . . , Pnα in
is a decomposable element of the form vℓ ∧ · · · ∧ v1 with vi ∈ Ai for all i = 1, . . . , ℓ
and Lj = VPj for j = 1, . . . , nα . The choice we make here of ordering vi in the
descending order in i is merely a matter of convenience and will be found suitable
when we use induction on ℓ. Needless to say, the element vℓ ∧ · · · ∧ v1 differs only
in sign from v1 ∧ · · · ∧ vℓ . At any rate, we have a natural evaluation map
(11)

m−ℓ
^

V → Fnq α

defined by

f 7→ cf ,

where

cf := (f ∧ P1 , . . . , f ∧ Pnα ) .

The Schubert code Cα (ℓ, m) is defined as the image of this evaluation map. The
Grassmann code C(ℓ, m) is a special case when αi = m − ℓ + i for i = 1, . . . , ℓ.
Note that a different choice of representatives results in a code that is monomially
Vm−ℓ
equivalent to Cα (ℓ, m). With this in view, given any f ∈
V , instead of f ∧ Pi
we shall often write f ∧ Li or f (Li ). This is an abuse of notation, but perfectly

MINIMUM WEIGHT CODEWORDS OF SCHUBERT CODES

7

unambiguous when we are only interested in the vanishing or nonvanishing of the
scalar f (Li ). This, for instance, is the case in the definition of the support of f :
(12)

W (f ) := {L ∈ Ωα (ℓ, m) : f (L) 6= 0}.

It is clear that the cardinality of W (f ) is wt(cf ), i.e., the Hamming weight of the
codeword cf of Cα (ℓ, m). In particular,
(13)

d(Cα (ℓ, m)) = min{|W (f )| : f ∈

m−ℓ
^

V and W (f ) is nonempty},

where for any finite set S, we let |S| denote the cardinality of S.
Vm−ℓ
We note that (11) gives a surjective map of
V onto Cα (ℓ, m), but this map

is, in general, not injective. In fact, its kernel is of dimension m
ℓ − kα , where kα
is as in (1). Moreover, from an alternative expression for kα given in [8, eq. (4)], it

is readily seen that kα < m
ℓ if and only if Ωα (ℓ, m) 6= Gℓ,m . Note also that
(14)

f ∧ L = 0 if f ∈

m−ℓ
^

V and L ∈ Ωα (ℓ, m) are such that Vf ∩ L 6= {0}.

This easily verifiable observation can be used tacitly in the sequel.
3. Minimum distance of Schubert Codes
For the remainder of this paper, fix a prime power q, positive integers ℓ, m with
ℓ < m and an m-dimensional vector space V over Fq . Also, let us fix a partial flag
A1 ⊂ · · · ⊂ Aℓ of nonzero subspaces of V and let α = (α1 , . . . , αℓ ) be its dimension
sequence. For any integer j, we set Aj := {0} if j ≤ 0 and Aj := V if j > ℓ, by
convention. Given any v1 , . . . , vr ∈ V , we shall denote by hv1 , . . . , vr i the linear
subspace of V generated by v1 , . . . , vr . Likewise, if L′ is a subspace of V and v ∈ V ,
then by hL′ , vi we denote the subspace of V generated by v and the elements of L′ .
Given a finite dimensional vector space W , a subspace of W of dimension dim W −1
may be referred to as a hyperplane in W . We shall use the notation and terminology
Vm−ℓ
introduced in the previous section. In particular, given any f ∈
V , we denote
by cf the corresponding codeword in the Schubert code Cα (ℓ, m).
In case ℓ > 1, we will denote by α′ the (ℓ − 1)-tuple (α1 , . . . , αℓ−1 ), which is the
dimension sequence of the truncated partial flag A1 ⊂ · · · ⊂ Aℓ−1 . Moreover, when
Vm−ℓ
ℓ > 1 and f ∈
V is given, we put
E := {x ∈ Aℓ : cf ∧x is the zero codeword in Cα′ (ℓ − 1, m)}

and F := Aℓ \ E.

It is clear that E is a subspace of Aℓ . Naturally, E and F depend on f and to make
this dependence explicit, we could denote them by Ef and Ff . However, in most
V
situations there will be a fixed f ∈ m−ℓ V , and we will drop the subscript so as to
simply write E and F . The following lemma is a simple, but crucial, observation
made by Xiang [19]. We include a proof for the sake of completeness.

8

SUDHIR R. GHORPADE AND PRASANT SINGH

Vm−ℓ
Lemma 3.1. Assume that ℓ > 1 and f ∈
V is given. Let E be as above and
let t be a nonnegative integer such that codimAℓ E ≤ t. Then Aℓ−t ⊆ E.
Proof. If t = 0 or t ≥ ℓ, then the result holds trivially. Thus, assume that 1 ≤ t < ℓ.
Suppose, on the contrary, there is some x ∈ Aℓ−t \ E. Then there are xi ∈ Ai for
1 ≤ i ≤ ℓ − 1 such that
(15)

f ∧ x ∧ xℓ−1 ∧ · · · ∧ x1 6= 0.

In particular, x, xℓ−t , . . . , xℓ−1 are linearly independent. Now if y is any nonzero
element of hx, xℓ−t , . . . , xℓ−1 i, then we can replace x or some xj (ℓ − t ≤ j ≤ ℓ − 1)
by y to obtain a basis of hx, xℓ−t , . . . , xℓ−1 i consisting of y and all except one among
x, xℓ−t , . . . , xℓ−1 . So it follows from (15) that f ∧ y ∧ yℓ−1 ∧ · · · ∧ y1 6= 0 for some
yi ∈ Ai (1 ≤ i ≤ ℓ − 1). Consequently, y 6∈ E. Thus E ∩ hx, xℓ−t , . . . , xℓ−1 i = {0}.
Hence, dim E ≤ αℓ − t − 1, i.e., codimAℓ E ≥ t + 1, which is a contradiction.

Corollary 3.2. If codimAℓ E = 1, then L 6⊆ Aℓ−1 for every L ∈ W (f ).
Proof. Suppose, if possible, there is L ∈ W (f ) such that L ⊆ Aℓ−1 . Then L ⊆ E, by
Lemma 3.1. However, since L ∈ W (f ), there is x ∈ L and L′ ∈ Ωα′ (ℓ − 1, m) such
that L = L′ +hxi and (f ∧x)(L′ ) 6= 0. But then x 6∈ E, which is a contradiction. 
The next lemma is also due to Xiang [19]. We give a coordinate-free proof.
Vm−ℓ
Lemma 3.3. Assume that ℓ > 1 and f ∈
V is given. Let α′ and E be as
defined above. Also, let
Z(α′ , f ) = {(L′ , x) ∈ Ωα′ (ℓ − 1, m) × Aℓ : (f ∧ x)(L′ ) 6= 0}
and let φ : Z(α′ , f ) −→ W (f ) be the map given by (L′ , x) →
7 hL′ , xi. Then φ is
well-defined and surjective. Moreover, given any L ∈ W (f ), the following holds.
(i) If L 6⊆ Aℓ−1 then |φ−1 (L)| = q ℓ−1 (q − 1).
(ii) If L ⊆ Aℓ−1 and if t := codimAℓ E, then |φ−1 (L)| ≤ q ℓ−1 (q t − 1).
Proof. It is clear that φ is well-defined (i.e., hL′ , xi ∈ W (f ) whenever (L′ , x) is in
Z(α′ , f )) and that φ is surjective. Now let L ∈ W (f ).
(i) Suppose L 6⊆ Aℓ−1 . Since L ∈ Ωα (ℓ, m), we see that dim(L ∩ Aℓ−1 ) = ℓ − 1.
Now if (L′ , x) ∈ φ−1 (L), then L′ is an (ℓ − 1)-dimensional subspace of L ∩ Aℓ−1 and
hence L′ = L ∩ Aℓ−1 . On the other hand, x can be an arbitrary element of L \ L′ .
Thus φ−1 (L) = q ℓ − q ℓ−1 = q ℓ−1 (q − 1).
(ii) Suppose L ⊆ Aℓ−1 and t := codimAℓ E. Let (L′ , x) ∈ φ−1 (L). Observe that
(16)

L′ ∩ Aℓ−t = L ∩ Aℓ−t .

Indeed, the inclusion ⊆ is obvious, whereas if there exists u ∈ (L ∩ Aℓ−t ) \ L′ , then
L = hL′ , ui and by Lemma 3.1, u ∈ E, which implies that (f ∧ u)(L′ ) = 0 and
hence f (L) = 0, which contradicts the assumption that L ∈ W (f ).

MINIMUM WEIGHT CODEWORDS OF SCHUBERT CODES

9

Now let Lt := L ∩ Aℓ−t . From (16), we see that L′ is necessarily a hyperplane
in L containing Lt . The number of such hyperplanes is equal to the number of
hyperplanes in L/Lt . Thus if r := dim Lt and N ′ := (q ℓ−r − 1)/(q − 1), then we see
that there are at most N ′ choices for L′ . Note that since L ∈ Ωα (ℓ, m), we have
r ≥ ℓ−t and hence N ′ ≤ (q t −1)/(q−1). Moreover, x has to be in L\L′ and so there
are at most q ℓ − q ℓ−1 possibilities for x. It follows that |φ−1 (L)| ≤ q ℓ−1 (q t − 1). 
Vm−ℓ
V be such that cf 6= 0 and let E
Lemma 3.4. Assume that ℓ > 1. Let f ∈
and F be the corresponding sets as defined above. Also, let t := codimAℓ E. Then
X
X
1
1
wt(cf ∧x ) + ℓ−1 t
wt(cf ∧x ).
(17) wt(cf ) ≥ ℓ−1
q (q − 1)
q (q − 1)
x∈F ∩Aℓ−1

x∈F \Aℓ−1

Moreover, the inequality above is strict if the inequality in part (ii) of Lemma 3.3
is strict for some L ∈ W (f ) with L ⊆ Aℓ−1 .
Proof. Let α′ , Z(α′ , f ), and φ : Z(α′ , f ) −→ W (f ) be as in Lemma 3.3. Then
X
X
X
|φ−1 (L)|.
|φ−1 (L)| +
|φ−1 (L)| =
|Z(α′ , f )| =
L∈W (f )
L*Aℓ−1

L∈W (f )

L∈W (f )
L⊆Aℓ−1

On the other hand, considering the fibres of the projection Z(α′ , f ) → F , we obtain
X
X
X
|Z(α′ , f )| =
wt(cf ∧x ) =
wt(cf ∧x ) +
wt(cf ∧x ).
x∈F

x∈F \Aℓ−1

x∈F ∩Aℓ−1

′

Now observe that for any L ∈ Ωα′ (ℓ − 1, m) and x ∈ Aℓ , we have
L′ + hxi ∈ W (f ) and L′ + hxi * Aℓ−1 ⇐⇒ x ∈ F \ Aℓ−1 and L′ ∈ W (f ∧ x).
This implies the first equality below, which in turn, yields the second inequality.
X
X
X
X
|φ−1 (L)| =
wt(cf ∧x ).
|φ−1 (L)| =
wt(cf ∧x ) and
L∈W (f )

x∈F \Aℓ−1

L*Aℓ−1

L∈W (f )
L⊆Aℓ−1

x∈F ∩Aℓ−1

Hence, if we let θ1 := |{L ∈ W (f ) : L * Aℓ−1 }| and θ2 := |{L ∈ W (f ) : L ⊆ Aℓ−1 }|,
then wt(cf ) = θ1 + θ2 and from Lemma 3.3, we see that
X
X
wt(cf ∧x ) = θ1 q ℓ−1 (q − 1) and
wt(cf ∧x ) ≤ θ2 q ℓ−1 (q t − 1).
x∈F \Aℓ−1

x∈F ∩Aℓ−1

This implies (17). Moreover, if |φ−1 (L)| < q ℓ−1 (q t − 1) for some L ∈ W (f ) with
L ⊆ Aℓ−1 , then it is clear that the inequality in (17) is strict.

For ease of reference, we state the following result for which a short proof is given
in [6, Prop. 5.2], while an alternative proof is given in [19, Thm. 1]. Yet another
proof will be sketched in Remark 5.4.
Proposition 3.5. d(Cα (ℓ, m)) ≤ q δ(α) .

10

SUDHIR R. GHORPADE AND PRASANT SINGH

We are now ready to show that the MDC holds in the affirmative, in general.
We shall also see that the proof also gives us some information about the minimum
weight codewords of Cα (ℓ, m).
V
Theorem 3.6. d(Cα (ℓ, m)) = q δ(α) . Moreover, if ℓ > 1 and f ∈ m−ℓ V is such
that cf is a minimum weight codeword in Cα (ℓ, m), then cf ∧x is a minimum weight
codeword in Cα′ (ℓ − 1, m) for every x ∈ F and furthermore, we must have either (i)
t = 1 and t′ = 0, or (ii) t′ = t ≥ 2, αℓ − αℓ−1 = 1, and equality holds in (17). Here
α′ , E and F are as before, while t := codimAℓ E and t′ := codimAℓ−1 (E ∩ Aℓ−1 ).
Proof. In view of Proposition 3.5, in order to show that d(Cα (ℓ, m)) = q δ(α) , it
suffices to show that
(18)

wt(cf ) ≥ q δ(α)

for every f ∈

m−ℓ
^

V such that cf 6= 0.

We now proceed to prove (18) by induction on ℓ (1 ≤ ℓ < m). The initial case can
be deduced from facts about Grassmann codes or first order projective Reed-Muller
codes, but we will give a direct and self-contained proof. The induction step will
make use of the above lemma.
V
First, suppose ℓ = 1 and f ∈ m−ℓ V . Then f is necessarily decomposable, say
f = f1 ∧ · · · ∧ fm−1 for some f1 , . . . , fm−1 ∈ V . Further, suppose cf 6= 0. Then
we must have A1 * Vf = hf1 , . . . , fm−1 i. Consequently, A1 + Vf = V and hence
dim A1 ∩ Vf = α1 − 1. Noting that W (f ) = {hxi : x ∈ A1 \ (A1 ∩ Vf )}, we obtain
wt(cf ) = |W (f )| =

q α1 − q α1 −1
= q α1 −1 = q δ(α) .
q−1

Next, suppose 1 < ℓ < m and (18) holds for positive values of ℓ smaller than the
given one. Note that t ≥ 1 since cf 6= 0. Note also that t′ := codimAℓ−1 (E ∩ Aℓ−1 )
satisfies t′ ≤ t since the inclusion Aℓ−1 ֒→ Aℓ induces an injective homomorphism
Aℓ−1 /E ∩ Aℓ−1 ֒→ Aℓ /E. We shall now divide the proof into two cases.
Case 1. t = 1.
In this case, by Lemma 3.1, Aℓ−1 ⊆ E. Hence F \ Aℓ−1 = F and F ∩ Aℓ−1 = ∅.
It follows that |F \ Aℓ−1 | = |F | = |Aℓ | − |E| = q αℓ − q αℓ −1 . Moreover, by the
′
induction hypothesis, wt(cf ∧x ) ≥ q δ(α ) , for every x ∈ F . Now (17) reduces to
X
′
1
1
(q αℓ − q αℓ −1 )q δ(α ) = q δ(α) .
wt(cf ∧x ) ≥ ℓ−1
wt(cf ) ≥ ℓ−1
q (q − 1)
q (q − 1)
x∈F

′

Thus, (18) is proved in this case. Also, it is clear that if wt(cf ∧x ) > q δ(α ) for some
x ∈ F , then wt(cf ) > q δ(α) . Note also that t′ = 0 in this case, since Aℓ−1 ⊆ E.
Case 2. t ≥ 2.
First note that, with t and t′ as above,

′
|F \Aℓ−1 | = (|Aℓ | − |E|)−(|Aℓ−1 | − |E ∩ Aℓ−1 |) = q αℓ − q αℓ −t − q αℓ−1 −q αℓ−1 −t .

MINIMUM WEIGHT CODEWORDS OF SCHUBERT CODES

11

We will now consider three different subcases as follows.
Subcase 2.1. αℓ − αℓ−1 ≥ 2.
Here, using the expression for |F \ Aℓ−1 | obtained above, we see that


′
|F \ Aℓ−1 | − q αℓ − q αℓ −1 = q αℓ −1 − q αℓ −t − q αℓ−1 + q αℓ −t > 0,

where the last inequality follows by noting that q αℓ −1 ≥ 2q αℓ −2 ≥ q αℓ −t + q αℓ−1 ,
since t ≥ 2 and αℓ − αℓ−1 ≥ 2. Hence, by (17) and the induction hypothesis,
wt(cf ) ≥

′
′
1
1
|F \ Aℓ−1 | q δ(α ) > ℓ−1
(q αℓ − q αℓ −1 )q δ(α ) = q δ(α) .
q ℓ−1 (q − 1)
q (q − 1)

Thus, we obtain (18) with, in fact, a strict inequality.
Subcase 2.2. αℓ − αℓ−1 = 1 and t′ 6= t.
Here, t′ ≤ t − 1 and so using the expression for |F \ Aℓ−1 | obtained earlier, we


′
see that |F \ Aℓ−1 | − q αℓ − q αℓ −1 = q αℓ −1−t − q αℓ −t ≥ 0, and also that strict
inequality holds when t′ = 0. Hence, by (17) and the induction hypothesis,
wt(cf ) >

1
q ℓ−1 (q

′

− 1)

(q αℓ − q αℓ −1 )q δ(α ) = q δ(α) ,

where the above inequality is strict either because t′ > 0 in which case the second
summation in (17) is nonempty and contributes a positive term or because t′ = 0

in which case |F \ Aℓ−1 | > q αℓ − q αℓ −1 . This yields (18), with a strict inequality.
Subcase 2.3. αℓ − αℓ−1 = 1 and t′ = t.
In this subcase of Case 2, we readily see that

|F \ Aℓ−1 | = q αℓ −t−1 (q t − 1)(q − 1) and |F ∩ Aℓ−1 | = q αℓ −t−1 (q t − 1).
Hence, from (17) and the induction hypothesis, we obtain
wt(cf ) ≥

q αℓ −t−1 (q t − 1) δ(α′ ) q αℓ −t−1 δ(α′ )
q
+
q
= q δ(α) .
q ℓ−1
q ℓ−1
′

Also, it is clear that if wt(cf ∧x ) > q δ(α ) for some x ∈ F or if the inequality in (17)
is strict, then wt(cf ) > q δ(α) .
Thus, (18) is proved in all cases. Hence, by induction on ℓ we conclude that
d(Cα (ℓ, m)) = q δ(α) . The remaining assertions in the statement of the theorem are
also clear from the proof.

4. Annihilators of Decomposable Elements
Now that we know the minimum distance of Schubert codes, it is natural to
ask for a classification as well as enumeration of the minimum weight codewords.
In this section, we shall take some preliminary steps towards such a classification
Vm−ℓ
by analysing the intersections of annihilators of decomposable elements of
V
with the constituent subspaces of the partial flag defining the given Schubert variety.
As in Section 3, integers ℓ, m with 1 ≤ ℓ < m, an m-dimensional vector space
V over Fq , a partial flag A1 ⊂ · · · ⊂ Aℓ of nonzero subspaces of V with dimension

12

SUDHIR R. GHORPADE AND PRASANT SINGH

sequence α = (α1 , . . . , αℓ ) will be kept fixed throughout this section. Also, recall
Vm−ℓ
V , by Vf we denote the annihilator of f .
(from §2.2) that for any f ∈
Vm−ℓ
Lemma 4.1. Suppose f ∈
V is a decomposable element with cf 6= 0. Then
αi − ℓ ≤ dim(Vf ∩ Ai ) ≤ αi − i

for all i = 1, . . . , ℓ.

In particular, dim(Vf ∩ Aℓ ) = αℓ − ℓ.
Proof. Since f is decomposable, dim Vf = m − ℓ. Hence, for 1 ≤ i ≤ ℓ,
m ≥ dim(Vf + Ai ) = dim(Vf )+ dim(Ai )− dim(Vf ∩Ai ) = m− ℓ + αi − dim(Vf ∩Ai ),
and thus dim(Vf ∩ Ai ) ≥ αi − ℓ. Further, since cf 6= 0, there are xj ∈ Aj for
j = 1, . . . , ℓ such that f ∧ xℓ ∧ . . . ∧ x1 6= 0. Consequently, for each i = 1, . . . , ℓ,
there are linearly independent x1 , . . . , xi ∈ Ai such that f ∧ xi ∧ . . . ∧ x1 6= 0 and
therefore Vf ∩ hx1 , . . . , xi i = {0}. This implies that dim(Vf ∩ Ai ) ≤ αi − i.

It turns out that the attainment of the upper bound given in Lemma 4.1 for
dim(Vf ∩ Ai ) has a nice characterization when i = ℓ − 1.
Vm−ℓ
V be a decomposable element with
Lemma 4.2. Assume that ℓ > 1. Let f ∈
cf 6= 0, and E the corresponding subspace as in §3. Then:
dim(Vf ∩ Aℓ−1 ) = αℓ−1 − (ℓ − 1) ⇐⇒ codimAℓ E = 1.
Proof. Since cf 6= 0, there are xi ∈ Ai for 1 ≤ i ≤ ℓ such that f ∧ (xℓ ∧ . . . ∧ x1 ) 6= 0.
Consequently, Vf ∩ hx1 , . . . , xℓ i = {0} and xℓ 6∈ E. In particular, E 6= Aℓ .
Suppose dim(Vf ∩Aℓ−1 ) = αℓ−1 −(ℓ−1). Observe that x1 , . . . , xℓ−1 ∈ E. Indeed,
if xi ∈
/ E for some i ≤ ℓ − 1, then there exist yj ∈ Aj for j = 1, . . . , ℓ − 1 such
that (f ∧ xi ) ∧ (yℓ−1 ∧ . . . ∧ y1 ) 6= 0; consequently, hxi , y1 , . . . , yℓ−1 i is a subspace
of Aℓ−1 of dimension ℓ such that Vf ∩ hxi , y1 , . . . , yℓ−1 i = {0}, and this yields a
contradiction. It follows that (Vf ∩ Aℓ ) + hx1 , . . . , xℓ−1 i is an (αℓ − 1)-dimensional
subspace of E. Since E 6= Aℓ , we conclude that codimAℓ E = 1.
Conversely, suppose codimAℓ E = 1. Note that dim(Vf ∩ Aℓ−1 ) ≤ αℓ−1 − (ℓ − 1),
thanks to Lemma 4.1. In case dim(Vf ∩Aℓ−1 ) < αℓ−1 −(ℓ−1), there exists yℓ ∈ Aℓ−1
such that yℓ 6∈ (Vf ∩ Aℓ−1 ) + hx1 , . . . , xℓ−1 i. Clearly, f ∧ (yℓ ∧ xℓ−1 ∧ . . . ∧ x1 ) 6= 0.
It follows that xℓ−1 and yℓ are linearly independent elements of Aℓ−1 and neither of
them is in E. Changing xℓ−1 ∧yℓ to xℓ−1 ∧z or z ∧yℓ for any nonzero z ∈ hxℓ−1 , yℓ i,
we see that hxℓ−1 , yℓ i∩E = {0}, and so codimAℓ E > 1, which is a contradiction. 
5. Schubert Decomposability and Minimum Weight Codewords
We will continue to use the notation and terminology of the previous two sections.
For the dimension sequence α = (α1 , . . . , αℓ ) of the fixed partial flag A1 ⊂ · · · ⊂ Aℓ ,
we let u and p0 , p1 , . . . , pu , pu+1 denote the unique integers satisfying (8) and (9).
Vm−ℓ
V is said to be Schubert decomposable (w.r.t. Ωα (ℓ, m)) if
Recall that f ∈

MINIMUM WEIGHT CODEWORDS OF SCHUBERT CODES

13

dim(Vf ∩ Api ) = αpi − pi for i = 1, . . . , u. Note that this equality for dimension
also holds for i = u + 1, thanks to Lemma 4.1.
We shall now proceed to relate Schubert decomposability with the minimum
weight codewords of Cα (ℓ, m). We begin with a simple and basic observation.
Vm−ℓ
Lemma 5.1. Let f ∈
V be Schubert decomposable. Then cf is nonzero.
Proof. Since dim(Vf ∩ Ap1 ) = αp1 − p1 , by extending a basis of Vf ∩ Ap1 to Ap1 , we
can find a p1 -dimensional subspace L1 of Ap1 such that L1 ∩ Vf = {0}. Now since
α1 , . . . , αp1 are consecutive, we see that
dim(L1 ∩ Ap1 −j ) ≥ dim(L1 ∩ Ap1 −j+1 ) − 1

for each 1 ≤ j < p1

and this implies that dim(L1 ∩ Ai ) ≥ i for i = 1, . . . , p1 . Hence, we can choose
xi ∈ Ai for i = 1, . . . , p1 such that {x1 , . . . , xp1 } forms a basis of L1 . Next, observe
that dim(Vf ∩Ap2 )+L1 = αp2 −p2 +p1 . Now since αp1 +1 , . . . , αp2 are consecutive, by
arguing as before, we can find xi ∈ Ai for i = p1 + 1, . . . , p2 such that {x1 , . . . , xp2 }
forms a basis of a p2 -dimensional subspace L2 of Ap2 such that L2 ∩ Vf = {0} and
L1 ⊂ L2 . Continuing in this manner, we obtain linearly independent x1 , . . . , xℓ ∈ V
such that xi ∈ Ai for i = 1, . . . , ℓ and Vf ∩ hx1 , . . . , xℓ i = {0}. Consequently,
L := [x1 ∧ · · · ∧ xℓ ] is in Ωα (ℓ, m) and since f is decomposable, we must have
f (L) 6= 0. Thus, cf 6= 0.

Our next result is a refined version of Lemma 3.3 with an additional hypothesis
of Schubert decomposability.
V
Lemma 5.2. Assume that ℓ > 1 and f ∈ m−ℓ V is Schubert decomposable. Let
α′ , E, Z(α′ , f ) and φ : Z(α′ , f ) −→ W (f ) be as in Lemma 3.3, and t := codimAℓ E.
Then t = 1 or t = ℓ − pu . Moreover,
(19)

|φ−1 (L)| = q ℓ−1 (q t − 1)

for every L ∈ W (f ).

Proof. If t = 1, then (19) follows from Corollary 3.2 and part (i) of Lemma 3.3. Now
suppose t > 1. Then from Lemma 4.1 and 4.2, we obtain dim(Vf ∩Aℓ−1 ) = αℓ−1 −ℓ.
Now pu ≤ ℓ−1, and if we had pu = ℓ−1, then dim(Vf ∩Apu ) = αℓ−1 −ℓ < αpu −pu ,
which contradicts that f is Schubert decomposable. So we must have pu < ℓ − 1.
Moreover, since αpu +1 , . . . , αℓ−1 are consecutive, if for some j with pu +1 ≤ j ≤ ℓ−1,
we had dim(Vf ∩ Aj ) ≥ αj − j, then we would obtain
dim(Vf ∩ Aℓ−1 ) ≥ αj − j = αℓ−1 − (ℓ − 1 − j) − j = αℓ−1 − (ℓ − 1),
which is a contradiction. Thus, for each j = pu + 1, . . . , ℓ − 1, we have
(20) dim(Vf ∩Aj ) < αj − j, and in particular, dim(Vf ∩Apu +1 ) ≤ αpu +1 − pu − 2.
Now since dim(Vf ∩ Api ) = αpi − pi for i = 1, . . . , u, by arguing as in the proof
of Lemma 5.1, we obtain linearly independent elements x1 , . . . , xpu ∈ V such that
Vf ∩ hx1 , . . . , xpu i = {0} and hx1 , . . . , xpi i ⊆ Api for each i = 1, . . . , u. Hence

14

SUDHIR R. GHORPADE AND PRASANT SINGH

the sum (Vf ∩ Apu +1 ) + hx1 , . . . , xpu i is a subspace of Apu +1 (as well as Aℓ−1 )
of dimension ≤ αpu +1 − 2, and so we can find y1 , y2 in Apu +1 and y3 , . . . , yℓ−pu in
Aℓ−1 such that x1 , . . . , xpu , y1 , y2 , . . . , yℓ−pu are linearly independent and moreover,
Vf ∩ hx1 , . . . , xpu , y1 , y2 , . . . , yℓ−pu i = {0}. Since f is decomposable, it follows that
f ∧ x1 ∧ · · · ∧ xpu ∧ y1 ∧ · · · ∧ yℓ−pu 6= 0. Consequently, y1 ∈ Apu +1 \ E and so
Apu +1 * E. Hence from Lemma 3.1, we see that codimAℓ E > ℓ − (pu + 1), i.e.,
codimAℓ E ≥ ℓ − pu . We will now proceed to show that codimAℓ E = ℓ − pu .
To this end, observe that Apu ⊆ E. Indeed, if there exists x ∈ Apu \ E, then
f ∧ x ∧ z1 ∧ · · · ∧ zℓ−1 6= 0 for some zi ∈ Ai (1 ≤ i ≤ ℓ − 1). In particular,
f ∧ x ∧ z1 ∧ · · · ∧ zpu 6= 0, and hence Vf ∩ hx, z1 , . . . , zpu i = {0}. This implies that
dim(Vf ∩ Apu ) ≤ αpu − pu − 1, which contradicts the assumption that f is Schubert
decomposable. Thus, Apu ⊆ E and hence (Vf ∩ Aℓ ) + Apu ⊆ E. Consequently,
(αℓ − ℓ) + αpu − (αpu − pu ) ≤ dim E,

that is,

codimAℓ E ≤ ℓ − pu .

Thus, we have proved that t = ℓ − pu .
Now fix any L ∈ W (f ). Then L ∈ Ωα (ℓ, m) with f (L) 6= 0. Note that L ⊆ Aℓ .
Let Lt := L ∩ Aℓ−t = L ∩ Apu . Observe that dim Lt ≥ pu , since L ∈ Ωα (ℓ, m).
Also, since L ∩ Vf = {0}, we see that (Vf ∩ Apu ) ∩ Lt = {0}. Hence, the Schubert
decomposability of f implies that αpu − pu + dim Lt ≤ αpu , i.e., dim Lt ≤ pu . Thus
dim Lt = pu . Next, we claim that for any L′ ∈ Gℓ−1 (V ) and x ∈ Aℓ ,
(L′ , x) ∈ φ−1 (L) ⇐⇒ L′ is a hyperplane in L containing Lt and x ∈ L \ L′ .
The implication ⇒ is clear because we have seen in the proof of Lemma 3.3 that if
(L′ , x) ∈ φ−1 (L), then L′ ∩ Aℓ−t = Lt . For the other implication, suppose L′ is a
hyperplane in L and x ∈ L \ L′ . Then it is clear that L = hL′ , xi. Further, suppose
Lt ⊆ L′ . Now since ℓ − t = pu ≥ pi for i = 1, . . . , u, we find
L ∩ Apu = Lt ⊆ L′ =⇒ L ∩ Apu = L′ ∩ Apu =⇒ L ∩ Api = L′ ∩ Api for i = 1, . . . , u.
Hence in view of (7), we see that L′ ∈ Ωα′ (ℓ − 1, m) and thus the claim is proved.
As a consequence, we see that |φ−1 (L)| = N ′ (q ℓ − q ℓ−1 ), where N ′ is exactly the
number of hyperplanes in L containing Lt . Now N ′ = (q ℓ−(ℓ−t) − 1)/(q − 1), exactly
as in the proof of Lemma 3.3. This yields the desired formula for |φ−1 (L)|.

Vm−ℓ
V is Schubert decomposable, then cf is a minimum
Theorem 5.3. If f ∈
weight codeword of Cα (ℓ, m).
Proof. We use induction on ℓ. If ℓ = 1, then the desired result follows from
Lemma 5.1 since Ωα (1, m) = P(A1 ) and Cα (1, m) is the q-ary simplex code of
length (q α1 − 1) /(q − 1) and dimension α1 , and hence every nonzero codeword of
Cα (1, m) is a minimum weight codeword.
Now suppose ℓ > 1 and that the result holds for values of ℓ smaller than the
Vm−ℓ
V be Schubert decomposable, and let E and F be the
given one. Let f ∈

MINIMUM WEIGHT CODEWORDS OF SCHUBERT CODES

15

corresponding subsets of Aℓ as in Section 3. Given any x ∈ F , we note that
Vm−(ℓ−1)
V satisfying Vf ⊂ Vg and
g := f ∧ x is a decomposable element of
cg 6= 0. In particular, we find Vf ∩ Api ⊆ Vg ∩ Api for 1 ≤ i ≤ u. On the
other hand, dim Vg ∩ Api ≤ αpi − pi = dim Vf ∩ Api for 1 ≤ i ≤ u, thanks to
Lemma 4.1 and the Schubert decomposability of f . It follows that g is Schubert
decomposable and hence by the induction hypothesis, cg is a minimum weight
codeword of Cα′ (ℓ − 1, m). Now, proceeding as in the proof of Lemma 3.4, except
for applying Lemma 5.2 in place of part (ii) of Lemma 3.3, we see that
X
X
wt(cf ∧x ) = θ1 q ℓ−1 (q − 1) and
wt(cf ∧x ) = θ2 q ℓ−1 (q t − 1),
x∈F \Aℓ−1

x∈F ∩Aℓ−1

where θ1 := |{L ∈ W (f ) : L * Aℓ−1 }| and θ2 := |{L ∈ W (f ) : L ⊆ Aℓ−1 }|. Since
′
wt(cf ) = θ1 + θ2 and since f ∧ x is of weight q δ(α ) for every x ∈ F , we obtain
(21)

wt(cf ) =

′
′
1
1
|F \ Aℓ−1 | q δ(α ) + ℓ−1 t
|F ∩ Aℓ−1 | q δ(α ) .
q ℓ−1 (q − 1)
q (q − 1)

In case t = 1, this gives
′
′
1
1
|F | q δ(α ) = ℓ−1
(q αℓ − q αℓ −1 )q δ(α ) = q δ(α) .
wt(cf ) = ℓ−1
q (q − 1)
q (q − 1)
Now suppose t > 1. Then t = ℓ − pu by Lemma 5.2 and so pu < ℓ. Consequently,
αℓ − αℓ−1 = 1. Thus, Aℓ−1 is a hyperplane in Aℓ , and therefore
dim E ∩ Aℓ−1 ≥ dim E − 1.
Moreover, in view of Lemmas 4.2 and 4.1, we see that
dim(Vf ∩ Aℓ−1 ) = αℓ−1 − ℓ = αℓ − ℓ − 1 = (dim Vf ∩ Aℓ ) − 1.
Hence we can find some z ∈ Vf ∩ Aℓ such that z 6∈ Vf ∩ Aℓ−1 . Since Vf ⊆ E, we
see that z ∈ E \ (E ∩ Aℓ−1 ) and therefore
dim E ∩ Aℓ−1 ≤ dim E − 1.
It follows that dim E ∩ Aℓ−1 = dim E − 1, and hence t′ := codimAℓ−1 (E ∩ Aℓ−1 ) is
equal to t. Consequently, as in Subcase 2.3 of the proof of Theorem 3.6,
|F \ Aℓ−1 | = q αℓ −t−1 (q t − 1)(q − 1) and |F ∩ Aℓ−1 | = q αℓ −t−1 (q t − 1).
Using this together with (21), we obtain wt(cf ) = q δ(α) . Since Theorem 3.6 shows
that q δ(α) is the minimum distance of Cα (ℓ, m), the proof is complete.

Remark 5.4. Except for the last line in the proof of above theorem, the fact that
q δ(α) is the minimum distance of Cα (ℓ, m) has not been used anywhere. In fact, our
V
proof of Theorem 5.3 shows that if f ∈ m−ℓ V is Schubert decomposable, then
cf is a codeword of Cα (ℓ, m) of weight q δ(α) . Since it is easy to construct (m − ℓ)dimensional subspaces W of V such that dim W ∩Api = αpi −pi for i = 1, . . . , u+1,
we can deduce that d(Cα (ℓ, m)) ≤ q δ(α) . This provides an alternative proof of
Proposition 3.5.

16

SUDHIR R. GHORPADE AND PRASANT SINGH

We will now prove that the converse of Theorem 5.3 is true provided that the
Vm−ℓ
V is assumed to be decomposable.
element f of
Vm−ℓ
V is decomposable. If cf is a minimum
Theorem 5.5. Assume that f ∈
weight codeword of Cα (ℓ, m), then f is Schubert decomposable.
Proof. We use induction on ℓ. If ℓ = 1, then u = 0 and there is nothing to prove.
Suppose ℓ > 1 and that the result holds for values of ℓ smaller than the given one.
Vm−ℓ
Let f ∈
V be a decomposable element such that cf is a minimum weight
codeword of Cα (ℓ, m). In particular, cf 6= 0 and if E and F denote the subsets
of Aℓ associated to f , as in Section 3, then t := codimAℓ E satisfies 1 ≤ t ≤ αℓ .
Moreover, by Theorem 3.6, cf ∧x is a minimum weight codeword of Cα′ (ℓ − 1, m)
for every x ∈ F and furthermore, we either have t = 1 or we have t > 1 and
αℓ − αℓ−1 = 1.
Note that for an arbitrary x ∈ F , by induction hypothesis we see that g := f ∧ x
is Schubert decomposable. Hence dim Vg ∩ Api = αpi − pi for all i = 1, . . . , u. Now
since f is decomposable, so is g; moreover, Vf is a hyperplane in Vg . Hence
(22)

qi := dim Vf ∩ Api = αpi − p′i

where

p′i = pi or pi + 1 for i = 1, . . . , u.

Let us also note that it suffices to show that Vg ∩Apu ⊆ Vf ∩Apu because in that case,
we obtain Vf ∩ Apu = Vg ∩ Apu , the other inclusion being trivial, and consequently,
dim Vf ∩ Api = αpi − pi for all i = 1, . . . , u, i.e., f is Schubert decomposable. We
will now divide the proof into two cases according as t = 1 or t > 1.
Case 1. t = 1
In this case pu ≤ ℓ−1 and by Lemma 3.1, Apu ⊆ E. Let x be an arbitrary element
of F and as before, let g = f ∧ x. Let y ∈ Vg ∩ Apu . Since y ∈ Vg = Vf + hxi, we
can write y = z + λx for some z ∈ Vf and λ ∈ Fq . Also since y ∈ Apu , we find
y ∈ E and so cf ∧y = 0. Moreover, cf ∧z = 0 simply because z ∈ Vf . It follows that
0 = cf ∧y = cf ∧z + λ cf ∧x = λ cf ∧x

and hence

λ = 0 so that y ∈ Vf ∩ Apu .

Thus Vg ∩ Apu ⊆ Vf ∩ Apu and so, as noted before, f is Schubert decomposable.
Case 2. t > 1
In this case αℓ − αℓ−1 = 1 and so pu < ℓ − 1, i.e., pu + 2 ≤ ℓ. Recall that as per
our convention pu+1 := ℓ and so in view of (22) and Lemma 4.1, we set p′u+1 := ℓ
and qu+1 := αℓ − ℓ. Now we can recursively find y1 , . . . ym−ℓ such that
Vf ∩ Api = hy1 , . . . , yqi i for i = 1, . . . , u + 1

and Vf = hy1 , . . . , ym−ℓ i.

In view of the dimension formulas (22) (that are also valid for i = u + 1), this
ensures that no nontrivial linear combination of yqi +1 , . . . , ym−ℓ is in Api for each
i = 1, . . . , u + 1. By recursively extending these bases of Vf ∩ Api to Api , we can
also find z1 , . . . , zℓ ∈ Aℓ such that
Api = hy1 , . . . , yqi , z1 , . . . , zp′i i for i = 1, . . . , u + 1.

MINIMUM WEIGHT CODEWORDS OF SCHUBERT CODES

17

Now consider the subspaces L and L′ of Aℓ defined by
L = hz1 , . . . , zℓ i and L′ = hz1 , . . . , zp′u , zp′u +2 , . . . , zℓ i.
It is clear that dim L = ℓ = dim L′ + 1 and also that
dim(L ∩ Api ) = dim(L′ ∩ Api ) = dimhz1 , . . . , zp′i i = p′i ≥ pi for i = 1, . . . , u.
Hence, in view of (7), we see that L ∈ Ωα (ℓ, m) and L′ ∈ Ωα′ (ℓ − 1, m). Moreover,
by our choice of z1 , . . . , zℓ , it is clear that Vf ∩ L = {0}. Since f is decomposable,
it follows from (14) that cf (L) 6= 0. Hence if we let x := zp′u +1 , then we find
cf ∧x (L′ ) 6= 0. It follows that x ∈ F and so induction hypothesis applies to g = f ∧x
for this choice of x. Thus, g is Schubert decomposable. Moreover, if y ∈ Vg ∩ Apu ,
then being an element of Vg = Vf + hxi, we can write
y = z + λx for some z ∈ hy1 , . . . , ym−ℓ i and λ ∈ Fq .
On the other hand, being an element of Apu , we see that
y ∈ hy1 , . . . , yqu , z1 , . . . , zp′u i.
Thus, if λ 6= 0, then x = zp′u +1 can be expressed as a linear combination of
y1 , . . . , ym−ℓ , z1 , . . . , zp′u , which contradicts the choice of y’s and z’s. So λ = 0 and
y ∈ Vf ∩ Apu . Thus Vg ∩ Apu ⊆ Vf ∩ Apu and so f is Schubert decomposable. 
In view of Theorems 5.3 and 5.5, we make the following conjecture.
Conjecture 5.6. Minimum weight codewords of the Schubert code Cα (ℓ, m) are
V
precisely the codewords corresponding to Schubert decomposable elements of m−ℓ V .
6. Completely Non-consecutive Case
We will continue to use the notation and terminology of the last three sections.
The main result of this section is an affirmative answer to Conjecture 5.6 when
the dimension sequence α = (α1 , . . . , αℓ ) of the fixed partial flag A1 ⊂ · · · ⊂ Aℓ is
completely non-consecutive, i.e., when αi − αi−1 ≥ 2 for 1 < i ≤ ℓ.
Theorem 6.1. Assume that α is completely non-consecutive. If c is a minimum
Vm−ℓ
weight codeword of Cα (ℓ, m), then c = ch for some decomposable h ∈
V.

Proof. We will use induction on ℓ. The result clearly holds when ℓ = 1 since every
Vm−1
V is decomposable. Suppose ℓ > 1 and the result is true
nonzero element of
for values of ℓ smaller than the given one. Let c be a minimum weight codeword of
Vm−ℓ
V such that c = cf , and let E, F be as in Section 3. Since
Cα (ℓ, m). Fix f ∈
αℓ − αℓ−1 ≥ 2, by Theorem 3.6 we see that codimAℓ E = 1 and f ∧ x is a minimum
weight codeword of Cα′ (ℓ − 1, m) for every x ∈ F . Moreover, Aℓ−1 ⊆ E, thanks to
Lemma 3.3. Thus, we can and will choose a basis {e1 , . . . , em } of V such that
(23)

Ai = he1 , . . . , eαi i for i = 1, . . . , ℓ and E = he1 , . . . , eαℓ −1 i.

18

SUDHIR R. GHORPADE AND PRASANT SINGH

Let x := eαℓ . Clearly, x ∈ F and hence f ∧ x is a minimum weight codeword of
Cα′ (ℓ − 1, m). Moreover, α′ is completely non-consecutive. So by induction hyVm−ℓ+1
pothesis, cf ∧x = cg for some decomposable g ∈
V . Moreover, by Theorem
5.5, g is Schubert decomposable, and so dim Vg ∩ Ai = αi − i for i = 1, . . . , ℓ − 1.
Thus, we can recursively choose z1 , . . . , zℓ−1 such that
z1 ∈ A1 \ (Vg ∩ A1 ) and zi ∈ Ai \ (hz1 , . . . , zi−1 i + Vg ∩ Ai ) for i = 2, . . . , ℓ − 1.
In particular, z1 , . . . , zℓ−1 span an (ℓ − 1)-dimensional subspace, say Bℓ−1 of Aℓ−1
such that Aℓ−1 = Bℓ−1 + (Vg ∩ Aℓ−1 )). This implies that Vg ∩ Bℓ−1 = {0}. Also
since dim Vg = m − ℓ + 1 and x 6∈ Aℓ−1 , we see that dim Vg ∩ (Bℓ−1 + hxi) ≥ 1.
Hence, Vg contains an element of the form b + x for some b ∈ Bℓ−1 . Consequently,
we can find g1 , . . . gm−ℓ ∈ V such that g1 , . . . gαℓ−1 −(ℓ−1) span Vg ∩ Aℓ−1 and
g = g1 ∧ · · · ∧ gm−ℓ ∧ (b + x) = g ′ ∧ b + g ′ ∧ x,

where g ′ := g1 ∧ · · · ∧ gm−ℓ .

Note that Vg ∩ Aℓ−1 = hg1 , . . . gαℓ−1 −(ℓ−1) i ⊆ Vg′ ∩ Aℓ−1 ⊆ Vg ∩ Aℓ−1 . Thus,
Vg′ ∩ Aℓ−1 = Vg ∩ Aℓ−1

and

dim(Vg′ ∩ Aℓ−1 ) = αℓ−1 − (ℓ − 1).

We claim that cg′ ∧b = 0. This is clear if b ∈ Vg′ . Now suppose b 6∈ Vg′ . Then
Vg′ ∧b ∩ Aℓ−1 = (Vg′ + hbi) ∩ Aℓ−1 = (Vg′ ∩ Aℓ−1 ) + hbi has dimension αℓ−1 − ℓ + 2
and therefore Vg′ ∧b ∩ Aℓ−1 has nonzero intersection with any (ℓ − 1)-dimensional
subspace of Aℓ−1 . In particular, U ∩Vg′ ∧b 6= {0} for every U ∈ Ωα′ (ℓ − 1, m). Thus,
in view of (14), the claim is proved. From the claim, it follows that cg = cg′ ∧x .
Writing each of g1 , . . . gm−ℓ as a linear combination of e1 , . . . , em and noting that
Vm−ℓ
x = eαℓ , we see that g ′ ∧ x = h ∧ x, where h is a decomposable element of
V
of the form h1 ∧· · ·∧hm−ℓ , where each of h1 , . . . , hm−ℓ is in the (m− 1)-dimensional
space V spanned by {e1 , . . . , em } \ {x}. We will now proceed to prove that cf = ch .
Let L ∈ Ωα (ℓ, m) and let P = uℓ ∧ · · · ∧ u1 with ui ∈ Ai for 1 ≤ i ≤ ℓ, be the
V
representative of L in ℓ V among the fixed representatives P1 , . . . , Pnα as in §2.3.
We wish to show that cf (P ) := f ∧ uℓ ∧ · · · ∧ u1 is equal to ch (P ) := h ∧ uℓ ∧ · · · ∧ u1 .
Since cf ∧x = ch∧x , we readily see that f ∧x∧uℓ−1 ∧· · ·∧u1 = h∧x∧uℓ−1 ∧· · ·∧u1 . We
will now consider two cases. First, suppose uℓ ∈ E. Then cf ∧uℓ is the zero codeword
in Cα′ (ℓ − 1, m) and hence cf (P ) = 0. On the other hand, by (23) and our choice
of h, we see that Vh + E is a subspace of V ′ . Since dim Vh + dim L = m > dim V ′ ,
we must have Vh ∩ L 6= {0} and so by (14), we obtain ch (L) = 0 as well. Now
suppose uℓ 6∈ E. Then uℓ = vℓ + λx for a unique vℓ ∈ E and λ ∈ Fq with λ 6= 0.
As in the previous case, f ∧ vℓ ∧ uℓ−1 ∧ · · · ∧ u1 = 0 = h ∧ vℓ ∧ uℓ−1 ∧ · · · ∧ u1 .
Consequently,
ch (P ) = λ (h ∧ x ∧ uℓ−1 ∧ · · · ∧ u1 ) = λ(f ∧x∧uℓ−1 ∧· · ·∧u1 ) = f ∧uℓ ∧uℓ−1 ∧· · ·∧u1 ,
and thus ch (P ) = cf (P ). This establishes cf = ch and so the theorem is proved. 

MINIMUM WEIGHT CODEWORDS OF SCHUBERT CODES

19

As an immediate consequence of the above theorem, we see that Conjecture 5.6
holds in the affirmative when α is completely non-consecutive.
Corollary 6.2. Assume that α is completely non-consecutive. Then the minimum
weight codewords of Cα (ℓ, m) are precisely the codewords corresponding to Schubert
Vm−ℓ
decomposable elements of
V . More precisely, for any c ∈ Cα (ℓ, m),
c has minimum weight ⇐⇒ c = ch for some Schubert decomposable h ∈

m−ℓ
^

Proof. Follows from Theorems 5.3, 5.5 and 6.1.

V.


We note that a special case of the last corollary implies that Conjecture 5.6 holds
in the affirmative when ℓ = 2.
Corollary 6.3. The minimum weight codewords of Cα (2, m) are precisely the codeVm−2
words corresponding to Schubert decomposable elements of
V.

Proof. Follows from Corollary 6.2 and the characterization by Nogin [13] of minimum weight codewords of Grassmann codes because when ℓ = 2, the pair α must
be either completely consecutive or completely nonconsecutive.

7. Enumeration and Generation
In this section, we consider the problem of enumerating the number of minimum
weight codewords of Schubert codes and also of determining whether or not the
minimum weight codewords generate the Schubert code Cα (ℓ, m). The case of
Grassmann codes, which is when αi = m − ℓ + i for i = 1, . . . , ℓ, is well-known.
 
Here we know that the number of minimum weight codewords is (q − 1) m
ℓ q and
also that the minimum weight codewords of the Grassmann code C(ℓ, m) generate
C(ℓ, m). Both these assertions follow readily from Nogin’s characterization of the
minimum weight codewords as those that correspond to decomposable elements of
Vm−ℓ
V . In the case of Schubert codes, we have noted earlier that the map given
V
by f 7→ cf from m−ℓ V onto Cα (ℓ, m) is “many-to-one”. But for studying the
minimum weight codewords of Cα (ℓ, m), it suffices to consider the restriction of
V
this map to the set of Schubert decomposable elements of m−ℓ V , and examine to
what extent it is injective. This is done in the next two lemmas.
V
Lemma 7.1. Let f, g ∈ m−ℓ V be Schubert decomposable elements such that
cf = cg . Then Vf ∩ Api = Vg ∩ Api for all i = 1, . . . , u + 1.
Proof. Assume the contrary, i.e., suppose Vf ∩ Api 6= Vg ∩ Api for some i ≤ u + 1.
We will assume that i is the least positive integer with this property. Then
(24)

Vf ∩ Apj = Vg ∩ Apj

for 0 ≤ j < i,

where

p0 = 0 and A0 := {0}.

20

SUDHIR R. GHORPADE AND PRASANT SINGH

Since dim(Vf ∩ Api ) = dim(Vg ∩ Api ), we see that Vf ∩ Api 6⊆ Vg ∩ Api . So there is
some x ∈ Vf ∩ Api such that x 6∈ Vg ∩ Api . By (24), x 6∈ Apj for 0 ≤ j < i. Since f, g
are Schubert decomposable, we can recursively choose x1 , . . . , xℓ ∈ Aℓ such that
(Vg ∩ Apj ) + hx1 , . . . , xpj i = Apj

for j = 1, . . . , u + 1

and xpi = x,

where pu+1 = ℓ. Now let L = hx1 , . . . , xℓ i. By our choice of x1 , . . . , xℓ , it is clear
from (7) that L ∈ Ωα (ℓ, m) and Vg ∩ L = {0}. Since g is decomposable, this implies
cg (L) 6= 0. On the other hand, since x ∈ Vf ∩ L, we see from (14) that cf (L) = 0.
Thus, cf 6= cg , which contradicts the hypothesis.

A partial converse of the above result is also true.
V
Lemma 7.2. Let f, g ∈ m−ℓ V be Schubert decomposable elements such that
Vf ∩ Api = Vg ∩ Api for all i = 1, . . . , u + 1. Then cf = λ cg for some λ ∈ Fq \ {0}.
Proof. Let ri := αpi − pi for 1 ≤ i ≤ u + 1 and r := ru+1 . We can recursively find
linearly independent f1 , . . . , fr , e1 , . . . , eℓ ∈ Aℓ such that for each i = 1, . . . , u + 1,
Vf ∩ Api = Vg ∩ Api = hf1 , . . . , fri i and Api = (Vf ∩ Api ) + he1 , . . . , epi i.
Extend {f1 , . . . , fr } to bases {f1 , . . . , fm−ℓ } and {f1 , . . . , fr , g1 , . . . , gm−αℓ } of Vf
and Vg respectively, such that f = f1 ∧· · ·∧fm−ℓ and g = f1 ∧· · ·∧fr ∧g1 ∧· · ·∧gm−αℓ .
Note that Vf ∩ he1 , . . . , eℓ i = {0} and thus {f1 , . . . , fm−ℓ , e1 , . . . , eℓ } is a basis of V .
In particular, for each j = 1, . . . , m − αℓ , we can write gj = xj + yj + zj for
unique xj ∈ hf1 , . . . , fr i, yj ∈ hfr+1 , . . . , fm−ℓ i and zj ∈ he1 , . . . , eℓ i. Hence, by
multilinearity, we see that g is a finite sum of elements of the form
h = f1 ∧ · · · ∧ fr ∧ h1 ∧ · · · ∧ hm−αℓ , where hj ∈ {xj , yj , zj } for j = 1, . . . , m − αℓ .
Now if hj = xj for some j, then clearly h = 0. Also, if hj = zj for some j, then we
Vm−ℓ
find that h is a decomposable element of
V such that
dim(Vh ∩ Aℓ ) ≥ dimhf1 , . . . , fr , zi i = αℓ − ℓ + 1

and thus ch = 0, because otherwise Lemma 4.1 is contradicted. It follows that
cg = ch∗ , where h∗ := f1 ∧ · · · ∧ fr ∧ y1 ∧ · · · ∧ ym−αℓ . By Lemma 5.1, cg 6= 0 and
hence h∗ 6= 0. Consequently, y1 , . . . , ym−αℓ are linearly independent elements of
hfr+1 , . . . , fm−ℓ i, and therefore y1 ∧ · · · ∧ ym−αℓ and fr+1 ∧ · · · ∧ fm−ℓ differ by a
nonzero scalar. This implies that cf = λ cg for some λ ∈ Fq \ {0}.

Remark 7.3. It may be noted that with hypothesis as in Lemma 7.2, the stronger
conclusion that f = λ g for some λ ∈ Fq \ {0} or equivalently, Vf = Vg , is not
true, in general. Indeed, this is indicated by the proof and examples are easy to
construct. For instance, if ℓ = 2, m = 4 and α = (2, 4), then f = e1 ∧ e3 and
V
g = e1 ∧ (e2 + e3 ) are Schubert decomposable elements of 2 V such that cf = cg ,
but f and g do not differ by a scalar. Here e1 , e2 , e3 , e4 denote the elements of a
fixed basis of V .

MINIMUM WEIGHT CODEWORDS OF SCHUBERT CODES

21

The following lemma is a variant of [8, Lem. 3], but with a simpler formula and
a more direct proof.
Lemma 7.4. Let B be a finite-dimensional vector space over Fq and let A be
a subspace of B and R a subspace of A. Suppose b = dim B, a = dim A and
r = dim R. Let u be any integer with 0 ≤ u ≤ b and, as before, let Gu (B) denote
the Grassmannian of u-dimensional subspaces of B. Then


b−a
|{U ∈ Gu (B) : U ∩ A = R}| =
q (a−r)(u−r) .
u−r q
Proof. Let U := {U ∈ Gu (B) : U ∩ A = R} We have a natural surjective map
U
U
U +A
≃
= .
A
U ∩A
R
Note that an arbitrary element of Gu−r (B/A) is of the form T /A, where T is a
subspace of B containing A with dim T = a + u − r. Fix such T /A. Then
ψ : U → Gu−r (B/A)

given by

U 7−→

N eψ −1 (T /A) = {U ∈ Gu (B) : U ∩ A = R and A + U = T }
To estimate the cardinality of this fibre, let us fix an ordered basis {x1 , . . . , xa }
of A such that {x1 , . . . , xr } is a basis of R. Now T has an ordered basis of the
form {x1 , . . . , xa , y1 , . . . , yu−r }, and U := hx1 , . . . , xr , y1 , . . . , yu−r i is in ψ −1 (T /A).
Moreover, every element of ψ −1 (T /A) can be obtained in this manner by choosing
z1 , . . . , zu−r ∈ T such that hz1 , . . . , zu−r i ∩ A = {0} and z1 , . . . , zu−r are linearly
independent. Since |T | = q a+u−r and |A| = q a , the number of ordered (u−r)-tuples
(z1 , . . . , zu−r ) with this property is



(25)
q a+u−r − q a q a+u−r − q a+1 · · · q a+u−r − q a+u−r−1
Two ordered (u − r)-tuples (y1 , . . . , yu−r ) and (z1 , . . . , zu−r ) give rise to the same
subspace if and only if



..
x1
.

 . 
 . 

 
..

 . 
z1
.



 .  
  xr 
..
 . =


.
Q
 y 
 .   P
1 



..

 . 
zu−r

 . 
.

 . 
..
yu−r
.

for some (u − r) × r matrix P and (u − r) × (u − r) nonsingular matrix Q with
entries in Fq . Indeed, in that case the two ordered bases {x1 , . . . , xr , y1 , . . . , yu−r }
and {x1 , . . . , xr , z1 , . . . , zu−r } will differ by a nonsingular u × u matrix of the form


..
I
.
0

 r


 . . . . . . . . .


..
P
.
Q

22

SUDHIR R. GHORPADE AND PRASANT SINGH

where Ir denotes the identity matrix of size r × r and 0 denotes the r × (u − r)
matrix all of whose entries are zero. The number of ways in which matrices P and
Q of the kind above can be chosen is clearly given by



(26)
q r(u−r) q u−r − 1 q u−r − q · · · q u−r − q u−r−1 .

It follows that the cardinality of ψ −1 (T /A) is obtained by dividing the expression
in (25) by that in (26). Thus,


b − a (a−r)(u−r)
−1
(a−r)(u−r)
|ψ (T /A) | = q
and hence |U| =
q
.
u−r q
This completes the proof.



We are now ready to prove the main result of this section.
Theorem 7.5. The number of codewords of Cα (ℓ, m) corresponding to Schubert
V
decomposable elements of m−ℓ V is equal to

u 
Y
αpj+1 − αpj
P
Mα := (q − 1)q
pj+1 − pj q
j=0
where, as per our usual conventions, p0 = 0, pu+1 = ℓ, and α0 = 0, and where
P=

u
X
j=1


pj αpj+1 − αpj − pj+1 + pj .

Consequently, the number of minimum weight codewords of Cα (ℓ, m) is at least Mα .
Moreover, if α is completely non-consecutive, then the number of minimum weight
codewords of Cα (ℓ, m) is exactly Mα .
Proof. Let us temporarily denote by Sα the set that we wish to enumerate, i.e., let
Sα := {cf : f ∈

m−ℓ
^

V is Schubert decomposable}.

Note that by Theorem 5.3, elements of Sα are minimum weight codewords of
Cα (ℓ, m) and in particular, nonzero elements of Fnq α . Consider the relation ∼ on Sα
defined by c ∼ c′ ⇔ c = λc′ for some λ ∈ Fq \ {0}. Clearly, ∼ is an equivalence relation and each equivalence class has cardinality (q −1). Thus, if we denote by Sα the
set of all equivalence classes, then |Sα | = (q − 1)|Sα |. On the other hand, there is
a similar equivalence relation (viz., proportionality) on the set of all decomposable
Vm−ℓ
elements of
V , and the map f 7→ Vf sending a decomposable element to its
annihilator clearly gives a bijection between the set of equivalence classes and the
Grassmannian Gm−ℓ (V ) of (m − ℓ)-dimensional subspaces of V . This equivalence
relation preserves Schubert decomposability and the set of equivalence classes of
V
Schubert decomposable elements of m−ℓ V is clearly in bijection with
Λα := {W ∈ Gm−ℓ (V ) : dim W ∩ Api = αpi − pi for all i = 1, . . . , u + 1} .

MINIMUM WEIGHT CODEWORDS OF SCHUBERT CODES

23

For any c ∈ Sα , denote by [c] its equivalence class in Sα . Then the map


θ : Λα → Sα given by hw1 , . . . , wm−ℓ i 7→ cw1 ∧···∧wm−ℓ

is clearly well-defined and surjective. By Lemmas 7.1 and 7.2, for any W, W ′ ∈ Λα ,
θ(W ) = θ(W ′ ) ⇔ W ∩ Api = W ′ ∩ Api for all i = 1, . . . , u + 1 ⇔ W ∩ Aℓ = W ′ ∩ Aℓ .
It follows that for any [c] ∈ Sα , the fibre θ−1 ([c]) is in bijection with the set of all
W ∈ Gm−ℓ (V ) such that W ∩ Aℓ is equal to a fixed (αℓ − ℓ)-dimensional subspace,
say Wℓ , of Aℓ . Hence, by Lemma 7.4,


X
m − αℓ
−1
q ℓ(m−αℓ ) |Sα | = q ℓ(m−αℓ ) |Sα | .
(27) |Λα | =
θ ([c]) =
m − ℓ − (αℓ − ℓ) q
[c]∈Sα

Now let ri := αpi − pi for 1 ≤ i ≤ u + 1 and consider the following sequence of maps
πu+1

π

πu−1

π

π

1
2
u
Λ1
Λ2 −→
Λu −→ . . . −→
Λα −→ Λu+1 −→

where for 1 ≤ j ≤ u + 1, the set Λj is defined by

Λj := U ∈ Grj (Apj ) : dim U ∩ Api = αpi − pi for 1 ≤ i < j ,

while for 1 ≤ j ≤ u + 1, the map πj : Λj+1 → Λj is defined by πj (U ) = U ∩ Apj for
any U ∈ Λj+1 , where, by convention, we have set
Λu+2 := Λα , ru+2 := m − ℓ, Apu+2 := V, αpu+2 := m, and as before, pu+1 := ℓ.

By Lemma 7.4, we see that the cardinality Nj := |πj−1 (U )| of the fibre of any
U ∈ Λj is independent of the choice of U and is given by


αpj+1 − αpj
(28)
Nj =
q pj (rj+1 −rj ) for j = 1, . . . , u + 1.
rj+1 − rj q
It follows that
(29)

|Λα | = Nu+1 |Λu+1 | = Nu+1 Nu |Λu | = · · · = Nu+1 Nu · · · N1 |Λ1 |.

Now note that

 

αp1
m − αℓ
Nu+1 =
q ℓ(m−αℓ ) = q ℓ(m−αℓ ) and |Λ1 | = |Gr1 (Ap1 )| =
.
m − ℓ − (αℓ − ℓ) q
r1 q
Substituting this and (28) in (29) and then comparing with (27), we obtain


u 
u 
Y
Y
αpj+1 − αpj
αpj+1 − αpj
pj (rj+1 −rj )
q pj (rj+1 −rj ) ,
q
=
|Sα | =
p
−
p
r
−
r
j+1
j
j+1
j
q
q
j=0
j=0
where, as before, we have set p0 = 0 = αp0 = r0 . This implies that |Sα | = Mα .
The remaining assertions follow from Theorem 5.3 and Corollary 6.2.


24

SUDHIR R. GHORPADE AND PRASANT SINGH

Remark 7.6. It is clear that if Conjecture 5.6 holds in the affirmative, then Mα
given in Theorem 7.5 is precisely the number of minimum weight codewords of
Cα (ℓ, m). Note that when α is completely consecutive, i.e., when u = 0, we have
 
Mα = (q − 1) αℓℓ q , which is consistent with the result of Nogin [13] mentioned
earlier since in this case Ωα (ℓ, m) is the Grassmannian Gℓ (Aℓ ).
The question as to whether or not the minimum weight codewords of a code
generate the code is often of some interest. It is a classical result that this is true in
the case of binary Reed-Muller codes (see, e.g., [12, Ch. 13, 6]), whereas for q-ary
generalized Reed-Muller codes, it is not true, in general (see, e.g., [4, Thm. 1]). For
Grassmann codes as well as for related classes of codes such as affine Grassmann
codes of an arbitrary level, the minimum weight codewords generate the code (see,
e.g., [1, Thm. 18 and Rem. 1]). However, we will show below that Schubert codes
are, in general, not generated by their minimum weight codewords.
Theorem 7.7. Assume that α has more than two consecutive blocks, i.e., u > 1.
Then the Fq -linear subspace of Cα (ℓ, m) generated by the codewords corresponding
Vm−ℓ
to Schubert decomposable elements of
V is a proper subset of Cα (ℓ, m).

Vm−ℓ
V is Schubert decomposable}.
Proof. As in the last proof, let Sα := {cf : f ∈
The hypothesis on α implies that p2 + 1 ≤ ℓ, and also that
either (i) αp1 ≥ p1 + 1 or

(ii) αp1 = p1 and αp2 ≥ p2 + 1.

Now fix a basis {e1 , . . . , em } of V such that Ai = he1 , . . . eαi i for i = 1, . . . , ℓ.
Also let L = he1 , . . . , eℓ i and g := eℓ+1 ∧ · · · ∧ em . Then g is a decomposable
Vm−ℓ
Vm−ℓ
element of
V such that cg (L) 6= 0. Now suppose f ∈
V is any Schubert
decomposable element. Then in case (i) holds, i.e., when αp1 ≥ p1 + 1, we find
dim Vf ∩ Ap1 = αp1 − p1

and

dim L ∩ Ap1 ≥ p1 + 1

and consequently, dim(Vf ∩ L) ≥ 1, which in view of (14) shows that cf (L) = 0.
On the other hand, if (ii) holds, then
dim Vf ∩ Ap2 = αp2 − p2

and

dim L ∩ Ap2 ≥ p2 + 1

and consequently, dim(Vf ∩ L) ≥ 1, which implies once again that cf (L) = 0.
It follows that if c ∈ Cα (ℓ, m) is any linear combination of elements of Sα , then
c(L) 6= 0. Hence, cg ∈ Cα (ℓ, m) is not in the linear span of Sα .

Corollary 7.8. Suppose α is completely non-consecutive and ℓ > 2. Then Cα (ℓ, m)
is not generated by its minimum weight codewords.
Proof. Since α is completely non-consecutive, we have u = ℓ − 1 and so u > 1.
Thus the desired result follows from Corollary 6.2 and Theorem 7.7.


MINIMUM WEIGHT CODEWORDS OF SCHUBERT CODES

25

Remark 7.9. As in Remark 7.6, it is clear that if Conjecture 5.6 holds in the affirmative, then Theorem 7.7 shows that Cα (ℓ, m) is not generated by its minimum weight
codewords, provided u > 1. In fact, our proof of Theorem 7.7 shows that its conclusion as well as the last assertion is also valid when u = 1, provided αp1 > p1 . On the
other hand, when u = 0, i.e., when α is consecutive, then Ωα (ℓ, m) ≃ Gℓ (Aℓ ) and
Cα (ℓ, m) is equivalent to the Grassmann code C(ℓ, αℓ ). So we know from the work
of Nogin [13] that Cα (ℓ, m) is generated by its minimum weight codewords. Moreover, when u = 1 and αp1 = p1 , then any W ∈ Ωα (ℓ, m) satisfies W ∩ Ap1 = Ap1 ,
i.e., Ap1 ⊆ W , and hence W 7→ W/Ap1 sets up a natural isomorphism between
Ωα (ℓ, m) and Gℓ−p1 (Aℓ /Ap1 ). Consequently, Cα (ℓ, m) is equivalent to the Grassmann code C(ℓ − p1 , αℓ − αp1 ). So once again, Nogin’s result implies that Cα (ℓ, m)
is generated by its minimum weight codewords in this case.
Acknowledgments
The first named author would like to thank Lucio Guerra for a preliminary
discussion many years ago about the minimum distance conjecture in the case
ℓ = 3 and some correspondence related to [19]. He is also grateful to Christian
Krattenthaler for pointing out that the formula in [8, Lem. 3] can be rewritten as
a hypergeometric series and simplified using q-Chu-Vandermonde identity. Thanks
are also due to the referees for their comments as well as suggestions for improving
the exposition in an earlier version of this paper.
References
[1] P. Beelen, S. R. Ghorpade, and T. Høholdt, Duals of affine Grassmann codes and their
relatives, IEEE Trans. Inform. Theory, 58 (2012), 3843–3855.
[2] P. Beelen and F. Piñero, The structure of dual Grassmann codes, Des. Codes Cryptogr.
79 (2016), 451–470.
[3] H. Chen, On the minimum distance of Schubert codes, IEEE Trans. Inform. Theory 46
(2000), 1535–1538.
[4] P. Ding and J. D. Key, Minimum-weight codewords as generators of generalized ReedMuller codes, IEEE Trans. Inform. Theory 46 (2000), 2152–2158.
[5] S. R. Ghorpade and K. V. Kaipa, Automorphism groups of Grassmann codes, Finite
Fields Appl. 23 (2013), 80–102.
[6] S. R. Ghorpade and G. Lachaud, Higher weights of Grassmann codes, Coding Theory,
Cryptography and Related Areas (Guanajuato, 1998), J. Buchmann, T. Høholdt, H.
Stichtenoth and H. Tapia-Recillas Eds., Springer-Verlag, Berlin, 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. 15
(2009), 54–68.
[8] S. R. Ghorpade and M. A. Tsfasman, Schubert varieties, linear codes and enumerative
combinatorics, Finite Fields Appl. 11 (2005), 684–699.
[9] L. Guerra and R. Vincenti, On the linear codes arising from Schubert varieties, Des.
Codes Cryptogr. 33 (2004), 173–180.

26

SUDHIR R. GHORPADE AND PRASANT SINGH

[10] J. P. Hansen, T. Johnsen, and K. Ranestad, Grassmann codes and Schubert unions,
Arithmetic, Geometry and Coding Theory (AGCT-2005, Luminy), F. Rodier and S.
Vlăduţ Eds., Sémin. Congr., vol. 21, Soc. Math. France, Paris, 2010, pp. 103–121.
[11] M. Marcus, Finite Dimensional Multilinear Algebra, Part II, Marcel Dekker, New York,
1975.
[12] F. J. MacWilliams and N. J. A. Sloane, The Theory of Error Correcting Codes, Elsevier,
New York, 1977.
[13] D. Yu. Nogin, Codes associated to Grassmannians, Arithmetic, Geometry and Coding
Theory (Luminy, 1993), R. Pellikaan, M. Perret, S. G. Vlăduţ, Eds., Walter de Gruyter,
Berlin, 1996, pp. 145–154.
[14] F. Piñero, The structure of dual Schubert union codes, IEEE Trans. Inform. Theory 63
(2017), 1425–1433.
[15] C. T. Ryan, An application of Grassmannian varieties to coding theory, Congr. Numer.
57 (1987), 257–271.
[16] C. T. Ryan, Projective codes based on Grassmann varieties, Congr. Numer. 57 (1987),
273–279.
[17] M. Tsfasman, S. Vlăduţ and D. Nogin, Algebraic Geometric Codes: Basic Notions,
Math. Surv. Monogr., vol. 139, Amer. Math. Soc., Providence, 2007.
[18] C. T. Ryan and K. M. Ryan, The minimum weight of Grassmannian codes C(k, n), Disc.
Appl. Math. 28 (1990), 149–156.
[19] X. Xiang, On The Minimum Distance Conjecture For Schubert Codes, IEEE Trans.
Inform. Theory 54 (2008), 486–488.
Department of Mathematics, Indian Institute of Technology Bombay,
Powai, Mumbai 400076, India.
E-mail address: srg@math.iitb.ac.in
Department of Mathematics, Indian Institute of Technology Bombay,
Powai, Mumbai 400076, India.
E-mail address: psinghprasant@gmail.com

