# What are matroids and in what cases are they useful?

I came across the concept of matroids while studying up on the concept of greedy algorithms specifically The minimum spanning tree problem . I got this definition from Wolfram MathWorld:

Roughly speaking, a matroid is a finite set together with a generalization of a concept from linear algebra that satisfies a natural set of properties for that concept. For example, the finite set could be the rows of a matrix, and the generalizing concept could be linear dependence and independence of any subset of rows of the matrix.

Intuitively what does matroid help us to do ? Also what is meant by this example ? can some one please clarify ?

-

## 1 Answer

A matroid gives a general description of those problems where a greedy algorithm provides an optimal solution. Intuitively, they state that you can build a solution step-by-step (this is given by two of the matroid properties, "the empty set is contained in the matroid" and "if a set is contained in the matroid, every subset is contained as well"), and if the solution can be further optimized, it doesn't matter which path you take to the optimum (this is the exchange property of matroids).

The example is, in my opinion, not really illustrative. What they mean is: Say you are trying to find a basis for the vector space generated by the rows of a matrix. The basis is a finite subset of these rows, and a basis is a maximal linear independent set. Now, we know that the empty set is (trivially) linearly indepedent, and every subset of a linearly independent set is also linearly indepedent. Also, if a set is linear indepedenent but not a basis, it doesn't matter which exact new vector we add (as long as it's linearly independent) - every valid extension will lead us to a basis.

-