Squared Distance Matrix of a Tree


December 9, 2014


Ravindra B. Bapat


Indian Statistical Institute, Delhi


Let G be a connected graph with vertex set V(G) = {1, …, n}. The distance between vertices i,j ∈ V(G), denoted d(i,j), is defined to be the minimum length (the number of edges) of a path from i to j. The distance matrix D(G), or simply D, is the n × n matrix with (i,j)-element equal to 0 if i = j and d(i,j) if i not = j.

According to a well-known result due to Graham and Pollak, if T is a tree with n vertices, then the determinant of the distance matrix D of T is (-1)n-1(n-1)2n-2. Thus the determinant depends only on the number of vertices in the tree and not on the tree itself. A formula for the inverse of the distance matrix of a tree was given by Graham and Lovász.Several generalizations of these two results have been proved.

We first provide an overview of various distance matrices associated with a tree. These include a weighted analog of the classical distance matrix, a weighted analog with matrix weights, a q-analog, and the exponential distance matrix, which has the (i,j)-element equal to qd(i,j).

We then consider the entry-wise square of the distance matrix of a tree. Thus the squared distance matrix Δ has its (i,j)-element equal to d(i,j)2. In joint work with S. Sivasubramanian, we gave a formula for the determinant of Δ, which involves only the vertex degrees. It turns out that Δ is nonsingular if and only if the tree has at most one vertex of degree 2 and we give a formula for Δ-1 when it exists. When the tree has no vertex of degree 2, the formula for Δ-1 is particularly simple and depends on a certain “two-step” Laplacian of the tree. We also determine the inertia of Δ.


Ravindra B. Bapat

Ravindra B. Bapat had his schooling and undergraduate education in Mumbai. He obtained B.Sc. from University of Mumbai, M.Stat. from the Indian Statistical Institute, New Delhi and Ph.D. from the University of Illinois at Chicago in 1981. After spending one year in Northern Illinois University in DeKalb, Illinois and two years in Department of Statistics, University of Mumbai, Prof. Bapat joined the Indian Statistical Institute, New Delhi, in 1983, where he holds the position of Professor, Stat-Math Unit, the moment. He held visiting positions at various Universities in the U.S. and visited several Institutes abroad in countries including France, Holland, Canada, China and Taiwan for collaborative research and seminars. The main areas of research interest of Prof. Bapat are nonnegative matrices, matrix inequalities, matrices in graph theory and generalized inverses. He has published more than 100 research papers in these areas in reputed national and international journals and guided three Ph.D. students. He has written books on Linear Algebra, published by Hindustan Book Agency, Springer and Cambridge University Press. He wrote a book on Mathematics for the general reader, in Marathi, which won the state government award for best literature in Science for 2004. Prof. Bapat has been on the editorial boards of Linear and Multilinear Algebra, Electronic Journal of Linear Algebra, India Journal of Pure and Applied Mathematics and Kerala Mathematical Association Bulletin. He has been elected Fellow of the Indian Academy of Sciences, Bangalore and Indian National Science Academy, Delhi. Prof. Bapat served as President of the Indian Mathematical Society during its centennial year 2007-2008. For the past several years he has been actively involved with the Mathematics Olympiad Program in India and served as the National Coordinator for the Program. Prof. Bapat served as Head, ISI Delhi Centre, during 2007-2011. He was awarded the J.C. Bose fellowship in 2009.