Is this matrix invertible? I have been working on a proof and am stuck with showing that the below matrix is invertible. I am not interested in the explicit inverse, only showing it has a nonzero determinant as the existence of the inverse is enough for my proof. I have the important stipulation that x is a non root of unity. (Lets work over the complex numbers)
\begin{array}{ccccc}
x-1 & x^2-1 & x^3-1 & \ldots & x^n-1 \\
x^2-1 & x^4-1 & x^6-1 &\ldots & x^{2n}-1 \\
x^3-1 & x^6-1 & x^9-1 &\ldots & x^{3n}-1\\
\vdots& \ldots& \ldots& \ldots & \vdots \\
x^n-1 & x^{2n}-1 & x^{3n}-1 & \ldots & x^{n\times n}-1 
  \end{array}
I have computed various examples in maple and shown that this has an inverse when x is a non-root of 1 (this seems essential) but I require a general argument. Any assistance would be very helpful. 
 A: Call your matrix $A$. If $X=(a,b,c,\ldots,f)^T$ is a column vector then the polynomial
$$ p(y) = ay+by^2+cy^3+\cdots+fy^n-(a+c+d+\cdots+f) $$
applied to $x, x^2, x^3, \ldots, x^n$ will produce the elements of $AX$.
If $AX=0$, then accordingly $x, x^2, x^3, \ldots, x^n$ are all roots of $p$. We can also see directly that $1$ is a root of $p$. If the powers of $x$ up to $x^n$ are all different and neither of them equals $1$, then $p$ has too many roots for a nonzero polynomial of degree at most $n$.
Thus under these conditions, $A$ will have a trivial null space and therefore be invertible.
In particular $x$ can be a $k$th root of unity for $k>n$.

ON the other hand if the powers of $x$ are not different, or one of them equals $1$, then $A$ will have two rows identical, or a zero row, and so it obviously is not invertible. So the criterion is both necessary and sufficient.
A: Take the column $k$. If we denote $x^k=z$ then it looks like
$$
\left[\matrix{z-1\\ z^2-1\\z^3-1\\ \vdots\\ z^n-1}\right]=(z-1)\left[\matrix{1\\ z+1\\z^2+z+1\\ \vdots\\ z^{n-1}+\ldots+z+1}\right].
$$
Now use the top row of ones to eliminate all other ones and $z$ to eliminate all other $z$ and so on
$$
(z-1)\left[\matrix{1\\ z+1\\z^2+z+1\\ \vdots\\ z^{n-1}+\ldots+z+1}\right]\sim
(z-1)\left[\matrix{1\\ z\\z^2+z\\ \vdots\\ z^{n-1}+\ldots+z}\right]\sim\ldots\sim
(z-1)\left[\matrix{1\\ z\\z^2\\ \vdots\\ z^{n-1}}\right].
$$
We get the column of (transposed) Vandermonde matrix with $\alpha_k=x^k$. It gives the determinant to be
$$
\underbrace{\prod_{k=1}^n(x^k-1)}_{\text{column factors}}\cdot\underbrace{\prod_{1\le k<m\le n}(x^k-x^m)}_{\text{vandermonde det}}.
$$
P.S. It can be simplified some more if needed.
