1
$\begingroup$

I want to check my understanding of matroid concept.

Consider, for example, matrix $\begin{pmatrix} 1 & 0 & 0 & 0 & 0\\ 0 & 1 & 1 & 0 & 0\\ 0 & 1 & 0 & 1 & 0 \end{pmatrix}$.

For convenience, lets denote every column starting from left side as $a,b,c,d,e$.

Then, what will be $\cal{I}$? Is it the set of all independent sets $\cal{I} = \{\emptyset,a,b,c,d,e,ab,bc,bd,ac,ad,cd,abc,abd,acd\}$ or is $\cal{I}$ a particular independent set from this collection? It seems straight from definition that $\cal{I}$ should be the set of all independent sets, but I know that for graphic matroids $\cal{I}$ would be definitely the spanning forest (or spanning tree for connected graph), not the set of all possible combinations of spanning forest edges. I'm a little bit confused with this difference.

What are the bases of that column matroid? Am I right that $\cal{B} = \{abc,abd,acd\}$?

What are the loops? Is it only $e$?

What are coloops? Are there $a,b,c$?

Please correct, if I did any mistakes. Any help and additional explanations will be very appreciative.

$\endgroup$
3
$\begingroup$

To the extent that "$\mathcal{I}$" has a canonical meaning in matroid theory (I guess you could say following Oxley's terminology), $\mathcal{I}$ is the collection of independent sets.

You have a number of things backwards. If you're working from a book on matroid theory, read the first chapter and do some exercises. If you're not, get one.

A spanning forest for a graphic matroid is a basis, and as you know, a basis is an independent set. There's nothing special about any particular basis, or any particular spanning forest. They all have the maximum number of elements (edges) without having any circuits (cycles) within them.

Enumerating independent sets isn't a very efficient task. It's generally a better idea to find all the bases and then use the inheritance axiom of independent sets to say that the subsets are independent (but even that can be computationally hard for large examples).

A loop is an element that is not in any basis, and a coloop is an element that is in every basis. In your linear matroid example, you should say what field the matrix is over (although for such a small example, it doesn't really matter). Then independence or dependence works exactly like it does in linear algebra-- a set of vectors is dependent if some nonzero linear combination of them adds to zero. You can see that $a$ is a coloop because it is the only element that spans row $1$. Without using $a$, you can only have independent sets of size at most $2$.

So what does that say about $e$?

$\endgroup$
2
  • 1
    $\begingroup$ Thanks, your answer really clarifies my doubts about spanning forest in graphic matroid -- it is actually a basis, not $\cal{I}$. I also finally understood definitions of loops and coloops in terms of linear independence. As for $e$, it is a loop, since zero column is linearly dependent with any other, therefore can't be in any basis. $\endgroup$
    – Hasek
    Nov 14 '17 at 10:45
  • 1
    $\begingroup$ The reason that it doesn't really matter which field the entries of the matrix are supposed to be in is not so much that the example is small. There are matroids on fewer elements and with smaller smaller rank that are not representable over every field. The reason is that the matrix is totally unimodular and so is itself a representation of the underlying matroid over any field. In this sense it not only doesn't really matter which field you work over, but it really doesn't matter. $\endgroup$
    – Aaron Dall
    Nov 14 '17 at 23:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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