|
|
ON THE TRACE OF THE WIENER NUMBER
Milan Kunz
1. Introduction
About twenty years ago, I noticed a misunderstanding concerning H functions. Trying to clear it, I defined naive matrices N, having in each row just one unit vector ej (01, 02,...,1 j, .., 0n) [1]. The next step in this direction, the sums and differences of two naive naive matrices N, was a jump into graph theory, since these matrices are incidence matrices of oriented graphs S = (Nb - Na) or unoriented graphs G = (Nb + Na), respectively.
On my way, I have been meeting the Wiener number [2]. Due to my chemical background, this could be expected but it was strange that knowledge I found on my lazy walk was not commonly known, as my technique was elementary. In some cases, I was not the first one but if others were ahead on parallel paths no reviewer knew it. And if somebody went before us, his trace was lost in the sumps of obsolescent literature.
2. Path and walk matrices
It is well known [3] that the Laplace-Kirchhoff matrices have (n-1) nonzero eigenvalues. They are quadratic forms STS, where ST is transposed incidence matrix S. Both quadratic forms STS and SST have the same set of eigenvalues, except zero one. In trees with (n - 1) arcs, SST is (n - 1) dimensional square matrix, therefore it must be nonsingular. Inverting these matrices [4], I found inverse matrices SS-T of trees. On their trace I encountered the Wiener number for the first time. The elements of WW-1 are distances. More precisely, the Wiener number on the diagonal is obtained by counting how many times the arc (edge) j was used in all paths or walks between all vertices of the tree. This number is equal to the product of the number of vertices in subgraphs on its both ends. The off-diagonal elements are the counts of how many times the pairs of arcs (edges) ij were used in all paths together. In unoriented graphs, where GGT has all elements positive, at least some elements of the inverse must be negative. I defined the inverse in the form WTW, where W is a matrix which rows represent path (walk) i between all pairs of vertices. The columns represent the arcs (edges). The elements wij are 1 if arc j is incident with the path i, zero otherwise. Walk matrices, defined for unoriented graphs G, must have some elements negative and the sign alternates in the walk. For example for the unoriented tree 2-isopentane
WT
|
1 |
0 |
0 |
1 |
1 |
0 |
0 |
1 |
0 |
0 |
|
0 |
1 |
0 |
-1 |
0 |
1 |
0 |
0 |
1 |
0 |
|
0 |
0 |
1 |
0 |
-1 |
-1 |
0 |
-1 |
-1 |
1 |
|
0 |
0 |
0 |
0 |
0 |
0 |
1 |
1 |
1 |
-1 |
|
W TW |
|
GG T |
||||||
|
4 |
-1 |
-2 |
1 |
2 |
1 |
1 |
0 |
|
|
-1 |
4 |
-2 |
1 |
1 |
2 |
1 |
0 |
|
|
-2 |
-2 |
6 |
-3 |
1 |
1 |
2 |
1 |
|
|
1 |
1 |
-3 |
4 |
0 |
0 |
1 |
2 |
|
My definition of W does not give the inverse directly but its n multiple,
W
I prefered this form to keep the Wiener number intact and to avoid fractions.
3. Paths from the root
Arcs (edges) are coded in path (walk) matrices in their own space by only one element. If are coding in space of vertices we must mark an arc by its both ends.
To code trees, it is necessary to choose one vertex as the root and mark it [5]. There are (n - 1) paths from the root to other vertices. The code matrix C has n columns and the shortest path has two elements but the code matrix is singular. To remove this singularity a row with one unit element e1 is added. The code matrix C has lower triangular form (that is at least after suitable permutations) [6], and the unit diagonal. Therefore, it has the inverse. This is the incidence matrix S of the given oriented tree which singularity was removed same way by adding a row with one unit element e1.
There are n roots in a tree and the same number of code matrices C. But some of them are redundant since the corresponding roots are equivalent. Each matrix has (n - 1) row- paths, together n(n - 1), which is twice the number of rows in W (all paths are followed from both ends). The sum of all code matrices C is a difference of the full code.
It is possible to reverse the construction of the code matrix C. We define it as the inverse to the incidence matrix G of an rooted oriented tree S which matrix was perturbed by the unit element e1. So the code matrix C of an unoriented tree is defined which singularity was removed similarly by adding a row with one unit element e1, too. In its code matrix C negative signs must appear, as they do in walk matrices.
But more important and interesting is what is obtained, when we add rows having zero elements on the diagonal to both matrices. We are here at a bifurcation, because results are different for both possibilities.
4. Distances from coordinates
The fourth line in the matrix
|
1 |
0 |
0 |
|
1 |
1 |
0 |
|
1 |
1 |
1 |
|
1 |
0 |
1 |
can be interpreted as an arc between the first vertex and and the third one of the chain L3, defined by the first three rows. This is the closing arc of the cycle C4. Otherwise and more simply, it is the coordinate of the fourth point limiting the square with unit sides. The coordinates in the first columns are all equal to 1 and redundant. In this case they do not remove singularity of the matrix as previously. They can be replaced by zeroes and eliminated, to simplify the example.
Now we want to transform the coordinate matrix C into the distance matrix. For extracting distances we use a graph algorithm with four steps [6,7]:
a) finding the quadratic form of the coordinate matrix CC
T,b) framing the quadratic form of the coordinate matrix CC
T by the incidence matrices Sn and STn of the complete oriented graph Kn: SnCCTSTnc) extracting the diagonal of the product SnCCTSTn,
d) transforming the diagonal of SnCCTSTn by framing it as STn(*)Sn into the square n*n matrix, which off-diagonal elements are squadred mutual distances of points with given coordinates, and the diagonal elements are their row (column) sums.
In the used example, we get the quadratic distance matrix of cycle C4 having form (Q - D), where Q is the diagonal matrix of distance sums and D is the conventional distance matrix
|
4 |
-1 |
-2 |
-1 |
|
-1 |
4 |
1 |
-2 |
|
-2 |
-1 |
4 |
-1 |
|
-1 |
-2 |
-1 |
4 |
The form and properties of the quadratic distance matrix (Q - D) correspond to the form and properties of the Laplace-Kirchhoff matrix, which is obtained similarly by transforming the diagonal of adjacencies by framing it with S
Tn(*)Sn into the square n*n matrix. In simple graphs without multiple arcs and loops the adjacencies aij are just inverse distance (dij)-1.The diagonal of adjacencies can be framed with the incidence matrix G of the complete oriented graph Kn, also: G
Tn(*)Gn transforms the matrix (*) into the square n*n matrix. In this case we get positive off-diagonal elements (Q + D). The matrix (Q + D) was introduced by Diudea [8]5. Resistance distances
The incidence matrix S of the simple cycle C4 has the rooted incidence matrix
|
1 |
0 |
0 |
0 |
|
-1 |
1 |
0 |
0 |
|
0 |
-1 |
1 |
0 |
|
0 |
0 |
-1 |
1 |
|
1 |
0 |
0 |
-1 |
Since it has five rows and four columns it is singular, as is the code matrix of the unit square. Therefore it does not have the inverse but its quadratic form S
TS has, because it is overdetermined.The unit column J is the zero eigenvector from the right of all incidence matrices S. The matrix JJT leaves on the place of perturbation 1 in the first row and zeroes in in other rows of any Laplace-Kirchhoff matrix multiplied by it from the right. The root row must be balanced by the submatrix, which is inverse to J jSTS, where J jSTS is the matrix STS with the deleted j-th row and j-th column (here the first ones) [9]. The incidence matrix S of a cycle with a column deleted is identical with the transposed matrix of the linear chain Ln: J jS(Cn) = ST(Ln). Its inverse is the quadratic form WTW of the path matrix. The chain forms the spanning tree of the cycle. Its square matrix is decomposed into triangular form and added to the matrix JJT. Since WTW as it was originally defined to avoid fractions gives nI as the product with SST, it is necessary to divide it by n. So we have
|
W T |
|
W TW |
|
Triangular decomposition |
|||||||||
|
Square roots |
|||||||||||||
|
1 |
1 |
1 |
0 |
0 |
0 |
3 |
2 |
1 |
3/4 |
0 |
0 |
||
|
0 |
1 |
1 |
1 |
1 |
0 |
2 |
4 |
2 |
1/3 |
2/3 |
0 |
||
|
0 |
0 |
1 |
0 |
1 |
1 |
1 |
2 |
3 |
1/12 |
1/6 |
1/2 |
||
The diagonal elements of the quadratic form W
TW give resistance distances [10] (as in electrical circuits of the Kirchhoff problem) of the vertices from the root [6,7]. Other distances can be extracted from the inverse as before by the graph algorithm. We got the matrix (Q - D) (its 4 multiple|
10 |
-3 |
-4 |
-3 |
|
-3 |
10 |
-3 |
-4 |
|
-4 |
-3 |
10 |
-3 |
|
-3 |
-4 |
-3 |
10 |
The elements dij can be calculated directly as (1/dl + 1/dr )
-1, where dl and dr are the left and right distances from the root i to the vertex j, respectively. The fractions are known as conductivities. Multiple bonds which increase the conductivity and decrease distances between vertices are expressed in the incidence matrices S by repeating existing rows.Now, we have two distance matrices for graphs with circuits. One is obtained from coordinates of vertices, the second from the rooted Laplace-Kirchhoff matrix. To the matrix of resistance distances can be found matrices of coordinates of vertices [7] giving these distances. It seems like as if the rooting is deforming the original form of the graph.
6. Eichinger matrices
In the theory of polymer chains mechanics [11,12], two matrices of linear chains Ln has been used known as Rouse R and Forsman F matrices. The Rouse matrix is identical with the Laplace-Kirchhoff matrix of the linear chain Ln. The Forsman matrix is the generalized inverse (again its n multiple) of the Rouse matrix
RF = nI - JJ
Having difficulties with understanding the Forsman matrices, I noticed that their trace gives the Wiener number, more precisely, its double, since their diagonal elements are sums of distances to other vertices. The off-diagonal elements are distances unpassed in the paths between pairs of vertices i and j. It was then rather easy to generalize the relation on all trees and to give its proof [9]. In graphs with cycles the existence of the generalized inverse is based on reconstruction of the eigenvalue polynomial from the Ulam subgraphs polynomials. Indeed there are infinitely many generalized inverses [13] but generalized inverses of trees defined by distances are unique since they are derived as sums of partial inverses. They can be found for all Laplace-Kirchhoff matrices as Eichinger matrices E
E =
There are n partial inverses with (n - 1) unit elements in the sum therefore we get (n - 1) multiple of I on the diagonal of the generalized inverse.
7. Wiener number on the trace
Now, there are tree types of matrices which trace is the Wiener number or its double: W
TW, (Q - D) and E.It is well known that the Laplace- Kirchhoff matrices of complete graphs have (n-1) eigenvalues equal to n and one zero eigenvalue. Both quadratic forms STS and SST have the same eigenvalues except for the zero eigenvalue at SST, where they correspond to the number of cycling arcs or multiple bonds expressed as separate rows in S.
The eigenvalues xj of WTW must be inverse to STS, more exactly, they are fractions n/xj to give
WTWSST = nI.
The same is true for Eichinger matrices E but since their trace is twice the Wiener number, the Wiener number appears as the eigenvalue matching with the zero eigenvalue of the Laplace-Kirchhoff matrix.
The definition of Eichinger matrices E makes it possible to find eigenvalues of the Laplace-Kirchhoff matrices of complementary graphs. The complete graph K is the sum of the graph G and its complement G*: K = G + G*. Therefore
STS(G)E = STS(K) = STS(G) + STS(G*)
and by subtracting STS(G) from both sides we get
STS(G)(E - I) = STS(G*).
From this relation follows that eigenvalues of the Laplace- Kirchhoff matrix of the complementary graph STS(G*) must be (n - xj).
This gives us a hint what eigenvalues of the quadratic distance matrix (Q - D) are. At complete graphs Kn, the answer is trivial. Since the complementary graph to the complete graph K n is empty, and the spectrum of (Q - D)(Kn) is identical with the spectrum of STS(Kn).
At graphs with the diameter 2, the spectrum of (Q - D) is (n + xj), where xj eigenvalues are of the complementary graph. For example, the stars Sn have values of Q: (n-1), (2n-3)n-1. The eigenvalues of their quadratic distance matrix (Q - D) are n, (2n-1)n-2, 0. Both sums give the trace 2n2 + 4n + 2.
The same is true for graphs with larger diameters. They can be interpreted as matrices of the complete graphs Kn with multiple bonds. It seems to be obvious, but this leads to graphs with imaginary arcs. The complementary Laplace-Kirchhoff matrix to the graph with double arc *=*-* is
|
S TS |
|
2I-JJ T-STS |
||||
|
2 |
-2 |
0 |
0 |
1 |
-1 |
|
|
-2 |
3 |
-1 |
1 |
-1 |
0 |
|
|
0 |
-1 |
1 |
-1 |
0 |
1 |
|
The complementary matrix is obtained as the quadratic form S
TS of the incidence matrix ST with irrational numbers with its transpose|
-i |
i |
0 |
|
-1 |
0 |
1 |
So the Wiener path leads to graphs in complex space.
8. Wiener number as the eigenvalue
I met the Wiener number even as the lowest eigenvalue of the distance matrix D, derived from the line which coordinates were (0, 1, 2, 3, ..n-1)
T [14]. The distances in the matrix are squared by the algorithm shown above, similarly as distances of trees embedded in multidimensional cubes are. The are only three nonzero eigenvalues. This corresponds to the symmetry of a stiff rod whereas distance matrices of "linear chains" have all one positive and (n -1 ) negative eigenvalues [14].John published [15] an algorithm for calculation of the Wiener number of square and equilateral triangle lattices of any dimension. He clamed planarity of lattices but the algorithm fails to distinguish between distances in two of three configurations of 6 points with coordinates
A (1,1,0,0) (1,1,1,0) (1,1,1,1)
(1,0,0,0) (1,0,1,0)
(0,0,0,0)
B (0,0) (0,1) (0,2)
(1,0) (1,1)
(2,0)
C (2,0,0) (1,1,0) (0,2,0)
(1,0,1) (0,1,1)
(0,0,2)
The configurations A and B correspond to square lattices, the configuration C to the equilateral triangle lattice, respectively. But it is doubtful if the configuration A is planar.
The John´s algorithm gives for A and B the same result unless we count the straight orthogonal distances as their squares. In the case C, The John´s algorithm gives the true values for both moment distances. The scaling factor 1/2 appears as constant decreasing the length of distances between points, either as direct counts, e. g. 1/2[(2,0,0) - (0,1,1)] = 2, or as squared distances 1/2[(4,0,0) - (0,1,1)] = 3. Here 1/2 is the square of the square root.
The calculations using the Altenburg polynomial [16], that is lumping the number nk of distances of same lengths W = n kdk, agree with the results of the John´s algorithm, counting separately all distances in different directions in distance matrices:
The Altenburg polynomial W =
S nxdx [14]|
distances |
1 |
2 |
3 |
4 |
5 |
8 |
W |
|
A |
6 |
6 |
2 |
1 |
0 |
0 |
28 |
|
B |
6 |
4 |
0 |
4 |
5 |
1 |
40 |
|
Cd |
9 |
6 |
0 |
0 |
0 |
0 |
21 |
|
Cs |
9 |
0 |
3 |
3 |
0 |
0 |
30 |
The John´s algorithm
|
A |
6 |
6 |
B |
6 |
12 |
|
|
|
2 |
|
|
2 |
|
2*14 = 28 |
2*20 = 40 |
||||
|
Cd |
2 |
6 |
|
Cs |
2 |
12 |
|
|
|
6 |
|
|
|
6 |
|
2/3*14 = 21 |
|
2/3*20 = 30 |
||||
9. Discussion
It should be mentioned, that the distance matrix D of a tree is a part of the left hand inverse of its incidence matrix S: STDS = -2I. Rutherford [17] found this property solving the Kirchhoff problem, and I identifiing elements of Eichinger matrices as distances and became curious. This follows from the orthogonality of arcs in trees [14].
The Wiener number is not just some number or an indicator or an index because it is connected with physical properties. It links properties of molecules which are formed by complicated inner processes with their abstract structures [11,12,16].
The Wiener number can be decomposed into eigenvalues of given matrices or into the Altenburg polynomial [18]. Different eigenvalue decompositions of the Wiener number do not improve correlations with physical properties [19], but the polynomial decomposition does. Wiener himself [1] specified in his equation the distance d = 3 as having a specific effect. But this can be an artefact.
The Wiener path led me to the question of dimensionality of graphs [19]. In literature can be found different answers, graphs are considered as dimensionless, one dimensional, and or two dimensional objects.
A dictionary definition of dimension is extension in a single direction. I have shown how from a n*k matrix, n(n-1)/2 distances are obtained and how these distances are packed back into quadratic n*n matrix. This algorithm gives consistent results. We should accept these facts.
On the wall of the scull cave we live in, two dimensional figures of the outside world are projected by the eye nerves. We recognize the third dimension automatically by efforts of our eye muscles foccusing both eyes without our consciousness. We do not see higher dimensions, we find their traces only by efforts of our brains or computers as external brain extensions as are telescopes and microscopes for eyes. But we should accept what we know and not hide it behind stochastic variables and other abstract notions as is usually done by mathematicians. This topics was discussed by Weinberg [20].
References
[1] M. Kunz, About metrics of bibliometrics, J. Chem. Inform. Comput. Sci., 33, (1993) 193-196.
[2] H. Wiener, Structural determination of paraffin boiling points, J. Am. Chem. Soc., 69, (1949) 17-20.
[3] D. Cvetkovic, M. Doob, H. Sachs, Spectra of Graphs, Deutcher Verlag der Wissenshaften, Berlin, 1980.
[4] M. Kunz, Path and walk matrices of trees, Coll. Czech. Chem. Commun., 54 (1989) 2148- 2155.
[5] M. Aissen and B. Shay, Numerical codes for operation trees, In Graph Theory and Its Applications: East and West, Capobianco, M. F.; Guan, M.; Hsu, D. F.; Tian,F., Eds., Annals of the New York Academy of Sciences,1989, Vol. 576, 1.
[6] M. Kunz, Inverting Laplace-Kirchhoff matrices from their roots, J. Chem. Inform. Comput. Sci., in press.
[7] M. Kunz, An equivalence relation between distances and coordinate matrices, MATCH, 32 (1995) 193-203.
[8] M. V. Diudea, Molecular Topology 23. Novel Schultz Analogue Indices, MATCH, 32 (1995), 85-103.
[9] M. Kunz, A Moebius inversion of the Ulam subgraphs conjecture, J. Math. Chem., 9 (1992) 297-305.
[10] D.J. Klein and M. Randic, Resistance distance J. Math. Chem., 12, (1993), 81-95.
[11] B.C. Eichinger, Configuration statistics of Gaussian molecules, Macromolecules, 13 (1980) 1-11.
[12] B.C. Eichinger, Shape distributions of Gaussian molecules, Macromolecules, 18 (1985) 211-216.
[13] M. Kunz, Inverses of perturbed Laplace-Kirchhoff and some distance matrices, MATCH, 32, (1995) 221-234.
[14] M. Kunz, Distance matrices yielding angles between arcs of the graphs, J. Chem. Inform. Comput. Sci., 34, (1994) 957- 959.
[15] P. E. John, Über die Berechnung des Wiener-Index für ausgewählte delta-dimensionale Gitterstructuren, MATCH, 32, (1995) 207-219.
[16] K. Altenburg, Zur Berechnung des Radius verzweigter Molekule, Kolloid Zeits., 178 (1961) 112-119.
[17] J.S. Rutherford, Theoretical prediction of bond- valence networks, Acta. Cryst., B46 (1990) 289-292.
[18] M. Kunz, Wiener number desintegrated, J. Serb. Chem. Soc., submitted.
[19] M. Kunz, On topological and geometrical distance matrices, J. Math. Chem., 13 (1993) 145-151.
[20] S. Weinberg, The Unifying Thread in Science, Notices AMS, 13, (1986) 716-733.