Reading up on matroid theory in the context of graph optimization and in particular minimum spanning trees. It turns out that finding a set of acyclic arcs is equivalent to finding an independent vector basis of a matrix, which is nice.
In this example, we had a graph consisting of six nodes and nine arcs, which makes a $6\times9$ matrix from which we need to pick out five independent vectors. So there are $9 \choose 5$ potential candidates. What is not clear for me is how this produces a polynomial time algorithm - it seems to me as if all it produces is a possible way of enumerating the elements of the feasible set.
Which of course sounds like brute force, almost by definition. So where does the polynomial time algorithm pop up?
Some clarifications: when speaking of the(??) feasible set being a matroid, your lecturer was probably talking about greedoids in general. The statement about the feasible set being a matroid doesn't make a lot of sense to me, but saying that the greedoid (whose feasible set(s) we're talking about) is a matroid does make sense. Furthermore the matroid in this case (graph) is actually a special kind, called cycle matroid or graphic matroid.
For defining something like MST (or anything with weighted graphs), you further need the notion of weighted matroid. For weighted matroids in general, there is a polynomial time algorithm for finding a maximum-weight basis. And you can use it to find the minimum weight-basis too by "inverting" the weight function, i.e. subtracting it from a large enough constant.
EDIT: Oh, I realized I forgot to tell you anything about the overloading of the term "basis". For a greedoid/matroid, basis simply means a maximal feasible/independent set. It's somewhat natural to ask if this choice of terminology is related in any way to the notion of a basis of a vector space (and in particular of a matrix). The answer is yes, in terms of matroid representation. Briefly:
The linearly independent subsets of a finite set of vectors form a matroid; that's why a maximal such subset is called a basis.
If it exists, a representation of a matroid $(E,F)$ is a function $f$ from $F$ to a vector space $V$ such that a subset $A \subseteq E$ is feasible/independent (in the matroid) if and only if $f(A)$ is (linearly) independent (in the vector space). However, not all matroids are representable this way; those which are so are called linear matroids.
Graphic/cycle matroids are all linear though, and in fact are even regular matroids, meaning that choice of the field for the vector space does not matter. Furthermore, the linear matroid defined by the oriented incidence matrix (interpreted as a set of vectors) of an undirected graph $G$ coincides (is isomorphic with) with the cycle matroid of $G$.
There's a catch here if you try to push this coincidence further to weighted matroids (as to apply it to MST problems): I'm not sure how you can algebraically relate the weighted matroid of a weighted undirected graph to some (unweighted?) matroid of some (weighted?) incidence matrix of that graph. The issue is that on one side the weights get added on top of a "plain" matroid to get a weighted matroid, but on the other side, you'd have a "plain" linear matroid over some real-valued matrix (non just over ${-1, 0, 1}$)... So maybe you should tell us what coefficients you have in your $6\times 9$ matrix.