Determinant of the distance matrix of a tree with matrix weights

Let T be a tree with n vertices and let D be the distance matrix of T. According to a classical result due to Graham and Pollack, the determinant of D is a function of n, but does not depend on T. We allow the edges of T to carry weights, which are square matrices of a fixed order. The distance matrix D of T is then defined in a natural way. We obtain a formula for the determinant of D, which involves only the determinants of the sum and the product of the weight matrices.     

On the distance matrix of a directed graph

In this note, we show how the determinant of the distance matrix D(G) of a weighted, directed graph G can be explicitly expressed in terms of the corresponding determinants for the (strong) blocks G_i of G. In particular, when cof D(G), the sum of the cofactors of D(G), does not vanish, we have the very attractive formula .     

汉明距离矩阵的研究

汉明距离矩阵Ds是由测量定义在F_s~q：={0,1,…,q-1}^s上的码字的汉明距离的元素构成.汉明距离矩阵Ds可以由递归的形式表示出来.利用汉明距离矩阵Ds的递归公式求得了矩阵D_s所有特征根以及特征向量.在文章的最后还得出-cDs的Schur指数形的所有特征根.如果c〉0的话,-cDs的Schur指数形的所有特征根都大于零,从而-cDs的Schur指数形是正定的.     

On the greatest distance between two permanental roots of a matrix

The permanental spread of a complex square matrix A is defined to be the greatest distance between two roots of the equation per(zI − A) = 0. A preliminary study of this number as well as of two related quantities is given. In particular, we derive upper and lower bounds and deal with comparisons of different bounds. Finally, two inequalities involving the permanental spread are treated.     

The distance spectrum of a tree

Let T be a tree with line graph T*. Define K = 2I + A(T*), where A denotes the adjacency matrix. Then the eigenvalues of -2K^?1 interlace the eigenvalues of the distance matrix D. This permits numerous results about the spectrum of K to be transcribed for the less tractable D.     

On the multiplicities of eigenvalues of a Hermitian matrix whose graph is a tree

A different approach is given to recent results due mainly to R. C. Johnson and A. Leal Duarte on the multiplicities of eigenvalues of a Hermitian matrix whose graph is a tree. The techniques developed are based on some results of matching polynomials and used a work by O. L. Heilmann and E. H. Lieb on an apparently unrelated topic.      

Inverse of the distance matrix of a block graph

A connected graph G, whose 2-connected blocks are all cliques (of possibly varying sizes) is called a block graph. Let D be its distance matrix. By a theorem of Graham, Hoffman and Hosoya, we have det(D)?≠?0. We give a formula for both the determinant and the inverse, D ^?1 of D.     

Moore-penrose inverse of the incidence matrix of a tree

Let T be a tree with n vertices, where each edge is given an orientation, and let Q be its vertex-edge incidence matrix. It is shown that the Moore-Penrose inverse of Q is the (n-1)× n matrix M obtained as follows. The rows and the columns of M are indexed by the edges and the vertices of T respectively. If e,ν are an edge and a vertex of T respectively, then the (e,ν)-entry of M is, upto a sign, the number of vertices in the connected component of T\e which does not contain ν. Furthermore, the sign of the entry is positive or negative, depending on whether e is oriented away from or towards ν. This result is then used to obtain an expression for the Moore-Penrose inverse of the incidence matrix of an arbitrary directed graph. A recent result due to Moon is also derived as a consequence.     

The calculation of the distance to a nearby defective matrix

The distance of a matrix to a nearby defective matrix is an important classical problem in numerical linear algebra, as it determines how sensitive or ill‐conditioned an eigenvalue decomposition of a matrix is. The concept has been discussed throughout the history of numerical linear algebra, and the problem of computing the nearest defective matrix first appeared in Wilkinsons famous book on the algebraic eigenvalue problem. In this paper, a new fast algorithm for the computation of the distance of a matrix to a nearby defective matrix is presented. The problem is formulated following Alam and Bora introduced in (2005) and reduces to finding when a parameter‐dependent matrix is singular subject to a constraint. The solution is achieved by an extension of the implicit determinant method introduced by Spence and Poulton in (2005). Numerical results for several examples illustrate the performance of the algorithm. Copyright © 2013 John Wiley & Sons, Ltd.     

Left distance binary tree representations

We present a new scheme for representing binary trees. The scheme is based on rotations as a previous scheme of Zerling. In our method the items of a representation have a natural geometric interpretation, and the algorithms related to the method are simple. We give an algorithm for enumerating all the representations for trees onn nodes, and an algorithm for building the tree corresponding to a given representation.This work was supported by the Academy of Finland.     

On the 2-norm distance from a normal matrix to the set of matrices with a multiple zero eigenvalue

An elementary proof of a formula for the 2-norm distance from a normal matrix A to the set of matrices with a multiple zero eigenvalue is given. Earlier, the authors obtained this formula as an implication of a nontrivial result due to A. N. Malyshev. Bibliography: 4 titles. __________ Translated from Zapiski Nauchnykh Seminarov POMI, Vol. 323, 2005, pp. 50–56.     

A constructive algorithm for realizing a distance matrix

The natural metric of a weighted graph is the length of the shortest paths between all pairs of vertices. The investigated problem consists in a representation of a given metric by a graph, such that the total length of the graph is minimized. For that purpose, we give a constructive algorithm based on a technique of reduction, fusion and deletion. We then show some results on a set of various distance matrices whose optimal realization is known.     

On the degree distance of a graph

If G is a connected graph with vertex set V, then the degree distance of G, D^′(G), is defined as , where degw is the degree of vertex w, and d(u,v) denotes the distance between u and v. We prove the asymptotically sharp upper bound for graphs of order n and diameter d. As a corollary we obtain the bound for graphs of order n. This essentially proves a conjecture by Tomescu [I. Tomescu, Some extremal properties of the degree distance of a graph, Discrete Appl. Math. (98) (1999) 159-163].     

Decomposition algorithms for the tree edit distance problem

We study the behavior of dynamic programming methods for the tree edit distance problem, such as [P. Klein, Computing the edit-distance between unrooted ordered trees, in: Proceedings of 6th European Symposium on Algorithms, 1998, p. 91–102; K. Zhang, D. Shasha, SIAM J. Comput. 18 (6) (1989) 1245–1262]. We show that those two algorithms may be described as decomposition strategies. We introduce the general framework of cover strategies, and we provide an exact characterization of the complexity of cover strategies. This analysis allows us to define a new tree edit distance algorithm, that is optimal for cover strategies.     

The distance from a matrix polynomial to matrix polynomials with a prescribed multiple eigenvalue

For a matrix polynomial P(λ) and a given complex number μ, we introduce a (spectral norm) distance from P(λ) to the matrix polynomials that have μ as an eigenvalue of geometric multiplicity at least κ, and a distance from P(λ) to the matrix polynomials that have μ as a multiple eigenvalue. Then we compute the first distance and obtain bounds for the second one, constructing associated perturbations of P(λ).     

On the uniform edge-partition of a tree

We study the problem of uniformly partitioning the edge set of a tree with n edges into k connected components, where k?n. The objective is to minimize the ratio of the maximum to the minimum number of edges of the subgraphs in the partition. We show that, for any tree and k?4, there exists a k-split with ratio at most two. For general k, we propose a simple algorithm that finds a k-split with ratio at most three in O(nlogk) time. Experimental results on random trees are also shown.