0
$\begingroup$

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\}\}$$

$\endgroup$
1
  • $\begingroup$ Taking the closure of a set together with one extra element of the matroid is in general not a circuit. For example, in your matrix above the closure of columns 2 and 3 is $\{2,3\}$ and adding any other element to this set is a basis of the matroid and not a circuit. For another example, take any matrix with exactly one row and many nonzero entries. Then the closure of any nonzero column is the set of all elements of the matroid. This set contains many circuits. $\endgroup$
    – Aaron Dall
    Dec 18 '17 at 7:57
0
$\begingroup$

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.

$\endgroup$

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.