How to decide whether a linear subspace over $\mathbb{Z}_2$ is the cycle space of some graph?

Question

Preliminaries:

Assume we have a simple graph $G=(V,E)$ (no loops, no multiple edges). If we label the edges with $k=1,\dots,|E|$, its cycle space $C$ can be identified with a linear subspace of $\mathbb{Z}_2^{|E|}$ where $\vec x=(x_1,\dots,x_{|E|})^T\in C$ describes an Eulerian subgraph of $G$ with edges $k$ where $x_k=1$.

Now let $H\leq \mathbb{Z}_2^{L}$ be an arbitrary linear subspace given by a basis $B=\{\vec b_1,\dots,\vec b_N\}$ ($N\leq L$) with the only constraint that for all $i=1,\dots,L$ there is at least one element $\vec x\in H$ such that $x_i=1$ (i.e., there are no trivially "unused" components).

Apparently not all such subspaces $H$ can be interpreted as cycle space of some simple graph $G_H$ with $L$ edges. For instance, $H=\operatorname{span}\{\vec x_1,\vec x_2\}$ with $\vec x_1=(1,1,0)^T$ and $\vec x_2=(0,1,1)^T$ cannot occur as cycle space of any simple graph.

Questions:

1. Is there a characteristic property of $B$ (or $H$) to decide whether $H$ is a cycle space of some graph?

2. Is there an efficient (i.e., polynomial in N and L) algorithm to check this?

My graph theory knowledge is only rudimentary (i.e., self-taught) so that I find it hard to gauge whether this is a trivial textbook question or whether there is more behind it. My literature research did not produce any useful results except for the vague notion that it might be related to graphic matroids (for which there is an efficient algorithm by Tutte).

I would be thankful for any hint/explanation/reference that helps in answering the above questions (in particular the second one).

Answer 1

Matroid theory provides the answers you are looking for.

Given a linear subspace $V$ of an arbitrary vector space let $M$ be any matrix whose kernel is $V$. Let $\mathcal{M}$ be the vector matroid on the columns of $M$. If $V = \mathbb{Z}^n_2$, then $\mathcal{M}$ is called a binary matroid. A graphic matroid is a binary matroid that does not contain contain the matroids dual to either (1) the graphic matroid of $K_5$ (the complete graph on five vertices) or (2) the graphic matroid of $K_{3,3}$ (the complete bipartite graph). See here for more.

The Macaulay2 software package Matroids is useful for computing with these objects. It allows you to define a matroid from a matrix (or a graph or a hyperplane arrangement, etc) and, using the hasMinor method, determine if that matroid has a given matroid as a minor.