Is this matrix invertible?

Question

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.

Answer 1

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.

Answer 2

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.