Skip to content

3.5-final-2011-strang

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

Problem

6. (a) For this directed graph, write down the 5 by 4 incidence matrix \(A\). Describe the nullspace of \(A\).

The graph has 4 nodes (numbered 1, 2, 3, 4) and 5 directed edges: \(1 \to 2\), \(3 \to 2\), \(1 \to 3\), \(1 \to 4\), and \(4 \to 3\).

(b) Find the matrix \(G = A^T A\). Is this matrix \(G\) positive definite? (Explain why or why not.) The first entry is \(G_{11} = 3\) because the graph has ____.

(c) What is the sum of the squares of the singular values of \(A\)? Hint: Remember that those numbers \(\sigma^2\) are ____.

Solution (a) Each row of \(A\) corresponds to an edge, with \(-1\) at the start node and \(+1\) at the end node: \[ A = \begin{bmatrix} -1 & 1 & 0 & 0 \\ 0 & 1 & -1 & 0 \\ -1 & 0 & 1 & 0 \\ -1 & 0 & 0 & 1 \\ 0 & 0 & 1 & -1 \end{bmatrix}. \] The graph is connected, so the rank is \(4 - 1 = 3\) and the nullspace has dimension 1. Every row has one \(-1\) and one \(+1\), so \(A(1, 1, 1, 1) = 0\), and the nullspace is \[ N(A) = \text{span} \begin{bmatrix} 1 \\ 1 \\ 1 \\ 1 \end{bmatrix}. \] (b) \[ G = A^T A = \begin{bmatrix} 3 & -1 & -1 & -1 \\ -1 & 2 & -1 & 0 \\ -1 & -1 & 3 & -1 \\ -1 & 0 & -1 & 2 \end{bmatrix}. \] \(G\) is not positive definite: \(G\) is positive semidefinite (since \(x^T G x = \|Ax\|^2 \ge 0\)), but \(G(1, 1, 1, 1) = 0\) with \((1, 1, 1, 1) \ne 0\), so \(G\) is singular. The first entry is \(G_{11} = 3\) because the graph has three edges touching node 1 (the degree of node 1 is 3). (c) The sum of the squares of the singular values of \(A\) is the trace of \(A^T A\) (those numbers \(\sigma^2\) are the eigenvalues of \(A^T A\), which add to the trace): \[ \sum \sigma_i^2 = \mathrm{trace}(A^T A) = 3 + 2 + 3 + 2 = 10. \] Equivalently, it is the sum of the squares of all 30 entries of \(A\): each of the 5 edges contributes \((-1)^2 + 1^2 = 2\).

Keywords: incidence matrix, graph, positive semidefinite, singular values