Share
Explore BrainMass

# Graph theory: Find matrices representing the linear transformations ∂ and δ.

Please see attached file for full problem description.

Let C0 ={SUM (i = 1 to p) &#949;ivi&#9474;&#949;i is an element of F2, vi is an element of V(G)}
be the vector space of 0-chains
and
Let C1 ={SUM (i = 1 to q) &#949;iei&#9474;&#949;i is an element of F2, ei is an element of E(G)}
be the vector space of 1-chains

Recall the linear transformations
boundry &#8706; : C1 &#8594; C0 defined by &#8706;(uv) = u + v and
coboundary &#948;: C0 &#8594; C1 defined by &#948;(u) = SUM ei, where ei is adjacent to v.

Let Z(G) = { x an element of C1&#9474;&#8706;(x) = 0} be the cycle space of G
and
Let B(G) ={ x an element of C1&#9474;there exists y an element of C0, x = &#8706;(y)} be the coboundary space of G.

a. Find matrices representing the linear transformations &#8706; and &#948;.
b. Define an inner product on C1 by < x,y > = SUM &#949;i&#951;i, where x = SUM &#949;iei and y = SUM &#951;iei.
Prove that x is an element of Z(G) iff < x,y > = 0 for all y element of B(G)
c. Show that the dimensions of B(G) is p - k(G).
d. Characterize the class of graphs for which B(G) = C1(G)

#### Solution Preview

The explanations are in the attached pdf file.

As required by Brainmass, I past the original text in plain TEXT below.
You do not have to read it since all you need is in the pdf file.

=======
Here is the plain TEXT source

magnification=magstep1
baselineskip=12pt
parindent = 0pt
parskip = 12pt

defl{left}
defr{right}
defla{langle}
defra{rangle}
defp{partial}
defu{uparrow}
defd{downarrow}

centerline{bf Boundary and Coboundary}

bf (a) rm

A matrix representing the boundary operator \$p\$ for a gragh with \$p\$ vertices and \$q\$ edges, for \$C_0\$ and \$C_1\$ defined on field \$F_2={ 0 ~ 1}\$, is a \$ptimes q\$ matrix \$M_p\$ of \$p\$ rows and \$q\$ columns contaning 0s or 1s.
Each column represents an edge. If this edge connects vertices \$i\$ and \$j\$, ...

#### Solution Summary

Matrices and linear transformations are investigated.The solution is detailed and well presented. The response received a rating of "5/5" from the student who originally posted the question.

\$2.19