Linear Algebra, Segment Map

Segments to Segments

Let f be a continuous function from euclidean space to euclidean space, such that the image of a line segment is always a line segment, with end points mapping to end points. (The image could be trivial, if the segment maps to a single point.) Such a function is called a segment map.

The composition of segment maps is a segment map.

Every linear function is a segment map. If the function is one to one and onto then it can be reversed to give another segment map. A translation (shifting the origin to some other point in space) is also a reversible segment map. Given this, it is often convenient to shift the domain and range of a segment map so that the origin maps to the origin. This is the beginning of normalization, described below.

There are many possible segment maps into R¹, such as atan(x+y). And you can follow this up with maps that stretch and shrink portions of the real line in all sorts of ways. In contrast, a 2 dimensional image is highly constrained. thus I will assume that the range has at least two dimensions. I will also assume the domain is convex, which implies the range is convex.

Lines to Lines

By definition, f takes points between a and b (along the line segment) to points between f(a) and f(b), but we can make a similar statement for the entire line, or at least the longest line within the domain of f. If c lies beyond b, the segment from a to c maps to a segment that starts at f(a), and contains f(b), and ends at f(c), thus f(c) is colinear with f(a) and f(b), and lies at or beyond f(b). Take the union of all segments containing a and b and you have the entire line.

Monotonic

Decide, somewhat arbitrarily, that a is to the left of b, and f(a) is to the left of f(b). The function f from a to b is now monotonic. Suppose it is not - with c < d, but f(d) < f(c). One of the two points, c or d, is internal - assume it is d. The segment from c to b has an image that strays outside of f(c) - f(d). The endpoints are not the endpoints, and we have a contradiction. Therefore the function moves inexorably from f(a) to f(b).

Take the union of all segments containing a and b and f is monotonic on the ab line.

Compressing a Line

In one dimension we can map [0,1] to 0, x < 0 to x, and x > 1 to x-1, thus squashing part of the line; but we can't do this in higher dimensions.

Assume f(a) = f(b) = x. Thus the entire segment from a to b collapses into x. Move a to the left and b to the right as far as possible, such that the segment from a to b still maps into x. If this is the entire line then we are done, but if not then, by continuity, f(a) = f(b) = x, and points just outside of a and b do not map to x. Suppose points to the right of b, and arbitrarily close to b, do not map to x.

The range is more than a line, so the domain is more than a line. Suppose everything off the ab line maps to x. We already said c to the right of b does not map to x. By continuity, the points approaching c (from off the ab line) force f(c) = x, unless the segment from b to c extends outward from the domain like a stick; but then the domain is not convex. thus c maps to x, which is a contradiction. Therefore there is a point p off the ab line that maps to y, where y is not x.

The vertical angles at y, passing through a and b, and the interior of these angles, all map into the xy line in the range. Let m be the midpoint of x and y. Let r be the last point from a to p that maps to m. Let s be the last point from b to p that maps to m. From the perspective of c, draw a line through r or s, which ever is higher. The image of this line contains m and something else between m and y, thus it lies in the xy line. If you are unlucky and c r and s are colinear, shift c to the left just a bit so that this is not the case. Thus c maps into the xy line. By extension, the ab line maps into the xy line.

The image is not a line, so let q map to z, where z is not on the xy line. This implies q is not on the ab line. Reason as above to show that the ab line maps into the xz line. However, the xy and xz lines intersect only in x. Therefore the ab line maps entirely into x. Crunch a segment and you crunch the entire line. Either the line compresses to a point, or it maps monotonically and injectively to a line.

Compressing a Dimension

Continuing the above, let m be any point between x and y, and let r and s be the points on the ap and bp line that map to m. The rs line now maps to m. The rs line and the ab line must not intersect, for they map to different points. If the lines are infinite then they must be parallel. If however the domain is a small patch of the plane then the rs line could be tilted relative to the ab line. In any case, we find horizontal, or nearly horizontal lines that map onto points on the xy line, and by continuity the line passing through p maps to y. Since p is arbitrary, the entire domain consists of lines that are essentially parallel to ab, and compress down to points in the range, like a projection. We will assume that the domain has been compressed in this fashion, again and again, until f becomes injective.

Domain and Range

Place the origin inside a small hypercube inside the domain. The image of the axes establishes a parallelatope within the range. The dimension of this parallelatope has to equal the dimension of the original cube, else f is not injective.

Take any other point p in the domain and draw a segment from p back to the origin. This places p within the space spanned by our cube. Map this forward and f(p) lies in the space spanned by the parallelatope. Therefore the dimension of the range equals the dimension of the domain.

Normalization

Given f, slide the image of 0 over to 0, and then apply a linear transformation so that the image of 1 is 1 along each axis. This normalized version of f is still a segment map, but the unit simplex maps onto itself. Since linear transformations and translations are invertible, it is sufficient to describe these normalized functions.

