1
$\begingroup$

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?

$\endgroup$
2
  • $\begingroup$ 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. $\endgroup$ Sep 8, 2016 at 11:59
  • $\begingroup$ related math.stackexchange.com/q/417285/173147 $\endgroup$
    – glS
    Aug 25, 2020 at 15:07

2 Answers 2

1
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ How would I prove this? Using gaussian elimination? $\endgroup$
    – Martin
    Sep 8, 2016 at 12:05
  • $\begingroup$ 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. $\endgroup$ Sep 8, 2016 at 12:08
0
$\begingroup$

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$.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .