Оглавление

Hereinafter the distance between and from is defined as:

**Problem.** Find the distance from a point to a linear manifold in given by a system of linear equations

or in matrix form

It is assumed that and that , i.e. the linear system is consistent and defines the -dimensional manifold in .

Th

**Theorem 1.** [1]. *Compose the square matrix of the order* :

*Distance from* *to the linear manifold equals*

§

The radicand is nonnegative due to the assumption imposed on the and the properties of the Gram determinant:

=>

Distance from to the hyperplane (line if )

equals

The nearest to point of the hyperplane (line) is:

Let the manifold be represented parametrically as

for the given columns . Assume these columns to be linearly independent. Compose the following matrices

(here stands for concatenation).

Th

**Theorem 2.** *Distance from the point* *to the linear manifold* *equals*

§

The assumption of the linear independency of results in the positive definiteness of the matrix (property of the Gram determinant). The matrix has the nonnegative determinant for any choice of .

§

Last theorem is a particular case of the well-known application of the Gram determinant.

Th

**Theorem 3.** The nearest to point in the manifold is given by the formula

Ex

**Example.** Find the distance from to the manifold

**Solution.** *1-st method*: application of Theorem 1. One has:

*2-nd method*: application of Theorem 2. Find the general solution for the generating system:

Thus, the parametric equation of the manifold is as follows

where

One gets:

The nearest to point in the manifold is as follows:

**Result.** .

Let the linear manifolds in be given parametrically

and

for specified columns . We will assume these manifolds to be not parallel. Compose the matrices from these columns

(here stands for concatenation).

Th

**Theorem.** *Distance between linear manifolds* *and* *equals*

**Remark.** Using the Gram determinant properties one has:

columns are linearly independent

for

Ex

**Example**[2]. Find the distance between the manifolds

and

**Solution.**

**Result.** .

Th

**Theorem 1.** *The square of the distance to the quadric* *given by the equation*

*from the point* * not lying in the quadric (i.e.* ) * equals the minimal positive zero of the distance equation*

*provided that the mentioned zero is not a multiple one. Here*

*while* *stands for the discriminant of the polynomial (treated w.r.t. * ),* and * * is the identity matrix of the order* .

=>

[3,4]. The square of the distance from to the quadric in given by the equation

equals the minimal positive zero of the distance equation

provided that this zero is simple. Here is the characteristic polynomial of the matrix while is the adjoint matrix for .

=>

For the particular case (i.e. the quadric centered to the origin), one has:

and the distance from the origin to the quadric equals , where stands for the maximal eigenvalue of the matrix .

Ex

**Example.** Find the distance from the origin to the ellipsoid

**Solution.** Here

The adjoint matrix to :

Utilization of the determinantal representation for the discriminant yields:

Its real roots are as follows:

**Result.** .

§

For the case the problem stated corresponds to the *ellipsoid height* evaluation known in GPS systems.

To find the nearest point in the quadric, one can utilize the following algorithm which we illuminate for the case :

1. On evaluating (within a prescribed accuracy) the minimal positive root of the polynomial , one can restore the corresponding value of . The correspondence should be interpreted in the sence that for the specialization the discriminant of the polynomial

treated w.r.t. vanishes. That means the polynomial possesses a multiple root which will be denoted . This root can be represented as a rational function of with the aid of subdiscriminants.

2. The nearest point in the quadric is evaluated via the formula:

Th

**Theorem 2.** *Under the conditions of Theorem* , *the coordinates of the nearest to the given point* *point* *in the quadric, can be found as*

*here* *denotes the multiple zero for the polynomial* .

§

This means: the coordinates of the nearest point in the quadric *generically* can be expressed as rational functions from the squared distance.

Ex

**Example.** For the ellipsoid from the previous example, find the point nearest to the origin.

**Solution.** Substitute into the formula for the multiple root evaluation:

One gets . Substitute now this value into the formula for :

