algorithms - Checking whether a set family forms a matroid.

Here's a probabilistic approach.

First check if your set family $mathcal{I}$ is closed under taking subsets. If not, then it is not a matroid. Next assign a 'random' weight function $w: S to mathbb{R}_{+}$, to the ground set $S$. Now run the greedy algorithm. If $mathcal{I}$ is indeed a matroid, then the greedy algorithm will output a member $I$ of $mathcal{I}$ of maximum weight. However, we can directly compute the weight of each maximal (under inclusion) member of $mathcal{I}$. So, if $I$ does not have maximum weight, then $mathcal{I}$ is not a matroid. If $I$ does have maximum weight, then this does not mean that $mathcal{I}$ is a matroid, we may have just gotten lucky. So, we choose another random weight function and repeat. I haven't analyzed how many times we need to do this to be reasonably 'sure' that $mathcal{I}$ is a matroid.