5
$\begingroup$

Given $E$ a finite subset of a real vector space $V$, a circuit of the associated matroid is a minimal linearly dependent subset of $E$. For each circuit $\underline C$, a minimal linear dependence $$\sum_{v\in \underline C}\lambda_vv=0$$ gives rise to a signed circuit $C = (C^+,C^-)$ defined by $$C^+= \{v\in \underline C: \lambda_v>0\}$$ and $$C^-=\{v\in \underline C:\lambda_v<0\}.$$ (So $(C^-,C^+)$ is also a signed circuit.)

Given an arbitrary linear dependence of the form $$\sum_{v\in S\subset E}\lambda_v v = 0$$ with $\lambda_v\neq 0$ for all $v\in S$, by definition there is a circuit $\underline C$ with $\underline C\subset S$.

My question is: if we define $S^+ = \{v\in S:\lambda_v>0\}$ and $S^-=\{v\in S:\lambda_v<0\}$, must there exist a signed circuit $C$ with $C^+\subset S^+$ and $C^-\subset S^-$? Certainly not every circuit $\underline C\subset S$ has such a signature, but it seems easy enough to find one in particular examples by ad hoc means.

If it's useful or necessary, for my purposes I am only interested in situations where all coefficients are integers.

Thanks.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
6
$\begingroup$

Yes. If the dependence is minimal, then $(S^+, S^-)$ is a signed circuit. Now suppose that the dependence is not minimal. Then there is a subset $T\subsetneq S$ and a dependence $$\sum_{v\in T} \mu_v v =0$$ with $\mu_v \neq 0$ for all $v \in T$. Define $\mu_v=0$ for $v\in S\setminus T$. Let $t$ be the smallest positive real number such that $\lambda_v+t\mu_v=0$ or $\lambda_v-t\mu_v=0$ for some $v\in S$. Without loss of generality, suppose that the first case happened. Let $\rho_v=\lambda_v+t\mu_v$ for all $v\in S$. Then $$\sum_{v\in T} \rho_v v =0,$$ there is a $u\in S\setminus T$ such that $\rho_u\neq 0$, there is a $w\in T$ such that $\rho_w=0$, and for all $v \in S$, we have $\lambda_v\rho_v \ge 0$. In other words, we obtained a smaller dependence $S_1 \subsetneq S$, where $S_1^+\subseteq S^+$ and $S_1^-\subseteq S^-$. A signed circuit is then obtained by induction.

Improve this answer
$\endgroup$
6
  • $\begingroup$ Thank you for your reply. Could you explain why there is a $u\in T$ with $\rho_u\neq 0$, please? It seems to me that if there were some $T\subsetneq S$ such that $\sum_{v\in T}\lambda_vv=0$, then taking $\mu_v = -\lambda_v$ for $v\in T$ we would have $t=1$ and $\rho_v=0$ for all $v\in T$. $\endgroup$
    – bradhd
    Feb 12, 2014 at 0:07
  • $\begingroup$ On further reflection my counterexample above isn't relevant - you can assume without loss of generality that $\sum_{v\in T}\lambda_vv\neq 0$ for each $T\subsetneq S$, as otherwise you could just pass to this analysis on such a $T$. $\endgroup$
    – bradhd
    Feb 12, 2014 at 0:19
  • $\begingroup$ Is this fact written down somewhere (outside of MO, I mean)? I would like to cite it in my work. $\endgroup$
    – bradhd
    Feb 12, 2014 at 0:48
  • $\begingroup$ @Brad sorry for the confusion, I made a mistake: the $u$ should be taken from $S\setminus T$. Then it follows from the choice $\mu_u=0$. I am editing the answer accordingly. $\endgroup$
    – Jan Kyncl
    Feb 12, 2014 at 2:35
  • 1
    $\begingroup$ @Brad this proof is analogous to the proof of Radon's theorem. It also very likely follows from the theory of oriented matroids. For example, by Proposition 3.7.2 in the book "Oriented matroids" by Bjorner et al. (ams.org/mathscinet-getitem?mr=1744046). $\endgroup$
    – Jan Kyncl
    Feb 12, 2014 at 2:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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