This is one of those questions that make sense, but may be hard to prove.

Let $C$ be a nonempty closed convex pointed cone in a $n$-dimensional linear space $X$.

Also, assume that $int(C)\neq \emptyset$, so $span(C)=X$.

Motivation: A result by Fenchel (Lecture notes 1951, Thm. 7) tells us that any nonzero $x\in C$ can be written in the form $x=\sum_{i=1}^n\alpha_i x_i$ for some linearly independent vectors $x_1,\ldots,x_n\in C$ and some nonnegative scalars $\alpha_1,\ldots,\alpha_n$.

My question: Now, then let $x\in int(C)$. Is the following also true?

There exist linearly independent vectors $x_1,\ldots,x_n\in C$ such that $x=\sum_{i=1}^n \alpha_i x_i$, where $\alpha_i>0$, $\forall i\in \{1,\ldots,n\}$.

That is, can we always find such a representation with $n$ strictly positive coefficients, for interior points of $C$?

Thank you!

Reference: https://www.convexoptimization.com/TOOLS/Fenchel1951.pdf

Edit: Added "pointed" after a counterexample by @copper.hat.

  • 2
    $\begingroup$ If $x \neq 0$ then since $x \in C$ you have $x=1 \cdot x$. If $n=1$ and you take the $C=\mathbb{R}$ then $x=0$ cannot be written in the above fashion. $\endgroup$
    – copper.hat
    Aug 26 '21 at 16:22
  • $\begingroup$ @copper.hat You're right in your second statement, my question was not well formulated. I just added an assumption that $C$ is pointed as well, so $0\notin int(C)$. About your first statement, note that we're looking for a combination of exactly $n$ l.i. points of $C$. $\endgroup$
    – Myth
    Aug 26 '21 at 17:02

Yes this is possible. Note that the set $$S^{n-1}=\left\{\sum\alpha_ix_i\mid\alpha_i\ge0,\;\sum\alpha_i=1\right\}$$ is the affine $(n-1)$-simplex with vertices $\{x_i\}_{i=1}^n$ (see for example https://en.wikipedia.org/wiki/Simplex). If we let some of the $\alpha_i$'s be $0$ then we get a set of the same form where we have basically ignored some of the $x_i$'s, in other words we get a lower dimensional simplex $S^{n-m-1}$ (where $m$ is the number of $\alpha_i$'s which are zero. Crucially note that $S^{n-1}$ is the convex hull of the set $\{x_i\}_{i=1}^n$, and $S^{n-m-1}$ lies entirely in its boundary.

Now, given that your choice of $x$ is in the interior of $C$, the set $\{x_i\}_{i=1}^n$ can be chosen such that $x$ lies in the interior of the cone $$\mathbb{R}^{\ge0}S^{n-1}=\left\{\sum\alpha_ix_i\mid\alpha_i\ge0\right\}.$$ But from what I said above, the interior of this cone is exactly the set $$\left\{\sum\alpha_ix_i\mid\alpha_i\gneq0\right\}.$$


The slightly underhand part of my answer above is that I did not justify

the set $\{x_i\}_{i=1}^n$ can be chosen such that $x$ lies in the interior of the cone $$\mathbb{R}^{\ge0}S^{n-1}=\left\{\sum\alpha_ix_i\mid\alpha_i\ge0\right\}.$$

so let me do that explicitly. The point $x$ is in the interior of of $C$, so let $B=B(x,\varepsilon)$ be a closed ball centred on $x$ contained in $C$, and let $\partial B=\mathbb{S}^{n-1}$ be its boundary. There are $n$ points $\{x_i\}_{i=1}^n$ on $\mathbb{S}^{n-1}$ which define an $(n-1)$-simplex $S^{n-1}$ containing $x$ in its interior (and clearly $\{x_i\}_{i=1}^n$ must be linearly independent since they are not co-hyperplanar).

  • $\begingroup$ Hey, thank you! I was trying to follow the same path as you, but the hard part for me was to prove that "the set $\{x_i\}^n_{i=1}$ can be chosen such that x lies in the interior of the cone $\mathbb{R}^{\geq 0} S^n$". If there's no such simplex, then $x$ must be at the boundary of $C$, right? But how can we prove that? I also added the "pointed" assumption so $x=0$ is not an interior point of $C$. $\endgroup$
    – Myth
    Aug 26 '21 at 17:06
  • $\begingroup$ I realised I got the dimension of the simplex wrong, so I fixed that, and added justification of the point you queried. Is that now convincing? $\endgroup$ Aug 26 '21 at 17:26
  • $\begingroup$ Yes, thank you! It's really a pity that I cannot accept more than one answer, since the other one is also really good. $\endgroup$
    – Myth
    Aug 26 '21 at 17:32

Choose $x \in C^\circ$, note that $x \neq 0$. Let $L= \{x\}^\bot$ be the $n-1$ dimensional subspace orthogonal to $x$. Let $b_1,...,b_{n-1}$ be an orthogonal basis for $L$ and note that $0 = b_1+\cdots+b_{n-1} + b_n$ where $b_n=(-1) (b_1+\cdots+b_{n-1})$ (note that the $b_k$ are affinely independent). Choose $\epsilon$ such that $x+\epsilon b_k \in C^\circ$ and note that the points $x+\epsilon b_k$ are linearly independent.

  • $\begingroup$ Thank you, this is really clever. $\endgroup$
    – Myth
    Aug 26 '21 at 17:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.