4.1-exam2-2012¶
Quiz 2, 2012 · Section 4.1: Orthogonality of Vectors and Subspaces Source: exam2_2.pdf, pp. 23-26
Problem¶
4 (29 pts.)
A graph with four nodes labeled 1, 2, 3, 4 and six directed edges labeled 1 through 6. (The figure is not in the corpus; the three independent small loops — the edge sets (1, 4, 5), (2, 4, 6), and (3, 5, 6) — are recoverable from the loop basis vectors in the solution.)
a) (15 pts.) Use loops or otherwise to find a basis for the left nullspace of the incidence matrix \(A\) for the graph above. We will start you off: one basis vector is \(\begin{bmatrix} 1 \\ 0 \\ 0 \\ -1 \\ 1 \\ 0 \end{bmatrix}\).
There are 24 ways to relabel the four nodes in the graph in part (a). Edge labels remain unchanged. This produces 24 incidence matrices \(A\).
b) (7 pts.) Is the row space of \(A\) independent of the labelling? Argue convincingly either way.
c) (7 pts.) Is the column space of \(A\) independent of the labelling? Argue convincingly either way.
Solution
a) The incidence matrix is 6 by 4. Since the graph is connected, the nullspace has dimension 1, and it is the line generated by \((1, 1, 1, 1)^T\); therefore, the matrix has rank 3. It follows that the left nullspace has dimension \(6 - 3 = 3\). We use the result of page 425 of the book: a basis of the left nullspace of the incidence matrix is given by a set of independent loops. In this case, we need to find 3 independent loops in the graph. It is easy to check that the 3 small loops are independent, so a basis of the left nullspace is \[ \begin{bmatrix} 1 \\ 0 \\ 0 \\ -1 \\ 1 \\ 0 \end{bmatrix}, \quad \begin{bmatrix} 0 \\ 1 \\ 0 \\ -1 \\ 0 \\ 1 \end{bmatrix}, \quad \begin{bmatrix} 0 \\ 0 \\ 1 \\ 0 \\ -1 \\ 1 \end{bmatrix}. \] b) Yes, it is independent. Indeed, the incidence matrix of a connected graph with 4 nodes has the line generated by \((1, 1, 1, 1)^T\) as its nullspace whatever the graph is. In particular, we see that the nullspace is independent of the labelling. Since the row space is the orthogonal complement of the nullspace, it is also independent of the labelling. c) Yes, it is independent. Relabelling the nodes has the effect of permuting the columns of the incidence matrix. The column space is the space of linear combinations of the columns of the matrix; therefore, it is independent of the way the columns are ordered in the matrix.Keywords: incidence matrix, left nullspace, graph, loops, column space