Properties of a certain matrix in a certain field 
Let $\mathbb{F}$ be a field on two elements, $0$ and $1$ and $G = (V,E)$ be a graph. Let $S$ be a $|V|\times |E|$ matrix in $F$ whose $(i,j)$ entry is $1$ if edge $j$ is incident with vertex $i$ and $0$ otherwise. Determine, with proof, which vectors are in the null space of $S$ in the field $\mathbb{F}$ and which vectors are in the row space of $S$ in terms of $G$.

By definition, the right null space of $S$ is the set of vectors $x\in \mathbb{F}^{|E|}$ so that $S x = 0.$ Each column of $S$ contains $2$ nonzero entries, since each edge is connected to $2$ vertices. In order for $Sx = 0,$ we need each vertex of $G$ to be incident with an even number of edges corresponding to entries of $x$ ($0$ if the edges are included and $1$ otherwise). But I'm not sure what the set of these vectors represents in terms of $G$.
As for the row space, by definition, the row space is the set of vectors in $\mathbb{F}^{|E|}$ of the form $S^T x$ for some $x\in \mathbb{F}^{|V|}.$ The rows of $S^T$ each have exactly two $1$'s and the rest of the entries are $0$. So if row $e$ of $S^T$ is incident with two vertices $v_1$ and $v_2$ corresponding to entries of $x$, then the $e$th entry of $S^T x$ will be $0.$ Similarly, if row $e$ of $S^T$ is incident with no vertices corresponding to entries of $x$, then the $e$th entry of $S^T x$ will be $0.$ Only when row $e$ of $S^T$ is incident with exactly one vertex corresponding to an entry of $x$ will the $e$th entry of $S^T x$ be $1$. But again I'm not sure what these vectors $S^T x$ represent in terms of $G$.
 A: In the product $Sx$, $x\in\mathbf{F}_2^{\lvert E\rvert}$, the vector $x$ corresponds to a set of edges of $G$. As you've observed, $Sx=0$ means that every vertex of $G$ is incident on an even number of edges of the edge set represented by $x$. The set of edges of a cycle of $G$ has this property. More generally, the set of edges of tour of $G$ has this property. (In a tour, vertices may be visited multiple times, but edges are used only once.) More generally still, the set of edges of a disjoint union of tours has this property. Such disjoint unions are equivalent to edge sets of even-degree subgraphs, or, in other words, subgraphs in which every connected component has an Euler tour.
With regard to the row space of $S$: in the product $x^TS$, $x\in\mathbf{F}_2^{\lvert V\rvert}$, the vector $x$ represents a set of vertices of $G$. The elements of the vector $x^TS$ correspond to edges. As you have found, an element of $x^TS$ equals $0$ when either both vertices on the corresponding edge are in the vertex set corresponding to $x$ or neither vertex is in that set; an element of $x^TS$ equals $1$ when exactly one of the vertices on the corresponding edge is in the vertex set corresponding to $x$. Hence the vector $x^TS$ represents the set of edges that join a vertex in the set corresponding to $x$ to a vertex not in that set. There is an induced subgraph corresponding to $x$, and $x^TS$ can be thought of as the set of external edges—edges connecting to vertices outside the induced subgraph.
The correspondence between row-space vectors and sets of external edges of induced subgraphs is not one-to-one for the following reasons: (1) if $X$ is the sets of vertices corresponding to $x$, the the subgraph induced by $X$ has the same external edge set as the subgraph induced by $V\setminus X$; (2) if $G$ is not connected then any connected component or union of connected components has no external edges, just as the empty subgraph does. In other words, if $y_1$, $y_2$, ..., $y_m$ are vectors corresponding to vertex sets of connected components, then $y_j^TS=0$ for all $j\in\{1,2,\ldots,m\}$ and
$$
(x^T+y_1^T+\ldots+y_m^T)S=x^TS
$$
for any $x\in\mathbf{F}_2^{\lvert V\rvert}$.
So there is a one-to-one correspondence between vectors in the row space of $S$ and equivalence classes of partitions of the vertex set of $G$ into two parts, where the partition $\{X,Y\}$ is the same partition as $\{Y,X\}$. The notion of equivalence being used here is the following: let $V$ be partitioned as $\{X,Y,C\}$ where $C$ is the set of vertices of a connected component of $G$. Then $\{X\cup C,Y\}\sim\{X,Y\cup C\}$.
