Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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 ?

share|improve this question
add comment

1 Answer

up vote 2 down vote accepted

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.

share|improve this answer
add comment

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.