In two dimensions, let f(1/2,0) = a,0 and let f(0,1/2) = 0,b where a and b are strictly between 0 and 1. Draw lines in the domain from 1/2,0 up to 0,1 and from 0,1/2 over to 1,0. These intersect in 1/3,1/3. Apply f, and lines map to lines, hence the image of 1/3,1/3 is determined.

The next point to nail down is 1/4,1/4. This is the intersection of the segments from 0,0 to 1/3,1/3 and from 1/2,0 to 0,1/2.

Extend the main diagonal outward to meet the far side of the triangle and find f(1/2,1/2).

Start at the top of the triangle and travel down through 1/4,1/4 to hit the x axis at 1/3. Thus f is defined on this point, and on y = 1/3, and on 1/6,1/6.

If you're ready to leave the confines of the triangle, we can do that. Extend the line from the apex down through x = 1/3 and intersect it with the vertical line at x = 1/2. This defines f on 1/2,-1/2. From here we can establish f on 2/3-1/3 and 3/4-1/4. Continue this line up into the first quadrant and intersect with the line through 0,1/3 and 1/2,1/2. This establishes f(2,1). Similarly define f on 1,2, then 3,0 and 0,3.

I think you can see where we're headed from here. A grid spreads across the plane, and we can make this grid as fine as we like. Continuity does the rest. Therefore f is uniquely determined by the images of 1/2 along the axies. And this works in n dimensions.

But does it really work like that? Certainly the points cluster towards 0. From the apex through 1/6,1/6 gives us x = 1/5, and y = 1/5 by symmetry, and then 1/10,1/10. Do the same with 1/10,1/10 to get x and y = 1/9, and then 1/18, 1/18. Continue this process and the points approach 0 along the axes and the main diagonal. If we believe f is real analytic then I suppose it is defined.

Do the points of intersection cluster anywhere else? Do they spread out to infinity in the first quadrant? Do they venture forth into the other three quadrants? I don't know the answer to the first two questions, but I suspect the answer to the third question is no, as we shall see below.

Defining f

Let v be a vector of constants v₁ v₂ v₃ … v_n, such that each v_i is larger than -1. Let x be a vector in n space. The image of x is given by:

y_i = x_i×(1+v_i) / (1+v.x)

The origin maps to the origin.

Each of the n unit vectors maps to itself.

The image of 1/2 along each axis maps to 1 - 1/(2+v_i). This lies strictly between 0 and 1 as v_i runs from -1+ε to infinity. And it is reversible; we can build v uniquely based on the images of 1/2 along the axes.

If each v_i is 0 then the map is the identity map. This carries 1/2 to 1/2, as you would expect.

The denominator drops to zero when v.x = -1. The domain is all of n space sans the hyperplane determined by v.x = -1. This is not convex, but we can consider each half space in turn. The domain of interest is typically v.x > -1. This includes the origin, and 1 along each axis, hence the unit simplex.

Suppose the spreading points of intersection include 4,-1. Set v = (0,1), and v.x = -1. The image of f is determined, yet it is undefined. I therefore believe that our points of intersection don't stray far from the first quadrant; they can't foray down to y = -1 or x = -1. I would prefer a more direct proof, but I don't have one.

Is this really a segment map? As a warm-up, scale the input vector x by a constant t. This changes the denominator in a manner that does not depend on i, and it multiplies each numerator by t. Thus f(tx) is a scale multiple of f(x), though not necessarily by t. This is of course a necessary condition for a segment map, but we also need monotonicity. The base vector f(x) is scaled by t×(1+v.x)/(1+tv.x). Fold the second factor into f(x) and don't worry about it any more. That leaves t/(1+tu) where u = v.x. If u = 0 then monotonicity is obvious. Otherwise replace t with t/u, and fold 1/u into f(x), leaving t/(1+t), or 1-1/(1+t). This is monotonic on either side of t = -1.

Now for the lines that don't pass through the origin. Let x be the vector a+tb, where a and b are fixed vectors and t is a scaling factor. Consider f(x) - f(a).

(a_i+tb_i) × (1+v_i) / (1+a.v+tb.v) - a_i×(1+v_i) / (1+a.v)

Pull out 1+v_i, and find a common denominator for the two fractions. This denominator changes with t, but in a manner that does not depend on i, so let's set it aside for now.

(a_i+tb_i)×(1+a.v) - a_i×(1+a.v+tb.v)

tb_i×(1+a.v) - a_i×tb.v

This is proportional to t. The difference is a vector whose components are all multiplied by the same scaling factor, determined by t.

The monotonicity argument is much like that given above. After some adjustments to the base vector, the scaling factor is t over something plus some multiple of t, which is monotonic. Therefore f maps lines to lines, and is a segment map. We have built the unique segment map that corresponds to the images of 1/2 along the axes.

Example

