A Lower bound for the dimension of the space of symmetric a-like matrices for the Johnson Graph J(n; 2)

The concept of A-like matrices, which originated in the study of tridiagonal pairs of linear transformations, was introduced by Stefko Miklavi c and Paul Terwilliger in The A-like matrices for a hypercube, Electronic Journal of Linear Algebra 22, 796-809, 2011. Let {u100000} denote a nite undirected graph with vertex set X. Let A 2 MatX(R) denote the adjacency matrix of {u100000}. A matrix B 2 MatX(R) is said to be A-like whenever both (i) BA = AB and (ii) for all x y 2 X that are neither equal nor adjacent, the (x y)-entry of B is zero. In their paper, Miklavi c and Terwilliger determined the subspace of MatX(R) consisting of all A-like matrices for a hypercube H(n; 2), where n 1 is an integer, and showed that its dimension is {u100000}n 2 +n+1. In this paper, we focus on the Johnson graph J(n; 2) where n 4 is an integer. We nd a lower bound for the dimension of the space Lsym of all symmetric A-like matrices for J(n; 2). To do this, we nd it convenient to view a vertex x = fr sg of J(n; 2), where 1 r \u3c s n, as an ordered n-tuple x = x1 x2 ::: xn such that xr = xs = 1 and xh = 0 for all h 2 f1; 2 ::: ngnfr; sg. Vertices x and y are adjacent whenever, as n-tuples, x and y di er in exactly two coordinates. Moreover, we introduce the notion of ij-adjacency of vertices in J(n; 2) as follows. For integers i j with 1 i \u3c j n, vertices x y 2 X are said to be ij-adjacent whenever they di er in the ith and jth coordinates and are equal in all other coordinates. We de ne ij to be the matrix in MatX(R) such that for all distinct vertices x y, the (x y)-entry of ij is 1 if vertices x y are ij-adjacent and 0 if not, and whose (x x)-entry is 1 if xi = xj and 0 if not. We show that for all integers n 4, the matrices I and ij (1 i \u3c j n) are symmetric A-like matrices for J(n 2) and are linearly independent. In particular, dim Lsym {u100000}n 2 + 1: We show that equality holds when n = 4 or n = 5. We conjecture that equality holds for any integer n 4, that is, we propose that the matrices I and ij (1 i \u3c j n) form a basis for the space Lsym for J(n; 2) where n 4 is any integer