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) εivi│ε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) εiei│ε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 ∂ : C1 → C0 defined by ∂(uv) = u + v and
coboundary δ: C0 → C1 defined by δ(u) = SUM ei, where ei is adjacent to v.

Let Z(G) = { x an element of C1│∂(x) = 0} be the cycle space of G
and
Let B(G) ={ x an element of C1│there exists y an element of C0, x = ∂(y)} be the coboundary space of G.

a. Find matrices representing the linear transformations ∂ and δ.
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)

Attachments

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