Affine Combinations and Span

39 Views Asked by At

I was reading a bit of convex analysis and came across this problem.

Let $S$ be convex. Let $A$ be the set of finite affine combinations of points in $S$ (i.e. finite linear combinations whose weights sum to $1$). Prove that the difference $A+(-A)$, where $+$ denotes the Minkowski sum, is the span of $S+(-S)$.

It seems like one direction of the set containment is straightforward (going from the span to the difference).

In the other direction starting with the difference, I ran into a roadblock. We can express elements as differences of finite affine combinations, but I did not manage to decompose it as a linear combination of differences of elements in $S$. I also tried Caratheodory's theorem (since $A$ is convex) to try to force the decomposition, but the question of which differences of elements in $S$ to choose still remains (I am still not sure why $S$ being convex is relevant).

I am looking for an efficient method to prove this other direction, as it seems like several other argument paths require too much case analysis.

1

There are 1 best solutions below

3
On

Let $r_1 x_1 + \ldots + r_m x_m$ and $s_1 y_1 + \ldots + s_n y_n$ be elements of $A$, i.e., two affine combinations where all the $x_i$ and $y_j$ belong to $S$. Then $r_m = 1 - (r_1 + \ldots + r_{m-1})$ and so we may write

$$r_1 x_1 + \ldots + r_m x_m = r_1(x_1 - x_m) + \ldots + r_{m-1}(x_{m-1}-x_m) + x_m$$ with a similar observation for $s_1 y_1 + \ldots + s_n y_n$. Then

$$(r_1 x_1 + \ldots + r_m x_m) - (s_1 y_1 + \ldots + s_n y_n) =$$ $$r_1(x_1 - x_m) + \ldots + r_{n-1}(x_{m-1} - x_m) - s_1(y_1 - y_m) + \ldots - s_n(y_{n-1} - y_n) + 1 \cdot (x_m - y_n)$$ is manifestly a linear combination of elements of $S + (-S)$, and so $A + (-A) \subseteq \mathrm{span}(S + (-S))$, which seems to be the direction you want.

By the way, the other inclusion is wrong for $S$ the empty set! Because the span always contains the zero element and yet $A$ and $-A$ and $A + (-A)$ for this case are all empty!