Constructing Vector Matroid Algorithm

Question

Suppose I am given a set $V$ of $n$ vectors in $\mathbb{R}^3$. I want to construct the matroid associated with these vectors (i.e. $M=(E,\mathcal{I})$ with $E=\{1,\dots, n\}$ and $E\supseteq I\in\mathcal{I}$ if $\{v_i:i\in I\}$ are linear independent). I am wondering what the most efficient algorithms is to generate all the independent sets? Can I do better than to consider all subsets of $V$ of size at most 3 and determine if the vectors are linearly independent?

Answer 1

I assume that $n>3$. You do not have to check all subsets of size at most 3. It suffices to check the subsets of size exactly 3. The subsets of size 3 which are independent are the bases of the matroid. The independet sets of size less than 3 are the proper subsets of the bases.

There is a total of $\binom{n}{3}=\frac{n!}{(n-3)!3!}=\frac{n(n-1)(n-2)}{6}=\frac{n^3-3n^2+2n}{6}$ subsets of size 3 you would have to check this way. While this still takes up a lot of time it is still an improvement over checking all $2^n$ subsets.

A potential improvement to the performance could be the following. Assume you find that a 3 element set $\{e_1,e_2,e_3\}$ turns out to be dependent. You could take a closer look at that set and check whether or not there is a 2-element dependent subset in it (i.e. you have $e_i=k\cdot e_j$ for $i,j\in\{1,2,3\}$ and $i\not =j$. You can then neglect all 3 element subsets which contain both $e_i$ and $e_j$ in the next iterations. However, each such pair $(e_i,e_j)$ saves you from looking at at most $(n-1)$ subsets. Hence, the possible improvement you can obtain this way is only very small.