**Check.**

and is normal to ellipsoid at the point :

§

Further details for the distance equation for the particilar cases and are ☞ HERE .

**Problem.** Find the distance from the ellipsoid in given by an equation

to a linear manifold in given by a system of linear equations

or, in matrix form

We assume that and that i.e. the linear manifold in is a -dimensional one.

Th

**Theorem.** *The ellipsoid intersects the linear manifold iff*

=>

The vanishement of the determinant from the above theorem provides the necessary and sufficient condition for the existence of the tangency point for the manifolds.

Th

**Theorem.** *If the condition of the previous theorem is not satisfied then the square of the distance from the ellipsoid to the linear manifold equals the minimal positive zero of the polynomial*

*provided that this zero is simple. Here* *stands for the discriminant of the polynomial treated w.r.t.* .

=>

If the system of rows of is an orthonormal one then, by transforming the determinant in the theorem, one can diminish its order: the expression under discriminant can be reduced into

Ex

**Example.** Find the distance to the -axis from the ellipsoid

**Solution.** Here

and one can choose

Matrix is negative definite, therefore the intersection condition is not fulfilled:

Use the Corollary to the theorem:

and the discriminant of this polynomial w.r.t. equals

Positive zeros of this polynomial are .

**Result.** .

**Remark.** For the general case, one gets , i.e. the degree of equals the doubled number or linear equations yielding the manifold. For the particular case , one gets quadric equation:

=>

The distance from

to the nearest and to the farthest points on the ellipsoid

equals the absolute values of the zeros of:

Here and it is assumed the surfaces do not intersect.

Ex

**Example.** Find the distance from the line to the ellipse .

**Solution.** Here

and zeros of this polynomial are as follows:

**Result.**

Th

**Theorem.**[4]. *Let* *and* *be the quadrics in* *with the first one being an ellipsoid. These quadrics do not intersect iff the matrix* *is sign definite.*

**Proof** is
☞
HERE

Th

**Theorem.** [3]. *Under the condition of the previous theorem, the square of the distance between the ellipsoid* *and the quadric* *equals the minimal positive zero of the polynomial*

*provided that this zero is not a multiple one. Here* *stands for the discriminant of the polynomial treated w.r.t.* .

Ex

**Example.** Find the distance between the ellipses

**Solution.** Here

and the matrix is positive definite. Thus the ellipses do not intersect.

and the discriminant of this polynomial w.r.t. equals

Its positive roots are as follows:

**Result.** .

§

For the general case, the degree of from the last theorem (on excluding the extraneous factor ) equals .

To find the nearest points in the quadrics one can utilize the following algorithm:

1. If is a zero of then the polynomial

has a multiple zero . Under the assumptions of the theorem, the multiplicity of this zero equals to 2, there is no other multiple zeros, and this zero can be expressed as a rational function of via subdiscriminants.

2. The coordinates column of the point in the first quadric satisfies the system of the linear homogeneous equations

with an infinite set of solutions (since its determinant vanishes). From the mentioned set we extract the solutions with the property .

Under the assumptions of the theorem, there exists precisely two such solutions (due to the symmetry of the problem, v. Fig.).

Similarly, the coordinate column of the point in the second quadric is a solution of the system

§

Notice, that the matrices of the considered linear systems differ only by transposition.

To find the solution to the system of linear homogeneous equations, let us compose the solution column from the cofactors to the entries of any *row* of the matrix

Then differs from this column only by the multiple which can be determined from the condition . In a similar way, to find the column let us compose it from the cofactors to the elements of any *column* of the same matrix , and multiply it by a constant in order to provide the fulfilment of the condition .

3. The obtained pairs should be adjusted by the restriction

Ex

**Example.** Find the nearest points in the ellipses from the previous example.

**Solution.** For the obtained value the determinant of the matrix

treated as a polynomial in , possesses a multiple zero. We find this zero1) via the subdiscriminant technique:

