Deviation transformation and its use to determine the coordinate system for a set of distances

Introduction

Applied mathematics can be considered as a set of tools that allow solving various problems arising in practice. In this article we will consider one of these tools - the transformation of the deviation applied to the analysis of the matrix of Euclidean distances . The spectrum of the resulting matrix allows to judge the dimension of the source data and calculate the coordinates of the original points relative to its own center of coordinates.

Suppose we have n > 2 points and we know all the distances between them. Potential dimensionality of space is n-1 . It is necessary to determine the space of a dimensionality given points, as well as the coordinates of points in this space.
One of the indirect ways of determining the dimensionality of space based on the distance between points is the calculation of the Cayley-Menger determinant (KM) . However, this method is unsuitable for the analysis of spaces of large dimension.

1. Conversion deviation

So, we have at the input a certain symmetric matrix M of dimension N with zero trace (the elements of the main diagonal are equal to zero). We need to define a transformation to some new matrix U. The values ​​of the original matrix should be calculated from the new by the rules of the addition of distances:


')
Then the values ​​of the matrix M can be expressed in terms of the spectrum U as a weighted sum of the difference of squares of the components of the eigenvectors:



Here - a set of eigenvalues ​​of the matrix U , and - matrix of eigenvectors corresponding to eigenvalues. The length of the vectors is normalized to 1.
The general form of the matrix U , satisfying condition (1.1), is the expression:



Here Is an arbitrary vector, and Is an arbitrary constant. To determine these values, you must specify additional conditions. Such a condition is the requirement of the Laplacian similarity of the matrix U. In the matrix of the Laplacian, the elements of the main diagonal are equal to the sum of the elements of the corresponding column (row) with the opposite sign:



Substituting (1.3) into (1.4) taking into account the symmetry of M , we obtain the identity:



from which we define the desired expressions for the vector and the constant:




Thus, the vector in (1.3) is the vector of the average values ​​of the row (column) of the original matrix (in terms of graphs, the mean cardinality / degree of the graph vertex), and the constant is the average value of the matrix as a whole (the average degree of the graph vertices):



The transformation (1.3 ') we called the deviation transformation , since it reflects the deviation (deviation) of the values ​​of the original matrix from the average values. The result of the transformation will be called the deviation matrix .

2. Properties of the deviation matrix

The matrix is ​​degenerate (zero determinant and one of the eigenvalues) is a consequence of the Laplacian requirement.
The elements of the main diagonal of the deviation reflect the average values ​​of the original matrix:



The deviation trace is associated with the average value of the initial matrix and can be expressed in terms of the sum of the eigenvalues:



The product of the eigenvalues ​​is proportional to the potential deviation - a non-zero minor of the matrix:



Deviation is reversible. Based on the deviation matrix, you can restore the original:



Note that the deviation transform is abstract and is not associated precisely with the metric matrix. Thus, the application of the deviation transform to the matrix of resistive distances allows us to obtain the inverse matrix of the Laplacian from the conduction matrix. That is, in the end, to restore the matrix of conductivity on the matrix of resistive distances.

Next, we consider the application of the transformation of the deviation to the metric matrix (Euclidean distances).

3. Deviation of distances, own coordinate system

So, let at the entrance we have a set of points with given distances between them. All distances are known — between any pair — the distance graph is complete. Here we consider the direct problem - it is necessary to determine the dimension of the space to which the points and their coordinates in the given space belong.

The initial set of distances is represented in the form of a symmetric matrix of squares of distances between points. We denote this matrix as D2 , where two means square. The application of the deviation operation to the matrix of squares of distances gives the matrix of the deviation of distances G :



This matrix and its spectrum have remarkable properties. Namely:

• The number of nonzero eigenvalues ​​(the rank of the matrix) coincides with the dimension of the space in which the initial points are located.
• The values ​​of the eigenvectors are the coordinates of points in the new space.
• The symmetry of eigenvalues ​​reflects the symmetry of the relative position of points.

Thus, the spectrum of the distance deviation matrix determines its own coordinate system of the original set of points. The weight of each coordinate is determined by the value of the spectrum (its own number). The center of the new coordinate system is called the centroid . On the main diagonal of the deviation matrix are located the squares of the distance from the centroid to the vertices:



The sum of all such distances (deviation trace) determines the average radius of the set R2 . This radius is equal to the sum of the spectrum values ​​and is related to the average value of the original distance matrix in accordance with formula (2.2):



The centroid of the set minimizes the average dial radius. That is, for any other position of the centroid, the average dialing radius will be more significant. Adding the centroid itself to the original set of points does not change the spectrum, since the centroid of the new set coincides with the old one.

4. Spectra of some sets

Spectra of three vertices (triangles)

So, we got a hammer in our hands. Looking for nails.
For one / two points, there is no special meaning to apply the deviation matrix. Two non-identical points always belong to the same straight line, that is, one-dimensional space.
But for three points options already appear. The simplest case is the vertices of an equilateral triangle. If the side length is 1, then the deviation matrix will look like:



The trace of this matrix is ​​1, and the potential (1/3) ^ 2 - (1/6) ^ 2 = 1/9 - 1/36 = 1/12.
Consider the spectrum (in brackets are the squares of the distances between the points):



Here, on the left, the eigenvalues ​​of the spectrum are shown, and on the right, the corresponding values ​​of the vectors (coordinates).
We see that:

• The spectrum has two meanings. This is understandable - a non-degenerate triangle always belongs to a 2-dimensional space (plane).
• Both eigenvalues ​​are equal. This is a consequence of the symmetry of an equilateral triangle.

Let's check the properties of the spectrum: the sum of the eigenvalues ​​is 1, the product is 1/2 * 1/2 = 1/4 = 1/12 * 3. That's right.

In passing, we note that the spectrum of the three vertices is related to the area of ​​the triangle formed by them (a kind of Heron's formula):



Accordingly, the square of the area of ​​an equilateral 1-triangle is 3/4 * 1/4 = 3/16.

Moving on. If the points belong to one straight line, then the spectrum should contain only one value.
Calculate the value of the spectrum for the three points of the segment (two on the edges and one in the middle) . We get:



Indeed, the spectrum contains only one component. The centroid is in the middle of the segment, as expected.

Now we will ask a tricky question - what space does an impossible triangle belong to, that is, the one in which the triangle inequality is violated?


If the spectrum contains negative values, then this means that in a Euclidean space a set of points with such characteristics cannot be realized — the coordinates of the points become imaginary. You can use this spectrum property to check the validity of the distance matrix.

Respite

Let's pause and look around. We defined the deviation transform and applied it to a matrix of squares of distances. The resulting distance deviation matrix reflects the properties of the space of the original set of points.

Numerically check the described properties for small matrices can be done interactively using spreadsheets and the wolframalpha service to calculate eigenvalues ​​/ vectors.

If there are no large objections, then in the next article we will continue to consider the spectral properties of some standard sets of geometric points - gratings, figures, lines, and also look at the spectra of sets of figures.

Continued ...