231.9. Some linear algebra1.9 Some linear algebraLet G = (V,E) be a graph with n vertices and m edges, say VG =(V,E)[ ui,.., un ] and E - [ei,..,em ]. The verter space V(G) of G is thevector space over the 2-element field F2 = [0, 1 ] of all functions V- F2(space V(G)Every element of V(G) corresponds naturally to a subset of V, the set ofthose vertices to which it assigns a l, and every subset of V is uniquelyrepresented in v(G) by its indicator function. We may thus think ofV(G) as the power set of V made into a vector space: the sum U + U+of two vertex sets U,U' V is their symmetric difference (why?), andU = -U for all U C V. The zero in V(G), viewed in this way, is theempty (vertex) set 0. Since ((ui),..,( un)) is a basis of V(G), itsstandard basis, we have dim V(G) = nIn the same way as above, the functions E -→ F2 form the edgeedge spacspace E(G) of G: its elements are the subsets of E, vector additionE(G)amounts to sysymmetric difference, 0 C E is the zero, and F--F forstandardall FC E. As before, ((ei ).., em J) s the standard basis of e(G),basisand dimE(G) = m.Since the edges of a graph carry its essential structure, we shallmostly be concerned with the edge space. Given two edge sets F, F'e(G) and their coeficients Ai,.,Am and X'...,'m with respect to thestandard basis, we write(F, F") := AiAi+...+AmAm eF2.(F,F")Note that (F, F") = 0 may hold even when F = F' + 0::indeed,(F,F') = O if and only if F and F' have an even number of edgesin common. Given a subspace F of e(G), we writeFLF+ := [D e E(G) I (F, D) = 0 for all F e F) .This is again a subspace of (G) (the space of all vectors solving a certainset of linear equations-which?), and we have(t)dimF+dimF+=m.cycle spaceThe cycle space C = C(G) is the subspace of e(G) spanned by all"C(G)the cycles in G-more precisely, by their edge sets.10 The dimension ofC(G) is sometimes called the cyclomatic number of G.Proposition 1.9.1. The induced cycles in G generate its entire cycle[3.2.3]space.10Forsmplicity, weshalnotalwaysdistinguish betweentheedge sets Fe(G)and the subgraphs (V,F) they induce in G. When we wish to be more precise, suchas in Chapter 8.5, we shall use the word ‘circuit'for the edge set of a cycle1.9. Some linear algebra 23 1.9 Some linear algebra Let G = (V,E) be a graph with n vertices and m edges, say V = G = (V,E) { v1,...,vn } and E = { e1,...,em }. The vertex space V(G) of G is the vector space over the 2-element field F2 = { 0, 1 } of all functions V →F2. vertex space V(G) Every element of V(G) corresponds naturally to a subset of V , the set of those vertices to which it assigns a 1, and every subset of V is uniquely represented in V(G) by its indicator function. We may thus think of V(G) as the power set of V made into a vector space: the sum U + U + of two vertex sets U, U ⊆ V is their symmetric difference (why?), and U = −U for all U ⊆ V . The zero in V(G), viewed in this way, is the empty (vertex) set ∅. Since { { v1 },..., { vn } } is a basis of V(G), its standard basis, we have dim V(G) = n. In the same way as above, the functions E → F2 form the edge space E(G) of G: its elements are the subsets of E, vector addition edge space E(G) amounts to symmetric difference, ∅ ⊆ E is the zero, and F = −F for all F ⊆ E. As before, { { e1 },..., { em } } is the standard basis of E(G), standard basis and dim E(G) = m. Since the edges of a graph carry its essential structure, we shall mostly be concerned with the edge space. Given two edge sets F, F ∈ E(G) and their coefficients λ1,...,λm and λ 1,...,λ m with respect to the standard basis, we write F, F  := λ1λ 1 + ... + λmλ m ∈ F2 . F, F
 Note that F, F  = 0 may hold even when F = F = ∅: indeed, F, F  = 0 if and only if F and F have an even number of edges in common. Given a subspace F of E(G), we write F⊥ :=  D ∈ E(G) | F, D = 0 for all F ∈ F . F⊥ This is again a subspace of E(G) (the space of all vectors solving a certain set of linear equations—which?), and we have dim F + dim F⊥ = m . (†) The cycle space C = C(G) is the subspace of E(G) spanned by all cycle space C(G) the cycles in G—more precisely, by their edge sets.10 The dimension of C(G) is sometimes called the cyclomatic number of G. Proposition 1.9.1. The induced cycles in G generate its entire cycle [ 3.2.3 ] space. 10 For simplicity, we shall not always distinguish between the edge sets F ∈ E(G) and the subgraphs (V,F) they induce in G. When we wish to be more precise, such as in Chapter 8.5, we shall use the word ‘circuit’ for the edge set of a cycle.