INVERSES OF PERTURBED LAPLACE-KIRCHHOFF AND SOME DISTANCE MATRICES

Jurkovičova 13, 63800 Brno, Czech Republic

ABSTRACT

It is shown that generalized inverse matrices of Laplace-Kirchhoff matrices, Eichinger matrices E, are inverse matrices of perturbed Laplace-Kirchhoff matrices. Similarly, singular distance matrices have inverses, when perturbed. The slightest perturbation is necessary for long chains.

Properties of chemical bonds of molecules are related with eigenvalues of their adjacency matrices A, which were therefore studied intensively [1]. Great interest was paid to distance matrices D. They are connected with the oldest topological index, the Wiener number W, which is one half of the sum of elements of the distance matrix [2,3].

Only recently, chemical applications of Laplace-Kirchhoff matrices aroused interest [4-9], although they have been used in crystallography [10].

The Laplace-Kirchhoff matrix is a quadratic form of the incidence matrix S of an oriented graph

where V is the diagonal matrix of vertex degrees, and S^Tis the transposed matrix S.

For linear chains and simple n-cycles Eichinger [11] defined generalized inverses to the corresponding Laplace-Kirchhoff matrices by way of the matrix equation

S^TSE = nU (2)where U is the generalized unit matrix :U = I - 1/n JJ^TI is the diagonal unit matrix,J is the unit vector-column,nU is identical with the Laplace-Kirchhoff matrix of the complete graph, n being the number of vertices.

Recently, Klein and Randic [12] proposed for finding the generalized inverses of S^TS equation (3)

and for complete graphs E = U.

The generalized inverses of S^TS according to the equations (3) and (4) differ sometimes. E. g. for star S₄

Since S^TSJ^TJ = 0, there can be infinite many generalized inverses of S^TS differing by

cJ^TJ.

Eichinger matrices with known elements have an important property. They are nonsingular and therefore they have inverses E^-1 with the properties

S^TS = nUE^-1EE^-1 = I

In this paper inverses of Eichinger and distance matrices of several types of graphs are studied.

The difference matrix X between a Laplace-Kirchhoff matrix S^TS and the inverse of its Eichinger matrix must yield the difference between matrices I and U, which is 1/nJJ^T.

Because the row and column sums of Eichinger matrices are constant, it was possible to formulate the following conjecture and prove it for trees, simple cycles and complete graphs.

Conjecture: An Eichinger matrix is the inverse of the Laplace-Kirchhoff matrix perturbed by a fraction c of the quadratic unit matrix

Proof for complete graphs: It is given by the definition. The sum of matrix elements is just (n - 1) = 1/c.

Interesting results were obtained for a disconnected graph, e. g. G = L₂ + L₃. It was necessary to find at first the Eichinger matrix of its complement G_C = (K - G) and its inverse. E^-1(G_C) is the corresponding Laplace-Kirchhoff matrix perturbed by noise elements in the range n = 0.0310 to 0.0313. The Eichinger matrix E(G) was then found as the difference E(G) = E(K) - E(G_C). Its elements were rather large numbers. Nevertheless, the product S^TSE was a surprisingly simple matrix. It was the Laplace-Kirchhoff matrix of K₂ + K₃ with different multiplicities of both components.

The Laplace-Kirchhoff matrices of disconnected graphs have as many zero eigenvalues as the corresponding graphs have components. Even if all zero eigenvalues are removed by perturbation, they are restored by multiplication with their inverses.

D^-1_K = 1/(1-n)S^TS_K - I

(ii) D^-1 of star graphs S_n rooted in the first vertex:

d_ii = 0 bd^-1_ii = 4(n - 2)

d_i1 = d_1j = 1 bd^-1_ii = n -2, otherwise

d_ij = 2, otherwise d^-1_i1 = d^-1_1j = -2

d^-1_ij =-1, otherwise

