2
$\begingroup$

In Boyd and Vandenberghe's Convex Optimization, they say $k+1$ points $v_0,\dots, v_k\in\mathbb{R}^n$ are affinely independent if $v_1-v_0,\dots, v_k-v_0$ are linearly independent. They then go on to define the simplex defined by $v_0,\dots, v_k$ to be the convex hull of these points, i.e. the set $C$ given by $$C:=\operatorname{conv}\{v_0,\dots, v_k\} = \{\theta_0v_0+\cdots+ \theta_kv_k\mid \theta_i\ge 0\forall i, \sum_{i=1}^k \theta_i=1\}.$$

They claim that the affine dimension of $C$ is equal to $k$, that is the dimension of $V:=\operatorname{aff}(C)-x^*$, where $x^*\in \operatorname{aff}(C)$ is arbitrary. (Note that $V$ is a subspace of $\mathbb{R}^n$ and is independent of the choice of $x^*$.) I was trying to rigorously prove this by finding a basis of this subspace, but I was getting lost in the details.

Looking for help on the proof of this using just the information here (i.e, not using some alternative definition of a simplex, unless proven equivalent). Details would be appreciated! I am not sure if finding a basis is too difficult here or if there is a more clever solution. Note that $$ \operatorname{aff}(C):=\{\gamma_0y_0+\cdots +\gamma_ly_l\mid y_0,\dots,y_l\in C,\gamma_0+\cdots\gamma_l=1\}\\ =\big\{(\gamma_0\theta_{00}+\cdots \gamma_l\theta_{l0})v_0+\cdots +(\gamma_0\theta_{0k}+\cdots \gamma_l\theta_{lk})v_k\mid \gamma_0+\cdots+\gamma_k=1, \\\theta_{ij}\ge 0\forall i,j, \sum_{j=0}^k \theta_{ij}=1\forall1\le i\le l\big\}.$$

$\endgroup$
1
$\begingroup$

For those interested, after thinking about it a little more, it's not too hard of a problem. One can easily show that $$\text{aff}C-v_0=\text{span}\{v_1-v_0,\dots,v_k-v_0\}$$ by some basic manipulation of the above definitions. Since $v_0,\dots, v_k$ are affinely independent, the result follows (since $v_0\in \text{aff}C$). I can put details if desired, but it's fairly elementary.

$\endgroup$
  • $\begingroup$ It's equivalent to showing that $v_i-v_0$ for all $1 \leq i \leq k$ is a basis for $\mathbb{R}^k.$ $\endgroup$ – Vivek Kaushik May 20 '17 at 19:02
  • $\begingroup$ @VivekKaushik these are vectors in $\mathbb{R}^{n}$, so this is obviously not true. $\endgroup$ – Satana May 20 '17 at 19:07
  • $\begingroup$ You're right sorry. I didn't read the $v_i \in \mathbb{R}^n.$ I thought our space was $\mathbb{R}^k.$ $\endgroup$ – Vivek Kaushik May 20 '17 at 19:07
  • $\begingroup$ @VivekKaushik No problem, just making sure! I'm fairly confident my "answer" is correct (i.e., by claim), but let me know otherwise. $\endgroup$ – Satana May 20 '17 at 19:09

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.