1

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?

kaba
  • 2,035
  • 1
    By a non-negative vector you presumably mean $x_i\geq 0$? A matroid doesn't capture the data of signs. You could have two matrices with the same matroid, but such that the nullspace of one is generated by a non-negative vector and of the other by a vector with entries of mixed sign. However, oriented matroids do capture the data of signs; those that have a non-negative vector are called cyclic oriented matroids (easiest example is a directed graph with a directed cycle). I'm not sure that this is exactly what you are looking for, but it might be a step in the right direction. – Randy Marsh Jul 25 '20 at 03:40
  • Totally cyclic oriented matroids are exactly what I was looking for! It seems like literature considers acyclic oriented matroids, but from what I understood their theory is equivalent because they are orthogonal complements of each other? (I have little experience on matroids). So it seems I can translate those results. You could just make that an answer, and I'll accept it. – kaba Jul 25 '20 at 19:20
  • The usual terminology is just "orthogonal", not orthogonal complement, or equivalently, dual. – Randy Marsh Jul 25 '20 at 20:55

1 Answers1

2

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 $\sigma\colon E\to \{-,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.

Randy Marsh
  • 2,857