Linear algebra over GF(2) for some reason

NOTE: I was going to post this on my other blog, since as a quick jerk of your scrollbar will tell you, it is quite rambling. However it is not completely incoherent, hence I decided to post it here.

So, today, on Canada’s birthday, while everyone is out partying and getting drunk, us *ahem* more refined and sophisticated individuals will be doing some linear-algebraic graph theory. OK, I’m kidding, there is no lucrative innovative intellectual socially-dynamic group-synergy occurring, it’s just me sitting on a couch bashing out my thoughts. I am starting to realize that (with respect to time) this is asymptotic to a metaphor for my life.

You know, I can’t even count the number of abstract algebra/group theory books I’ve read that mentioned the fact that for any set S, the power set 2^S = \{ T : T \subseteq S \} forms a group under the symmetric difference operation \oplus, which is the set-theoretic manifestation of logical XOR (this really reminds me of an embarrassing truth-table proof I did for a quantum information assignment), just like the union corresponds to logical OR. To wit, for two subsets A, B \in 2^S we define

\displaystyle A \oplus B := (A \cup B) \setminus (A \cap B) = \{ x \in S : x \text{ is in } A \text{ or } B \text{ but not both} \}.

The identity is obviously the empty set \varnothing, it is associative and commutative, and every element has an inverse, namely itself. So it’s an abelian group, in fact we might term it a Boolean group, or something. After reading such examples, I always thought to myself, “Man, symmetric difference? What a lame and contrived example. I bet that would never be useful.” Well, it turns out that (as is almost always the case) I was wrong. This term, I am taking an introductory course in graph theory, and this very example has been the foundation for the past 2 or 3 weeks worth of lecture material… which brings me to the point of this post.

Why would this seemingly trivial textbook example of a group find any use in a graph-theoretic context? To be honest, I have no idea, but intuitively it seems like we want a way of decomposing edge sets in graphs, in particular, we want to investigate cycles. One thing we note is that in the complete graph K_4, if we choose a 4-cycle, it can be obtained by taking the symmetric difference of two 3-cycles which share an edge. Any abelian group (the likes of which we usually write additively) automatically carries the structure of a \mathbb{Z}module (view the scalar multiplication as iterated addition), so that’s nice, however it’s not really what we want here. Taking our scalars from \mathbb{Z} is overkill, because the entire ideal \langle 2 \rangle of the ring \mathbb{Z} annihilates everything. That is, \lambda v = 0 whenever \lambda \in \langle 2 \rangle. So, with the minimalist laziness so characteristic of mathematicians, we quotient out this inconvenient ideal, therefore working instead over \mathbf{GF}(2), the field with 2 elements (otherwise known as \mathbb{Z}_2). We now have a module over a field, otherwise known as (surprise, surprise) a vector space.

Let’s see what kind of sinister avatars the above generalities can animate in the graph-theoretic realm. I won’t waste my breath developing the trivialities of basic linear algebra over \mathbf{GF}(2); we’ll proceed instead to discussing the so-called cycle space. Let G be a graph (finite, undirected, lacking parallel edges, loops, and other analogous hodgepodge). We denote the vertex and edge sets of G by V(G) and E(G), respectively. We’ll be toiling away in the space 2^{E(G)}, since we care about cycles. One property we note about edge sets of cycles is as follows: if C is a cycle in G, then every vertex v \in G is incident to an even number of edges in E(C) \subseteq E(G). So we are lead to believe that we should care about subsets S \subseteq E(G) satisfying this property. This motivates the following.

Definition. The cycle space of G, written \mathcal{Z}(G) because Zyklus is German for cycle, is the set of all subsets S \subseteq E(G) such that for all v \in V(G), the vertex v is incident to an even number of edges within the set S. Equivalently, it consists of all subsets S which induce so-called Eulerian subgraphs.

This is naturally (as can be seen by definition) a subset of 2^{E(G)}; it is also (by a small argument) a subspace of 2^{E(G)}. The elements in the cycle space can, in a sense, be thought of as formal combinations of cycles in G.

