Data geometry 3. Scalar product of pairs

The distance invariant (squared distance) between elements can be generalized by multiplying the difference of elements not by itself, but by another difference of elements. The resulting value will reflect the scalar product of ordered pairs .

Table of contents

1. Simplexes and graphs
2. Definition of di- and bi-coordinates
3. Scalar product pairs
4. The space of the graph
5. Base conversion
6. Count star

Ordered pair

The coordinates of the vector can be obtained as the difference of the coordinates of the elements, but the reverse is not true - the coordinates of the elements forming it cannot be reconstructed from the coordinates of the vector. The coordinates of the two elements carry more information than the coordinates of the vector. Therefore, one can form a pair of elements - an improved analogue of the vector. Such a set of two elements is called an ordered pair .

Each ordered pair can be mapped a vector - the difference of the elements forming a pair. For two vectors, you can define the scalar product, which can also be considered as a characteristic of the four elements of space.
')

Scalar product

To reduce bulkiness in this part, we denote elements by lowercase characters. A pair is a combination of two elements:

(i, j)

$(i, j)$ . The vector corresponding to the pair is the difference of the elements of the pair:

m a t h b f v_{i j} = j - i q u a d (3.1)

$\ mathbf {v} _ {ij} = j - i \ quad (3.1)$

The element rate is its scalar product with itself:

n_{i} = i c d o t i q u a d (3.2)

$n_i = i \ cdot i \ quad (3.2)$

The same definition can be used for the vector of a pair, which is known to reflect the square of the distance between the elements of the pair:

q_{i j} e q u i v n_{i j} = (j - i) c d o t (j - i) q u a d (3.3)

$q_ {ij} \ equiv n_ {ij} = (j - i) \ cdot (j - i) \ quad (3.3)$

If two different pairs are given

(i, j)

$(i, j)$ and

(k, l)

$(k, l)$ then the scalar product can be defined between the corresponding vectors:

g_{i j, k l} = (j - i) c d o t (l - k) = m a t h b f v_{i j} c d o t m a t h b f v_{k l} q u a d (3.4)

$g_ {ij, kl} = (j - i) \ cdot (l - k) = \ mathbf {v} _ {ij} \ cdot \ mathbf {v} _ {kl} \ quad (3.4)$

Indices

i j

$ij$ ask one pair, and indexes

k l

$kl$ - another.

Expression (3.4) defines a scalar depending on the relative position of the 4 elements. It is important that this scalar can be expressed in terms of the distances between the elements.

q_{i j}

$q_ {ij}$ .

As is known, the distance between the elements is associated with the scalar product between them:

q_{i j} = n_{i} - 2 g_{i j} + n_{j} q u a d (3.5)

$q_ {ij} = n_i - 2 g_ {ij} + n_j \ quad (3.5)$ .

Expanding the product (3.4) with (3.5) taken into account, we obtain:

g_{i j, k l} = (q_{i l} + q_{j k} - q_{i k} - q_{j l}) / 2 q u a d (3.6)

$g_ {ij, kl} = (q_ {il} + q_ {jk} - q_ {ik} - q_ {jl}) / 2 \ quad (3.6)$

This is the general formula for the scalar product of pairs. The order of the indices is important - it sets the pairs and the direction of the corresponding vectors.

Expressions like (3.6) often appear in different places in mathematics. This is due to the generality of the output of this formula. Note that we used only the most general properties of an algebraic expression. Therefore, any elements for which the product operation is defined can be used as elements. The identity will be true for them, in general form, it looks like this:

(A - B) c d o t (C - D) = ((A - D)^{2} + (B - C)^{2} - (A - C)^{2} - (B - D)^{2}) / 2 q u a d (3.6.1)

$(A-B) \ cdot (C-D) = ((A-D) ^ 2 + (B-C) ^ 2 - (A-C) ^ 2 - (B-D) ^ 2) / 2 \ quad (3.6.1)$

Couples with a common vertex - adjacent pairs

If couples have a common vertex

