Normal Equations - Linear Algebra

1. Let $\hat{\mathbf{x}}$ be the least-squares solution to $A\mathbf{x} = \mathbf{b}$, and let $W = \mathrm{Col}(A)$. Which of the following vectors must lie in the orthogonal complement of $W$, denoted $W^\perp$?
   Answer: The residual vector $\mathbf{b} - A\hat{\mathbf{x}}$. The fundamental principle of least squares is that the error vector (or residual vector) $\mathbf{b} - A\hat{\mathbf{x}}$ is orthogonal to the subspace onto which we are projecting, which is the column space $W$. Therefore, $\mathbf{b} - A\hat{\mathbf{x}}$ is in $W^\perp$. The vector $A\hat{\mathbf{x}}$ is in $W$ itself. The vector $\hat{\mathbf{x}}$ is in $\mathbb{R}^n$ (domain of the transformation), not necessarily related orthogonally to $W$. The vector $\mathbf{b}$ is generally not in $W^\perp$.
2. The system $A^T A \mathbf{x} = A^T \mathbf{b}$ is called the 'normal equations' because its solution $\hat{\mathbf{x}}$ ensures a specific orthogonality condition, from which the name is derived. What is this condition?
   Answer: The residual vector $(\mathbf{b} - A\hat{\mathbf{x}})$ is normal (orthogonal) to the column space of $A$. The term 'normal' is synonymous with 'orthogonal'. The normal equations are derived by enforcing the condition that the residual vector $\mathbf{b} - A\hat{\mathbf{x}}$ must be orthogonal to every column of $A$, and thus to the entire column space of $A$. This is the core geometric principle. The other options describe conditions that are not generally true or are special cases not central to the name's origin.
3. Suppose the system $A\mathbf{x} = \mathbf{b}$ is consistent, which implies that $\mathbf{b}$ is already in the column space of $A$. If the normal equations are used to find a least-squares solution $\hat{\mathbf{x}}$, what is the value of the least-squares error, defined as $\|\mathbf{b} - A\hat{\mathbf{x}}\|$?
   Answer: $0$ If the system $A\mathbf{x} = \mathbf{b}$ is consistent, it means there exists an exact solution. The least-squares method finds the vector in $\mathrm{Col}(A)$ closest to $\mathbf{b}$. Since $\mathbf{b}$ is already in $\mathrm{Col}(A)$, the closest vector is $\mathbf{b}$ itself. Therefore, the projection of $\mathbf{b}$ is $\mathbf{b}$, meaning $A\hat{\mathbf{x}} = \mathbf{b}$. The error $\|\mathbf{b} - A\hat{\mathbf{x}}\| = \|\mathbf{b} - \mathbf{b}\| = 0$.
4. Consider the quadratic form $Q(\mathbf{x}) = ||A\mathbf{x} - \mathbf{b}||^2$ where $A$ is $m \times n$ with linearly independent columns. The normal equations arise from setting $\nabla Q(\mathbf{x}) = \mathbf{0}$. Which expression correctly represents the gradient $\nabla Q(\mathbf{x})$?
   Answer: $\nabla Q(\mathbf{x}) = 2A^T(A\mathbf{x} - \mathbf{b})$ When you encounter quadratic forms involving matrix norms like $Q(\mathbf{x}) = ||A\mathbf{x} - \mathbf{b}||^2$, you're dealing with least squares optimization. The key insight is recognizing this as a composite function that requires the chain rule for differentiation. To find $\nabla Q(\mathbf{x})$, first expand the squared norm: $Q(\mathbf{x}) = (A\mathbf{x} - \mathbf{b})^T(A\mathbf{x} - \mathbf{b})$. This gives you $Q(\mathbf{x}) = \mathbf{x}^TA^TA\mathbf{x} - 2\mathbf{b}^TA\mathbf{x} + \mathbf{b}^T\mathbf{b}$. Taking the gradient term by term: the gradient of $\mathbf{x}^TA^TA\mathbf{x}$ is $2A^TA\mathbf{x}$, the gradient of $-2\mathbf{b}^TA\mathbf{x}$ is $-2A^T\mathbf{b}$, and the constant term disappears. This yields $\nabla Q(\mathbf{x}) = 2A^TA\mathbf{x} - 2A^T\mathbf{b} = 2A^T(A\mathbf{x} - \mathbf{b})$. Choice C is correct with this factor of 2 included. Choice A incorrectly places $A$ instead of $A^T$ in front, which would give the wrong dimensions. Choice B has the right structure but missing the factor of 2 that comes from differentiating the squared term. Choice D shows the expanded form before factoring, which is mathematically equivalent to C but doesn't match the standard factored form asked for. Remember: when differentiating squared norms, always expect a factor of 2, and the transpose of the coefficient matrix ($A^T$) appears in the gradient due to the chain rule.
