Prove the statements are equivalent for a directed graph $(V, E)$ and linear map $\partial:\Bbb R[E]\rightarrow\Bbb R[V]$

Question

For a directed graph $(V,E),$ there is a linear map $\partial:\Bbb R[E]\rightarrow\Bbb R[V]$ defined by $\partial(a,b)=b-a.\\$ Prove that the following are equivalent for a directed graph $(V, E)$: $\;\mathbf{(1)} \text{ dim } \Bbb R[V]-\text{dim im }\partial=\#V-\text{dim im }\partial=1 \\\;\mathbf{(2)}\text{ }V \text{ is non-empty and for some choice }v\in V \text{ and } (v_1,w_1),...,(v_n,w_n)\in E, \;\{v,w_1-v_1,...,w_n-v_n\} \text{ is a basis for }\Bbb R[V]\\\;\mathbf{(3)}\text{ } (V,E) \text{ is connected (ie }V \text{ is non-empty and for every pair } v,w\in V, \text{ there exists a path in } (V,E) \text{ connecting } v \text{ to }w \text{)}$

My attempt:

$\mathbf{(1)}\implies\mathbf{(2)}$ Since $\#V=1+\text{dim im}\partial\geq1,$ then $V$ non-empty. Let $\{w_1-v_1,...,w_n-v_n\}$ be a basis for im $\partial$. Since im $\partial$ is a subspace of $\Bbb R[V]$ and dim $\Bbb R[V]=1+\text{dim im }\partial,$ then we can extend the basis for im $\partial$ to a basis for $\Bbb R[V]$ by choosing appropriate $v\in V.$ Then $\{v,w_1-v_1,...,w_n-v_n\}$ is a basis for $\Bbb R[V].$

