Prove this $(n+1)\times (n+1)$ matrix $\bf{A}$ is invertible for $n < m-1$ and the $x_k$ distinct,
\begin{bmatrix} m &\sum_{k=1}^mx_k &\sum_{k=1}^mx_k^2 &\cdots &\sum_{k=1}^mx_k^n \\\\ \sum_{k=1}^mx_k &\sum_{k=1}^mx_k^2 & \cdots &\cdots&\sum_{k=1}^mx_k^{n+1} \\\\ \vdots &\vdots &\ddots &&\vdots \\ & & & &&\\\\ \sum_{k=1}^mx_k^n&\sum_{k=1}^mx_k^{n+1}&\cdots&\cdots&\sum_{k=1}^mx_k^{2n} \end{bmatrix}
I'm sure many of you recognize this as the normal matrix for polynomial least squares.
The hint in the book is as follows:
Suppose $\bf{A}$ is singular and that $\bf{c}\neq\bf{0}$ is such that $\bf{c}$$^\text{T}$$\bf{Ac}$$\;=0$. Show that the $n$th-degree polynomial whose coefficients are the coordinates of $\bf{c}$ has more than $n$ roots, and use this to establish a contradiction.
I worked on this for quite a while to no avail. First off I can't figure out why the matrix is multiplied on the left by the transpose of $\bf{c}$, I'm assuming $\bf{c}$ is chosen because it's a non-trivial element in the kernel, but that doesn't require its transpose on the left.
Second, things get pretty complicated once you start messing with the series, so I was hoping for something that avoided messy computations. It's the product of the Vandermonde matrix and its transpose, but they're not square so that seemed useless.
The closest I could get to even relating this to the polynomial $c_0+c_1t+...+c_nt^n$ was to consider the rows of the vector $\bf{A\cdot c}$. By that I mean consider the first row (set equal to zero), then dividing by $m$ we get: $$c_0 + c_1\frac{\sum_{k=1}^mx_k}{m}+...+c_n\frac{\sum_{k=1}^mx_k^n}{m}=0.$$
If the various $\frac{\sum_{k=1}^mx_k^r}{m}$ were powers of $\frac{\sum_{k=1}^mx_k}{m}$, then that would be a root, but they're clearly not. Or instead of dividing by $m$ you could split it into $m>n+1$ expressions of the form $$c_0 + c_1x_k + ... + c_nx_k^n\; ,$$ such that their sum is equal to zero, but that certainly doesn't imply they all have to be zero individually.
Anyways as you can see I'm stumped.
**Also note that while $n=m-1$ will most of the time be invertible, if one of the data points is zero, then it won't be.
It's important to remember where your matrix comes from. The normal matrix is given by $A=X^\mathrm{T}X$ where $$X = \begin{pmatrix} 1 & x_1 & x_1^2 & \cdots & x_1^n \\ 1 & x_2 & x_2^2 & \cdots & x_2^n \\ \vdots &\vdots &\vdots& \ddots & \vdots \\ 1 & x_m & x_m^2 & \cdots & x_m^n \\\end{pmatrix}$$ where $X$ is assumed to be $m\times (n+1)$ and where at least $n+1$ of the $m$ $x_i$ are distinct. Then you have $$\mathbf{c}^\mathrm{T}A\mathbf{c} = \mathbf{c}^\mathrm{T}X^\mathrm{T}X\mathbf{c}=(X\mathbf{c})\cdot (X\mathbf{c})=\|X\mathbf{c}\|^2$$ From the above, we see that $A\mathbf{c} = \mathbf{0}$ if and only if $X\mathbf{c} = \mathbf{0}$. Therefore the statement is equivalent to proving that $X$ has a trivial kernel. Suppose otherwise, then $$X\mathbf{c} = c_0\begin{pmatrix}1 \\ 1 \\ \vdots \\ 1\end{pmatrix} + c_1\begin{pmatrix}x_1 \\ x_2 \\ \vdots \\ x_m\end{pmatrix} + \cdots + c_n\begin{pmatrix}x_1^n \\ x_2^n \\ \vdots \\ x_m^n\end{pmatrix} = \begin{pmatrix}0 \\ 0 \\ \vdots \\ 0\end{pmatrix}$$ This is where your hint comes in. The above implies that the polynomial $$p(t) = c_0 + c_1t + \cdots + c_nt^n$$ has roots $\{x_1,\ \cdots,\ x_m\}$. Since at least $n+1$ of these numbers are distinct, this means that $p(t)$ is an $n$th degree polynomial with greater than $n$ roots. This contradicts the fundamental theorem of algebra. Therefore your polynomial is identically zero and hence $\mathbf{c} = \mathbf{0}$.
As for motivating the solution, I can think of two reasons why we might multiply by $\mathbf{c}$ on both the left and the right. The first is to be able to relate the equation back to $X$. Introducing the $\mathbf{c}^\mathrm{T}$ on the left introduces symmetry. The same trick is precisely what is used to prove that the rank of $A$ is equal to the rank of $A^\mathrm{T}A$ for any matrix $A$. If you know that the ranks are equal a priori, then a lot of this can be skipped.
A second reason is to note that your matrix is symmetric and (at least) positive semi-definite. This is due to the fact that $A$ is the gram matrix of $X$. Naturally, one way of proving that the matrix is invertible is to prove that it is not just positive semi-definite but in fact positive definite. Again, this leads to the consideration of the quadratic form $\mathbf{c}^\mathrm{T}A\mathbf{c}$.
The motivation here solely comes from the fact that you know the matrix factorization. The moral here is to simplify the problem. You have a factorization of the matrix, which is a very useful tool, so try to use that to your advantage.