Circuits of matroid after adding rows to its representation

77 Views Asked by At

I just started learning about matroids and oriented matroids, and my point of interest is their relation to the ideals of linear varieties/subspaces.

If I start with a proper linear subspace $L \subset \mathbb{R}^n$ spanned by column vectors $\vec{u}$ and $\vec{v}$, I can associate to it the matroid $M(L)$ represented by

$\begin{bmatrix}\vec{u}^T\\ \vec{v}^T\end{bmatrix}$

If I now take another vector $\vec{w}$, and define a linear subspace $L + \vec{w} = span\{\vec{u},\vec{v},\vec{w}\}$, consider the matroid $M(L+\vec{w})$: how does this matroid relate to $M(L)$, $L$, and $\vec{w}$? For example, can its circuits be understood in terms of the circuits of $M(L)$, possibly as the union of certain circuits, determined by the particular relation of $\vec{w}$ to $L$?

1

There are 1 best solutions below

7
On BEST ANSWER

I am assuming that the ground set of your matroids are $[n]$, corresponding to the columns of your matrix.

The notion relating $M(L+w)$ and $M(L)$ is a matroid quotient. Given matroids $M$ and $N$ on the same ground set, $M$ is a quotient of $N$, denoted $M \to N$, if every flat of $N$ is also a flat of $M$. This is equivalent to requiring that every (union of) circuit(s) of $M$ is a union of circuits of $N$, as cocircuits are complements of hyperplanes and by duality.

Theorem: if $L \subseteq L'$ are linear spaces, then $M(L') \to M(L)$ is a matroid quotient.

Proof: Given a linear space $L \subseteq \mathbb{R}^n$, let $L^\perp$ denote the orthogonal linear space with the standard dot produc. Also, let $supp: \mathbb{R}^n \to [n]$ be the map sending a vector to its support, i.e. the set of coordinates which are nonzero. Then the circuits of $M(L)$ are exactly the sets in $supp(L^\perp) \setminus \varnothing$ which are minimal with respect to inclusion.1 In fact, every element of $supp(L^\perp)$ is a union of circuits.2 Then if $L \subseteq L'$, by taking orthogonal complements $L^\perp \supseteq L'^\perp$, so $supp(L^\perp) \supseteq supp(L'^\perp)$. Thus, every circuit of $M(L')$ is a union of circuits of $M(L)$, i.e. there is a matroid quotient $M(L') \to M(L)$.

When a quotient $M \to N$ has $rk\, M - rk\, N = 1$, these quotients are equivalent to so-called modular cuts. This story can be found in the "Constructions" chapter of Oxley's book.

The same story holds for oriented matroids if we replace the appropriate notions above with their signed analogues. In particular, support must be replaced by signed support, and union of circuits must be replaced by component-wise "addition" $\circ$ defined by $+ \circ x = +, 0 \circ x = x, - \circ - = -$. A similar story also holds for valuated matroids, and in general matroids over tracts.


1 Circuits correspond to minimal dependent sets, which for a vector matroid correspond to dependence relations (i.e. perpendicular vectors) of minimal support.

2 This can be proved by induction as follows: if $v \in L^\perp$ and $supp(v)$ is not minimal, pick $w \in L^\perp$ such that $supp(w) \subseteq supp(v)$. Then for some $\lambda$, we have $supp(v + \lambda w)$ is strictly smaller than $supp(v)$ and can induct.