Proving that removing any vector of the linearly dependent set gives a linearly independent set Consider the matrix representing 6 linearly dependent vectors:
$$\left(\begin{array}{llllll}
1 & 0 & 0 & 0 & 0 & 1 \\
0 & 1 & 0 & 0 & 0 & 1 \\
0 & 0 & 1 & 0 & 0 & 1 \\
0 & 0 & 0 & 1 & 0 & 1 \\
0 & 0 & 0 & 0 & 1 & 1
\end{array}\right)$$
I know how to prove that the vectors in this matrix are linearly dependent, but how can I show (concisely) that removing any one of the vectors we get a linearly independent set?

Here the fastest method I can think of.
If (for example) the first 5 columns are linearly dependent, you can find a vector in the right kernel of the form
$$\left[
\begin{array}a
a\\
b\\
c\\
d\\
e\\
0
\end{array}\right],
$$
that is, a vector that ends with $0$. In general if you leave out the $i-th$ column and the rest are linearly dependent, you find a vector in the right kernel with a $0$ in the $i$-th position.
Since the only vectors in the right kernel of your matrix are the multiples of 
$$\left[
\begin{array}a
1\\
1\\
1\\
1\\
1\\
-1
\end{array}\right]
$$
and it has no zeros, you can deduce that any 5 columns are linearly independent. 
