Maximal values of a linear function

[Guest]

I am studying abroad for a semester and we were given an exercise no one could solve and they didn't even provide a solution. Maybe someone has an idea

Given are non-zero pairwise distinct vectors [tex]x_1,...,x_n \in \R^2[/tex]. Which condition do those vectors have to satisfy, so we can find a linear map [tex]f: \R^2 \rightarrow \R[/tex] and [tex]1 \leq k<l \leq n[/tex] with

[tex]f(x_k)= f(x_l) = max \{f(x_i)\} = max \{|f(x_i)|\}.[/tex]

[Guest]

Taking the linear map to be [tex]f(x) = 0[/tex] will always work. Perhaps you've written the question is wrong, or I've misunderstood the question.

R. Baber.

[Guest]

Oh yes, I am sorry, had to translate it, of course the linear function is supposed to be non-trivial.

[Guest]

If the function is not allowed to be [tex]f(x)=0[/tex] for all [tex]x[/tex]. Then the vectors must all be of the form
[tex]x_1+\mu(x_1-x_2)[/tex] for some real value [tex]\mu[/tex].

From the conditions on [tex]f[/tex] we know [tex]0=f(x_1)-f(x_2) = f(x_1-x_2)[/tex]. Similarly we know [tex]f(x_i-x_j)=0[/tex] for all [tex]i,j\leq n[/tex]. If there are two linearly independent vectors of the form [tex]x_i-x_j[/tex] then we have a basis for the space, so every vector is a linear combination of these two vectors, and by linearity we know [tex]f(x)=0[/tex] for all [tex]x[/tex]. So this means [tex]x_i-x_1[/tex] must be linearly dependent on [tex]x_1-x_2[/tex] or in other words [tex]x_i-x_1 = \mu(x_1-x_2)[/tex] for some value [tex]\mu[/tex] which rearranges to
[tex]x_i = x_1+\mu(x_1-x_2)[/tex].

It is easy to check the characterization I've given is sufficient. [tex]f[/tex] must map [tex]x_1-x_2[/tex] to [tex]0[/tex], but if [tex]x_1[/tex] is linearly independent to [tex]x_1-x_2[/tex] we can map it to [tex]1[/tex] which fully defines a non-trival linear function [tex]f[/tex] which satisfies [tex]f(x_i) = f(x_1+\mu(x_1-x_2)) = f(x_1) +\mu f(x_1-x_2) = 1+\mu\cdot 0 = 1[/tex] for all [tex]i\leq n[/tex]. If [tex]x_1[/tex] is linearly dependent on [tex]x_1-x_2[/tex] then we have only one condition on [tex]f[/tex] (that it maps [tex]x_1-x_2[/tex] to [tex]0[/tex]) so it is under constrained and we can choose it to be non-trivial.

R. Baber.

[Guest]

Thank you for your reply and your help. But we can only find a pair [tex]k<l[/tex] with [tex]k\ne l[/tex] such that [tex]f(x_k) = f (x_l)[/tex] and that this value is the maximum of all the values of the linear function on the given vectors. Plus, there should not be a vector [tex]x_r[/tex] such that [tex]f(x_r) < -f(x_k)[/tex]. We can find this pair k,l, yet, it does not mean this is valid for all possible pairs. The case that the vectors are all on one line will definitely work, but which other cases would?

Teddy

[Guest]

If you only care that there exists a pair which attain some maximum value, then just about everything works.

What you need to do is plot the points on a plane that the vectors represent. Take the convex hull, then take a rotation of 180 degrees of this convex hull and look at the convex hull of the convex hulls. If the points on this hull of hulls alternate between a point from the original hull then a point from the 180 rotated hull then no such function [tex]f[/tex] is possible. If it doesn't alternate then there'll be two consecutive points from the original hull which are part of the hull of the hull. These two points can be used as [tex]x_k[/tex] and [tex]x_l[/tex].

I'm not sure there is a simpler characterization. Are you sure you got the question right?

R. Baber.

[Guest]

Thank you so much. This one pair should not only have the maximum value of the function among all those vectors, but they should have equal values [tex]f(x_k) = f(x_l)[/tex], and there should not be any among the vectors that has a negative value under f with a larger absolute value than the maximum value.

I am not exactly sure if I understand your idea, what do you mean by the hull of the hull alternates? I will have to think about it some more.

Regards
Teddy

[Guest]

My apologies, when I talk about the convex hull I really mean the points on the boundary of the convex hull (also when I said rotate by 180 degrees I meant to say about the origin).

Given [tex]x_k[/tex] and [tex]x_l[/tex] we can fully define [tex]f[/tex] by simply taking [tex]f(x_k)=1[/tex] and [tex]f(x_k-x_l)=0[/tex] (assuming we are not in the degenerate case that all vectors lie on a straight line going through the origin). The problem is to find an appropriate [tex]x_k[/tex] and [tex]x_l[/tex] that will satisfy all the conditions.

For example take [tex]n=4[/tex] and the [tex]x_1,x_2,x_3,x_4[/tex] vectors to be the points (0.1,0.1), (1,0), (-0.5, 0.866), (-0.5, -0.866) respectively. They form (roughly) an equilateral triangle and a point inside it.

We can not use (0.1,0.1) as [tex]x_k[/tex] or [tex]x_l[/tex] as the line going through [tex]x_k[/tex] and [tex]x_l[/tex] will split the plane into two regions each containing a point. The region containing the origin will all have values which [tex]f[/tex] maps to something smaller than [tex]f(x_k)[/tex] and the region not containing the origin will contain points that get mapped to something larger than [tex]f(x_k)[/tex].

In fact (0.1, 0.1) will play no part in determining whether a linear map [tex]f[/tex] is possible. If there is such a linear map, since (0.1, 0.1) lies in the convex hull of the other three points it will automatically be dealt with. The convex hull of the three points is the equilateral triangle (by the way).

If we didn't have the condition that [tex]f(x_k)=\max\{|f(x_i)|\}[/tex] then any two choices of [tex]x_2, x_3, x_4[/tex] for [tex]x_k, x_l[/tex] would work. However since we do have that condition we need to consider the points [tex]-x_2, -x_3,-x_4[/tex] which we do by rotating the points by 180 degrees about the origin. Now we have 6 points whose convex hull is a (roughly) regular hexagon. The points on the boundary of the convex hull in anticlockwise order are [tex]x_1, -x_3, x_2, -x_1, x_3, -x_2[/tex] note that they alternate between our original points and the rotated/negative points. We can not find two consecutive points on the boundary of the convex hull which are not rotated, as such any choice of [tex]x_k, x_l[/tex] will split the region into two parts, as before, with some points getting a value greater than [tex]f(x_k)[/tex] and some points getting a smaller value. There is no such linear map [tex]f[/tex].

If we shifted everything to the left by translating all the points by (-1,0) then repeated the procedure we would find the convex hull of the points and the rotated points is now a rectangle, and [tex]x_2, x_3[/tex] are consecutive points on the boundary, so we can use them as [tex]x_k, x_l[/tex] to create [tex]f[/tex].

Although this convex hull idea works it is not a very simple characterization, and I can't see a simpler one. I seriously doubt this is the answer the exercise was looking for.

R. Baber.

[Guest]

Thank you so much. That helps me a lot, not sure if that was in any way what they were looking for, but it gives me a very good idea on how to even approach the problem!!