Principles of Mathematics in Operations Research

28 2 Preliminary Linear Algebra

Problems

2.1. Graph spaces

Definition 2.4.13 Let GF(2) be the field with + and x (addition and multi-

plication modulo 2 on I?)

01

01

10

and

01

00

01

Fig. 2.3. The graph in Problem 2.1

Consider the node-edge incident matrix of the given graph G = (V, E)

over G,F(2), A G RII^HXIISH:

a

b

c

A= d

e

f

9

h

12 3456 789 10 11 12 13

1 10000000 0 0 0 0

100000001 0 0 0 0

01 1000000 0 0 0 0

0011000010 0 0 0

0001 10000 10 0 0

00001 1000 0 0 11

000001 1000100

000000010 110 1

0000001100 0 1 0

The addition + operator helps to point out the end points of the path
formed by the added edges. For instance, if we add the first and ninth columns
of A, we will have [1,0,0,1,0,0,0,0,0]T, which indicates the end points (nodes
a and d) of the path formed by edges one and nine.

(a) Find the reduced row echelon form of A working over GF(2). Interpret