Recently, on an assignment, we were asked to describe the structure of \mathcal{Z}(G) for a few typical choices of G, namely, the complete graph K_5, the complete bipartite graph K_{3,4} and the 3-dimensional cube Q_3. You may have seen that I posted an awfully-written Python script to compute the size of these cycle spaces. Given the above definition, it is not so clear what the most efficient way to carry out this task is. Since it is germane to this discussion, we will now examine a different way of defining the cycle space — one which clearly suggests an efficient way to compute its size (and even find a basis for it).

Given an (undirected) graph, we can form a matrix known as its incidence matrix, as follows. If we have \nu vertices and \varepsilon edges, the incidence matrix will have size \nu \times \varepsilon. In the (i,j) entry of the matrix, we place a 1 if vertex i is incident to edge j and a 0 otherwise. Of course, the same graph can have many different incidence matrices (simply choose a different ordering on the vertex and/or edge sets), but the incidence matrix uniquely determines the graph up to isomorphism. Let us now think about an incidence matrix, say A, as a transformation from some \varepsilon-dimensional space to some \nu-dimensional space. If we suppose the spaces are over the real numbers, then what exactly is the interpretation of, say, Ax, where x is a 01-column vector? Recall that given any subset S of a finite set X = \{ x_1, \ldots, x_k \}, we can form a binary k-tuple, denoted \chi_S (actually it’s a function, but functions with finite domains are conveniently written as tuples after we agree on an ordering), the ith coordinate of which is 1 if x_i \in S and 0 otherwise. I have seen this termed the characteristic vector of S, although apparently this term is also used for eigenvectors.

So, in keeping with the above, we view the 01-column vector x as not a vector, but a subset, denoted S(x), of the edge set of G, in agreement with the way we ordered E(G) to form the incidence matrix. The image vector Ax is then a \nu-tuple, the ith element of which is the usual dot product between the ith row of A and x. In other words, the ith coordinate of Ax tells us how many edges in S(x) \subseteq E(G) are incident to the ith vertex of G. Modulo 2, this will be either 0 or 1 depending on whether the ith vertex is incident to an even, or odd number of the edges in S(x), respectively.

So now let us view the domain and codomain of an incidence matrix as \mathbf{GF}(2)-vector spaces. Then once we pick an ordering for V(G) and E(G), we can form an incidence matrix A of G. At this point, due to my above remarks, it is easily seen that the cycle space as we have defined it is precisely the nullspace (kernel) of the matrix A (the previous definition reads “the set of all subsets x \subseteq E(G) so that for all vertices v, the corresponding coordinate of the image vector Ax is 0 mod 2″). However, Gaussian elimination makes quick work of any matrix over a field. Therefore, this equivalent definition of the cycle space gives us a simple way to compute a basis for it, and hence understand it completely.

I’ve been thinking lately about how (well, if would be more suitable a word) we can relate the cycle space of G to the cycle space of the complement graph \overline{G} (i.e., the graph where two vertices are adjacent if and only if they are not adjacent in G) and also the edge-dual of G. Of further curiosity is how the cycle space behaves with respect to the graph tensor product (speaking of tensor products, Hedetniemi’s conjecture is something I was really surprised to learn is an unsolved problem). Also, when we look at the sequence of numbers d(n) = \dim\Big(\mathcal{Z}(K_n)\Big) for n \geq 1, we obtain (as far as I can tell) the sequence of triangular numbers (1, 1+2, 1+2+3, 1+2+3+4, \ldots), which is interesting, although I have not yet found the time to come up with a simple explanation for this.


About mlbaker

just another guy trying to make the diagrams commute.
This entry was posted in combinatorics and tagged , , , , , , . Bookmark the permalink.

