definition of closure and circuit of a matroid

444 Views Asked by At

By looking up at definition for closure and circuits of a matroid. It seems they are related.

Closure is the span of a given subspace, and circuit is the minimial dependent set.

By definition, adding a single linear combination of the subspace is a closure, same way it is the minimal dependent set (as the subspace is part of the independent set). So can we say that closure with just one extra element is equal to a circuit ?

To be concrete, consider the linear matroid of the below matrix $$ \begin{bmatrix} 1&0&0&1\\0&1&0&1\\0&0&1&0\\0&0&0&0 \end{bmatrix} $$ $$\text{Ground Set}~~~ \mathbf{E} = {1,2,3,4}$$ $$\operatorname{cl}(\{1,2\}) = \{1,2,4\}$$ and at the same time $$\operatorname{circuit} = \{ \{1,2,4\}\}$$

1

There are 1 best solutions below

0
On BEST ANSWER

It is not true that in a matroid the closure of a set $A$ together with just one element $e$ not in $A$ is equal to a circuit. For example, take

  1. $A = \{2,3\}$ and $e = 1$ in the vector matroid of the OP; or
  2. the closure of any single element in the rank-$1$ vector matroid $[0~1~2~3]$.

What is true is that if $A$ is an independent set (i.e., contains no circuit) and $e \in \mathrm{cl}(A) \setminus A$ then $A \cup \{e\}$ contains a unique circuit.