Skip to content

3.5-final-2014-strang-c

Final Exam, 2014 · Section 3.5: Dimensions of the Four Subspaces Source: finalexam_2.pdf, p. 142

Problem

8 (15 points) A 4-node graph has all six possible edges. Its incidence matrix \(A\) and its Laplacian matrix \(A^TA\) are

\[ A = \begin{bmatrix} -1 & 1 & 0 & 0 \\ -1 & 0 & 1 & 0 \\ -1 & 0 & 0 & 1 \\ 0 & -1 & 1 & 0 \\ 0 & -1 & 0 & 1 \\ 0 & 0 & -1 & 1 \end{bmatrix}, \qquad A^TA = \begin{bmatrix} 3 & -1 & -1 & -1 \\ -1 & 3 & -1 & -1 \\ -1 & -1 & 3 & -1 \\ -1 & -1 & -1 & 3 \end{bmatrix}. \]

(a) Describe the nullspace of \(A\).

(b) The all-ones matrix \(B = \mathrm{ones}(4)\) has what eigenvalues? Then what are the eigenvalues of \(A^TA = 4I - B\)?

(c) For the Singular Value Decomposition \(A = U\Sigma V^T\), can you find the nonzero entries in the diagonal matrix \(\Sigma\) and one column of the orthogonal matrix \(V\)?

Solution (a) The graph is connected (all six edges are present), so \[ N(A) = \mathrm{span} \left\{ \begin{bmatrix} 1 \\ 1 \\ 1 \\ 1 \end{bmatrix} \right\}. \] (Applying \(A\) to a vector of node potentials gives the potential drops along the edges; all drops are zero exactly when all potentials in the connected graph are equal.) (b) The all-ones matrix is \(B = \vec{1}\vec{1}^T\) with \(\vec{1} = (1, 1, 1, 1)\), so \(B = 4 (\vec{1}/2)(\vec{1}/2)^T\): it has eigenvalues \[ \lambda(B) = 4, 0, 0, 0. \] Since \(I\) and \(B\) share the same eigenvectors, the eigenvalues add: \[ \lambda_i(A^TA) = \lambda_i(4I) - \lambda_i(B) = 4 - (4, 0, 0, 0), \] so \[ \lambda(A^TA) = 0, 4, 4, 4. \] (c) The singular values are the square roots of the eigenvalues of \(A^TA\): \[ \sigma = 2, 2, 2 \] (three nonzero singular values; \(\mathrm{rank}(A) = 3\)). A column of \(V\) is an eigenvector of \(A^TA\): the vector for the zero eigenvalue is \[ v_1 = \frac{1}{2} \begin{bmatrix} 1 \\ 1 \\ 1 \\ 1 \end{bmatrix}, \] since every row of \(A^TA\) sums to zero, i.e. \(A^TA \vec{1} = 0\). (The other two columns of \(V\) lie in \(\vec{1}^\perp\), corresponding to the eigenvalue 4.)

Keywords: incidence matrix, Laplacian, eigenvalues, singular values