2 The Standard Basis of a Subspace of V = F

Ahmad Rio Adriansyah^a,b

aFaculty of Mathematics and Natural Sciences, Institut Teknologi Bandung, Jl. Ganesha 10, Bandung 40132 Indonesia,

bGraduate School of Natural Science and Technology, Kanazawa University, Kakuma, Kanazawa 920-1192 Japan,

E-mail: [email protected]

Abstract. The farthest subconstituent of the q-Johnson graph J_q(n, k) is well-known to be iso- morphic to the bilinear forms graphMk(q)in the case ofn= 2k. This fact is generalized forn≥2k.

Keywords: q-Johnson graph, farthest subconstituent.

1 Introduction

LetFqbe the finite field ofq-elements andV =Fⁿq then-dimensional vector space overFqconsisting of row vectors :

V ={v= (v1, v2, ..., vn)|vi∈Fq, (1≤i≤n)}.

LetX denote the set

V

k

q

ofk-dimensional subspace ofV and define a symmetric relation∼on X by

U₁∼U₂ ⇐⇒ dim(U₁∩U₂) =k−1.

The graph Γ = (X,∼) is called the q-Johnson graph and denoted by Jq(n, k). We may assume k≤n

2, sinceJ_q(n, k) is isomorphic toJ_q(n, n−k). Thus the diameter of Γ isk:

k=max{∂(U₁, U₂)|U₁, U₂∈X},

where∂(U1, U2) is the distance betweenU1andU2 in Γ, i.e., the length of shorthest paths joining U1 andU2.

Note it holds that

∂(U1, U2) =k−dim(U1∩U2).

The reader is referred to [1] for basic properties ofJq(n, k).

Fix a base vertexU0∈X and define thei-th subconstituent Γi(U0) by Γ_i(U₀) ={U ∈X |∂(U₀, U) =i}.

We call Γ_k(U₀) the farthest subconstituent.

In the case ofn= 2k, it is well-known that there is a bijectionφfrom Γk(U0) to the setMk(q) of k×kmatrices overFqsuch thatU1, U2∈Γk(U0) are adjacent if and only ifφ(U1)−φ(U2) has rank 1. In other words, the farthest subconstituent Γk(U0) is isomorphic to the bilinear forms graph

M_k(q). This paper aims to generalize this fact forn≥2k.

The general linear group GL(n, q) acts on X =

V

k

q

from the right naturally as a group of graph automorphisms of J_q(n, k). This action is distance-transitive, namely, GL(n, q) acts on X transitively and the stabilizer ofU₀inGL(n, q) acts on each Γ_i(U₀) transitively (0≤i≤k). From this point of view,Jq(n, k) can be regarded as an association scheme (theq-Johnson scheme) rather than a graph, and in the case ofn= 2k, the farthest subconstituent Γk(U0) is isomorphic to the bilinear forms scheme Mk(q) as an association scheme. The papers [2], [3] treat Γk(U0) in the general case as an association scheme and determine the parameters. We note that the problem dealt with in this paper is different from the one in [2], [3].

2 The Standard Basis of a Subspace of V = F

For a vectorv= (v₁, v₂, ..., v_n)∈V =Fⁿq, we denote thej-th entryv_j ofvbyv(j); v(j) =v_j. Set h(v) =min{j |v(j)6= 0, 1≤j≤n}

and call h(v) the head of v∈V.

Let U be a subspace of V. Then there exists a basis v₁,v₂, ...,v_t for U (t = dim(U)) such that

h(v₁)< h(v₂)< ... < h(v_t). (1) We may assume that forν =h(v_j) (1≤j≤t),

v_i(ν) =δ_ij (2)

where δij is the Kronecker delta, i.e.,δij = 1 fori=j, andδij= 0 for i6=j. A basisv1,v2, ...,vt

ofU is called standard if it satisfies (1),(2). It is easy to see that a standard basis exists uniquely for each subspace ofV.

For the standard basisv₁,v₂, ...,v_tofU, we set

supp(U) ={h(v₁), h(v₂), ..., h(v_t)}

and call it the support of U.

LetM_k×n(q) denote the set ofk×nmatrices overFq. For a matrixA∈M_k×n(q), we denote the i-th row ofA byA_i and the (i, j)-entry ofAbyA_i(j). The subspace spanned byA₁, A₂, ..., A_k is denoted byrow(A).