5. Let $W$ be the column space of a matrix $A$. For a vector $\mathbf{b}$, the least-squares solution $\hat{\mathbf{x}}$ to $A\mathbf{x} = \mathbf{b}$ is found. What is the geometric meaning of the vector $\hat{\mathbf{b}} = A\hat{\mathbf{x}}$?
   Answer: $\hat{\mathbf{b}}$ is the orthogonal projection of $\mathbf{b}$ onto the column space $W$. By definition, the vector $A\hat{\mathbf{x}}$ is the orthogonal projection of $\mathbf{b}$ onto the column space of $A$. This vector is the point in $W$ that is closest to $\mathbf{b}$. The vector described in (A) is the error vector $\mathbf{b} - \hat{\mathbf{b}}$. The subspaces in (C) and (D) are incorrect.
6. Given the matrix equation $A\mathbf{x} = \mathbf{b}$ where $A$ is $m \times n$ with $m > n$, suppose the normal equations yield $\hat{\mathbf{x}} = \begin{pmatrix} 2 \\ -1 \end{pmatrix}$. If the residual vector is $\mathbf{r} = \mathbf{b} - A\hat{\mathbf{x}} = \begin{pmatrix} 1 \\ 0 \\ -2 \end{pmatrix}$, what can be concluded about the relationship between $\mathbf{r}$ and the columns of $A$?
   Answer: The residual $\mathbf{r}$ is orthogonal to every column of $A$ because $A^T\mathbf{r} = \mathbf{0}$ is satisfied by the normal equations The normal equations $A^TA\hat{\mathbf{x}} = A^T\mathbf{b}$ can be rewritten as $A^T(A\hat{\mathbf{x}} - \mathbf{b}) = \mathbf{0}$, which means $A^T\mathbf{r} = \mathbf{0}$. This implies that $\mathbf{r}$ is orthogonal to every column of $A$. Choice B is incorrect because the sign of components in $\hat{\mathbf{x}}$ doesn't determine parallelism with columns. Choice C is wrong because $\mathbf{r}$ lies in the orthogonal complement of the column space. Choice D is incorrect because orthogonality to $\mathbf{b}$ is not guaranteed, and orthogonality to columns is guaranteed.
7. Let $P = A(A^T A)^{-1} A^T$ be the projection matrix that projects vectors in $\mathbb{R}^m$ onto the column space of an $m \times n$ matrix $A$. Which of the following expressions must evaluate to the $n \times 1$ zero vector for any vector $\mathbf{b}$ in $\mathbb{R}^m$?
   Answer: $A^T (\mathbf{b} - P\mathbf{b})$ The vector $P\mathbf{b}$ is the projection of $\mathbf{b}$ onto $\mathrm{Col}(A)$, which we denote as $\hat{\mathbf{b}}$. The vector $\mathbf{b} - P\mathbf{b}$ is the error vector $\mathbf{e}$, which is orthogonal to $\mathrm{Col}(A)$. The condition that $\mathbf{e}$ is orthogonal to $\mathrm{Col}(A)$ is precisely that it is orthogonal to every column of $A$. This can be written as $A^T \mathbf{e} = \mathbf{0}$, which is $A^T (\mathbf{b} - P\mathbf{b}) = \mathbf{0}$.
