basis for null space of matrix in a certain field

Question

Let $G=(V,E)$ be a connected graph. Let $T$ be a spanning tree of $G$. Fix a $2$-element field $\mathbb{F}$ (the elements are $\{0,1\}$). Let $S$ be an incidence matrix of $G$ in $\mathbb{F}$. Find a basis $A$ for the null space of $S$ so that for each edge $e\in E\backslash E(T),$ there is exactly one vector $w \in A$ for which $\mathbb{1}_w(e) = 1$ (here $\mathbb{1}_w(e)$ is the function that is $1$ if the entry corresponding to edge $e$ of vector $w$ is $1$ and $0$ otherwise). What are the sets of edges of $G$ corresponding to elements of $A$?

I know that the null space of $S$ has dimension $|E | - |E(T)|.$ However, I'm not sure how to find a basis for the null space. It might be useful to figure out what the left null space and row space of $S$ are, but again I'm not sure how to do that. I also think that a submatrix $F$ of $B$'s columns has linearly dependent columns iff $F$ contains a cycle. I'm not sure if an inductive argument might be useful, seeing as induction seems to be used quite often for proofs in combinatorics.

Answer 1

Note of topological bias: My viewpoint is entirely motivated by cellular homology.

You are right that the null space has dimension $|E|-|E(T)|$ (this should give a hint that your basis has something to do with the edges $E\setminus E(T)$). You are also right that this has to do with cycles. First, let me redefine things a tad to work in a setting free of unnecessary coordinates.

(Note that my graphs can have loops and multiple edges and cycles are allowed to repeat edges. Also, my graphs can be infinite and the same sort of proof will go through).

Take vector spaces $\mathbb{F} E$ and $\mathbb{F}V$ corresponding to finite "sums" of edges and vertices. The incidence "matrix" is then a linear map $S:\mathbb{F}E\rightarrow \mathbb{F}V$ defined on generators by: if $e\in E$ has endpoints $u,v\in V$, then $S(e)=u+v.$ The goal is to understand the kernel of this map.

Definition. Call $y\in \mathbb{F}E$ a cycle if $y=e_1+\dots+e_j$, where $(e_1,\dots,e_j)$ are the edges of a cycle.

Lemma. An element $x\in \mathbb{F}E$ is in $\ker S$ if and only if $x$ is a sum of cycles.

Proof. You can check that cycles are in $\ker S$, using the fact that $2=0$ in $\mathbb{F}$. From this, we get that sums of cycles are also in $\ker S$. Conversely, suppose $x=e_1+\dots+e_j\in\ker S$, for some $e_1,\dots,e_j\in E$. We will show that some of these edges form a cycle. Then we can subtract off that cycle to get a sum of fewer edges, still in $\ker S$. Continuing this process inductively, we can decompose $x$ into a sum of cycles (with no edges occuring more than once). Let $S(e_1)=u+v$. If $u=v$, then $e_1$ is a loop and we're done. Otherwise, there must be some $e_i$ (where $i\neq 1$) with $S(e_i)=v+w$ to cancel out the $v$ coming from $e_1$. If $u=w$, then $(e_1,e_i)$ is a cycle and we're done. Otherwise, we can cancel $w$, etc. Eventually, we must indeed get back to $u$ and thus form a cycle. For otherwise, we will run out of edges without cancelling the $u$ coming from $e_1$, contradicting the fact that $S(x)=0. \ \square$

So now that we've characterized $\ker S$, how can we find an appropriate basis? This requires some facts that I will state without proof. I am going more off of algebraic topology intuition, but I will provide hints that can hopefully help you find inductive proofs form them.

1. If $(e_1,\dots,e_j)$ form a cycle in $T$, then $e_1+\dots+e_j=0\in \mathbb{F}E$. (Hint: The graph spanned by the edges $\{e_i:i=1,\dots,j\}$ is a tree. Why? At a leaf of this tree, the cycle "turns around," so the same edge is repeated twice in a row. Thus, this edge sums with itself to give $0$ in $\mathbb{F}E$ and the remaining edges form a smaller cycle. How does this facilitate a proof by induction?)
2. If $e\in E\setminus E(T)$, then there is a cycle $(e,e_1,\dots,e_j)$, where $e_1,\dots,e_j\in E(T)$. (Hint: Use the fact that $T$ is a spanning tree.)
3. If $x\in \ker S$, then we can write $x=y_0+y_1+\dots+y_k$, where each $y_i$ is a cycle with exactly one edge in $E\setminus E(T)$ and these edges outside of $T$ do not repeat. (Hint: Define a map $\ell:\mathbb{F}E\rightarrow \mathbb N$ as follows: if $x=f_1+\dots+f_m$, where $f_1,\dots,f_m\in E$ are distinct edges, then $\ell(x)$ is the number of $f_i$'s in $E\setminus E(T)$. You can prove (3) by induction on $\ell(x)$. The base case uses (1) and the lemma, where we need to show that $x=0$ and take an empty sum of $y_i$'s. For the inductive step, pick an $e_i\in E\setminus E(T)$ and find a cycle $y$ as in (2). Then we have $\ell(x+y)=\ell(x)-1$ and $x+y\in \ker S$ because $y$ is a cycle.)

For your basis, now take $\{e+e_1+\dots+e_j:e\in E\setminus E(T)\}$, where the cycles $(e,e_1,\dots,e_j)$ come from (2). Use (1) and (3), along with the lemma, to prove that this is indeed basis. By construction, each edge in $E\setminus E(T)$ occurs once in the basis, and each basis element has exactly one edge from $E\setminus E(T)$. This is your desired condition.

Final note: My solution is a little sloppy, in that it doesn't necessarily produce the canonical result: the fundamental cycles that Matt mentioned. That is because I am allowing cycles to have repeating edges. To fix this, you can refine (2) to produce cycles without repeating edges, simply by noting that any two vertices in $G$ are connected by a unique path in $T$ (with no repeating edges). This fact also allows for different proof of (1), which I think is quite nice. See if you can spot it.

Answer 2

What does it mean to be in the null space?
We are working in the field GF(2), so multiplying $S$ by a vector $w$ means that we can interpret $w$ as being a set of edges, and $Sw$ is the list of vertices that are incident to an odd number of edges in $w$. So if $Sw=0$, then all vertices are incident to an even number of edges in $w$. Recalling Eulerian graphs, this means that $w$ can be expressed as a union of cycles.

The basis $A$ for the null space, and edges outside the spanning tree
The problem asks for each edge in $E\,\backslash E(T)$ (each edge outside the spanning tree) to occur in exactly one vector of $A$. This defines a mapping from edges outside the spanning tree to vectors in $A$.

This mapping must be surjective (onto), because every vector in $A$, being a union of cycles, contains at least one edge outside the spanning tree. And as you observed, the null space has dimension $|E|-|E(T)|$, so the number of edges outside the spanning tree is the same as the number of basis vectors in $A$.

The only way to have a surjective mapping to a set of the same finite size is if the mapping is a bijection. So every vector of $A$ contains exactly one edge outside the spanning tree.

The elements of $A$
The only way for a union of cycles to contain exactly one edge outside the spanning tree is for the "union" to be a single cycle, having all edges on the spanning tree except one. Indeed, given any edge not on the spanning tree, there is a unique path in the spanning tree between the two ends of that edge. This yields the unique cycle with this property.

So the elements of $A$ are the fundamental cycles, and $A$ is the fundamental cycle basis.