Talk
Speaker: Dr. Madhab Mondal, Dept of Maths, IIT Guwahati
Host: S. Krishnan
Title: On Incidence and Distance Matrices of Graphs with Matrix Weights
Time, day and date: 11:00:00 AM – 12:00:00 PM, Monday, March 30
Venue: Ramanujan Hall (https://meet.google.com/dkp-hbsd-rdd)
Abstract: Throughout all graphs are assumed to be simple and finite. A graph with matrix weights is a graph in which each edge is assigned a nonzero matrix from Ms, the set of all square matrices of order s. The main objective of this study is to investigate certain algebraic properties of matrices associated with matrix-weighted graphs. In particular, we consider the incidence matrix, the q-distance matrix, and the 2-Steiner distance matrix. Let G be a oriented weighted graph with n vertices and m edges, where the edge weights are matrices from Ms, and let Q(G) be the vertex-edge incidence matrix. We observed that when the edge weights are singular matrices, the rank of Q(G) depends on the structure of the graph and the selection of the weights on the edges of G. In particular, we showed that rank of Q(G) can be used to characterize trees and unicyclic graphs. Moreover, for large values of s, we proved that there exists rank one weights from Ms such that every integer between n − 1 and m can be realized as rank of Q(G). We also investigated the smallest possible values of s for which these ranks can be attained. Surprisingly, the smallest value of s for which m can be achieved as rank of Q(G) is the arboricity of the graph. This observation led us to introduce a new graph invariant, the k-semi-arboricity, which generalizes the classical notion of the arboricity. In 2006, Bapat, Lal and Pati introduced a q-analogue version of the distance matrix (called the q-distance matrix) of a tree. We consider the q-distance matrix Dq of a weighted tree, where the edge weights are matrices from Ms. We deduce a formula for the determinant of Dq. Subsequently, we present a necessary and sufficient condition for Dq to be invertible and derive an expression for the inverse whenever it exists. The expression for D−1 q leads us to introduce the q-analogue of the Laplacian matrix (named as the q-Laplacian matrix Lq) for a matrix-weighted tree. A formula for the determinant of Lq is also provided. In 2022, Azimi and Sivasubramanian studied the 2-Steiner distance matrix D2 for an arbitrary tree T. They showed that if T has n vertices and p pendant vertices, then rank D2 = 2n − p − 1. They also provided a class BT of bases for the row space Row(D2). More interestingly, it was shown that for each B ∈ BT , | det(D2[B, B])| = n − 1. Thus, just like the determinant of the distance matrix, | det(D2[B, B])| depends only on n. We consider the 2-Steiner distance matrix D2 of a weighted tree, where the edge weights are positive definite matrices of order s. We show that rank D2 is independent of the specific choice of the positive definite matrix weights from Ms. We provide a combinatorial construction of a much larger class B∗ T of bases for Row(D2) which contains BT with strong linearalgebraic structure (that is, every non-basic row is an affine combination with integer coefficients of a B∗ T -basic rows of D2). We prove a more general result: let T be a weighted tree on n vertices with p pendant vertices, where the edge weights are positive definite matrices of order s. Assume that T has weight matrices W1, . . . , Wp for the pendant edges and Wp+1, . . . , Wn−1 for the remaining edges. Then for each B, C ∈ B∗ T , the absolute value of the determinant | det(D2[B, C])| = det(W1 + · · · + Wn−1) det(W1 · · · Wn−1) det(Wp+1 · · · Wn−1). Thus, unlike the usual distance matrix, where the determinant remains the same for any tree on n vertices with edge weight matrices W1, . . . , Wn−1, this determinant remains the same for any tree on n vertices as long as the determinants of the products of the weight matrices of the non-pendant edges of the trees are equal.