8. Consider two overdetermined systems: System 1 has matrix $A_1$ and right-hand side $\mathbf{b}_1$, while System 2 has matrix $A_2 = A_1$ and right-hand side $\mathbf{b}_2 = 2\mathbf{b}_1$. If $\hat{\mathbf{x}}_1$ and $\hat{\mathbf{x}}_2$ are the respective least squares solutions, what is the relationship between the residual norms $||\mathbf{b}_1 - A_1\hat{\mathbf{x}}_1||$ and $||\mathbf{b}_2 - A_2\hat{\mathbf{x}}_2||$?
   Answer: $||\mathbf{b}_2 - A_2\hat{\mathbf{x}}_2|| = 2||\mathbf{b}_1 - A_1\hat{\mathbf{x}}_1||$ When you encounter problems comparing least squares solutions with scaled right-hand sides, the key insight is that least squares solutions and residuals both scale linearly with the right-hand side vector. For System 1: $A_1\hat{\mathbf{x}}_1 \approx \mathbf{b}_1$, and for System 2: $A_2\hat{\mathbf{x}}_2 \approx \mathbf{b}_2$ where $A_2 = A_1$ and $\mathbf{b}_2 = 2\mathbf{b}_1$. Since the matrix is identical in both systems, but the right-hand side is scaled by 2, the least squares solution also scales by the same factor: $\hat{\mathbf{x}}_2 = 2\hat{\mathbf{x}}_1$. You can verify this because if $\hat{\mathbf{x}}_1$ minimizes $||A_1\mathbf{x} - \mathbf{b}_1||^2$, then $2\hat{\mathbf{x}}_1$ minimizes $||A_1\mathbf{x} - 2\mathbf{b}_1||^2$. The residual for System 2 becomes: $\mathbf{b}_2 - A_2\hat{\mathbf{x}}_2 = 2\mathbf{b}_1 - A_1(2\hat{\mathbf{x}}_1) = 2(\mathbf{b}_1 - A_1\hat{\mathbf{x}}_1)$ Taking norms: $||\mathbf{b}_2 - A_2\hat{\mathbf{x}}_2|| = ||2(\mathbf{b}_1 - A_1\hat{\mathbf{x}}_1)|| = 2||\mathbf{b}_1 - A_1\hat{\mathbf{x}}_1||$ This confirms answer B is correct. A incorrectly squares the scaling factor ($2^2 = 4$), confusing linear scaling with quadratic relationships. C suggests no relationship, ignoring the scaling entirely. D uses $\sqrt{2}$, which would arise from some geometric relationship but doesn't apply here. Study tip: Remember that least squares solutions scale linearly with the right-hand side when the coefficient matrix stays the same. Both the solution and residual scale by the same factor as the right-hand side.
9. The normal equations $A^T A \hat{\mathbf{x}} = A^T \mathbf{b}$ produce the set of all least-squares solutions. Under what geometric condition will there be infinitely many least-squares solutions $\hat{\mathbf{x}}$?
   Answer: When the columns of the matrix $A$ are linearly dependent. The set of least-squares solutions is unique if and only if the matrix $A^T A$ is invertible. This occurs if and only if the columns of $A$ are linearly independent. If the columns of $A$ are linearly dependent, then $A^T A$ is singular, and the system $A^T A \hat{\mathbf{x}} = A^T \mathbf{b}$ will have infinitely many solutions. Geometrically, this means that a vector in the column space can be formed as a linear combination of the columns in more than one way.
10. The normal equations $A^T A \hat{\mathbf{x}} = A^T \mathbf{b}$ are used to find the least-squares solution to an inconsistent system $A\mathbf{x} = \mathbf{b}$. A unique least-squares solution $\hat{\mathbf{x}}$ is guaranteed to exist if and only if:
    Answer: the columns of the matrix $A$ are linearly independent. A unique least-squares solution exists if and only if the matrix $A^T A$ is invertible. The matrix $A^T A$ is invertible if and only if the columns of $A$ are linearly independent. Choice (A) and (B) are sufficient conditions but not necessary. Choice (D) means the system $A\mathbf{x}=\mathbf{b}$ is consistent and has an exact solution, but it does not guarantee the solution is unique unless the columns of $A$ are linearly independent.
