This site is being phased out.

Cochains on graphs

From Mathematics Is A Science
(Redirected from Cochains)
Jump to navigationJump to search

The algebra of plumbing, continued

We introduce more algebra with the familiar metaphor:

We think of a graph as a plumbing system that consists of a network of pipes and joints, and each joint and each pipe is equipped with an on-off switch.

Pipes and joints switches.png

The two plumbers “flip the switch” on a joint or a pipe which is recorded with binary numbers and the repeated flips are cancelled via binary addition. Since this activity is happening at every joint and every pipe, we have the two groups: the chains of nodes and the chains of edges: $$C_0\cong ({\bf Z}_2)^n,\ C_1\cong ({\bf Z}_2)^m.$$

Now, we need to be careful with the illustrations above as they don't depict the outcomes of the requests but only how the state of the given switch is to change. We can assume that all switches are closed in the beginning of the day, then the requests will tell us the state of each switch in the end of the day. We use $0$ for closed and $1$ for open.

We add water now.

Pipes, joints, switches, and pumps.png

Each switch has a water pump (or a water reservoir). We will, for each joint and each pipe, look at:

  • the state of the pump;
  • the flip request;
  • the resulting flow of water.

All of these are binary numbers, $0$ or $1$. How this works is obvious:

  • pump on ($1$) and switch flipped ($1$), then water flows ($1$);
  • pump off ($0$) and switch flipped ($1$), then water doesn't flow ($0$); etc.

We discover that this isn't binary addition but binary multiplication: $$1\times 1=1,\ 0\times 1=0,\ 1\times 0 =0,\ 0\times 0=0.$$

However, the two numbers in the left-hand side refer to two very different entities and it would be misleading to suggest that these are group operations. Instead, we rename the states of the pump as $0^*$ and $1^*$. Then that we have: $$1^*\times 1=1,\ 0^*\times 1=0,\ 1^*\times 0 =0,\ 0^*\times 0=0.$$ In fact, the best way to think of these numbers is as functions: $$1^*(1)=1,\ 0^*(1)=0,\ 1^*(0) =0,\ 0^*(0)=0.$$ Furthermore, the distributive property proves that these are homomorphisms $$x^*:{\bf Z}_2 \to {\bf Z}_2.$$ They can be defined on all switches and, therefore, on all chains; that's why these functions are called cochains.

Recall also how we interpret the boundary operator: $\partial (AB)=A+B$ means replacing the request “flip the switch of pipe $a=AB$” with “flip the switches at joints $A$ and $B$”.

Pipes and joints switches related.png

A related situation occurs when the pump at joint $A$ malfunctions (or the reservoir is empty). An obvious if imperfect substitution for having it on is to have water flow to all pipes adjacent to $A$: $AB,AC,...$.

Pipes and joints and pumps related.png

As we shall see, this substitution defines a function from cochains of pipes to cochains of joints.

The dual of a group

What follows is the algebra we need in order to understand cochains.

Suppose $G$ is isomorphic to ${\bf Z}_2$. Then it is very simple: $$H=\{0,A\},$$ with $A+A=0$, etc. Let $H^*$ be the set of all homomorphisms $$s:H \to G={\bf Z}_2.$$ It is called the dual group of $H$.

There are only two such homomorphisms: the zero and the identity. The former may be thought of as the multiplication by $0$ and the latter by $1$. We can denote them by $0^*$ and $1^*$, just as in the last subsection. Then, $$H^*:=\{0^*,1^*\}.$$ In other words, we see the following again: $$0^*(0)=0,\ 0^*(1)=0,\ 1^*(0)=0,\ 1^*(0)=1.$$

Since the sum of two homomorphisms is a homomorphism, we make the following conclusion.

Proposition. The dual of ${\bf Z}_2$ is a group isomorphic to ${\bf Z}_2$.

So, $H\cong H^*$! However, this doesn't mean that this is the same thing.

The first crucial difference is that we can multiply the elements of the latter since the product of two homomorphisms is also a homomorphism. We make the following conclusion.

Proposition. The dual $H^*$ is a ring.

Exercise. Prove the proposition.

Exercise. Find the duals (over $G={\bf Z}_2$) of the following groups: (a) ${\bf Z}_3$, (b) ${\bf Z}_2\times {\bf Z}_2$, (c) $({\bf Z}_2)^n$.

Further, what happens to the dual $H^*$ under homomorphisms of $H$?

