Draženka Višnjić: The distance function on Coxeter like graphs

Abstract (pdf version attached): Let Sn(𝔽2) be the set of all n×nsymmetric matrices with coefficients from the binary field 𝔽2={0,1}, and let SGLn(𝔽2) be the subset of all invertible matrices. Let Γ̂ n be the graph with the vertex set Sn(𝔽2), where two matrices A,B∈Sn(𝔽2) form an edge if and only if rank(A−B)=1. Let Γn be the subgraph in Γ̂ n which is induced by the set SGLn(𝔽2). In particular, Γ3 is well known-Coxeter graph.

The distance function on Γ̂ n is given by

d(A,B) = rank (A-B), if (A-B) is nonalternate or zero

d(A,B) = rank (A-B) + 1 if (A-B) is alternate and nonzero.

Even the Coxeter graph shows that the distance in Γn must be different. The primary goal is to characterize the distance function on this graph, from which consequently, we can determine the diameter of the graph Γn. Since the vertices of Γn are invertible symmetric matrices, which are not closed under addition, describing these results is more difficult compared to the graph Γ̂ n.

As Γn is an induced subgraph in Γ̂ n, we have dΓn ≥ dΓ̂ n