11. In a least squares problem, suppose $A = QR$ where $Q$ has orthonormal columns and $R$ is upper triangular and invertible. How do the normal equations $A^TA\mathbf{x} = A^T\mathbf{b}$ simplify when expressed in terms of the QR decomposition?
    Answer: $R\mathbf{x} = Q^T\mathbf{b}$ When you encounter QR decomposition in least squares problems, you're looking at a powerful way to simplify the normal equations by exploiting the orthogonal structure of matrix $Q$. Starting with the normal equations $A^TA\mathbf{x} = A^T\mathbf{b}$ and substituting $A = QR$, you get: $(QR)^T(QR)\mathbf{x} = (QR)^T\mathbf{b}$ This expands to: $R^TQ^TQR\mathbf{x} = R^TQ^T\mathbf{b}$ Here's the key insight: since $Q$ has orthonormal columns, $Q^TQ = I$ (the identity matrix). This dramatically simplifies the equation to: $R^TR\mathbf{x} = R^TQ^T\mathbf{b}$ Since $R$ is invertible, you can multiply both sides by $(R^T)^{-1}$ to get: $R\mathbf{x} = Q^T\mathbf{b}$ This is answer C. Looking at the wrong choices: A) $QR\mathbf{x} = Q^T\mathbf{b}$ incorrectly keeps the original $A = QR$ without accounting for the $A^TA$ structure. B) $R^TR\mathbf{x} = R^TQ^T\mathbf{b}$ stops one step short of the full simplification—it's correct but not simplified. D) $Q^TQR\mathbf{x} = R^T\mathbf{b}$ has the wrong right-hand side and fails to use the orthonormality property. Study tip: Remember that $Q^TQ = I$ for orthonormal columns is the magic that makes QR decomposition so useful—it eliminates the problematic $A^TA$ multiplication that can cause numerical instability.
12. Let $W$ be a subspace of $\mathbb{R}^m$ and let $\mathbf{b}$ be a vector in $\mathbb{R}^m$. The least-squares solution $\hat{\mathbf{x}}$ to $A\mathbf{x}=\mathbf{b}$ (where $W=\mathrm{Col}(A)$) minimizes the distance $\|\mathbf{b} - \mathbf{w}\|$ for all $\mathbf{w} \in W$. Which expression represents the square of this minimum distance?
    Answer: $\|\mathbf{b} - A(A^T A)^{-1} A^T \mathbf{b}\|^2$ When you encounter least-squares problems, you're dealing with finding the best approximation to a vector $\mathbf{b}$ within a subspace $W$. The key insight is that the minimum distance occurs when we project $\mathbf{b}$ onto $W$, and the distance we want is from $\mathbf{b}$ to this projection. The projection of $\mathbf{b}$ onto the column space of $A$ is given by $P\mathbf{b} = A(A^T A)^{-1} A^T \mathbf{b}$, where $P = A(A^T A)^{-1} A^T$ is the projection matrix. The minimum distance is the length of the error vector: $\mathbf{b} - P\mathbf{b} = \mathbf{b} - A(A^T A)^{-1} A^T \mathbf{b}$. Therefore, the square of this minimum distance is $\|\mathbf{b} - A(A^T A)^{-1} A^T \mathbf{b}\|^2$, which is answer D. Let's examine why the other options are incorrect. Option A represents $\|\mathbf{b}\|^2$ plus the square of the projection length, which doesn't correspond to any meaningful geometric quantity in this context. Option B gives you the square of the length of the projection itself, not the distance from $\mathbf{b}$ to the projection. Option C represents the square of the length of the least-squares solution vector $\hat{\mathbf{x}} = (A^T A)^{-1} A^T \mathbf{b}$, which lives in the domain space, not the distance we're measuring. Remember: in least-squares problems, you're always measuring the distance between the original vector and its projection onto the subspace. The answer will involve the difference $\mathbf{b} - \text{projection}$, not just the projection itself.
