Suppose we have a subset of edges that contains a cycle. For simplicity, suppose the cycle is given by:

\{pq, qr, rs, st\}

Now consider the column vectors c_p, c_q, c_r, c_s:

\begin{bmatrix}
c_p & c_q & c_r & c_s\\
1 & 0 & 0 & -1 \\
-1 & 1 & 0 & 0 \\
0 & -1 & -1 & 0 \\
0 & 0 & 1 & 1
\end{bmatrix}
Note that:

1 \cdot c_p + 1 \cdot c_q + (-1) \cdot c_r + 1 \cdot c_s

is a linear combination with constants (1,1,-1,1) that establish that these vectors are linearly dependent. In general, write down the columns in the order in which they appear on the cycle. If the first entry in the column is not +1, then multiply the column by -1 (except the last column, where we do the reverse: if the first entry is +1, then we multiply the column by -1). This way, we have a situation where every row contains exactly one +1 entry and one -1 entry, and the linear combination sums to 0.

This shows that dependent subsets of the matroid correspond to linearly dependent columns of M.

To see that independent subsets S \subseteq E(G) correspond to linearly independent columns, consider the set of columns that correspond to S:

\{c_e ~|~ e \in S\ }

Suppose, for the sake of contradiction, that there was some non-trivial linear combination of these columns that vanished, i.e, for non-empty subset T \subseteq S, there exist constants \{\alpha_e\}_{e \in T} where:

\sum_{e \in T} \alpha_e c_e = 0

But now consider the subgraph consisting of the edges in T. Note that the minimum degree of T must be two (suppose u \in T has degree one, and its unique neighbor is v: then consider the entry in the row corresponding to u in the column corresponding to the edge uv: this is non-zero and there is no cancelation possible in the sum above). However, a graph whose minimum degree is two cannot be acyclic, and this is a contradiction.