{"id":191724,"date":"2014-12-09T00:00:00","date_gmt":"2014-12-09T11:13:33","guid":{"rendered":"https:\/\/www.microsoft.com\/en-us\/research\/msr-research-item\/squared-distance-matrix-of-a-tree\/"},"modified":"2016-07-15T15:21:12","modified_gmt":"2016-07-15T22:21:12","slug":"squared-distance-matrix-of-a-tree","status":"publish","type":"msr-video","link":"https:\/\/www.microsoft.com\/en-us\/research\/video\/squared-distance-matrix-of-a-tree\/","title":{"rendered":"Squared Distance Matrix of a Tree"},"content":{"rendered":"
\n

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

According to a well-known result due to Graham and Pollak, if T<\/i> is a tree with n<\/i> vertices, then the determinant of the distance matrix D<\/i> of T<\/i> is (-1)n-1<\/sup>(n-1)2n-2<\/sup>.<\/i> 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.<\/p>\n

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<\/i>-analog, and the exponential distance matrix, which has the (i,j)<\/i>-element equal to qd(i,j)<\/sup>.<\/i><\/p>\n

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

<\/p>\n","protected":false},"excerpt":{"rendered":"

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 […]<\/p>\n","protected":false},"featured_media":198763,"template":"","meta":{"msr-url-field":"","msr-podcast-episode":"","msrModifiedDate":"","msrModifiedDateEnabled":false,"ep_exclude_from_search":false,"_classifai_error":"","msr_hide_image_in_river":0,"footnotes":""},"research-area":[],"msr-video-type":[],"msr-locale":[268875],"msr-post-option":[],"msr-session-type":[],"msr-impact-theme":[],"msr-pillar":[],"msr-episode":[],"msr-research-theme":[],"class_list":["post-191724","msr-video","type-msr-video","status-publish","has-post-thumbnail","hentry","msr-locale-en_us"],"msr_download_urls":"","msr_external_url":"https:\/\/youtu.be\/9UnS_uS7jFo","msr_secondary_video_url":"","msr_video_file":"","_links":{"self":[{"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-video\/191724","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-video"}],"about":[{"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/types\/msr-video"}],"version-history":[{"count":0,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-video\/191724\/revisions"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/media\/198763"}],"wp:attachment":[{"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/media?parent=191724"}],"wp:term":[{"taxonomy":"msr-research-area","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/research-area?post=191724"},{"taxonomy":"msr-video-type","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-video-type?post=191724"},{"taxonomy":"msr-locale","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-locale?post=191724"},{"taxonomy":"msr-post-option","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-post-option?post=191724"},{"taxonomy":"msr-session-type","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-session-type?post=191724"},{"taxonomy":"msr-impact-theme","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-impact-theme?post=191724"},{"taxonomy":"msr-pillar","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-pillar?post=191724"},{"taxonomy":"msr-episode","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-episode?post=191724"},{"taxonomy":"msr-research-theme","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-research-theme?post=191724"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}