13. For the linear system $A\mathbf{x} = \mathbf{b}$ with $A$ being $m \times n$ and $m > n$, let $\mathbf{x}_0$ be any particular solution to the normal equations $A^TA\mathbf{x} = A^T\mathbf{b}$. If $A$ has rank $r < n$, what is the general form of all solutions to the normal equations?
    Answer: $\mathbf{x} = \mathbf{x}_0 + \mathbf{y}$ where $\mathbf{y} \in \text{null}(A^TA)$ When you encounter normal equations with a rank-deficient matrix, you're dealing with an underdetermined system that has infinitely many solutions. The key insight is understanding which null space governs the solution structure. The normal equations $A^TA\mathbf{x} = A^T\mathbf{b}$ form a homogeneous system when you consider the difference between any two solutions. If $\mathbf{x}_1$ and $\mathbf{x}_2$ are both solutions, then $A^TA\mathbf{x}_1 = A^T\mathbf{b}$ and $A^TA\mathbf{x}_2 = A^T\mathbf{b}$. Subtracting these equations gives $A^TA(\mathbf{x}_1 - \mathbf{x}_2) = \mathbf{0}$, meaning $\mathbf{x}_1 - \mathbf{x}_2 \in \text{null}(A^TA)$. Therefore, all solutions have the form $\mathbf{x} = \mathbf{x}_0 + \mathbf{y}$ where $\mathbf{y} \in \text{null}(A^TA)$, confirming answer B. Answer A incorrectly uses $\text{null}(A)$ instead of $\text{null}(A^TA)$. While $\text{null}(A) \subseteq \text{null}(A^TA)$, this gives only a subset of solutions when $A$ is rank-deficient. Answer C suggests $\text{col}(A^T) = \text{row}(A)$, which is the orthogonal complement of $\text{null}(A)$, not the space of homogeneous solutions. Answer D uses $\text{row}(A)$ directly, which is the same incorrect reasoning as C. Study tip: For any linear system $M\mathbf{x} = \mathbf{c}$, the general solution is always "particular solution plus null space of the coefficient matrix." Here, the coefficient matrix is $A^TA$, so you need $\text{null}(A^TA)$.
14. Consider the overdetermined system $A\mathbf{x} = \mathbf{b}$ where $A = \begin{pmatrix} 1 & 2 \\ 0 & 1 \\ 1 & 0 \end{pmatrix}$ and $\mathbf{b} = \begin{pmatrix} 3 \\ 1 \\ 2 \end{pmatrix}$. If $\hat{\mathbf{x}}$ is the least squares solution obtained from the normal equations, what is the geometric interpretation of $A\hat{\mathbf{x}}$?
    Answer: $A\hat{\mathbf{x}}$ is the orthogonal projection of $\mathbf{b}$ onto the column space of $A$ The least squares solution $\hat{\mathbf{x}}$ minimizes $||A\mathbf{x} - \mathbf{b}||^2$, which means $A\hat{\mathbf{x}}$ is the point in the column space of $A$ closest to $\mathbf{b}$. This is precisely the orthogonal projection of $\mathbf{b}$ onto $\text{Col}(A)$. Choice B is incorrect because the null space of $A^T$ is orthogonal to the column space. Choice C is wrong because the left null space consists of vectors orthogonal to the row space. Choice D is incorrect because this describes a reflection, not a projection.
15. Consider fitting a line $y = ax + b$ to the data points $(0,1)$, $(1,3)$, and $(2,4)$ using least squares. The normal equations for this problem take the form $\begin{pmatrix} \sum x_i^2 & \sum x_i \\ \sum x_i & n \end{pmatrix}\begin{pmatrix} a \\ b \end{pmatrix} = \begin{pmatrix} \sum x_i y_i \\ \sum y_i \end{pmatrix}$. What is the coefficient matrix of the normal equations?
    Answer: $\begin{pmatrix} 5 & 3 \\ 3 & 3 \end{pmatrix}$ For the data points $(0,1)$, $(1,3)$, $(2,4)$, we have $n = 3$ points. Calculate: $\sum x_i^2 = 0^2 + 1^2 + 2^2 = 5$, $\sum x_i = 0 + 1 + 2 = 3$, and $n = 3$. The coefficient matrix is $\begin{pmatrix} 5 & 3 \\ 3 & 3 \end{pmatrix}$. Choice B swaps the positions of $\sum x_i^2$ and $n$. Choice C incorrectly uses $\sum y_i = 8$ in place of $n = 3$. Choice D incorrectly uses $\sum y_i = 8$ in the (1,1) position instead of $\sum x_i^2 = 5$.
