What is an Extreme Point in a Convex Set?

In summary, In summary, this person is trying to show that if a matrix preserves L1 norm then it must necessarily preserve L2 norm, but they can't seem to do it. They also say that it is easy to show that a matrix preserves L1 norm if it is unitary, but they can't seem to show that it must be complex permutation matrix.
  • #1
mikepol
19
0
Hi,

I've been trying to show that the set of matrices that preserve L1 norm (sum of absolute values of each coordinate) are the complex permutation matrices. Complex permutation matrix is defined as permutation of the columns of complex diagonal matrix with magnitude of each diagonal element equal 1. (This problem is from Matrix Analysis by Horn and Johnson).

I've spend quite a lot of time trying to solve this but without much success. It is easy to show that complex permutation matrix keeps the L1 norm of a vector the same, but I can't show the opposite, that every such matrix must be a complex permutation matrix. The only thing I came up with is to take a vector [tex]x=(1-\epsilon,\epsilon)[/tex], and just say that L1 norm of [tex]Bx[/tex] can't be linear for all values of [tex]\epsilon \ge 1[/tex]. But that is not really a proof.

Also it is easy to show from scalar product that such set of transformations for L2 norm are the unitary matrices. If I could somehow show that if a matrix preserves L1 norm then it must necessarily preserve L2 norm, then norm preserving matrices for L1 must be a subset of norm preserving matrices for L2. Then it is fairly easy to show that such a unitary matrix must be complex permutation matrix. But I can't seem to show that L1 preserving matrix must be L2 preserving.

Please, if someone could give me some hints or suggestions, it would be very appreciated!
Thanks.
 
Physics news on Phys.org
  • #2
Preserves norm (and linear) -> preserves distances.

Therefore, it maps the extreme points of the unit ball to extreme points of the unit ball.

In the l_1 norm, those extreme points are just scalar of modulus 1 times basis vector. That should be a start.
 
  • #3
g_edgar thanks for your answer.

I'm not sure what you mean by "extreme points" of a unit ball. For example, in real 2D space, unit ball for L1 norm is a rhombus. You are saying that its extreme points are plus/minus the x and y unit vectors. But I don't see why the image of a unit vector along an axis under linear isometry should also be a unit vector along an axis.

Thanks.
 
  • #4
Ok I think I finally got it. I will post my solution later today.
 
  • #5
g_edgar thanks for your hints, I think I have a solution now. By extreme points you mean the points on L1 unit ball that maximize L2 norm. By using that and drawing a rhombus, I finally saw how to produce a contradiction by showing that if transformation is not a complex permutation matrix, then two opposite extreme points will map to the same quadrant. This proof is just putting that idea into algebra:

First, by regarding complex space as real 2D space and using Cauchy Schwartz inequality, it is possible to prove that triangle inequality
[tex]|a+b| \le |a| + |b|[/tex]
becomes an iquality for fixed non-zero complex number 'a' and complex number 'b' of fixed non-zero magnitude iff
[tex]b = \beta a[/tex]
for [tex]\beta[/tex] real and strictly positive.

Now suppose that B is an isometry for L1 norm, so that for any x:
[tex] ||Bx|| = ||x|| [/tex]
B must be invertible, so if each column of B contains exactly one nonzero element, then they must occur in different rows and have magnitude 1, so B must be a complex permutation martix. Assume then that first column of B contains at least two nonzero elements at rows i and j, and that second column contains a nonzero element at row i (it is always possible to find two such columns if B is not a complex permutation matrix).

So [tex]B e_1 = x[/tex] where [tex]x_i \ne 0, x_j \ne 0[/tex], and [tex]B e_2 = y[/tex] where [tex]y_i \ne 0 [/tex]. Then
[tex]||B(e_1 + e_2)|| = ||x + y|| = \sum_k |x_k + y_k| = ||e_1 + e_2|| = 2[/tex]
But by triangle inequality, the above sum will equal 2 if and only if
[tex]y_i = \beta x_i [/tex]
for some real [tex]\beta > 0[/tex].

Now consider [tex]B(-e_2) = z[/tex], where by above assumption and linearity [tex]z_i \ne 0[/tex]. Similarly:
[tex]||B(e_1-e_2)|| = ||x+z|| = \sum_k |x_k + z_k| = ||e_1 - e_2|| = |1| + |-1| = 2[/tex]
And also by triangle inequality, the sum is equal to 2 if and only if
[tex]z_i = \gamma x_i[/tex]
for some real [tex]\gamma > 0[/tex].

But by linearity of B:
[tex]z = B(-e_2) = -B(e_2) = -y[/tex], so we must have [tex]\gamma = -\beta[/tex]. Hence there is a contradiction. Therefore B must be complex permutation matrix.

This came out a little long, but I tried to include a few steps in between to make sure I'm not missing something, and I think it's correct. If anyone sees a problem with this proof, please post something, I'll be interested in hearing your opinion.

And again, thanks to g_edgar for the hints.
 
  • #6
In general, an extreme point of a convex set [itex] C [/itex] is a point [itex] c \in C[/itex] such that for all [itex]a,b \in C [/itex], if [itex] c = ta+(1-t)b[/itex] with [itex] 0 < t < 1[/itex], then [itex] a = b = c [/itex] .
 

Related to What is an Extreme Point in a Convex Set?

1. What is an isometry group for L1 norm?

An isometry group for L1 norm refers to a set of transformations that preserve distances measured by the L1 norm. This means that the sum of the absolute differences between corresponding points in two vectors remains the same after the transformation.

2. How is the L1 norm defined?

The L1 norm, also known as the Manhattan distance or taxicab norm, is a way of measuring the distance between two points in a vector space. It is defined as the sum of the absolute differences between corresponding components of the two vectors.

3. Why is the L1 norm important in isometry groups?

The L1 norm is important in isometry groups because it is a commonly used distance metric that has practical applications in fields such as signal processing and image recognition. By preserving distances measured by this norm, isometry groups can help maintain the integrity of data and patterns in these applications.

4. How is the isometry group for L1 norm different from other isometry groups?

The isometry group for L1 norm is different from other isometry groups because it specifically preserves distances measured by the L1 norm. Other isometry groups may preserve distances measured by different norms, such as the L2 norm (Euclidean distance) or the L infinity norm (maximum difference).

5. What are some examples of transformations that belong to the isometry group for L1 norm?

Some examples of transformations that belong to the isometry group for L1 norm include translations, rotations, and reflections. These transformations preserve distances measured by the L1 norm, making them useful in applications that require maintaining the shape and structure of data.

Similar threads

Replies
9
Views
1K
  • Linear and Abstract Algebra
Replies
17
Views
4K
  • Linear and Abstract Algebra
Replies
1
Views
2K
  • Advanced Physics Homework Help
Replies
20
Views
1K
  • Calculus and Beyond Homework Help
Replies
2
Views
5K
  • Linear and Abstract Algebra
Replies
1
Views
2K
  • Math Proof Training and Practice
Replies
25
Views
2K
  • Calculus and Beyond Homework Help
Replies
5
Views
2K
  • Linear and Abstract Algebra
Replies
1
Views
15K
  • Special and General Relativity
Replies
15
Views
982
Back
Top