14 Responses to Linear algebra over GF(2) for some reason

  1. Victor says:

    \oplus is not idempotent, since x \oplus x = \varnothing.

  2. Victor says:

    \mathbb{Z}_2 is the 2-adic integers.

  3. Victor says:

    Or, the graph determines its incidence matrix up to similarity by permutation matrices.

    • Victor says:

      I see that your definition of an incidence matrix is nonstandard. Oops, this claim is no longer true.

    • mlbaker says:

      It is the “unoriented incidence matrix”. I think, at least, that my definition is standard. Maybe you are thinking of an adjacency matrix.

  4. Victor says:

    I fail to see how the cycle space of the triangle (which consists of two elements) can have dimension 6.

    • mlbaker says:

      It doesn’t. It has dimension 1, of course. Hm, maybe I should have been more precise about where I started indexing the sequence.

  5. Victor says:

    How do I reply to your reply? This is so lame. Yes, I’m thinking of the adjacency matrix.

    • mlbaker says:

      As a habit, I usually reply to the topmost post in the relevant thread. Replying to a reply to a reply to a [… \varinjlim] leads to headaches.

  6. Victor says:

    Indeed, the triangular numbers result from the following observation: \mathrm{nullity}(A) + \mathrm{rank}(A) = n(n-1)/2. To show that \mathrm{nullity}(A) = \dim(\ker(A)) = \dim(\mathcal{Z}(K_n)) = (n-1)(n-2)/2, it suffices to show that
    \mathrm{rank}(A) = n-1 (check this algebra!).

    I will label the columns by the edge labels, so I have n(n-1)/2 columns while having n rows. (From this we immediately gather \mathrm{rank}(A) \leq n, but we need to be more precise.) Well, with the regular n-gon in mind as our picture for K_n, we traverse the “outer n-cycle” first, and we will put those edges (columns) first in our matrix. As an example with n = 5, an excerpt of the incidence matrix A ordered this way reads

    \displaystyle \begin{pmatrix} 1 & 1 & 0 & 0 & 0 \\ 0 & 1 & 1 & 0 & 0 \\ 0 & 0 & 1 & 1 & 0 \\ 0 & 0 & 0 & 1 & 1 \\ 1 & 0 & 0 & 0 & 1 \end{pmatrix}

    were our n = 5, as an example. This segment demonstrates why the rank is at least n - 1, since Gaussian elimination to row-reduced echelon form with that many leading 1’s guarantee it. On the other hand, I can column-sum a pair of these columns to get any other column in the matrix, since any column only has exactly two 1’s (recall that an edge is adjacent to exactly two vertices) and we are working over \mathbf{GF}(2). Hence the \mathrm{rank}(A) = \mathrm{rank}(A'), where A' is this initial excerpt of the matrix A shown in the above example. Of course, basic linear algebra gives the column rank of this matrix to be n - 1, and we are done.

  7. Jimmy says:

    Another way to prove this is to refer to assignment 7, last question, last part. In particular, we know that if 1) H is a connected subgraph of a graph G, 2) P is a path in G, and 3) P is intersects H only at its endpoints, then \dim(\mathcal{Z}(H \cup P)) = \dim(\mathcal{Z}(H)) + 1. Thus, we need simply consider how we may add paths to K_n as it is embedded in K_{n+1} to make it K_{n+1}. To do so, label the vertices of K_{n+1} by 1, 2, ..., n+1. Look at the copy of K_n embedded in K_{n+1}. We can get K_{n+1} by: 1) adding a path (1,n+1,2) to K_n, and then 2) adding edges \{n+1,i\} to resulting graph, for all 3 \leq i \leq n. This amounts to augmenting \mathcal{Z}(K_n)‘s dimension by n-1, and thus \dim(\mathcal{Z}(K_{n+1})) = \dim(\mathcal{Z}(K_n)) + n - 1. (Of-course, this only works if n \geq 2.) Hence, when we apply this to K_2 in K_3, we get \dim(\mathcal{Z}(K_3)) = 1, K_3 in K_4 we get \dim(\mathcal{Z}(K_4)) = 1 + 2, K_4 in K_5 we get \dim(\mathcal{Z}(K_5)) = 1 + 2 + 3 and so forth.

    Indeed, we see something nice about this approach of adding paths to build up a graph; we can easily apply it to figure out the dimension of any family of graphs which have the above property than you can build up the larger graphs from the smaller graphs (for example, complete bipartite graphs and n-dimensional cubes).

  8. d(n) = E(K_n) - V(K_n) +1 = n(n-1)/2 - n + 1 = (n^2-3n+2)/2 = (n-1)(n-2)/2
    We prove this on Assignment 8 : D

    • mlbaker says:

      You are right. We prove a result that relates the cycle space dimension of a connected graph to the difference of the size of its edge set, and the size of the edge set of a spanning tree — but a tree on n vertices always has n-1 edges 🙂

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s