Skip to content

3.5-final-2013-strang-b

Final Exam, 2013 (strang) · Section 3.5: Dimensions of the Four Subspaces Source: finalexam_2.pdf, p. 118

Problem

6 (4+3+3 pts.) This graph has \(m = 12\) edges and \(n = 9\) nodes. Its 12 by 9 incidence matrix \(A\) has a single -1 and +1 in every row, to show the start and end nodes of the corresponding edge in the graph.

(a) Write down the 4 by 4 submatrix \(S\) of \(A\) that comes from the 4-node graph (a loop) in the corner. Find a vector \(x\) in the nullspace \(N(S)\) and a vector \(y\) in \(N(S^T)\).

(b) For the whole matrix \(A\), find a vector \(Y\) in \(N(A^T)\). You won't need to write \(A\) or to know more edge numbers.

(c) The all-ones vector \((1, 1, \dots, 1)\) spans \(N(A)\). Find the dimension of the left nullspace \(N(A^T)\) (give a number).

Solution (a) The 4-node loop in the corner has 4 edges, so \(S\) is the \(4 \times 4\) submatrix \[ S = \begin{bmatrix} -1 & 1 & 0 & 0 \\ -1 & 0 & 1 & 0 \\ 0 & -1 & 0 & 1 \\ 0 & 0 & -1 & 1 \end{bmatrix}, \] where the rows are the edges \(1 \to 2\), \(1 \to 3\), \(2 \to 4\), \(3 \to 4\) of the loop. Every column of \(S\) sums to zero, so the all-ones vector is in the nullspace: \[ x = \begin{bmatrix} 1 \\ 1 \\ 1 \\ 1 \end{bmatrix} \in N(S) \] (all four nodes have the same potential — the loop is why this vector exists). A vector in \(N(S^T)\) is a circulation around the loop: \[ y = \begin{bmatrix} 1 \\ -1 \\ 1 \\ -1 \end{bmatrix} \in N(S^T): \qquad S^T y = \begin{bmatrix} -1 - 1 \\ 1 - 1 \\ 1 - 1 \\ 1 - 1 \end{bmatrix} = 0. \] (b) The same idea applies to the whole graph: a current flowing around the corner loop and zero on all other 9 edges satisfies conservation of current at every node, so \[ Y = \begin{bmatrix} 1 \\ -1 \\ 1 \\ -1 \\ 0 \\ 0 \\ 0 \\ 0 \\ 0 \\ 0 \\ 0 \\ 0 \end{bmatrix} \in N(A^T), \] where the first four entries correspond to the four edges of the corner loop (the rows of \(S\)). (c) Since \(N(A)\) is spanned by the all-ones vector, \(\dim N(A) = 1\) and \(\mathrm{rank}(A) = 9 - 1 = 8\). Therefore \[ \dim N(A^T) = 12 - \mathrm{rank}(A) = 12 - 8 = 4. \]

Keywords: incidence matrix, nullspace, left nullspace, loop