Skip to content

4.3-exam1-2001-fall-b

Quiz 1, 2001 (fall) · Section 4.3: Least Squares Approximations Source: exam1_1.pdf, pp. 48-49

Problem

Problem 2. Consider the triangle graph (all three nodes interconnected), with incidence matrix

\[ A_0 = \begin{bmatrix} -1 & 1 & 0 \\ -1 & 0 & 1 \\ 0 & 1 & -1 \end{bmatrix}, \]

and let \(A\) be the matrix obtained from \(A_0\) by omitting the third column:

\[ A = \begin{bmatrix} -1 & 1 \\ -1 & 0 \\ 0 & 1 \end{bmatrix}. \]

(a) Compute \(K_0 = A_0^T A_0\) and \(K = A^T A\).

(b) For \(b = (1, 1, 1)^T\), compute \(A^T b\) and solve \((A^T A)x = A^T b\).

(c) Show that the equation \(A_0^T A_0 \bar{x} = A_0^T b\) cannot be solved uniquely; find the best \(\bar{x}\) (the general solution).

(d) Write down the matrix \(G\) — for the triangle (all nodes interconnected) and for the 4-node structure (all nodes connected except 1 and 4) — and compute \(K_0 + G\) in both cases. What does the resulting matrix tell you?

Solution (a) We have \[ A_0 = \begin{bmatrix} -1 & 1 & 0 \\ -1 & 0 & 1 \\ 0 & 1 & -1 \end{bmatrix}; \quad A = \begin{bmatrix} -1 & 1 \\ -1 & 0 \\ 0 & 1 \end{bmatrix}, \] \[ K_0 = A_0^T A_0 = \begin{bmatrix} -1 & -1 & 0 \\ 1 & 0 & 1 \\ 0 & 1 & -1 \end{bmatrix} \begin{bmatrix} -1 & 1 & 0 \\ -1 & 0 & 1 \\ 0 & 1 & -1 \end{bmatrix} = \begin{bmatrix} 2 & -1 & -1 \\ -1 & 2 & -1 \\ -1 & -1 & 2 \end{bmatrix}, \] \[ K = A^T A = \begin{bmatrix} -1 & -1 & 0 \\ 1 & 0 & 1 \end{bmatrix} \begin{bmatrix} -1 & 1 \\ -1 & 0 \\ 0 & 1 \end{bmatrix} = \begin{bmatrix} 2 & -1 \\ -1 & 2 \end{bmatrix}. \] (b) \[ A^T b = \begin{bmatrix} -1 & -1 & 0 \\ 1 & 0 & 1 \end{bmatrix} \begin{bmatrix} 1 \\ 1 \\ 1 \end{bmatrix} = \begin{bmatrix} -2 \\ 2 \end{bmatrix}. \] And so \[ x = (A^T A)^{-1} A^T b = \begin{bmatrix} 2 & -1 \\ -1 & 2 \end{bmatrix}^{-1} \begin{bmatrix} -2 \\ 2 \end{bmatrix} = \begin{bmatrix} -2/3 \\ 2/3 \end{bmatrix}. \] (c) The equation \[ A_0^T A_0 \bar{x} = A_0^T b \] cannot be solved uniquely because \(A_0\) is not full rank. Since the third column of \(A_0\) is a linear combination of the first two (it's minus their sum) it doesn't "contribute" to the column space and, therefore, the column space is the same. While it cannot be solved uniquely, it can be solved to "within" one degree of freedom. Note that \[ \begin{bmatrix} -2/3 \\ 2/3 \\ 0 \end{bmatrix} \] is a solution. All other solutions can be found by adding any vector from the null space of \(A_0^T A_0\) to this one. The null space of \(A_0^T A_0\) is clearly \[ \left\{ \begin{bmatrix} 1 \\ 1 \\ 1 \end{bmatrix} \right\}, \] and so \[ \bar{x} = \begin{bmatrix} -2/3 \\ 2/3 \\ 0 \end{bmatrix} + C \begin{bmatrix} 1 \\ 1 \\ 1 \end{bmatrix}. \] (d) Write down \(G\). For the triangle, all nodes are interconnected so \[ G = \begin{bmatrix} 0 & 1 & 1 \\ 1 & 0 & 1 \\ 1 & 1 & 0 \end{bmatrix}, \] and \[ K_0 + G = \begin{bmatrix} 2 & -1 & -1 \\ -1 & 2 & -1 \\ -1 & -1 & 2 \end{bmatrix} + \begin{bmatrix} 0 & 1 & 1 \\ 1 & 0 & 1 \\ 1 & 1 & 0 \end{bmatrix} = \begin{bmatrix} 2 & 0 & 0 \\ 0 & 2 & 0 \\ 0 & 0 & 2 \end{bmatrix}. \] For the 4-node structure, all nodes are connected except 1 and 4. So \[ G = \begin{bmatrix} 0 & 1 & 1 & 0 \\ 1 & 0 & 1 & 1 \\ 1 & 1 & 0 & 1 \\ 0 & 1 & 1 & 0 \end{bmatrix}. \] Also, \[ A_0 = \begin{bmatrix} -1 & 1 & 0 & 0 \\ -1 & 0 & 1 & 0 \\ 0 & 1 & -1 & 0 \\ 0 & -1 & 0 & 1 \\ 0 & 0 & -1 & 1 \end{bmatrix}, \] and \[ A_0^T A_0 + G = \begin{bmatrix} 2 & 0 & 0 & 0 \\ 0 & 3 & 0 & 0 \\ 0 & 0 & 3 & 0 \\ 0 & 0 & 0 & 2 \end{bmatrix}. \] The resulting matrix simply tells us how many edges share a given node.

Keywords: incidence matrix, graph, normal equations, least squares, column space