16. To find the best-fit line of the form $y = c_0 + c_1 x$ for the data points $(0, 1)$, $(1, 3)$, and $(2, 4)$, one must find the least-squares solution to the system $A\mathbf{c} = \mathbf{y}$. What are the normal equations $A^T A \mathbf{c} = A^T \mathbf{y}$ for this problem?
    Answer: $\begin{pmatrix} 3 & 3 \\ 3 & 5 \end{pmatrix} \mathbf{c} = \begin{pmatrix} 8 \\ 11 \end{pmatrix}$ When you encounter a least-squares problem, you're solving an overdetermined system where you have more equations than unknowns. The key is setting up the correct matrix equation $A\mathbf{c} = \mathbf{y}$ and then finding the normal equations $A^T A \mathbf{c} = A^T \mathbf{y}$. For the line $y = c_0 + c_1 x$ through points $(0,1)$, $(1,3)$, and $(2,4)$, you need matrix $A$ where each row corresponds to a data point. The first column represents the coefficient of $c_0$ (always 1), and the second column represents the coefficient of $c_1$ (the $x$-value): $A = \begin{pmatrix} 1 & 0 \\ 1 & 1 \\ 1 & 2 \end{pmatrix}, \quad \mathbf{y} = \begin{pmatrix} 1 \\ 3 \\ 4 \end{pmatrix}$ Computing $A^T A$: $A^T A = \begin{pmatrix} 1 & 1 & 1 \\ 0 & 1 & 2 \end{pmatrix} \begin{pmatrix} 1 & 0 \\ 1 & 1 \\ 1 & 2 \end{pmatrix} = \begin{pmatrix} 3 & 3 \\ 3 & 5 \end{pmatrix}$ Computing $A^T \mathbf{y}$: $A^T \mathbf{y} = \begin{pmatrix} 1 & 1 & 1 \\ 0 & 1 & 2 \end{pmatrix} \begin{pmatrix} 1 \\ 3 \\ 4 \end{pmatrix} = \begin{pmatrix} 8 \\ 11 \end{pmatrix}$ This confirms answer D is correct. Option A has the wrong $A^T \mathbf{y}$ vector (14 instead of 11). Option B shows the original system $A\mathbf{c} = \mathbf{y}$, not the normal equations. Option C has incorrect entries in $A^T A$ - the computation errors likely come from mishandling the matrix multiplication. Study tip: Always double-check your matrix multiplications when computing normal equations. Set up $A$ systematically: first column all 1's for the constant term, subsequent columns for the $x$-coefficients.
17. Consider the problem of finding the least-squares solution to the system of equations: $-$x + y = 3$$ $\quad x + y = 0$ $\quad y = 4$ $$\ Which of the following represents the corresponding normal equations $A^T A \hat{\mathbf{x}} = A^T \mathbf{b}$?
    Answer: $\begin{pmatrix} 2 & 0 \\ 0 & 3 \end{pmatrix} \hat{\mathbf{x}} = \begin{pmatrix} -3 \\ 7 \end{pmatrix}$ The system can be written as $A\mathbf{x}=\mathbf{b}$ where $A = \begin{pmatrix} -1 & 1 \\ 1 & 1 \\ 0 & 1 \end{pmatrix}$, $\mathbf{x} = \begin{pmatrix} x \\ y \end{pmatrix}$, and $\mathbf{b} = \begin{pmatrix} 3 \\ 0 \\ 4 \end{pmatrix}$. We compute $A^T A$ and $A^T \mathbf{b}$. $A^T = \begin{pmatrix} -1 & 1 & 0 \\ 1 & 1 & 1 \end{pmatrix}$. $A^T A = \begin{pmatrix} -1 & 1 & 0 \\ 1 & 1 & 1 \end{pmatrix} \begin{pmatrix} -1 & 1 \\ 1 & 1 \\ 0 & 1 \end{pmatrix} = \begin{pmatrix} 2 & 0 \\ 0 & 3 \end{pmatrix}$. $A^T \mathbf{b} = \begin{pmatrix} -1 & 1 & 0 \\ 1 & 1 & 1 \end{pmatrix} \begin{pmatrix} 3 \\ 0 \\ 4 \end{pmatrix} = \begin{pmatrix} -3 \\ 7 \end{pmatrix}$. Thus, the normal equations are $\begin{pmatrix} 2 & 0 \\ 0 & 3 \end{pmatrix} \hat{\mathbf{x}} = \begin{pmatrix} -3 \\ 7 \end{pmatrix}$.
18. Let $A$ be an $m \times n$ matrix and $\mathbf{b}$ be a vector in $\mathbb{R}^m$. If $\hat{\mathbf{x}}$ is the least-squares solution to the system $A\mathbf{x} = \mathbf{b}$, which statement best describes the geometric relationship involving the error vector $\mathbf{e} = \mathbf{b} - A\hat{\mathbf{x}}$?
    Answer: The error vector $\mathbf{e}$ is orthogonal to the column space of $A$. The normal equations $A^T A \hat{\mathbf{x}} = A^T \mathbf{b}$ are derived from the orthogonality condition $A^T(\mathbf{b} - A\hat{\mathbf{x}}) = \mathbf{0}$. This condition means that the error vector $\mathbf{e} = \mathbf{b} - A\hat{\mathbf{x}}$ is orthogonal to every column of $A$. Therefore, the error vector is orthogonal to the entire column space of $A$.
