Making the matrix $A_{mn} = \frac{1}{\sqrt{N}} e^{-i\frac{2\pi}{N}x_m k_n}$ unitary

Question

Let's say we have a matrix

$$A_{mn} = \frac{1}{\sqrt{N}}e^{-i\frac{2\pi}{N} x_m k_n}$$

where $0 \leq x_m < N$, and each of $m, n$ is an integer from $0$ to $N - 1$. If $x_m$ is an integer where $x_m = m$, we can find that $k_n = n$ makes the matrix $A_{mn}$ unitary, i.e., $\mathbf{AA}^H = \mathbf{A}^H\mathbf{A} = \mathbf{I}$. However, if $x_m$ is not integer (but assuming the values of $x_m$ are all unique), does there exist a set of $k_n$ that could make the matrix $A_{mn}$ unitary? If it exists, how to find $k_n$?

Answer 1

A suitable set of $k_n$ does not necessarily exist; here's a counterexample for $N=3$. Take $$ x_0 = 0, \quad x_1 = \frac 13, \quad x_2 = 1. $$ The orthogonality of the first two columns gives us $$ 0 = \sum_{n=0}^2 e^{-i\frac{2\pi}{3} k_n(x_1 - x_0)} = \sum_{n=0}^2 e^{-i\frac{2\pi}{3} \frac 13 k_n} = \sum_{n=0}^2 e^{-i\frac{2\pi}9 k_n} $$ Adding in the result from the other two pairs gives us $$ 0 = \sum_{n=0}^2 e^{-i\frac{2\pi}9 k_n}= \sum_{n=0}^2 e^{-i\frac{4\pi}9 k_n}= \sum_{n=0}^2 e^{-i\frac{6\pi}9 k_n}. $$ Take $z_n = e^{-i\frac{2\pi}9 k_n}$; note that $|z_n| = 1$. The above equations can be rewritten as $$ 0 = z_0 + z_1 + z_2 = z_0^2 + z_1^2 + z_2 ^2 = z_0^3 + z_1^3 + z_2^3. $$ With Newton's identities, we can deduce that the unique solution to this system of equations is $z_0 = z_1 = z_2 = 0$. Our $z_n$ are non-zero, so there are no suitable $k_n$.

Answer 2

This is only a partial answer, but for the specific case $N = 2$ there do exist such couples $(k_0,k_1)$ for every $(x_0,x_1)$ with $x_0 \neq x_1$, and we can have them all:

In that case, since we already have $1$s on the diagonal and $AA^H$ is hermitian, it suffices to check that $(AA^H)_{0,1} = 0$ : $$(AA^H)_{0,1} = \sum_{s=0}^{2-1} e^{-i\frac{2\pi}{2}x_0k_s} \overline{e^{-i\frac{2\pi}{2}x_1k_s}} = e^{i\pi(x_1 - x_0)k_0} + e^{i\pi(x_1 - x_0)k_1}$$ As such: $$\begin{split}(AA^H)_{0,1} = 0 & \Leftrightarrow e^{i\pi(x_1 - x_0)k_0} + e^{i\pi(x_1 - x_0)k_1} = e^{i\pi(x_1-x_0)k_0}\left(1+e^{i\pi(x_1-x_0)(k_1-k_0)}\right) = 0\\ & \Leftrightarrow 1+e^{i\pi(x_1 - x_0)(k_1 - k_0)} = 0\\ & \Leftrightarrow \pi(x_1 - x_0)(k_1 - k_0) \equiv \pi \mod 2\pi\\ & \Leftrightarrow k_1 - k_0 \equiv \frac{1}{x_1 - x_0} \mod \frac{2}{x_1 - x_0}\end{split}$$

And that last condition can be satisfied for any choice of $k_0$, which gives us the existence of the couples $(k_0,k_1)$ as well as their full description.

However, like Ben Grossmann in the comments above is saying, it might get trickier, at least for $N \geq 4$:
you'll need the $N$ unknown variables $k_0,\dots,k_{N-1}$ to satisfy $\frac{N(N-1)}{2} > N$ (non-linear) equations, and so intuitively, by overdetermination of the system, there might not always exist solutions, though of course this remains to be proven.
($N = 3$ might still be feasible? but it's three equations with three unknowns and it's probably not going to be as easy as $N = 2$.)