Determinant of Circulation Matrix or Vandermonde Alteration?

Question

I'm stuck on this problem:

Given $n$ complex numbers $\alpha_\nu$, show that the determinant of

$$ \begin{vmatrix} \alpha_1 & \alpha_2 & \cdots & \alpha_{n-1} & \alpha_n \\ \alpha_2 & \alpha_3 & \cdots & \alpha_n & \alpha_1 \\ \vdots \\ \alpha_n & \alpha_1 & \cdots & \alpha_{n-2} & \alpha_{n-1} \end{vmatrix} $$

is equivalent to $(-1)^{\frac{n(n-1)}{2}}\beta\cdots\beta_n$ where $$\beta_k=\sum_\nu \epsilon^\nu_k \alpha_\nu$$ and $$\epsilon_k=cos(\frac{2\pi k}{n})+isin(\frac{2\pi k}{n})$$.

Hint: Multiply the above matrix by $$ \begin{pmatrix} \epsilon_1 & \cdots & \epsilon_n\\ \vdots\\ \epsilon_1^n & \cdots & \epsilon_n^n \end{pmatrix} $$

I didn't know exactly how to multiply out that matrix, but I think I may have found another way to solve this. So, what I've done is first notice that this matrix permutes backwards every row down. I wanted to proceed by induction. I let my base case be $n=2$ and I came up with

$$ \begin{vmatrix} \alpha_1 & \alpha_2\\ \alpha_2 & \alpha_1 \end{vmatrix} =\alpha_1^2-\alpha_2^2 $$

Then, for $n=2$, I computed $\beta_1$ and $\beta_2$ like so: $$\beta_1=\epsilon_1^1 \alpha_1+\epsilon_1^2 \alpha_2=-\alpha_1+\alpha_2$$ and $$\beta_2=\epsilon_2^1 \alpha_1+\epsilon_2^2 \alpha_2=\alpha_1+\alpha_2$$.

When I plug in $n=2$ into our equivalence term, I see that this is just $-1 \beta_1 \beta_2$. So this works.

I have no clue how to even start the induction step. So here are my questions: 1. Could someone possibly give me a hint on how to start the induction step on this problem? We are using leibniz notation for determinants. 2. How do I multiply this matrix out like the hint says? 3. Would multiplying this matrix out make a big difference? Any help is greatly appreciated! Thanks!

Answer 1

Doing row/column expansion and arguing by induction seems to be quite complicated so let me follow the hint given to you. First, note that the expression you are given for the determinant has $(-1)^{\frac{n(n-1)}{2}}$ inside which suggests that we should perform $\frac{n(n-1)}{2}$ row or column exchanges in order to get rid of the sign. Moving the $n$-th row to the first row, the $n-1$-th row to the second row and so on we perform $(-1)^{\frac{n(n-1)}{2}}$ row exchanges resulting in the following matrix:

$$ A = \begin{pmatrix} \alpha_n & \alpha_1 & \alpha_2 & \cdots & \alpha_{n-2} & \alpha_{n-1} \\ \alpha_{n-1} & \alpha_n & \alpha_1 & \cdots & \alpha_{n-3} & \alpha_{n-2} \\ \vdots \\ \alpha_{2} & \alpha_3 & \alpha_4 & \cdots & \alpha_{n} & \alpha_1 \\ \alpha_1 & \alpha_2 & \alpha_3 & \cdots & \alpha_{n-1} & \alpha_{n} \end{pmatrix}. $$

The matrix $A$ is called a Circulant matrix and has the nice property that each diagonal is constant and each row is a right shift of the previous one. Following the hint, let us denote by $v_k = (\epsilon_k, \epsilon_k^2, \ldots, \epsilon_k^n)^T$ and $B = (v_1 | \ldots | v_n)$ the matrix you were suggested to multiply $A$ by. Calculating $Av_k$, we have:

$$ Av_k = \begin{pmatrix} \alpha_n \epsilon_k + \alpha_1 \epsilon_k^2 + \alpha_2 \epsilon_k^3 + \cdots + \alpha_{n-2} \epsilon_k^{n-1} + \alpha_{n-1} \epsilon_k^n \\ \alpha_{n-1} \epsilon_k + \alpha_n \epsilon_k^2 + \alpha_1 \epsilon_k^3 + \cdots + \alpha_{n-3} \epsilon_k^{n-1} + \alpha_{n-2} \epsilon_k^n \\ \vdots \\ \alpha_{2} \epsilon_k + \alpha_3 \epsilon_k^2 + \alpha_4 \epsilon_k^3 + \cdots + \alpha_{n} \epsilon_k^{n-1} + \alpha_1 \epsilon_k^n \\ \alpha_1 \epsilon_k + \alpha_2 \epsilon_k^2 + \alpha_3 \epsilon_k^3 + \cdots + \alpha_{n-1} \epsilon_k^{n-1} + \alpha_{n} \epsilon_k^n \end{pmatrix} = (\alpha_n + \alpha_1 \epsilon_k + \ldots + \alpha_{n-2} \epsilon_k^{n-2} + \alpha_{n-1} \epsilon_k^{n-1}) \begin{pmatrix} \epsilon_k \\ \epsilon_k^2 \\ \epsilon_k^3 \\ \vdots \\ \epsilon_k^{n-1} \\ \epsilon_k^n \end{pmatrix} = (\alpha_1 \epsilon_k + \ldots + \alpha_{n-2} \epsilon_k^{n-2} + \alpha_{n-1} \epsilon_k^{n-1} + \alpha_n \epsilon_k^n) v_k = \beta_k v_k. $$

Here, we used the fact that $\epsilon_k$ is a $n$-th root of unity and so $\epsilon_k^n = 1$ and $\epsilon_k^{n+j} = \epsilon_k^j$.

If you are familiar with the notion of eigenvalues, then this shows that $v_k$ is an eigenvector of $A$ corresponding to the eigenvalue $\beta_k$. The vectors $v_k$ are linearly independent as can be seen from the fact that $\epsilon_1, \ldots, \epsilon_n$ are all distinct and thus $\det B \neq 0$ (being a Vandermonde determinant). Thus, we have found all the eigenvalues of $A$ and so we must have $\det(A) = \prod_{j=1}^n \beta_j$ as required.

If you are not familiar with the notion of eigenvalues, we can finish the argument directly. We have

$$ A \cdot B = (Av_1 | \ldots | Av_n) = (\beta_1 v_1 | \ldots | \beta_n v_n) = B \cdot \mathrm{diag}(\beta_1, \ldots, \beta_n). $$

Taking the determinant of both sides and using the multiplicativity property, we have $\det(A) \det(B) = \det(B) \prod_{j=1}^n \beta_j$. Since $\det(B) \neq 0$, we have $\det(A) = \prod_{j=1}^n \beta_j$.