A matrix E ∈ M_k×n(q) is said to be in echelon form if E1, E2, ..., Et form the standard basis forrow(E) andEi= (0, ...,0) holds fort+ 1≤i≤k. For a matrixE in echelon form, we set

supp(E) ={h(E1), ..., h(Et)},

wheret=rank(E), and call it the support ofE. Obviously,supp(E) coincides withsupp(row(E)).

LetM_k×n^t (q) denote the subset ofM_k×n(q) consisting matricesE such thatE is in echelon form with|supp(E)|=t. Let

V

t

q

denote the set oft-dimensional subspace ofV =Fⁿq. The following lemma is an elementary fact of linear algebra.

Lemma 1.

(i) The following mapping is a bijection : M_k×n^t (q)−→

V

t

q

(E7→row(E))

(ii) LetE, F ∈Mk×n(q) be in echelon form. If row(E)⊃row(F), thensupp(E)⊃supp(F).

SetY =M_k×n^k (q). ThenY is bijectively mapped ontoX =

V

k

q

by sendingE∈Y torow(E)∈ X.

3 The Farthest Subconstituent of J

(n, k)

We keep the notation of the previous sections. SoX=

V

k

q

,Y =M_k×n^k (q), and there is a natural bijection betweenX andY. When considering the farthest subconstituent Γk(U0), we may choose the base vertexU0arbitrarily without loss of generality, sinceGL(n, q) acts onX transitively as a group of graph automorphisms. We set

U0={v∈V |v(1) =v(2) =...=v(n−k) = 0}.

Sosupp(U0) ={n−k+ 1, n−k+ 2, ..., n}and the corresponding matrix in echelon form is [O I], whereO is the zero matrix of size k×n−k andIis the identity matrix of sizek.

We observe that for E ∈ Y, row(E) belongs to Γ_k(U₀), i.e., dim(U ∩U₀) = 0 (U = row(E)) if and only if

supp(E)⊆ {1,2, ..., n−k} (3)

So the following proposition holds.

Proposition 1. Set

Yk={E∈Y |E satisfies(3)}.

Then the following mapping is a bijection :

Y_k−→Γ_k(U₀) (E7→row(E)).

ForE, E⁰∈Yk, we setU =row(E), U⁰=row(E⁰) and ask whenU ∼U⁰ holds in Γk(U0).

SupposeU ∼U⁰. Thendim(U∩U0) =k−1, so there existα, β /∈supp(U∩U⁰) such that

supp(U) =supp(U∩U⁰)∪ {α}, (4)

supp(U⁰) =supp(U∩U⁰)∪ {β}. (5) In view ofsupp(U) =supp(E), supp(U⁰) =supp(E⁰), we set

supp(E) ={i1, i2, ..., ik} withα=ir, (6) supp(E⁰) ={i⁰₁, i⁰₂, ..., i⁰_k}withβ =i⁰_s, (7) wherei1< i2< ... < ik, andi⁰₁< i⁰₂< ... < i⁰_k.

By symmetry, we may assume

α≤β. (8)

Then we have

supp(U∩U⁰) ={i1, ..., i_r−1, i_r+1, ..., i_k}

={i⁰₁, ..., i⁰_s−1, i⁰_s+1, ..., i⁰_k} (9) withr≤sand

i⁰_j=

ij if 1≤j≤r−1, s+ 1≤j≤k,

ij+1 ifr≤j≤s−1. (10)

SinceU =row(E), the standard basis ofU isE₁, E₂, ..., E_kandh(E_j) =i_j. So the standard basis ofsupp(U∩U⁰) consists of

E_j+x_jE_r (1≤j≤r−1) (11)

and

Ej (r+ 1≤j≤k) (12)

for some x_j ∈Fq (1≤j≤r−1).

Similiarly since E₁⁰, E₂⁰, ..., E_k⁰ form the standard basis of U⁰ and h(E_j⁰) = i⁰_j, the standard ba- sis ofsupp(U∩U⁰) consists of

E_j⁰+x⁰_jE_r⁰ (1≤j≤s−1) (13) and

E_j⁰ (s+ 1≤j≤k) (14)

for some x⁰_j ∈Fq (1≤j≤s−1).

SinceU∩U⁰ has a unique standard basis, we have the following equations :

Ej+xjEr=E_j⁰ +x⁰_jE_s⁰ (1≤j ≤r−1) (15) Ej+1=E_j⁰+x⁰_jE_s⁰ (r≤j ≤s−1) (16)