$\mathbf{(2)}\implies\mathbf{(3)}$ Let $v,w \in V.$ Then $w-v\in \Bbb R[V],$ so $w-v$ can be written uniquely as $w-v=\alpha_1(v')+\alpha_2(w_1-w_2)+\cdot\cdot\cdot+\alpha_{n+1}(w_n-v_n)$ for some $\alpha_1,...,\alpha_{n+1}\in\Bbb R.$ This gives a path in $(V,W)$ that connects $v$ to $w$.

I think my proof for $\mathbf{(1)}\implies\mathbf{(2)}$ is mostly correct. $\mathbf{(2)}\implies\mathbf{(3)}$ kind of makes sense in my mind, but I don't really know how to put it all into words. Lastly, I really don't know how I should go about proving $\mathbf{(3)}\implies\mathbf{(1)}$.

Answer 1

One can be brief.

Introduce the map $\varepsilon:\mathbb R[V]\to \mathbb R$ sending every element to $1$. Let $\{v,v_1,\ldots,v_n\}$ list the elements of $V$. Observe that the image of your map $\mathbb R[E] \to \mathbb R[V]$ lands in the kernel of $\varepsilon$.

Now suppose that $(V,E)$ is connected. Then one can pick a vertex $v$ and for every other vertex $v_i$ a path $P_i: v\to v_i$. In this case $\{v,v_1-v,\ldots,v_n-v\}$ is a basis of $\mathbb R[V]$ and each $v_i-v$ is in the image of $\partial$, since we can consider sums $P_i = [v,w_1]+[w_1,w_2]+\cdots+ [w_t,v_i]$ representing the path $P_i$ above. Moreover, this trick allows you to show that $\dim\ker \varepsilon = \dim \mathrm{im}\, \partial$. It follows that $\dim V -1 = \dim \ker \varepsilon = \dim \mathrm{im}\,\partial$.

Assume now that $\dim V -1 = \dim \mathrm{im}\,\partial$. Since the kernel of $\varepsilon$ has this dimension, we must have $\dim \ker \varepsilon =\dim \mathrm{im}\,\partial$, and this means that we can choose a basis for $\ker \varepsilon$ made up of differences where the vertices are edges. Adding a vertex gives a basis of the desired form.

Finally, assume we have such a basis. The previous analysis shows that we must again have $\dim \ker \varepsilon =\dim \mathrm{im}\,\partial$, so pick two vertices $v$ and $w$. Since $v-w$ is in the kernel of $\varepsilon$, we can write it as the image of a sum $\sum_i \lambda_i\partial E_i$ where each $E_i$ is an edge. Since vertices form a basis of $\mathbb R[V]$, we conclude that the edges cancel out, meaning that they form in fact a path $v\to w$, which is what we wanted.

Answer 2

Here is my approach for $(2)\implies (3)$. I am assuming that (3) means the directed graph $D(V,E)$ is weakly connected (namely, the undirected graph underlying $(V,E)$ is a connected graph). Suppose that (2) is true.

For convenience let $G$ be the underlying undirected graph of $D(V,E)$ (that is, $G$ has the same vertex set $V$ but the edge set $F$ of $G$ consists of $\{a,b\}$ where $(a,b)\in E$). Let $X_1,X_2,\ldots,X_k$ be all connected components of $G$.

Define a linear functional $f_j:\Bbb{R}[V]\to\Bbb{R}$ for $j=1,2,\ldots,k$ by linearly extending the relation $$f_j(v)=\left\{\begin{array}{ll}1&\text{if }v\in X_j\\0&\text{if }v\in V\setminus X_j.\end{array}\right.$$ Clearly, $f_j\circ\partial$ is $0$ for all $j=1,2,\ldots,k$. Since $w_1-v_1,w_2-v_2,\ldots,w_n-v_n\in \operatorname{im}\partial$, $$f_j|_{\operatorname{span}\{w_1-v_1,w_2-v_2,\ldots,w_n-v_n\}}=0.$$ But $f_j$ is not a zero map, so $f_j(v)\ne 0$. This shows that $v\in X_j$ for every $j$. Since $v$ can be in at most one connected component, we conclude that $k=1$. That is, $G$ is a connected graph, so that $D$ is weakly connected.

To show $(3)\implies (1)$, we proceed as follows. Let (3) be true. Then, the underlying undirected graph $G(V,F)$ of $D(V,E)$ is connected. Thus it has a spanning tree $T$. Clearly, $T$ has exactly $|V|-1$ (undirected) edges. Suppose $\{w_1,v_1\},\{w_2,v_2\},\ldots,\{w_n,v_n\}\in F$ be the edges of $T$. We may assume that $(w_i,v_i)\in E$ for each $i$. We claim that $\{w_1-v_1,w_2-v_2,\ldots,w_n-v_n\}$ is a linearly independent subset of $\Bbb R[V]$. This shows that $\operatorname{im}\partial$ is at least $n$-dimensional.

The case $n=1$ is trivial. For $n>1$, we assume wlog that $\{w_n,v_n\}$ is a leaf of $T$. Let $T'$ be the tree obtained by removing $\{w_n,v_n\}$ from $T$. By induction, $\{w_1-v_1,w_2-v_2,\ldots,w_{n-1}-v_{n-1}\}$ is linearly independent. Because $\{w_n,v_n\}$ is a leaf of $T$, exactly one of $w_n$ or $v_n$, say $x$, does not show up among $w_1,v_1,w_2,v_2,\ldots,w_{n-1},v_{n-1}$. Define a linear functional $\phi:\Bbb R[V]\to \Bbb R$ by extending the relations $\phi(x)=0$ and $\phi(v)=0$ for every $v\in V\setminus\{x\}$. Suppose that $$\alpha_1(w_1-v_1)+\alpha_2(w_2-v_2)+\ldots+\alpha_n(w_n-v_n)=0.$$ Then, applying $\phi$ on the equation above we get $$\pm \alpha_n=0.$$ So $\alpha_n=0$. That is, $$\alpha_1(w_1-v_1)+\alpha_2(w_2-v_2)+\ldots+\alpha_{n-1}(w_{n-1}-v_{n-1})=0.$$ Since $\{w_1-v_1,w_2-v_2,\ldots,w_{n-1}-v_{n-1}\}$ is linearly independent, $\alpha_1=\alpha_2=\ldots=\alpha_{n-1}=0$. The induction is now complete.

Now define a linear functional $\psi:\Bbb{R}[V]\to\Bbb R$ as follows. For each $v\in V$, $\psi(v)=1$ and extend $\psi$ linearly. Because $\psi\ne 0$, the map $\psi$ is surjective and we conclude that $$\dim\ker\psi=\dim\Bbb{R}[V]-\dim\Bbb R=|V|-1=n.$$ Clearly, $\psi\circ\partial=0$. So $\operatorname{im}\partial\subseteq\ker\psi$. But we have proven that $\dim\operatorname{im}\partial\ge n$. Therefore $\operatorname{im}\partial=\ker\psi$. This proves (1).

For (2), we can replace the phrase "for some choice $v\in V$ and $(w_1,v_1),(w_2,v_2),\ldots,(w_n,v_n)\in E$" with "for some choice $(w_1,v_1),(w_2,v_2),\ldots,(w_n,v_n)\in E$ and for any $v\in V$". In your proof of $(2)\implies (3)$, it can be shown that $\alpha_1=0$. You also have a typo. You should have $\alpha_2(w_1-v_1)$ instead of $\alpha_2(w_1-w_2)$.

From this, we can show that the following conditions are equivalent for a finite directed graph $(V,E)$.

1. $\dim \Bbb R[V]-\dim\operatorname{im}\partial=|V|-\dim\operatorname{im}\partial=k$,
2. $V$ has at least $k$ vertices and for some choice $(w_1,v_1),(w_2,v_2),\ldots(w_n,v_n)\in V$ and for some choice $u_1,u_2,\ldots,u_k\in V$, the set $\{u_1,u_2,\ldots,u_k,w_1-v_1,w_2-v_2,\ldots,w_n-v_n\}$ is a basis for $\Bbb R[V]$,
3. $(V,E)$ has exactly $k$ weakly-connected components.

I would like to note that this construction has something to do with graph homology. Let $G(V,E)$ be a finite undirected graph on a totally ordered set $V\ne\emptyset$ with respect to some ordering $<$. Fix a ring $R$ with $1$. Define $C_p(G;R)$ to be the free left $R$-module with the generating set $\Gamma_p(G)$, the set of $(p+1)$-cliques in $G$. Therefore, $\Gamma_0(G)=V$ and $\Gamma_1(G)=E$. We also define $$C_{-1}(G;R),C_{-2}(G;R),\ldots=\{0\}.$$ There are $R$-module homomorphisms $\partial_p:C_p(G;R)\to C_{p-1}(G;R)$ for $p=1,2,\ldots$ defined by linearly extending the relation $$\partial_p[v_0,v_1,\ldots,v_{p}]=\sum_{i=0}^{p}(-1)^{i}[v_0,v_1,\ldots,\hat{v}_i,\ldots,v_p].$$ Here, $[v_0,v_1,\ldots,v_p]$ is a $(p+1)$-clique of $G$ such that $v_1<v_2<\ldots<v_p$.

We also define $$\partial_0=\partial_{-1}=\partial_{-2}=\ldots=0.$$ Then the pairs $\big(C_p(G;R),\partial_p\big)$ form a complex, and $H_p(G;R)=\frac{\ker\partial_p}{\operatorname{im}\partial_{p+1}}$ is the $p$-th homology of $G$ with coefficients in $R$. In particular, $H_0(G;R)=\frac{\ker\partial_0}{\operatorname{im}\partial_1}$ is the free left $R$-module generated by the connected components of $G$. In your case $R=\Bbb R$ so $\dim_{\Bbb R}H_0(G;\Bbb R)=|V|-\dim_{\Bbb R}\operatorname{im}\partial_1$ gives you the number of connected components of your graph.