As it turns out, this is a wrong question to ask. Suppose there is another group $K$ also isomorphic to ${\bf Z}_2$ and suppose $h:H\to K$ is a homomorphism. Then for any $s\in H^*$, what happens is seen in the following diagrams: $$\newcommand{\ra}[1]{\!\!\!\!\!\xrightarrow{\quad#1\quad}\!\!\!\!\!} \newcommand{\da}[1]{\left\downarrow{\scriptstyle#1}\vphantom{\displaystyle\int_0^1}\right.} \begin{array}{ccccccccc} H &\ra{s} & {\bf Z}_2 &\quad & A & \mapsto & 0\text { or } 1\\ \da{h} & & || &\quad & \da{h} & & ||\ ? \\ K &\ra{t} & {\bf Z}_2 &\quad & h(A) & \mapsto & 0\text { or } 1. \end{array}$$ It would be natural to try to express $t$ in terms of $s$, but it's impossible to combine $s$ with $h$. In fact, the opposite is what we need to consider as $th$ makes sense. Then we simply require the first diagram to be commutative or, which is the same thing, that the outputs of the two homomorphisms coincide on the right in the second diagram. As a result, $s$ is defined in terms of $t$: $$s(A):=th(A).$$ Then $t\in K^*$ is the input and $s\in H^*$ is the output of the new homomorphism.

To summarize, the dual homomorphism of a homomorphism $$h:H\to K$$ is the homomorphism (note the direction of the arrow) $$h^*:K^*\to H^*,$$ defined by: $$h(y^*)(x):=y^*h(x),$$ for any $x\in H$ and any $y\in K$.

Exercise. Provide a formula for $h^*$ for every possible $h$.

Exercise. (a) How many homomorphisms ${\bf Z}_3\to {\bf Z}_3$ are there? (b) How many homomorphisms $({\bf Z}_2)^n\to {\bf Z}_2$ are there?

Cochains of nodes and cochains of edges

We apply the algebra developed in the last subsection to cochains.

Suppose we are given a graph $G$ with the set of nodes $N$ and the set of edges $E $. Then, the group of chains of nodes, or $0$-chains, and the group of chains of edges, or $1$-chains, are respectively: $$C_0=C_0(G):=\{ \Sigma_i A_i: A_i \in N\}=< N >,$$ $$C_1=C_1(G):=\{ \Sigma_i a_i: a_i \in E\}=< E >.$$

Definition. A $k$-cochain on graph $G$ is a homomorphism $s:C_k(G) \to {\bf Z}_2$.

Since the sum of two homomorphisms is a homomorphism, we make the following conclusion.

Proposition. The $0$- and $1$-cochains on graph $G$ form groups, denoted by $C^0(G)$ and $C^1(G)$ respectively.

If we consider one node (or edge) at a time, we are in the setting of the last subsection. As we know, there are only two such homomorphisms: the zero $0^*$ and the identity $1^*$. Therefore,

  • a $0$-cochain assigns a number, $0$ or $1$, to each node, and
  • a $1$-cochain assigns a number, $0$ or $1$, to each edge.

Just like chains!

Cochains on graphs.png

There is a special way to present the cochains in terms of the “basic chains”, i.e., the nodes and the edges. For every such chain $x\in C_k,k=0,1$, define a “basic cochain” $x^*:C_k\to {\bf Z}_2$, by $$x^*(t)=\begin{cases} 1 & \text{ if } t=x,\\ 0 & \text{ if } t\ne x. \end{cases}$$ Then every cochain is simply the sum of a set of the basic cochains.

Proposition. $$C^0=\{ \Sigma_i A_i^*: A_i \in N\},$$ $$C^1=\{ \Sigma_i a_i^*: a_i \in E\}.$$

Proposition. The function $x\mapsto x^*$ generates an isomorphism between the groups of chains and cochains: $$C_k\cong C^k.$$

Since everything is expressed in terms of these generators, this isomorphism is given explicitly by: $$(\Sigma_i A_i)^*:=\Sigma_i A_i^*.$$

Exercise. Prove the propositions.

Next, with ordered sets of nodes $N$ and edges $E$ fixed as bases of the groups of chains, both chains and cochains can be written coordinate-wise, as column-vectors and row-vectors.

Example. Let's again consider this graph $G$:

  • $N=\{A,B,C,D\}$,
  • $E=\{AB,BC,CA,CD\}$.
Graph example 2.png

Then its chains of nodes are $$A=\left[ \begin{array}{llllll} 1 \\ 0 \\ 0\\ 0 \end{array} \right],\ B=\left[ \begin{array}{lllll} 0 \\ 1 \\ 0\\ 0 \end{array} \right],\ ...,\ A+B=\left[ \begin{array}{lllll} 1 \\ 1 \\ 0\\ 0 \end{array} \right],\ ... $$ Then the cochains of nodes are: $$A^*=[1,0,0,0],\ B^*=[0,1,0,0],\ ...,\ (A+B)^*=[1,1,0,0],\ ...$$ Similarly, the cochains of edges are: $$AB^*=[1,0,0,0],\ BC^*=[0,1,0,0],\ ...,\ (AB+BC)^*=[1,1,0,0],\ ...$$

$\square$

Proposition. The value of a cochain $s$ at a given chain $a$ is the dot-product of the two: $$s(a)=\langle s,a \rangle.$$

We always put the cochain first in this dot product. This way, the output is simply the matrix product $sa$ of a $1\times n$ matrix $s$ and an $n\times 1$ matrix $a$.

Example. To illustrate this formula, let's consider a very simple example:

  • $G$, a graph with $8$ edges numbered from $0$ to $8$,
  • $a$, a chain equal to the sum of the edges from $1$ to $5$, and
  • $s$, a cochain with $1$s and $0$'s shown.
Binary 1-cochain.png

Then $$a=[0,1,1,1,1,1,0,0,0]^T,\ s=[1,1,0,1,1,0,1,1].$$ We compute: $$\begin{array}{lllll} s(a)&=\langle s,a \rangle =\Sigma_i s_ia_i\\ &=1\cdot 0+1\cdot 1+0\cdot 1+1\cdot 1+1\cdot 1+0\cdot 0+1\cdot 0 +1\cdot 0\\ &=1\cdot 1+0\cdot 1+1\cdot 1+1\cdot 1 =1. \end{array}$$ This is (computed with binary arithmetic) the area under the graph of $s$!

$\square$

The notation so justified is $$s(a)=\int_a s, \quad \text{ or } s(AB)=\int_A^B s.$$ Meanwhile, in this context, cochains are called discrete differential forms, to be discussed later.

Exercise. Verify the counterparts of the Linearity, Additivity, and other properties of the Riemann integral.

Exercise. Provide a similar, integral interpretation of $0$-cochains.

Maps of cochains

Now, what happens to chains under graph maps is very simple. If $f:G\to J$ is such a map, its chain maps $$f_k:C_k(G)\to C_k(J)$$ are defined as follows. If $A$ is a node in $G$, then we have the following: $$f_0(A)=f(A).$$

What about the cochains? We already know that the arrows will be reversed, in a “dual” way.

Suppose $s$ is a $k$-cochain in $G$ and $t$ in $J$. Then the relation between them is seen in the following commutative diagram: $$\newcommand{\ra}[1]{\!\!\!\!\!\xrightarrow{\quad#1\quad}\!\!\!\!\!} \newcommand{\da}[1]{\left\downarrow{\scriptstyle#1}\vphantom{\displaystyle\int_0^1}\right.} \begin{array}{ccccccccc} C_k(G)&\ra{s}& {\bf Z}_2 \\ \da{f_k}& & || \\ C_k(J)&\ra{t}& {\bf Z}_2 . \end{array}$$

Definition. The cochain maps of a graph map $f:G\to J$ are the homomorphisms (note the direction of the arrow): $$f^k:C^k(J)\to C^k(G),$$ defined by: $$f^k(t)(a):=tf_k(a),$$ for any $k$-chain $a$ in $G$ and any $k$-cochain $t$ in $J$.

Example. Let's consider the formula for a specific $f:G\to G$, the shift (with one collapse) of the three-edge graph $G$:

  • $G:=\{0,1,2,3;01,12,23\}$,
  • $f(0)=1,\ f(1)=2,\ f(2)=3,\ f(3)=3.$
Shift of graph.png

First, the nodes. We have

  • $f_0(0)=1,\ f_0(1)=2,\ f_0(2)=3,\ f_0(3)=3.$

It suffices to compute the cochain map $f^0$ for

  • all basic $0$-chains of $G$, $a=p$, and
  • all basic $0$-cochains of $G$, $t=q^*$;

where $p,q=0,...,3$. We use the formula: $$f^0(q^*)(p):=q^*f_0(p),$$ with the latter equal to $0$ (the number, not the node) unless $q=f_0(p)$. Then, $f^0(q^*)(p)=0$ unless $q=p+1$ or $q=p=3$. The answer is:

  • $f^0(0^*)=0$ (i.e., it's trivial);
  • $f^0(q^*)=(q-1)^*,\ q=1,2$;
  • $f^0(3^*)=3^*$.

We next compare the matrices: $$f_0=\left[ \begin{array}{ccccc} 0&0&0&0\\ 1&0&0&0\\ 0&1&0&0\\ 0&0&1&1 \end{array}\right], \quad f^0=\left[ \begin{array}{ccccc} 0&1&0&0\\ 0&0&1&0\\ 0&0&0&1\\ 0&0&0&1 \end{array}\right] $$ The second matrix is the transposes of the first!

Second, the edges. We have

  • $f_1(01)=12,\ f_1(12)=23,\ f_1(23)=0.$

It suffices to compute the cochain map $f^1$ for

  • all basic $1$-chains of $G$, $a=p$, and
  • all basic $1$-cochains of $G$, $t=q^*$;

where $p,q=01,12,23$. We use the above formula: $$f^1(q^*)(p):=q^*f_1(p),$$ which is equal to $0$ unless $q=f_1(p)\ne 0$. The answer is:

  • $f^1(01^*)=0$;
  • $f^1([m,m+1]^*)=[m-1,m]^*,\ m=2,3$.

Compare the matrices: $$f_1=\left[ \begin{array}{cccc} 0&0&0\\ 1&0&0\\ 0&1&0 \end{array}\right], \quad f^1=\left[ \begin{array}{cccc} 0&1&0\\ 0&0&1\\ 0&0&0 \end{array}\right] $$ Again, they are the transposes of each other.

$\square$

Exercise. Compute the cochain maps of other specific $f$s -- shift, flip, fold -- for the graph in the example above.

To make sense of this formula, let's use the integral notation above ($k=1$): $$\int_a f^1(t)=\int_{f_1(a)}t.$$ Then, if we set $a=AB$, we have $$\int_A^B f^1(t)=\int_{f(A)}^{f(B)}t.$$ But this is just the formula of integration by substitution!

The coboundary operator

Recall that the boundary operator $$\partial: C_1(G) \to C_0(G) $$ is set by its value for each edge: $$\partial (AB) = A+B.$$

What happens to the cochains? Just as in the last subsection, we expect that the arrows will be reversed, in a “dual” way.

Suppose $s$ is a $1$-cochain in $G$ and $Q$ a $0$-cochain. Then the relation between them is seen in the following commutative diagram, similar to the one in the last subsection: $$\newcommand{\ra}[1]{\!\!\!\!\!\xrightarrow{\quad#1\quad}\!\!\!\!\!} \newcommand{\da}[1]{\left\downarrow{\scriptstyle#1}\vphantom{\displaystyle\int_0^1}\right.} \begin{array}{ccccccccc} C_1(G)&\ra{s}& {\bf Z}_2 \\ \da{\partial}& & || \\ C_0(G)&\ra{Q}& {\bf Z}_2 . \end{array}$$

Definition. The coboundary operator of a graph $G$ is the homomorphism: $$d=\partial ^*:C^0(G)\to C^1(G),$$ defined by: $$d(Q)(a):=Q\partial (a),$$ for any $1$-chain $a$ and any $0$-cochain $Q$ in $G$.

Example. Here is an example:

Boundary and coboundary operators on graph.png

Our claim is that $$dA^*=AB^*+AC^*+AD^*+AE^*.$$ We prove it by evaluating $dA^*$ for each of the four basic $1$-chains: $$dA^*(AB)=(AB^*+AC^*+AD^*+AE^*)(AB)=1+0+0+0=1,$$ and similarly: $$dA^*(AC)=1,\ dA^*(AD)=1,\ dA^*(AE)=1.$$ We can also use the definition with $Q=A^*$: $$dA^*(AB):=A^*\partial AB=A^*(A+B)=A^*A+A^*B=1+0=1, \text{ etc. }$$

$\square$

Exercise. Generalize this example.

Example. Consider the boundary operator for this graph again:

Graph example 2.png

Then:

  • 1. $\partial ([1,0,0,0]^T)=[1,1,0,0]^T,\ d ([1,0,0,0])=[1,0,1,0]$;
  • 2. $\partial ([0,1,0,0]^T)=[0,1,1,0]^T,\ d ([0,1,0,0])=[1,1,0,0]$;
  • 3. $\partial ([0,0,1,0]^T)=[1,0,1,0]^T,\ d ([0,0,1,0])=[0,1,1,1]$;
  • 4. $\partial ([0,0,0,1]^T)=[0,0,1,1]^T,\ d ([0,0,0,1])=[0,0,0,1]$;

Therefore, the matrices are $$\partial = \left[ \begin{array}{llllll} 1 & 0 & 1 & 0 \\ 1 & 1 & 0 & 0 \\ 0 & 1 & 1 & 1 \\ 0 & 0 & 0 & 1 \end{array} \right], \quad d = \left[ \begin{array}{llllll} 1 & 1 & 0 & 0 \\ 0 & 1 & 1 & 0 \\ 1 & 0 & 1 & 0 \\ 0 & 0 & 1 & 1 \end{array} \right].$$ They are the transposes of each other.

$\square$

Exercise. Provide the details of the computations above.

To make sense of the formula in the definition we use the integral interpretation again, with $a=AB$: $$\int_{AB} dQ=\int_{\partial (AB)}Q=\int_{A+B}Q=Q(A)+Q(B).$$ But that's the (binary) Fundamental Theorem of Calculus! That's why, when we think of cochains as differential forms, $d$ is called the exterior derivative (or the differential). In this sense, $Q$ is an antiderivative of $dQ$.

We are in a position to conjecture that this isn't a coincidence...