In 2 dimensions, let v₁ = v₂ = 1. The domain is the half plane above x+y = -1. Consider the vertical line through x = 1, parameterized as 1,t. The image is (2,2t)/(2+t). Subtract f(1,0) from this and get (-1,2) times t/(2+t). (The mapt does not preserve angles; the input was perpendicular to the x axis, and the output is not.) For large t the image approaches 0,2. As t approaches -2 the line shoots down into the fourth quadrant. On the other side of -2 we are way off in the second quadrant, and as t approaches -infinity the line creeps back towards 0,2 from above.

It is tempting to close the circle in the domain and the range. Let t = -2 map to infinity, and t = infinity map to 0,2. This works for any given line in the plane, but I don't believe we can do it across the board. We would have to close up the line at infinity that is "opposite" to v.x = -1, and that is not a simple matter of compactification. So we may have to call it a segment map on one half space, and a segment map on another half space, and leave it at that.

Another example from the same map is the line that starts at 0,1 and travels up and to the left, parallel to the pathological line x+y = -1. The parametric formula for this line is 1-t,t. Verify that f maps each point on this line to itself. In other words, the line is fixed. Other lines with slope -1 move toward or away from the origin, and may stretch or shrink. For instance, 1/2, on the axis, moves to 2/3, hence that line moves away from 0 and expands.

Applications in Linear Optimization

Take a polyhedron in 3 space and place a marble inside it. The marble rolls to the lowest point, which has to be a vertex. Ok - you could place a cube flat on the table, and then an entire face is minimal, but you could just slide the marbel over to a corner and say it is at a vertex. So we are looking for the lowest vertex, even if the shape exists in thousands of dimensions. The simplex method simply rolls the marble to the bottom, as intuition suggests, and it works quite well. But the algorithm is not guaranteed to reach a solution in polynomial time. It is not mathematically satisfying. Karmarkar's Algorithm runs in polynomial time, and it begins with a segment map. The shape is transformed, but lines still map to lines. It is still a convex polyhedron with corners, edges, faces, etc. Inside the new shape, the marble is guaranteed to roll down to the bottom in polynomial time. I can't say anything more about Karmarkar's algorithm, because I don't understand it beyond this point. But I have heard that industry continues to use the simplex method, because it seems to work well enough for most "real world" applications.

Abstract Lines

Consider an arbitrary field F, which could be the reals or could be something else. Although lines are no longer geometric concepts, algebraic lines still exist. They take the form a+tb, where a and b are vectors and t is a free parameter. Build the rational function f as above, based on the vector v, with the understanding that v_i is never -1. We want to show that lines still map to lines, and they map bijectively, and even homeomorphically when that makes sense. This is clearly the case when v = 0 and f is the identity map, so assume v is not zero.

Note that f is still undefined on the hyperplane x.v = -1, just as it was before. If f(a) is not defined, because a.v = -1, then add b to a. It's still the same line; we just have a new point for t = 0. If f(a) is still undefined, because b.v = 0, then the entire line lives in the forbidden hyperplane where f is not defined. Let's set this case aside and assume our line slices through the forbidden hyperplane in a point, or runs parallel to the plane.

Consider first the case where the line and the forbidden plane are parallel, that is, b.v = 0. We already computed f(a+tb) - f(a) above. In this case the common fraction (1+v_i)/(1+a.v) pulls out. For every i, this fraction is nonzero - because v_i is not -1. Select an i where b_i is nonzero, and consider that component alone. The difference between f(x) and f(a), along this coordinate, is directly proportional to t. The map is a bijection, and when you bring in the other coordinates, f is a bijection from line to line.

Assume the line has a topology, because F is contained in the reals, or the complex numbers, or the p-adic numbers. Multiplication is a continuous operator, hence f is continuous in either direction. This makes f a homeomorphism from line to line. If you like, let f map infinity to infinity and it becomes a homeomorphism from circle to circle.

Next assume our line is not parallel to the forbidden hyperplane, that is, b.v is nonzero. For some value of t, (a+tb).v = 0. Add tb to a, giving a new value for a, a new starting point for our line. Now a.v = 0. Evaluate f(x) and simplify, giving:

t * (1+v_i) / (1+tb.v) * {b_i - a_ib.v}

Suppose the last term is 0 for every i. That makes b a scale multiple of a. Specifically, b is b.v times a. Since b.v is nonzero, a has to be the zero vector, and so is b. This isn't a line any more; it's a point. That is a contradiction. Therefore there is some i, some coordinate, where the image is t times q/(1+tr) for suitable nonzero values of q and r. Call this q/r times (1-1/(1+tr). Each step in this formula is injective, hence the map is injective. And the map is surjective, except for the point q/r, which cannot be realized by any t. Therefore f maps the line without -1/r onto the line without q/r. If you like, map -1/r to infinity, and infinity to q/r. This preserves the topology (when there is one), and the two circles are homeomorphic. I'll leave the continuity details to you.