I find that this proposition is hardly found in textbooks. And its proof is not easily found on the internet (including asking ChatGPT). Therefore I write it down here as a reference.
function co(X::Set) return convex_hull(X) end
[Proposition1] co(X) × co(Y) == co(X × Y) # "×" is the times---Cartesian Product symbol
[Corollary] ⨉_i co(S_i) = co(⨉_i S_i), # "⨉" is the bigtimes---Cartesian Product symbol
Proof:
Assume there is a point denoted by (x, y) ∈ co(X) × co(Y), where
x ∈ co(X) with x = _p * _x + p_ * x_ for some
_x, x_ ∈ X and _p, p_ ≥ 0 and _p + p_ == 1;
y ∈ co(Y) with y = _q * _y + q_ * y_ for some
_y, y_ ∈ Y and _q, q_ ≥ 0 and _q + q_ == 1;
We need to prove that (x, y) ∈ co(X × Y).
Indeed, there are 4 points in X × Y as follows
# point => its coefficient in a convex combination
(_x, _y) => _p * _q
(_x, y_) => _p * q_
(x_, _y) => p_ * _q
(x_, y_) => p_ * q_
such that their convex combination is precisely (x, y).
Therefore we've proved (x, y) ∈ co(X × Y).
The reverse direction is easier, hence omitted.
Therefore [Proposition1] holds.
Furthermore, co(X) × co(Y) × co(Z)
= co(X × Y) × co(Z)
= co(X × Y × Z).
Likewise, we conclude that [Corollary] holds.
Top comments (2)
This proposition was used in [Proposition 2, ref 1].
ref 1: doi.org/10.1016/S0167-6377(98)00050-9
Not every point in the convex hull of X (Y) can be written as a convex combination of just two points in X (Y), as by the Carathéodory's theorem. This makes the actual proof a bit more intricate, as X and Y may have different dimensions. Nevertheless, I believe the general idea is right. It should be enough that (x,y) is a convex combination of k points in
co(X x Y)iff x and y are convex combinations of the k points projected into their respective spaces. Making k large enough does the trick.