(k e q u i v l)

$(k \ equiv l)$ , the formula (3.6) is simplified:

g_{k i, k j} = (q_{i k} + q_{j k} - q_{i j}) / 2 q u a d (3.7)

$g_ {ki, kj} = (q_ {ik} + q_ {jk} - q_ {ij}) / 2 \ quad (3.7)$

Formula (3.7) is the cosine theorem for a triangle. Here the pairs between which the mutual norm is defined have a common element k - adjacent pairs.

Three scalar products can be defined on 3 vertices. Their sum is expressed in terms of the sum of the distances between the vertices:

g_{k i, k j} + g_{i k, i j} + g_{j i, j k} = (q_{j k} + q_{i k} + q_{i j}) / 2 q u a d (3.8.1)

$g_ {ki, kj} + g_ {ik, ij} + g_ {ji, jk} = (q_ {jk} + q_ {ik} + q_ {ij}) / 2 \ quad (3.8.1)$

The square of the scalar product on 3 vertices is related to the area of the triangle formed by them

s_{i j k}

$s_ {ijk}$ (Heron's formula):

4 s_{i j k}^{2} = q_{i k} q_{j k} - (g_{i k, j k})^{2} q u a d (3.8.2)

$4 s_ {ijk} ^ 2 = q_ {ik} q_ {jk} - (g_ {ik, jk}) ^ 2 \ quad (3.8.2)$

Independent pairs - four different peaks

In the general case, the vertices of the pairs may not lie in the same plane, therefore, this definition of the scalar product cannot always be associated with the cosine of the angle between the directions.

We list the properties of the scalar product (3.6).

1) Does not depend on the permutation of pairs:

g_{i j, k l} = g_{k l, i j} q u a d (3.9.1)

$g_ {ij, kl} = g_ {kl, ij} \ quad (3.9.1)$

2) Antisymmetric with respect to permutation of elements in a pair

i j

$ij$ or

k l

$kl$ :

g_{i j, k l} = - g_{j i, k l} = - g_{i j, l k} q u a d (3.9.2)

$g_ {ij, kl} = -g_ {ji, kl} = -g_ {ij, lk} \ quad (3.9.2)$

3) For 4 elements there are only two independent scalar products of pairs due to the identity:

g_{i j, k l} + g_{i k, l j} + g_{i l, j k} = 0 q u a d (3.9.3)

$g_ {ij, kl} + g_ {ik, lj} + g_ {il, jk} = 0 \ quad (3.9.3)$

Mathematicians will see in formula (3.9.3) the first Bianchi identity . From which it can be concluded that the structures of the curvature tensor (Riemann) and the scalar product of pairs are similar.

4) The rate of independent pairs can be expressed in terms of the difference between the rates of adjacent pairs:

g_{i j, k l} = g_{i j, i l} - g_{i j, i k} q u a d (3.9.4)

$g_ {ij, kl} = g_ {ij, il} - g_ {ij, ik} \ quad (3.9.4)$

We will use this identity in the next article.

5) Distance between elements

i

$i$ and

j

$j$ can be expressed in terms of the scalar products of adjacent and independent pairs:

q_{i j} = g_{i j, i k} - g_{i j, j k} = g_{i l, i k} + g_{j l, j k} - g_{i l, j k} - g_{j l, i k} q u a d (3.9.5)

$q_ {ij} = g_ {ij, ik} - g_ {ij, jk} = g_ {il, ik} + g_ {jl, jk} - g_ {il, jk} - g_ {jl, ik} \ quad ( 3.9.5)$

Pairs on the basis elements

As the elements forming a pair, the vertices of the base can be chosen. Then the scalar product of pairs becomes a tensor - a set of scalar products between all possible pairs of elements of a given basis. To distinguish tensors from scalars, we will use capital letters for the first ones. That is, instead of a scalar

g_{i j, k l}

$g_ {ij, kl}$ for the basis elements, we obtain the tensor

G_{i j, k l}

