Point in convex hull with negative weights

297 Views Asked by At

Consider a set of points $\textbf{x}^1,\dotsc,\textbf{x}^m \in \mathbb{R}^n$. The affine hull of the $m$ points contains all points $\textbf{z}$ for which there exists a $\lambda$ such that $$ \textbf{z} = \sum_{i=1}^m \lambda_i \textbf{x}^i ~\text{ and }~ \sum_{i=1}^m \lambda_i =1. ~~~~~~(1) $$ If the point $\textbf{z}$ is in the convex hull of $\textbf{x}^1,\dotsc,\textbf{x}^m$, then there exists weight vector $\lambda$ that additionally satisfies $\lambda_i \geq 0$ for all $i$. However, this result does not say that ‘inside convex hull implies weights must be nonnegative’, it only states that there exists a nonnegative weight vector.

My question is: Is it possible that, for $\textbf{z}$ in the convex hull of $\textbf{x}^1,\dotsc,\textbf{x}^m$, there exists a weight vector $\lambda$ satisfying (1) and $\lambda_j <0$ for some $j$? Differently stated: Is it possible that a vector $\textbf{z}$ can be written as both an affine combination with at least one negative weights and a convex combination?

1

There are 1 best solutions below

0
On BEST ANSWER

Not if $x^1,\ldots x^m$ are affinely independent.

Let's assume $\lambda_1\geq 0$, and rewrite $z$ as follows

$\lambda_{1}=1-\sum_{i=2}^{m}\lambda_{i}$

$z=x^{1}+\sum_{i=2}^{m}\lambda_{i}(x^{i}-x^{1})$

If the $\{x^1,\ldots x^m\}$ was an affine basis, the $\{x^2-x^1,\ldots x^m-x^1\}$ is a linear basis of the associated vector space, Affine_space#Affine_span_and_bases.

A negative coordinate takes the point outside of the positive hyper-quadrant containing the convex hull.

Otherwise, say if $x^2=x^1$ then $x^2=(-1)x^1+(2)x^2$