7. Some comments.

(a) When you first study linear algebra, you might think that R$^ n$ is useful only for $n = 2$ and $n = 3$. However, if you solve a $1000 \times 50$ least-squares problem, you are really relying on geometrical properties involving the $50$-dimensional subspace $W$ of the $1000$-dimensional space R$^ {1000}$!

(b) What about the nonsingularity of the normal equations in general? Here are two facts that are closely related to each other:

Fact (I). The rank of $A^t A$ equals the rank of $A$.

For example, consider a $20 \times 4$ least-squares problem $A$   x$\approx$   b. The normal equations are $4 \times 4$. They are nonsingular if their rank is 4. By Fact I, this happens if the rank of $A$ is 4, i.e., if the four columns of $A$ are linearly independent. But this is extremely likely if there is any random quality to the entries of $A$. In fact, since row rank = column rank, the rank of $A$ will be 4 if any four rows are linearly independent.

Fact (II). If $A$ is $m \times n$ with $m > n$, the determinant of $A^t A$ equals the sum of the squares of the determinants of all $n \times n$ submatrices of $A$.

Continuing the $20 \times 4$ example, if you take all the $4 \times 4$ submatrices of $A$ (almost 5000 of them), square their determinants, and add, you get the determinant of $A^t A$. As you can see, it's quite likely to be nonzero.