# Why if $k>d+1$ then $\{x_j-x_1\}_{j=2}^k\subset \mathbb R^d$ is linearly dependent?

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?

• 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. Sep 8, 2016 at 11:59
• – glS
Aug 25, 2020 at 15:07

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.
• 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. Sep 8, 2016 at 12:08
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$.