Substitution yields one .

Furthemore, for the obtained values of and the system of linear equations

treated with respect to the column has an infinite number of solutions. One of these solutions can be found with the aid of the cofactors to the entries of, for instance, the second row of the matrix :

Any other solution can be obtained from this on multiplication by a constant (i.e. by «streching» of the vector). We utilize such an opportunity with the aim to provide the condition .

Similarly, to find the point in the other ellipse, one should solve the system

with the aid of the cofactors to the second column of the matrix :

**Result.** and respectively (with the correlated signs).

**Check.** Taking the sign results in:

Th

**Theorem.** *Let* *and* *be quadrics in* , *with the first one being an ellipsoid. These quadrics intersect iff the polynomial*

*possesses zeros of distinct signs, or * . *Here* *is the discriminant of the polynomial treated w.r.t.* .

=>

For the existence of the tangency point for and it is necessary and sufficient that

Th

**Theorem.** [3]. *If the condition of the previous theorem is not fulfilled then
the square of the distance between the ellipsoid* *and the quadric * *equals the minimal positive zero of the polynomial*

*provided that this zero is simple. Here* *is the discriminant of the polynomial treated w.r.t.* .

Ex

**Example.** Find the distance between the ellipses

**Solution.** Here

Let us verify first the conditions of intersection of the manifolds. The polynomial

possesses precisely two real zeros, both are negative. Ellipses do not intersect. Furthemore,

Calculate the discriminant of this polynomial w.r.t. and via representation of the corresponding resultant

as the Bézout determinant [5]:

The expressions for the entries of the first and the last rows are ☞ HERE.

The first factor in is an extraneous one and should be reduced. Positive zeros of the second factor are:

**Result.** .

The coordinates of the nearest points in the quadrics can be found by the following algorithm:

- On evaluating the minimal positive zero of one can establish the corresponding values of and . This correspondence has the meaning that for the discriminant of the polynomial

treated w.r.t vanishes. That means the polynomial possesses a multiple zero which we denote . This zero can be represented as a rational function of with the aid of the minors of the Bézout matrix. Let, for instance, the matrix of the order be constructed for the monomial basis with the first three power product equal to . Denote by the cofactors to the entries of the last row of this matrix. One has then

- Compose the matrix

Then the coordinates columns of the nearest points in the quadrics can be found via the formulas:

Ex

**Example.** Find the nearest points in the ellipses from the previous example.

**Solution.** Substitute the value of the square of the distance into the formulas for the multiple zero evaluation:

with

and

(Complete expressions are ☞ HERE.) The result is as follows:

Then the matrix equals:

and using the above formulas for the coordinates columns one arrives at the

**Result.**

**Check.**

and the vector is normal to both ellipses in the corresponding points:

§

For the general case, the degree of from the last theorem (on excluding the extraneous factor) equals . Its coefficients might be huge:

Ex

**Example.** Find the distance between ellipsoids

and

**Solution.** Here

**Result.** .

**Problem.** Let an algebraic curve be defined by the equation

Here is a polynomial in and with real coefficients. Evaluate the distance to this curve from the origin.

For this problem, some extra obstacle appeared which has not caused much difficulty for the quadrics, nemely the problem of existence of solution. It might happened that the given equation does not define any real curve in the plane.

We start the treatment of the stated problem with a particular case of a polynomial: let it be *even* one w.r.t. . Geometrical meaning of this condition is the symmetry of the curve (if it exists)
w.r.t. the axis . Analytically such a polynomial can be represented in the form of a polynomial in :

Th

**Theorem 1 [7].** *Let* . *Equation* *does not possess real solutions if the following conditions are satisfied:*

**(a)** *Equation* *does not possess real solutions;*

**(b)** *Equation*

*does not possess positive solutions.*

*If any of these conditions fails then the distance from* *to the curve* *equals either the minimal absolute value of real zeros of the equation* *or the square root from the minimal positive zero of the equation* *provided that this zero is not a multiple one.*

Ex

**Example.** Evaluate the distance from the origin to the curve

**Solution.** Equation

has the real zeros and . Furthemore, one has

and

has a minimal positive zero equal to . Since , we arrive at the following

**Answer.** .

It is evident how to tackle the problem if the polynomial is an even one w.r.t. .
How to deal with the case of a polynomial which is not even in any of its variables? — Let us *evenize* it.
Consider the polynomial

Th

**Theorem 2 [7].** *Equation* *
does not possess real solutions if the following conditions are satisfied*:

**(a)** *equation* *does not possess real solutions;*

**(b)** *equation*

*does not possess positive solutions.*

*If any of these conditions fails then the distance from* *to the curve* *equals either the minimal absolute value of real zeros of the equation* *or the square root from the minimal positive zero of the equation* *provided that this zero is not a multiple one.*

Ex

**Example.** Evaluate the distance from the origin to the curve

**Solution.** Skipping the intermediate computations we present here just only the final expression for the discriminant:

where

and

Polynomial has three real zeros: . Polynomial has two real zeros: .

The factor is ignored as an extraneous one, i.e. the values of its zeros (all of them are multiple) are not compared with and . Where this multiple appeares from? — To guess its origin, let us evaluate its positive zeros: . Draw now the circumferences in the last figure:

Circumferences pass through the points of intersection of the curves and .

**Hypothesis.** Expand in powers of and split it in even and odd terms w.r.t. this variable:

The following identity is valid up to a constant factor

Here stands for the resultant of the polynomials treated w.r.t. .

**Answer.** .

**Problem.** Given the coordinates of three noncollinear points in the plane,
find the coordinates of the point which gives a solution for the optimization problem

for

Here are usually assumed to be real positive numbers.

The stated problem in its particular case of equal values is known since 1643 as the (classical) Fermat-Torricelli problem.
Generalization of the problem to the general case (of not necessarily equal ) was investigated since the XIX century.
This generalization is known under different names: *the Steiner problem*, *the Weber problem*, *the problem of railway junction*2), *the three factory problem*.
The two last names were inspired by the facility location problem like the following one. Let the cities and be the sources of iron ore, coal, and water respectively. To produce one ton of steel, the steel works need tons of iron, tons of coal and tons of water. Assuming that the freight charge for a ton-kilometer is independent of the nature of the cargo, find the optimal position for the steel works connected with , and via straight roads so as to
minimize the transportation costs.

§

The detailed discussion of this problem is ☞ HERE.

are ☞ HERE

[1]. **Cesàro E.** *Algebraic Analysis and Infinitesimal Calculus.*

[2]. **Ikramov H.D.** *Linear algebra: problems book*. Мir. Moscow. 1983

[3]. **Uteshev A.Yu., Yashina M.V.** *Distance Computation from an Ellipsoid to a Linear or a Quadric Surface in* . Lect.Notes Comput. Sci. 2007. V.4770. P.392-401

[4]. **Uteshev A.Yu., Yashina M.V.** *Metric Problems for Quadrics in Multidimensional Space.* J.Symbolic Computation, 2015, Vol. **68**, Part I, P. 287-315.

[5]. **Proskuryakov, I.V.** *Problems in Linear Algebra.* Mir. Moscow. 1978

[6]. **Bikker P.,Uteshev A.Yu.** *On the Bézout Construction of the Resultant.* J.Symbolic Computation, 1999, Vol.28, № 1. P.45-88

[7]. **Uteshev A.Yu.**, **Goncharova M.V.** *Metric problems for algebraic manifolds: Analytical approach.* Constructive Nonsmooth Analysis and Related Topics (dedicated to the memory of V.F. Demyanov) (CNSA), 2017, IEEE, http://ieeexplore.ieee.org/document/7974027/