The constant is b = 1/2 (1-n). The inverse distance matrix of the star graph can be written (except the element d^-1_ij) as bD^-1 = S^TS + (n-2)I - JJ^T.

(iii) D^-1 of linear chains L_n:

d^-1_ij = i - j bd^-1₁₁ = bd^-1_nn = n-2; bd^-1_ii = 2(n-1), otherwise

bd^-1_{i,i +/-1} = 1-n; bd^-1_1n = bd^-1_n1 = -1; d^-1_ij = 0.

The constant is b = 1/[2(1-n)]. The inverse of the topological distance matrix of the linear chain can be formulated again as its perturbed Laplace-Kirchhoff matrix

D_L^-1 = -1/2S^TS_L + bX.

where X has elements x₁₁ = x_1n = x_n1 = x_nn = 1, x_ij = 0 otherwise. For short chains, the perturbed matrix is similar to the Laplace-Kirchhoff matrix of a cycle, but for infinite chains b goes to 0 and the perturbation X needed to destroy the singularity of S^TS is negligible.

(iv) D_C^-1 of an odd-membered cycle C_n for the shorter path is

d^-1_ij = min |i -j| mod n/2 bd^-1_ii = 1 -2p²

n = 2p + 1; bd^-1_{i,i +p} = 1 +p - p²; b d^-1_ij = n, otherwise;

The constant is b = 1/(p² + p).The inverse distance matrix of odd-membered cycles can be expressed again as the sum of matrices

where P is an unit permutation matrix.

For distance matrices of graphs with multiple bonds, defined by Balaban [15] and of molecules with heteroatoms [16], relations were much more complicated.

To find a proof that the distance matrix of a tree is a multiple of an inner inverse of its quadratic form of incidence matrix took as many minutes as elapsed years when I did not suspect that such a relation could exist. I found it from a curiosity, realizing that the elements of corresponding Eichinger matrices E are distances. Rutherford discovered the relation before me [10], solving the classical Kirchhoff problem of spanning trees of electrical circuits formed by electrons in crystals. This paper was written simultaneously with [12], unfortunately it was lost by post and was idle. Klein and Randic were more general, but my proof, yielding the Wiener number W for an arbitrary constant c, could be interesting for chemistry and shows a specific role of the Eichinger matrices between the generalized inverses of S^TS. The constant c is not as arbitrary, as can be deduced from formal relations.

Finding of the generalized inverses of E using its complementary graph matrix, indicated shortly above, is possible probably by a relation of eigenvalues of the Laplace-Kirchhoff matrices both graphs, G and G_C, which are complementary, too.

Eichinger introduced matrices E for linear chains only, as matrices transforming the quadratic form SS^T of the complete graph into the quadratic form WW^T, where W is the walk or path matrix [17]. But this matrix is simultaneously the walk matrix of the linear chain W_L [17] and because the incidence matrix of the complete graph can be split into the product S_K = W_L S_L, it leads to formal equivalencies

The relations between different matrices can be interpreted as follows [18]: A structure, characterized by its incidence matrix S, projects into the Hilbert space as two quadratic forms S^TS and SS^T. Their traces, thus sums of their eigenvalues, are equivalent to the original vector S. Some physical and chemical properties depend directly on eigenvalues of both quadratic forms, other ones only on the eigenvalues of the off-diagonal adjacency matrix A. Other physical properties depend on the inverse eigenvalues or elements of inverse matrices, which for acyclic graphs are distances [9]. The Laplace-Kirchhoff matrices are singular, they have one zero eigenvalue. But they can be perturbed, meaning that a slight distortion of all their elements leads to nonsingular matrices with true inverses. Such a perturbation can be produced for example by the electrical potential, applied to a circuit [12].

The situation is complicated by embedding of molecules into the three dimensional space. Topological distances must be replaced by geometrical ones (or resistance ones), which are squares of Euclidean distances, to be comparable with topological distance matrices [19,20]. The conformation of the graph is changed. Different distance moments have different properties, which depend on symmetry.

REFERENCES