1

I don't get this step in proof of Carathéodory's theorem (convex hull) Why:

Suppose k > d + 1 (otherwise, there is nothing to prove). Then, the points $x_2 − x_1, ..., x_k − x_1$ are linearly dependent

Why is this true?

How can we cay these points are linearly dependent?

glS
  • 6,818
Martin
  • 155
  • There are at least $d+1$ such points. The dimension of the space is $d$, so the maximum linearly independent set can have only $d$ elements. Hence, one of them is linearly dependent on the others. – Sarvesh Ravichandran Iyer Sep 08 '16 at 11:59
  • related https://math.stackexchange.com/q/417285/173147 – glS Aug 25 '20 at 15:07

2 Answers2

1

Note that $k > d+1$, and that our points are vectors in $\Bbb R^d$. In $\Bbb R^d$ (or any $d$-dimensional vector space), any set consisting of more than $d$ vectors is linearly dependent.

Ben Grossmann
  • 225,327
  • How would I prove this? Using gaussian elimination? – Martin Sep 08 '16 at 12:05
  • What is there to prove? This is the definition of dimension. If you want to prove that $\Bbb R^d$ is indeed a $d$-dimensional space, it suffices to consider the usual basis. If you want the proof that every basis for a vector space contains the same number of elements (which is to say that dimension is well-defined), then you're looking for the dimension theorem. – Ben Grossmann Sep 08 '16 at 12:08
0

What is the cardinality of $\{x_2 − x_1, ..., x_k − x_1\}$? Now remember that there aren't any linearly independent set of cardinality greater than $d$ in $\Bbb R^d$.

Surb
  • 55,662