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...

Full description

Saved in:
Bibliographic Details
Main Author: Catibog, Jonjie M.
Format: text
Language:English
Published: Animo Repository 2016
Online Access:https://animorepository.dlsu.edu.ph/etd_masteral/5180
Tags: Add Tag
No Tags, Be the first to tag this record!
Institution: De La Salle University
Language: English
id oai:animorepository.dlsu.edu.ph:etd_masteral-12018
record_format eprints
spelling oai:animorepository.dlsu.edu.ph:etd_masteral-120182024-06-05T06:08:50Z A lower bound for the dimension of the space of symmetric a-like matrices for the Johnson Graph J(n; 2) Catibog, Jonjie M. 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. 2016-01-01T08:00:00Z text https://animorepository.dlsu.edu.ph/etd_masteral/5180 Master's Theses English Animo Repository
institution De La Salle University
building De La Salle University Library
continent Asia
country Philippines
Philippines
content_provider De La Salle University Library
collection DLSU Institutional Repository
language English
description 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.
format text
author Catibog, Jonjie M.
spellingShingle Catibog, Jonjie M.
A lower bound for the dimension of the space of symmetric a-like matrices for the Johnson Graph J(n; 2)
author_facet Catibog, Jonjie M.
author_sort Catibog, Jonjie M.
title A lower bound for the dimension of the space of symmetric a-like matrices for the Johnson Graph J(n; 2)
title_short A lower bound for the dimension of the space of symmetric a-like matrices for the Johnson Graph J(n; 2)
title_full A lower bound for the dimension of the space of symmetric a-like matrices for the Johnson Graph J(n; 2)
title_fullStr A lower bound for the dimension of the space of symmetric a-like matrices for the Johnson Graph J(n; 2)
title_full_unstemmed A lower bound for the dimension of the space of symmetric a-like matrices for the Johnson Graph J(n; 2)
title_sort lower bound for the dimension of the space of symmetric a-like matrices for the johnson graph j(n; 2)
publisher Animo Repository
publishDate 2016
url https://animorepository.dlsu.edu.ph/etd_masteral/5180
_version_ 1802997421945389056