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

Date of Publication

2016

Document Type

Master's Thesis

Degree Name

Master of Science in Mathematics

College

College of Science

Department/Unit

Mathematics and Statistics

Thesis Adviser

Arlene A. Pascasio

Defense Panel Member

Leonor Ruivivar

Melvin Vidar

Isagani Jos

Harris Dela Cruz

Abstract/Summary

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 < 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 < 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 < 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 < j n) form a basis for the space Lsym for J(n; 2) where n 4 is any integer.

Abstract Format

html

Language

English

Format

Electronic

Accession Number

CDTG006611

Shelf Location

Archives, The Learning Commons, 12F Henry Sy Sr. Hall

Physical Description

1 computer optical disc ; 4 3/4 in.

Upload Full Text

wf_no

This document is currently not available here.

Share

COinS