4.1-exam2-2011-edelman¶
Quiz 2, 2011 (edelman) · Section 4.1: Orthogonality of Vectors and Subspaces Source: exam2_2.pdf, pp. 38-40
Problem¶
1 (30 pts.)
Consider the directed graph with four vertices and four edges pictured below. (The figure is not in the corpus; the edge directions are recoverable from the incidence matrix \(A\) below.)
- (7 pts) The \(4 \times 4\) incidence matrix (following class conventions) of this directed graph is:
-
(7 pts) Find the determinant of the incidence matrix. (The easy way or the hard way)
-
(8 pts) Find a basis for the column space of the incidence matrix. (Note this can be done with or without the answer in part 1.)
-
(8 pts) Consider whether or not it is possible to have an incidence matrix for a graph with \(n\) nodes and \(n\) edges that is invertible. If it is possible, draw the directed graph; if not possible, argue briefly why not.
Solution
1. The incidence matrix is as given above. 2. \(\det(A) = 0\). This can be done by direct expansion or by appealing conceptually to show that the matrix is not invertible. One can use that the sum of all columns is 0, that we know from book/class that the rank is \(4 - 1 = 3\), or that the nullspace includes \((1, 1, 1, 1)^T\) (note this is equivalent to the columns summing to 0 condition) and thus is nonempty. 3. We need \(4 - 1 = 3\) basis vectors. Any three columns of \(A\) form a basis, as would any three independent vectors whose first three components sum to 0. 4. Impossible, as the ones vector is in the nullspace of every incidence matrix for every graph. As in problem 2, one can also argue from book/class knowledge, or explicitly show that the column sums are 0. One can also show that the rows corresponding to a loop must sum to 0 and we must have a loop.Keywords: incidence matrix, graph, column space, nullspace, determinant