# Matroid induced by a matrix where a circuit's nullspace is spanned by a non-negative vector

Mathematics Asked by kaba on January 7, 2022

Let $$A = [a_1, dots, a_n] in mathbb{R}^{m times n}$$, $$[n] = {1, dots, n}$$, and $$mathcal{I} subset mathcal{P}([n])$$ be the set of all $$I in mathcal{P}([n])$$ such that $${a_i : i in I}$$ is linearly independent for each $$I in mathcal{I}$$. Then $$M_A = ([n], mathcal{I})$$ is the matroid induced by $$A$$.

A circuit of $$M_A$$ is a minimal dependent set; i.e. a collection of column-indices of $$A$$ such that the columns are linearly dependent, but each proper subset is linearly independent. If we gather the columns of a circuit of $$A$$ into a matrix $$C in mathbb{R}^{m times q}$$, then $$C$$ has a 1-dimensional nullspace.

I’m looking for information about matroids induced by such matrices $$A$$ that each circuit nullspace can be spanned by a non-negative vector $$x in mathbb{R}^q$$; i.e. such that $$x geq 0$$.

Someone must have studied these kinds of matroids before. What are they called?

Matroids do not capture the data of signs, and in general they don't capture anything about the coefficients in a linear dependency except the combinatorial properties, e.g. $$7x-pi^2y+444z=0$$ from a matroid point of view (in characteristic $$0$$) results in the same dependency data as $$-x+y-z=0$$.

Hence one can have two matrices $$A_1$$ and $$A_2$$ such that their matroid is the same, but with a 1-dimensional nullspace generated by a positive and a mixed-sign vector, respectively, e.g. $$A_1=pmatrix{1 & 0 & -1\ 0 & 1 & -1}~text{and}~A_2=pmatrix{1 & 0 & 1\ 0 & 1 & 1}$$ have their null-space generated by $$(1~1~1)$$ and $$(-1~-1~1)$$, respectively, yet they have the same matroid since their collection of circuits is the same, i.e. the column-index set $${1,2,3}$$ is the only circuit.

Oriented matroids capture the data of signs in a linear dependency, direction in a directed graph, or the sides of a hyperplane. Oriented matroids are therefore matroids decorated with a sign function $$sigmacolon Eto {-,0,+}$$, so e.g. a circuit is a circuit in the matroid sense, but it is also decorated with additional data, so the usual circuit cryptomorphism has to be refined to account for this additional data.

Those oriented matroids that have a positive circuit (all decorations are +) are called cyclic. A simple example arises from a directed graph which has a directed cycle. Those in which every element is contained in a positive circuit are called totally cyclic. Those that do not have a positive circuit are called acyclic, and the dual of an acyclic oriented matroid is totally cyclic.

Answered by Randy Marsh on January 7, 2022

## Related Questions

### Numerically approximating the second order derivative at the end points of a closed interval

0  Asked on October 5, 2020 by aulwmate

### How are those vectors linearly independent?

1  Asked on October 5, 2020 by user378298

### Computing the variance of hypergeometric distribution using indicator functions

3  Asked on October 5, 2020 by xxx

### KF Riley problem 13.7

0  Asked on October 4, 2020 by user215736

### Critical values of the evaluation map for rational curves in toric surface

0  Asked on October 3, 2020 by blm

### Monoid, where $2+2 = 2$

0  Asked on October 3, 2020 by hekto

### Can a non-inner automorphism map every subgroup to its conjugate?

1  Asked on October 3, 2020 by benjamin

### Solving a system of nonlinear equations: show uniqueness or multiplicity of solutions

1  Asked on October 2, 2020 by stf

### Is there a symbol or notation for collinearity?

2  Asked on October 2, 2020 by kantura

### Why is the Volume integration & Surface Area integration of a sphere different?

1  Asked on October 1, 2020 by vignesh-sk

### Let $(X,d)$ be a metric space and $x_0∈X$ be a limit point of $X-{x_0}$

1  Asked on October 1, 2020 by calmat

### Cross Product of Image of Self-Adjoint Operator

1  Asked on September 30, 2020 by jos-victor-gomes

### Finding the associated unit eigenvector

1  Asked on September 30, 2020 by laufen

### how to solve rational problem solving question

1  Asked on September 29, 2020 by ranveer-masuta

### 3 category car insurance probability

1  Asked on September 29, 2020 by mizerex

### Relationship between projection of $y$ onto $x_1, x_2$ individually vs. projection on both?

0  Asked on September 29, 2020 by roulette01

### How do you solve for the intersection or multiplication rule of three dependent events?

1  Asked on September 27, 2020 by androidv11

### Looking for some background on closed linear span

0  Asked on September 25, 2020 by integrand

### a subset of $l_2$.

1  Asked on September 24, 2020 by luiza-silva

### Is the union of finitely many open sets in an omega-cover contained within some member of the cover?

2  Asked on September 23, 2020 by objectivesea