19. A researcher sets up normal equations to solve an overdetermined linear system, but discovers that the coefficient matrix $A^TA$ is singular. Given that the original matrix $A$ is $4 \times 3$, what is the most likely explanation for this singularity, and what does it imply about the solution?
    Answer: The columns of $A$ are linearly dependent; the normal equations have infinitely many solutions lying on an affine subspace When you encounter normal equations and a singular $A^TA$ matrix, you're dealing with fundamental concepts about linear independence and the least squares solution structure. The key insight is understanding what makes $A^TA$ singular. Since $A$ is $4 \times 3$, we have more equations than unknowns (overdetermined system). The matrix $A^TA$ becomes singular precisely when the columns of $A$ are linearly dependent. This happens because $A^TA$ inherits the rank deficiency from $A$ - if $\text{rank}(A) < 3$, then $\text{rank}(A^TA) < 3$, making it non-invertible. When $A^TA$ is singular, the normal equations $A^TA\mathbf{x} = A^T\mathbf{b}$ have infinitely many solutions forming an affine subspace (a translated version of the null space). This means multiple parameter vectors can minimize the least squares objective function equally well. Choice A incorrectly suggests a unique exact solution exists - but overdetermined systems rarely have exact solutions, and singularity indicates non-uniqueness. Choice B wrongly claims the normal equations are inconsistent; they're actually always consistent since $A^T\mathbf{b}$ lies in the column space of $A^TA$. Choice C misunderstands the relationship between $\mathbf{b}$ and solvability - even when $\mathbf{b}$ isn't in $A$'s column space, least squares solutions still exist and are meaningful. Study tip: Remember that $A^TA$ singular always means linearly dependent columns in $A$, which leads to infinitely many least squares solutions. This is a structural property of the matrix, not the right-hand side vector.
20. For the overdetermined system $A\mathbf{x} = \mathbf{b}$, let $P$ be the orthogonal projection matrix onto the column space of $A$. If the normal equations have solution $\hat{\mathbf{x}}$, which of the following expressions correctly represents the squared norm of the residual $||\mathbf{b} - A\hat{\mathbf{x}}||^2$?
    Answer: $||\mathbf{b}||^2 - ||P\mathbf{b}||^2$ When you encounter questions about least squares and projection matrices, remember that the residual represents the "leftover" part of $\mathbf{b}$ that cannot be expressed in the column space of $A$. The key insight is understanding what happens geometrically. The vector $A\hat{\mathbf{x}}$ is the orthogonal projection of $\mathbf{b}$ onto the column space of $A$, which we can write as $P\mathbf{b}$. The residual $\mathbf{b} - A\hat{\mathbf{x}} = \mathbf{b} - P\mathbf{b}$ is orthogonal to the column space. By the Pythagorean theorem in this orthogonal decomposition: $||\mathbf{b}||^2 = ||P\mathbf{b}||^2 + ||\mathbf{b} - P\mathbf{b}||^2$ Rearranging gives us $||\mathbf{b} - A\hat{\mathbf{x}}||^2 = ||\mathbf{b}||^2 - ||P\mathbf{b}||^2$, which is answer D. Let's see why the other options fail: A $\mathbf{b}^T A \hat{\mathbf{x}} - ||A\hat{\mathbf{x}}||^2$ incorrectly assumes you can factor the squared norm as a difference involving the inner product. B $||P\mathbf{b}||^2 - ||\mathbf{b}||^2$ has the terms reversed and would give a negative value, which is impossible for a squared norm. C $||\mathbf{b}||^2 - \mathbf{b}^T A \hat{\mathbf{x}}$ mixes a squared norm with an inner product without proper justification. Study tip: Always remember that in least squares problems, $\mathbf{b}$ decomposes orthogonally into its projection onto the column space ($P\mathbf{b}$) plus the residual. Use the Pythagorean theorem to relate their squared norms.

Start this quiz