Ej=E_j⁰ (s+ 1≤j≤k) (17)

Conversely, ifE, E⁰ are distinct elements ofY_k and satisfy the condition (6), (7), (8) for their sup- ports and the equations (15), (16), (17) for somexj∈F^q (1≤j≤r−1), x⁰_j∈F^q (1≤j≤s−1), thendim(U∩U⁰) =k−1 holds, i.e.,U ∼U⁰, whereU =row(E), U⁰ =row(E⁰).

We treat the case of α = β first. If α = β, then supp(E) = supp(E⁰) and r = s. Since i_j =i⁰_j (1≤j ≤k) andα=β =i_r, we haveE_j(α) =E_j⁰(α) = 0 (j6=r) andE_r(α) =E_r⁰(α) = 1.

So we havex_j=x⁰_j(1≤j≤r−1) from (15). The equation (15) becomes E_j−E_j⁰ =x_j(E_r⁰ −E_r) (1≤j≤r−1).

The equation (16) is empty. Thus we have the following theorem.

Theorem 1. ForE, E⁰ ∈Yk, assume E 6=E⁰ and supp(E) =supp(E⁰). Set U =row(E), U⁰ = row(E⁰). Then U ∼U⁰ inΓk(U0), i.e.,dim(U∩U⁰) =k−1if and only if rank(E−E⁰) = 1.

In the case of n = 2k, the assumption of supp(E) = supp(E⁰) always holds in the above theo- rem, since the support of every element ofYk is{1,2, ..., k}.

We now treat the case ofα < β. In this case,r < sholds in (9). We want to solve the equations (15), (16) under the conditions (6), (7), (10).

Since α = i_r, we have E_j(α) = 0 (j 6= r) and E_r(α) = 1. Since h(E_s⁰) = i⁰_s = β > α, we have E_s⁰(α) = 0. From (15), we get

x_j =E_j⁰(α) (1≤j≤r−1) (18)

Sinceβ =i⁰_s, we haveE⁰_j(β) = 0 (j6=s) andE_s⁰(β) = 1. From (15), we get

x⁰_j=Ej(β) +xjEr(β) (1≤j≤r−1). (19) By (16) we get

x⁰_j =Ej+1(β) (r≤j≤s−1). (20)

Thus we have the following conclusion.

Proposition 2. Let E, E⁰ ∈ Yk and set U = row(E), U⁰ = row(E⁰). If U ∼ U⁰ in Γk(U0), i.e., dim(U∩U⁰) =k−1, then either supp(E) =supp(E⁰)or |supp(E)∩supp(E⁰)|=k−1.

Theorem 2. FixE∈Y_k arbitrarily and setU =row(E).

(i.) PickE⁰∈Y_kthat satisfies|supp(E)∩supp(E⁰)|=k−1and setU⁰=row(E⁰). Defineα, β, r, s by supp(E) = (supp(E)∩supp(E⁰))∪ {α}, supp(E⁰) = (supp(E)∩supp(E⁰))∪ {β}, α = h(Er), β =h(E_s⁰). Assume U ∼U⁰ in Γk(U0), i.e., dim(U∩U⁰) =k−1. If α < β, then (15), (16), (17) hold forxj (1≤j≤r−1) in (18) andx⁰_j (1≤j≤s−1) in (19), (20).

(ii.) Conversely, for arbitrarily chosen r, s∈Z (1≤r < s≤k) andxj ∈Fq (1≤j ≤r−1), define x⁰_j (1 ≤ j ≤ s−1) by (19), (20). Set α = h(Er). Choose an arbitrary vector v∈V =Fⁿq such that h(Es)< h(v)< h(Es+1)andv(β) = 1 (β =h(v)), v(ν) = 0 (ν ∈ supp(E), ν6=α=h(Er)). LetE⁰be ak×nmatrix overFq such thatE_s⁰ =vandE_j⁰ (j6=s) are given by (15), (16), (17). ThenE⁰∈Yk andU ∼U⁰ inΓk(U0), whereU⁰=row(E⁰).

References

[1] A.E. Brouwer, A.M. Cohen, A. Neumaier . Distance-Regular Graph. Springer-Verlag. 1989.

[2] H. Kurihara . Character tables ofm-flat association schemes. Adv. Geom. 11 (2011), no.2, 293-301.

[3] K. Wang, J. Guo, F. Li .Association Schemes Based on Attenuated Spaces. European Journal of Combinatorics. 31 (2010), 297-305.