Prove this matrix is invertible for $n < m-1$ 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.
 A: 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.
