What do pseudo-inverses of Laplacianized distance matrices look like?
Speaker: Felix Goldberg (Hamilton Institute, Maynooth)
Time: 4.00 PM
Date: Monday March 4th 2013
Location: Casl Seminar Room (Belfield Office Park)
Abstract:
The distance matrix of a graph records the lengths of the shortest path between pairs of distinct vertices. Distance matrices of graphs have been studied and appreciated for a long time. One of the early and important results about them is due to Graham & Lovász (1978) who obtained an elegant formula for the inverse of the distance matrix of a tree. In this talk I shall concentrate on the Laplacianized version of the distance matrix: if $D$ is the usual distance matrix and $R$ is the diagonal matrix defined by the row sums on $D$, then the /Laplacianized distance matrix/ is defined as $M=R-D$. By definition, this is a singular irreducible $M$-matrix. At the recent 2012 Haifa Matrix Theory Conference R.Bapat offered a conjecture regarding the Moore-Penrose pseudo-inverse of $M$ when the graph is a tree - namely, that $M^† $ is also an $M$-matrix! After examining many examples we have good reason to think that it is in fact true for/ all graphs/; I shall present in the talk the partial results towards the generalized conjecture that we have obtained thus far:
1. The generalized Bapat's conjecture is true for graphs of diameter 2.
2. The generalized Bapat's conjecture is true for 1-split graphs.
3. The generalized Bapat's conjecture is true for the odd cycles.
Our results imply Bapat's original conjecture for stars and bistars (since stars have diameter 2 and bistars are 1-split graphs). The first result also shows that the generalized conjecture is true in a probabilistic sense, since it known that almost all graphs have diameter 2. I shall discuss some of the difficulties inherent to the problem and try to indicate possible directions for extension of the work reported. Finally, it is well worth mentioning that apart from its intrinsic interest, Bapat's conjecture can be thought of as an element in the general programme of studying the generalized inverses of singular $M$-matrices, initiated by Deutsch & Neumann (1984) who have shown that whether the group inverse is an $M$-matrix determines the convexity/concavity properties of the Perron root.
/This is joint work with Steve Kirkland/
Series: Algebra Seminar Series
Social Media Links