|
|
About eigenvalues of quadratic distance matrices of planar orthogonal objects
Corrected version.
Abstract
The quadratic distance matrices of planar (two dimensional) orthogonal objects have only four nonzero eigenvalues. It is conjectured that this is connected with their symmetry. For some configurations, there were determined the lowest eigenvalues. When right angles are distorted, the number of nonzero eigenvalues increases.
Introduction
Distance matrices D, which elements d(ij) are the distances between points i and j, are well known and studied.
There are topological distance matrices, where distances are counted as paths in graphs, and geometrical distance matrices, where distances are measured in 3 dimensional space [1, 2]. These distances are Euclidean ones.
I found [3], that the distance matrices give angles between arcs, and that the topological distances are in fact squared distances in n-dimensional space. To show that the points lie on a straight line, it is necessary to use squared distances, as 0, 1, 4, 9, 16 ...
Such distance matrices of straight lines have only three nonzero eigenvalues corresponding to symmetry elements of a straight line.
Here, some orthogonal configurations of points in two dimensions are studied. All have at most four nonzero eigenvalues. In some instances, it was rather easy to find formulas for evaluating their lowest eigenvalues.
The solution for two positive orthogonal axes
Two positive orthogonal axes, or otherwise, a straight line bent in the middle in the right angle. The number of points on each branch being k, n = 2k +1.
The example: The distance matrix (7, 7) has the form
0 |
1 |
1 |
4 |
4 |
9 |
9 |
1 |
0 |
2 |
1 |
5 |
4 |
10 |
1 |
2 |
0 |
5 |
1 |
10 |
4 |
4 |
1 |
5 |
0 |
8 |
1 |
13 |
4 |
5 |
1 |
8 |
0 |
13 |
1 |
9 |
4 |
10 |
1 |
13 |
0 |
18 |
9 |
10 |
4 |
13 |
1 |
18 |
0 |
The growing matrices have eigenvalues:
Value k
1: +2.7321, -0.7321, - 2.
2: +13.9525, -0.3153, - 3.6342, -10, 0.
3: +39,1512, -0,8316, -10,3195, -28, 0, 0, 0.
There are always at most four nonzero eigenvalues corresponding to elements of symmetry. The lowest eigenvalue of these distance matrices is twice the sum of squared distances i, i going from 1 till k = (n-1)/2.
The eigenvectors have values 0, +j/k and -j/k. These eigenvectors form differences of two consecutive vertices j and j+1, which are symmetrical according to the plane of symmetry lying between both axes. These differences can be tabulated as (always for two symmetrical columns)
2 |
4 |
6 |
8 |
... |
4 |
8 |
12 |
16 |
... |
6 |
12 |
18 |
24 |
... |
8 |
16 |
24 |
32 |
|
... |
... |
... |
... |
|
The elements of the difference tables are twice the products ij. Finding scalar products with the eigenvectors, we get the sums of 2jii/k, both i and j going from 1 till k. These sums can be split as j/k, which is the corresponding eigenvector, and twice the sum of squared indices i, which is the lowest eigenvalue.
This eigenvector has very simple form, which corresponds to the notion of symmetry plane. On the other hand, the topological distance matrix or the geometrical distance matrix with straight distances have no simple eigenvectors.
Two crossed orthogonal axes
Two crossed orthogonal axes with the same positive and negative parts have also only four nonzero eigenvalues.
The example: The matrix (9, 9) of the cross with nine vertices has the form
0 |
1 |
1 |
1 |
1 |
4 |
4 |
4 |
4 |
1 |
0 |
2 |
4 |
2 |
1 |
5 |
9 |
5 |
1 |
2 |
0 |
2 |
4 |
5 |
1 |
5 |
9 |
1 |
4 |
2 |
0 |
2 |
9 |
5 |
1 |
5 |
1 |
2 |
4 |
2 |
0 |
5 |
9 |
5 |
1 |
4 |
1 |
5 |
9 |
5 |
0 |
8 |
16 |
8 |
4 |
5 |
1 |
5 |
9 |
8 |
0 |
8 |
16 |
4 |
9 |
5 |
1 |
5 |
16 |
8 |
0 |
8 |
4 |
5 |
9 |
5 |
1 |
8 |
16 |
8 |
0 |
The growing matrices have eigenvalues:
Value k
1: 8.4721, -0.4721, -4, -4, 0.
2: 44.7386, -4.7386, -20, -20, 0, 0, 0, 0, 0.
The corresponding eigenvector for the last cross is:
0, -0.5, 0, 0.5, 0, -1, 0, 1, 0.
The lowest eigenvalue (20) is the four times sum of squared distances on axes, 4(1 + 4), or the sum of the squared doubled distances (4 + 16). The lowest eigenvalue is doubled, since there are two equivalent symmetry axes.
Three axes, two (i, j) lying on the straight line, the third one k orthogonal to them in their center, have also at most four nonzero eigenvalues.
*
* * * * *
The example: The matrix (7, 7) with three axes, k = 2, has the form
0 |
1 |
1 |
1 |
4 |
4 |
4 |
1 |
0 |
2 |
2 |
5 |
5 |
1 |
1 |
2 |
0 |
4 |
1 |
9 |
5 |
1 |
2 |
4 |
0 |
9 |
1 |
5 |
4 |
5 |
1 |
9 |
0 |
16 |
8 |
4 |
5 |
9 |
1 |
16 |
0 |
8 |
4 |
1 |
5 |
5 |
8 |
8 |
0 |
The eigenvalues for the values of the central axis k = 1 are:
Value k= 1: 5.9587, -0.4428, -1.5159, -4.
2: 25.3144, -1.4204, -3.8942, -20.
3: 68.5974, -1.5521, -11.0452, -56.
The eigenvalues for the values of the central axis k = 2 are:
Value k= 1: 11.3613, 0.8675, -4, -6.4938.
2: 31.2696, -3.4660, -7.4660, -20.
3: 75.4431, -6.9536, -12.4895, -56.
Here, the eigenvalue -4 for k = 1 is not the lowest one, since its element of the symmetry is overwhelmed by the element of the symmetry of the longer branch. The lowest eigenvalues are the same as at the crossed axes. The corresponding eigenvector splits the straight line in equal distances from -1 over 0 to 1. This eigenvector is very simple and differs from the eigenvectors of the topological distance matrix, which elements are not as simple, as well as from the eigenvectors of the geometrical distance with straight distances.
A column of square tiles
Two parallel lines form a column of tiles. It is possible to form boards with more lines of points. m will be the number of points in the columns, n the number of points in the rows. Thus, the size of matrix is mn. For n = 2, starting from n = 3, the eigenvector values are doubled and span from 1 to -1 with the step 2/(1-n). The elements of the last columns are always the pairs of distances (n-k)2 +1 and (n-k)2. The corresponding sums are consecutively: 2, 8, 20, 40, 70...
Nine points
The distance matrix of nine points arranged into a square has only four nonzero eigenvalues. They are: 25.2787, 12, 11.4793, 1.7989. The 9 point rhomb with 60 degrees angles has 6 nonzero eigenvalues:
26.3971, 1.6954, -1.0034, -6.4383, -17.6954.
Discussion
I conjectured that the number of nonlinear eigenvalues is connected with the dimensionality. This conjecture is wrong, since the shown couterexample has more eigenvalues.
There are two problems connected with the distance matrices with squared distances. The first of them is their eigenvectors, how to interpret them as the symmetry elements.
For example, for 9 point forming the square, there are eigenvectors, arranged into matrices as:
1,00 |
0,71 |
1,00 |
0,71 |
0,42 |
0,71 |
1,00 |
0,71 |
1,00 |
or
1,00 |
0,50 |
0,00 |
0,50 |
0,00 |
-0,50 |
0,00 |
-0,50 |
-1,00 |
or
0,00 |
-0,50 |
-1,00 |
0,50 |
0,00 |
-0,50 |
1,00 |
0,50 |
0,00 |
The first example can be explained as the rotation axis orthogonal to the plane or by the existence of two reflexion axes in the plane. The eigenvalues depend on the distance from the center.
The second example is symmetrical according to the main diagonal, the eigenvalues decrease from 1 to -1, or otherwise, they change signs according to the side diagonal.
The third example is symmetrical according to the side diagonal, the eigenvalues grow from -1 to 1, or otherwise, they change signs according to the main diagonal.
But the main problem of the distance matrices with squared distances is, how to interpret such squared distances, since our experience is connected with linear distance measures. In some cases there exist functions of squared distances. For example, gravitation is proportional to the inverse of squared distances between objects.
Literature
1. B. Bogdanov, S. Nikolic and N. Trinajstic, On the three dimensional Wiener index, J. Math. Chem., 3 (1989) 299-309.
2. Z. Mihalic, D. Veljan, D. Amic, S. Nikolic, D. Plavsic and N. Trinajstic, The distance matrix in chemistry, J. Math. Chem., 11 (1992) 223-258.
3. M. Kunz: Distance matrices yielding angles between arcs of the graphs, J. Chem. Inform. Comput. Sci., 34, (1994) 957-959.