4.1-exam2-2008¶
Quiz 2, 2008 · Section 4.1: Orthogonality of Vectors and Subspaces Source: exam2_1.pdf, pp. 159-160
Problem¶
1 (33 pts.)
(a) If \(Ax = b\) and \(A^Ty = 0\) then \(b\) is perpendicular to \(y\). (The column space of \(A\) is perpendicular to the nullspace of \(A^T\).) Prove this by computing \((Ax)^Ty\).
(b) Write down the 6 by 4 incidence matrix \(A\) of this graph (1 and \(-1\) in each row of \(A\)). What is the dimension of the column space \(C(A)\)? Describe the nullspace \(N(A)\). (The figure shows the 4 nodes 1-4 and the 6 edges 1-6; the edge directions are recoverable from the incidence matrix in the solution below.)
(c) Find one nonzero vector \(y = (y_1, y_2, \dots, y_6)\) that is in the nullspace of \(A^T\). (Think loops.) If voltages \(x_1, x_2, x_3, x_4\) are assigned to the nodes (keep the \(x\)'s as variables not numbers), multiply by \(A\) to find \(Ax\). Check that this \(Ax\) is perpendicular to your vector \(y\). (That's Kirchhoff's Voltage Law.)
Solution
Solution (6+13+14 points) a) We have \[ (Ax)^Ty = x^TA^Ty = x^T(0) = 0. \] So \(b = Ax\) is perpendicular to \(y\). b) To form the incidence matrix \(A\), for each edge we put a \(-1\) for the node where the edge starts, and a \(1\) for the node where the edge ends: \[ A = \begin{bmatrix} -1 & 1 & 0 & 0 \\ 0 & -1 & 1 & 0 \\ -1 & 0 & 1 & 0 \\ -1 & 0 & 0 & 1 \\ 0 & -1 & 0 & 1 \\ 0 & 0 & -1 & 1 \end{bmatrix}. \] Any incidence matrix has a one-dimensional nullspace spanned by the vector consisting of all 1's. Thus \(C(A)\) has dimension \(r = n - \dim(N(A)) = 4 - 1 = 3\), and the nullspace has the vector \((1, 1, 1, 1)\) as a basis. (Of course this can also be calculated by hand.) c) To find the left nullspace of an incidence matrix, we traverse around a closed loop, and keep track of the edges with signs. So for example if we go from node 1 to node 2 to node 4 and back to node 1, we find the vector \((1, 0, 0, -1, 1, 0)\) in the left nullspace of \(A\). Some other examples are: \((1, 1, -1, 0, 0, 0)\), \((0, 0, 1, -1, 0, 1)\), and \((0, 1, 0, 0, -1, 1)\). The matrix \(Ax\) is \[ Ax = \begin{bmatrix} x_2 - x_1 \\ x_3 - x_2 \\ x_3 - x_1 \\ x_4 - x_1 \\ x_4 - x_2 \\ x_4 - x_3 \end{bmatrix}. \] Taking the dot product of \(Ax\) with the first choice of \(y\) above yields \[ (Ax)^Ty = (x_2 - x_1) - (x_4 - x_1) + (x_4 - x_2) = 0. \]Keywords: incidence matrix, column space, nullspace, left nullspace