Theorem. A subset S of a vector space V is linearly independent if and only if 0 cannot be expressed as a linear combination of elements of S with non-zero coefficients.

Proof. 1. Suppose that a subset S of a vector space V is linearly independent. We need to prove that 0 cannot be expressed as a linear combination of elements of S with non-zero coefficients.

By contradiction, suppose that

where s₁,...,s_n are elements of S and not allcoefficients are equal to 0. Let x_i be a non-zero coefficient.

By subtracting x_is_i from both sides and dividing the resulting equality by -x_i we get:

where s_i is missing in the left hand sum. This equality implies that s_i is a linear combination of other elements of S. We obtained a contradiction with our assumption that S is linearly independent, which completes the proof.

2. Now we need to prove that if 0 cannot be expressed as a linear combination of elements of S with non-zero coefficients then S is linearly independent. By contradiction, suppose that S is not linearly independent. Then there exists an element s in S which is equal to a linear combination of other elements of S:

By subtracting s from both sides, we get:

Thus we have a linear combination of distinct elements of S which is equal to 0 and not all coefficients of this linear combination are equal to zero (for example, the coefficient of s is -1).

The proof is complete.