$G_ {ij, kl}$ .

Scalar Product and Laplacian Cofactors

The scalar product of pairs formed by elements of the basis can be expressed in terms of the properties of the Laplacian of the basis.

If two pairs of vertices are given

(i, j)

$(i, j)$ and

(k, l)

$(k, l)$ , the value of their scalar product can be obtained by dividing the cofactor of the 2nd order

U_{i j, k l} (L)

$U_ {ij, kl} (L)$ on the scalar potential of the laplacian

u (L)

$u (L)$ :

G_{i j, k l} = U_{i j, k l} (L) / u (L) q u a d (3.10.1)

$G_ {ij, kl} = U_ {ij, kl} (L) / u (L) \ quad (3.10.1)$

Cofactor

U_{i j, k l}

$U_ {ij, kl}$ is called the determinant of the minor of a square matrix (taking into account the sign). Scalar potential

u (L)

$u (L)$ - this is a cofactor of the 1st order from the Laplacian (see (1.12) from the first article ).

Thus, it is necessary to remove the columns corresponding to one vector from the Laplacian matrix (in the formula, this

i, j

$i, j$ th columns), and rows corresponding to another (

k, l

$k, l$ ), after which the determinant of the resulting minor is divided by the scalar potential

u (L) = d e t^{'} (L)

$u (L) = det '(L)$ . If the deleted columns and rows of the Laplacian are the same, then we obtain the value of the distance between the nodes.

Dot scalar product on a graph

Between any pairs of vertices of the graph, you can define their mutual norm - the scalar product. Since the graph is usually given by the Laplacian, the formula (3.10.1) can be used for the calculation.

Let, for example, be chosen as the generating vertices of two pairs -

A, B

$A, B$ and

M, N

$M, N$ . Then the scalar product between these pairs is given by formula (3.6):

G_{A B, M N} = (Q_{A N} + Q_{B M} - Q_{A M} - Q_{B N}) / 2

$G_ {AB, MN} = (Q_ {AN} + Q_ {BM} - Q_ {AM} - Q_ {BN}) / 2$

For a graph, which is an electrical circuit, the value of the scalar product reflects the concept of generalized resistance in an electrical circuit. To measure this (“apparent”) resistance, the current source (voltage) is applied to one node ( A and B ), and the potential difference is measured between the other ( M and N ). The mutual norm (scalar product) of pairs is equal to zero, if the external potential difference does not lead to the potential difference on the measured pair.

The graph does not have to be discrete, - the soil is an example of a solid (continuous) graph on which you can measure the scalar product between selected elements.

Installation scheme for the study of the resistance method: A and B - supply grounding; M and N - measuring grounding; 1 - measuring device (from the book "Electrical Prospecting", Yakubovsky Yu. B., M., 1980).

The figure shows the measurement scheme for the scalar product of pairs.

(A, B)

$(A, B)$ and

(M, N)

$(M, N)$ on the ground.

In the next article we will examine in more detail why the ratio of the given and measured potential differences of the nodes turned out to be associated with the scalar product of pairs.

The appeal of the minor laplacian

A submatrix of values of mutual norms (scalar products) of pairs can be obtained by inverting the minor of the Laplacian. Denote the Laplacian from which removed

a

$a$ row and

b

$b$ th column as

L^{i (a), j (b)}

$L ^ {i (a), j (b)}$ . Then the identity holds:

G_{j b, i a} = (L^{i (a), j (b)})^{- 1} q u a d (3.10.2)

$G_ {jb, ia} = (L ^ {i (a), j (b)}) ^ {- 1} \ quad (3.10.2)$

Note that in the matrix

G_{j b, i a}

$G_ {jb, ia}$ absent

b

$b$ row and

a

$a$ th column.

If the matrix of scalar products of pairs is known

G_{j b, i a}

$G_ {jb, ia}$ , then you can restore the distance matrix

Q_{i j}

$Q_ {ij}$ based on distance conversion. First we expand the submatrix

G_{j b, i a}

$G_ {jb, ia}$ missing line

b

$b$ and column

a

$a$ with zero values. Apply distance conversion to the resulting matrix:

D i s t_{i j} (X) = X_{i i} + X_{j j} - X_{i j} - X_{j i}

$Dist_ {ij} (X) = X_ {ii} + X_ {jj} - X_ {ij} - X_ {ji}$

which in our case takes the form of the identity (3.9.5):

Q_{i j} = G_{i b, i a} + G_{j b, j a} - G_{i b, j a} - G_{j b, i a} q u a d (3.10.3)

$Q_ {ij} = G_ {ib, ia} + G_ {jb, ja} - G_ {ib, ja} - G_ {jb, ia} \ quad (3.10.3)$

The combination of formulas (3.10.2) and (3.10.3) is one of the ways to get the distance matrix for a given Laplacian. Remove any of the nodes from the Laplacian (let

a

$a$ ) and pay. Get the matrix of scalar products of pairs

G_{i a, j a}

$G_ {ia, ja}$ (its other name is the fundamental matrix, see the next part). Index value

a

$a$ fixed - base vertex. In the matrix

G_{i a, j a}

$G_ {ia, ja}$ the first vertex of the pairs is in the base node

a

$a$ , and the second runs through the remaining vertices of the base.

Next, apply to the matrix

G_{i a, j a}

$G_ {ia, ja}$ distance conversion (3.10.3).

Square dot product, Jacobi matrix

If in the graph to change the value of the conductivity of the edge (element of Laplacian), then it is obvious that all distances between the vertices will change (the norms of vectors)

Q_{i j}

$Q_ {ij}$ . With an increase in conductivity, the distances should decrease (decrease). The gift of the gods is that it is possible to estimate the change in distances not only qualitatively, but also quantitatively. Denote the derivative of the laplacian distance matrix as

Y_{i j, k l} = p a r t i a l Q_{i j} / p a r t i a l L^{k l} q u a d (3.11.1)

$Y_ {ij, kl} = \ partial Q_ {ij} / \ partial L ^ {kl} \ quad (3.11.1)$

Tensor

Y_{i j, k l}

$Y_ {ij, kl}$ Is the Jacobi matrix , that is, the expression of changes in the values of the distance matrix

Q_{i j}

$Q_ {ij}$ when changing the values of the laplacian

L^{k l}

$L ^ {kl}$ . It turns out that this tensor is expressed in terms of the square of the scalar product of pairs:

Y_{i j, k l} = (G_{i j, k l})^{2} = (Q_{i l} + Q_{j k} - Q_{i k} - Q_{j l})^{2} / 4 q u a d (3.11.2)

$Y_ {ij, kl} = (G_ {ij, kl}) ^ 2 = (Q_ {il} + Q_ {jk} - Q_ {ik} - Q_ {jl}) ^ 2/4 \ quad (3.11.2 )$

That is, the change in the magnitude of the connection nodes

i, j

$i, j$ leads to a change in the distance between the nodes

k, l

$k, l$ proportional to the scalar product of pairs

(i, j)

$(i, j)$ and

(l, k)

$(l, k)$ .

Vertex quadroconnection tensor

Scalar product square tensor

Y_{i j, k l}

$Y_ {ij, kl}$ reversible. Imagine expression (3.11) in the following equivalent form:

p a r t i a l Q_{i j} = Y_{i j, k l} s p a c e p a r t i a l L^{k l} q u a d (3.11.3)

$\ partial Q_ {ij} = Y_ {ij, kl} \ space \ partial L ^ {kl} \ quad (3.11.3)$

This formula can be interpreted as a response.

p a r t i a l Q_{i j}

$\ partial Q_ {ij}$ on impact

p a r t i a l L^{k l}

$\ partial L ^ {kl}$ . Tensor

Y_{i j, k l}

$Y_ {ij, kl}$ plays the role of transfer function (reaction to exposure).

It is also possible to reverse the situation in which the impact and response change places. Forward and reverse

Y^{i j, k l}

$Y ^ {ij, kl}$ transfer functions are related by:

Y_{i j, k l} Y^{k l, m n} = d e l t a_{i j}^{m n} q u a d (3.12)

$Y_ {ij, kl} Y ^ {kl, mn} = \ delta_ {ij} ^ {mn} \ quad (3.12)$

Good luck again - tensor

Y^{i j, k l}

$Y ^ {ij, kl}$ can be expressed through the Laplacian:

Y^{i j, k l} = p a r t i a l L^{i j} / p a r t i a l Q_{k l} = (L^{i l} L^{j k} + L^{i k} L^{j l}) / 2 q u a d (3.13)

$Y ^ {ij, kl} = \ partial L ^ {ij} / \ partial Q_ {kl} = (L ^ {il} L ^ {jk} + L ^ {ik} L ^ {jl}) / 2 \ quad (3.13)$

Tensor values

Y^{i j, k l}

$Y ^ {ij, kl}$ we call quadratic connectivity .

Quadjunction Tensor Properties

The values of the tensor are determined by the values of the Laplacian for 4 vertices. We consider these vertices as vertices of the graph. Suppose that all 4 vertices are different:

Here vectors denote pairs of vertices, between which quadratic connectivity is assumed. Couples have a non-zero quadroherence only when their vertices are pairwise connected (the necessary connections are shown in the figure in the same color). If all the connections in the graph are positive, then the quadratic connectivity between different vertices is also always greater or equal to zero.

If the pairs have a common vertex, then the sense of quad-connectivity changes. This is due to the fact that the diagonal elements of the Laplacian are not zero (as in the distance matrix), but reflect the common connectivity (conductivity) of the node.

Y^{k i, k j} = (L^{k i} L^{k j} + L^{k k} L^{i j}) / 2 q u a d (3.13.1)

$Y ^ {ki, kj} = (L ^ {ki} L ^ {kj} + L ^ {kk} L ^ {ij}) / 2 \ quad (3.13.1)$

Pairs of vertices may coincide - the diagonal elements of the quadratic connected tensor.

Y^{i j} = Q^{i j, i j} = (L^{i i} L^{j j} + (L^{i j})^{2}) / 2 q u a d (3.13.2)

$Y ^ {ij} = Q ^ {ij, ij} = (L ^ {ii} L ^ {jj} + (L ^ {ij}) ^ 2) / 2 \ quad (3.13.2)$

Here

Y^{i j}

$Y ^ {ij}$ characterizes the connection of two nodes i and j . It is considered as the sum of the product of their total conductivity (degree of the top)

L^{i i} L^{j j}

$L ^ {ii} L ^ {jj}$ and square connection between nodes

(L^{i j})^{2}

$(L ^ {ij}) ^ 2$ .

Although it is formal for the tensor

Y^{i j, k l}

$Y ^ {ij, kl}$ elements of the form can be calculated

Y^{i j, l l}

$Y ^ {ij, ll}$ (one of the pairs is degenerate), the given (degenerate) elements are linearly dependent on the others. Can be calculated through the sum of the tensor for one of the indices of the pair:

Y^{i j, l l} = - Y^{i j, k l} 1_{k} q u a d (3.13.3)

$Y ^ {ij, ll} = -Y ^ {ij, kl} 1_k \ quad (3.13.3)$

___
Let's sum up. The concept of scalar product of pairs of elements that is useful in all respects is considered. In the next article we will work with the subspace of the graph - what it is and what its properties are.

Source: https://habr.com/ru/post/338762/

All Articles

Data geometry 3. Scalar product of pairs

Ordered pair

Scalar product

Couples with a common vertex - adjacent pairs

Independent pairs - four different peaks

Pairs on the basis elements

Scalar Product and Laplacian Cofactors

Dot scalar product on a graph

The appeal of the minor laplacian

Square dot product, Jacobi matrix

Vertex quadroconnection tensor

Quadjunction Tensor Properties

More articles: