Unitary Vandermonde matrices other than DFT? We know that building a Vandermonde matrix from all the different roots of 1 makes a unitary matrix up to scale ($M^* = c\cdot M^{-1}$) performing the discrete Fourier transform. Obviously, arbitrary permutation of the roots still makes a unitary matrix.
Are there any other unitary Vandermonde matrices? It feels like the answer is "no", but it's not obvious to me how to prove it.
 A: Let $V$ denote a size-$n$ square Vandermonde matrix associated with values (i.e. its second column is) $x_1,x_2,\dots,x_n$. The "dot-product" of any two rows is given by
$$
(VV^*)_{j,k} = \sum_{p=0}^{n-1} (x_j \bar x_k) = 
\begin{cases}
\frac{1 - (x_j\bar x_k)^n}{1 - (x_j \bar x_k)} & x_j\bar x_k \neq 1\\
n & x_j\bar x_k = 1.
\end{cases}
$$
With that, we see that in order for $V$ to have orthogonal rows (equivalently in order for $VV^*$ to be diagonal), it must be that $x_j \bar x_k$ satisfies $x_j \bar x_k \neq 0$ and $(x_j \bar x_k)^n = 1$ for all $j \neq k$. In order for $V$ to have rows of the same length (i.e. for $VV^*$ to be a multiple of the identity), it must hold that the following values are equal:
$$
(VV^*)_{j,j} = \sum_{p=0}^{n-1}|x_j|^{2p} = 
\begin{cases}
\frac{1 - |x_j|^{2n}}{1 - |x_j|^2} & |x_j|\neq 1\\
n & |x_j| = 1.
\end{cases}
$$
Ultimately, this means that we must have $|x_j| = |x_k|$ for all $j \neq k$. From the fact that $(x_j\bar x_k) = 1$, we must have $(|x_j||x_k|)^n = 1$, so it must hold that $|x_k| = 1$ for all $k$.

With that established, here are a few other Vandermonde matrices that are a multiple of a unitary matrix. Note that for any $x_1$ with $|x_1| = 1$, we can take $x_j = \omega^{j}x_{1}$, where $\omega = \exp(2 \pi i/n)$. We can of course permute these choices $x_j$ (and hence the rows of the Vandermonde matrix); some of these permutations can be reached by choosing an alternative primitive root of unity instead of $\omega$.
The Vandermonde matrices obtained as above can all be expressed in the form
$$
V = PWD_\gamma, \quad D_\gamma = \pmatrix{1\\&\gamma \\ && \ddots \\ &&& \gamma^{n-1}} 
$$
where $P$ is a permutation matrix, $W$ denotes the (unnormalized) DFT matrix, and $|\gamma| = 1$. $\gamma$ corresponds to our choice of $x_1$.
These are the only Vandermonde matrices that are multiples of unitary matrices.
To see that this is the case, let $x_1,\dots,x_n$ denote the values associated with such a Vandermonde matrix. As discussed above, we have $|x_j| = 1$ for all $j$, and in particular $x_1 \neq 0$. Consider the values $x_j \bar x_1$ for $j = 2,\dots,n$. We note that the values $x_j\bar x_1$ must be distinct for all $j = 2,\dots,n$; otherwise, we have a Vandermonde matrix associated with repeated values, which means that the matrix is not invertible and hence not a multiple of a unitary matrix. Moreover, we have $|x_j| = 1$ for all $j$, and we cannot have $x_j\bar x_1 = 1$. Finally, $x_j \bar x_1$ must be a root of unity.
With that we conclude that $x_j \bar x_1 = x_j/x_1$ is equal to an $n$th root of unity. That is, we have $x_1 \bar x_j = \omega^{p_j}$ where $\omega = \exp(2 \pi i/n)$ and $p_2,\dots,p_n$ are distinct and non-zero modulo $n$. That is,
$$
x_j = x_1 \omega^{p_j}, \quad j = 2,\dots,n,
$$
which means that our Vandermonde matrix is of the above form. $\square$

Given $p_1 = 0$ and $1 \leq p_2,\dots,p_n \leq n-1$, we can build the corresponding $P$ and $D_\gamma$ as follows: if we take $e_0,e_1,\dots,e_{n-1}$ to denote the standard basis of $\Bbb C^n$ (i.e. the rows of the identity matrix), then take $P$ to be the matrix whose $j$th row is $e_{p_j}$. From there, take $\gamma = x_1$.
