When is the Fourier transform of a periodic discrete signal $\mathcal{F}x[k]$ the same as $x[k]$ up to a diagonal matrix

Question

I am looking for all pairs $(x[n],q)$ where $x[n]$ is a periodic discrete signal with period $N$ and $q$ is a rational number satisfying the following identity: $$\mathcal{F}x[k]=e^{i(q-\frac{\pi k}{N})}x[k]$$ where $k=0,1,\cdots, N-1$.

Answer 1

Let $\newcommand{\F}{\mathbf{F}_{{}_N}} \F$ be the (unitary) DFT-Matrix of size $N$. Let $\newcommand{\x}{\mathbf x}\x$ be the vector $\x=(x[0],\ldots x[N-1])$. Your equation says:

\begin{align}\DeclareMathOperator{\diag}{diag}\newcommand{\tildF}{\tilde{\mathbf{F}}_{{}_N}}\newcommand{\D}{\mathbf D_{{}_N}} \F \x &= \diag\left(e^{i\left(q-\frac{\pi k}N\right)}\right)_{k=0,\ldots,N-1} \x\\ &=e^{iq}\diag\left(e^{-i\frac{\pi k}N}\right)_{k=0,\ldots,N-1}\x\\ \F\underbrace{\diag\left(e^{i\frac{\pi k}N}\right)_{k=0,\ldots,N-1}}_{=:\D}\x&=e^{iq}\x\\ \underbrace{\F\D}_{=:\tildF}\,\x&=e^{iq}\x\\ \tag{1}\label{evprob} \tildF\x&=e^{iq}\x \end{align} so you're looking for eigenvalues and eigenvectors of $\tildF$ (it's a given that all EV take the shape $e^{ir},r\in\mathbb R$, since $\|\tildF\|\equiv1$)!

Since that involves a DFT matrix, it's not trivial, but

B. Dickinson and K. Steiglitz, "Eigenvectors and functions of the discrete Fourier transform," in IEEE Transactions on Acoustics, Speech, and Signal Processing, vol. 30, no. 1, pp. 25-31, February 1982, doi: 10.1109/TASSP.1982.1163843. Link.

shows us an approach.

Note that if I'm not mistaken, then $\F\D$ is a kind of a cyclic shift of $\F$, so that the eigenvalues might simply be the same.

Answer 2

tl;dnr version: No nonzero vector can satisfy the requirement stated in the body of this question.

The rest of this answer is a long-winded proof of the assertion above.

The Discrete Fourier Transform of the column vector $\mathbf x = \big[x[0], x[1], \ldots, x[N-1]\big]^T$ is defined as the column vector $\mathbf X = \big[X[0], X[1], \ldots, X[N-1]\big]^T$ where $$X[k] = \sum_{n=0}^{N-1} x[n]\exp\left(-j\frac{2\pi kn}N\right).\tag{1}$$ Thus, $\mathbf X = \mathbf{Fx}$ where $\mathbf F$ is the $N\times N$ DFT matrix (with rows and columns numbered from $0$ to $N-1$) with entries given by $\mathbf F_{k,n}=\exp\left(-j\frac{2\pi kn}N\right)$. It is well-known that $\mathbf F$ is a symmetric matrix and enjoys the property that for $1 \leq k \leq N-1$, the $k$-th row of $\mathbf F$ is the complex conjugate of the $(N-k)$-th row. Furthermore, the inverse of $\mathbf F$ is $N^{-1}\mathbf F^*$ where $\mathbf F^*$ is the $N\times N$ matrix with entries $\mathbf F^*_{k,n}=\exp\left(j\frac{2\pi kn}N\right) = \left(\mathbf F_{k,n}\right)^*$. Thus, the set of rows of $\mathbf F^*$ is the same as the set of rows of $\mathbf F$, but the rows occur in reverse order from Row $1$ through Row $N-1$ in the two matrices. All this is a verbose way of saying that $$x[k] = \frac 1N\sum_{n=0}^{N-1} X[n]\exp\left(j\frac{2\pi kn}N\right)\tag{2}$$ or $\mathbf x$ is the inverse DFT of $\mathbf X$. Finally, note that the $(k,n)$-th element of $\mathbf F^2$ is \begin{align} \mathbf F_{k,n}^2 &= \sum_{m=0}^{N-1}\mathbf F_{k,m}\mathbf F_{m,n}\\ &= \sum_{m=0}^{N-1}\exp\left(-j\frac{2\pi km}N\right)\exp\left(-j\frac{2\pi mn}N\right)\\ &= \sum_{m=0}^{N-1}\exp\left(-j\frac{2\pi m(n+k)}N\right)\\ &= \begin{cases}N, & n+k \equiv 0\bmod N, \\ 0, &\text{otherwise.}\end{cases} \end{align} Thus, $$\mathbf F_{0,0}^2= \mathbf F_{1,N-1}^2= z\mathbf F_{2,N-2}^2 = \cdots = \mathbf F_{N-1,1}^2 = N \tag{3}$$ and all other entries in $\mathbf F^2$ are $0$.

---

The query in the title of this question asks "When does $\mathbf X$ equal $\operatorname{diag}[d_0, d_1, \ldots, d_{N-1}]\mathbf x$?" has the trivial answer "Whenever no entry of $\mathbf x$ is $0$."; all we need to do is set $d_k = \dfrac{X[k]}{(x[k])}$ for $0 \leq k \leq N-1$ where we know the the fraction is properly defined since we are guaranteed that $x[k]\neq 0$ for any $k$.

The query in the body of this question is considerably more restricted and possibly has no solution at all. It asks "When does $X[k]$ equal $\exp\left(j \left(q - \frac{\pi k}N\right)\right)x[k]$ for all $k$, $0 \leq k \leq N-1$, where $q$ is some fixed rational number?" Equivalently, we want to find all $\mathbf x$ such that \begin{align} \mathbf X &= \exp(-jq) \operatorname{diag}\left[1, \exp\left(-j\frac{2\pi}N\right), \exp\left(-j\frac{2\pi 2}N\right), \cdots, \exp\left(-j\frac{2\pi(N-1)}N\right)\right]\mathbf x \tag{3}\\ \mathbf X &= \exp(-jq)\hat{\mathbf x} \tag{4} \end{align} where $\hat{\mathbf x}$ is the vector with $n$-th element $\displaystyle\hat{x}[n] = \exp\left(-j\frac{2\pi n}N\right) x[n]$.

For an arbitrary vector $\mathbf x$ (that is, not necessarily a solution to $(3)$ or $(4)$), what is the DFT $\hat{\mathbf X}$ of $\hat{\mathbf x}$? Well, from $(1)$, we have that \begin{align} \hat{X}[k] &= \sum_{n=0}^{N-1} \hat{x}[n]\exp\left(-j\frac{2\pi kn}N\right)\\ &= \sum_{n=0}^{N-1} \exp\left(-j\frac{2\pi n}N\right){x}[n]\exp\left(-j\frac{2\pi kn}N\right)\\ &= \sum_{n=0}^{N-1} {x}[n]\exp\left(-j\frac{2\pi (k+1)n}N\right)\\ &= X[k+1 \bmod N]. \end{align} Thus, $$\hat{\mathbf X} = \big[\hat X[0], \hat X[1], \ldots, \hat X[N-1]\big]^T = \big[X[1], X[2], \ldots, X[N-1], X[0]\big]^T$$ which is the cyclic shift referred to in Marcus Müller's answer.

And now, let us resume the assumption that $\mathbf x$ is an alleged solution to $(3)$ and $(4)$. Remembering that $\exp(-jq)$ is a scalar, we have that \begin{align} \mathbf X &= \exp(-jq)\hat{\mathbf x}\\ \mathbf{Fx}&= \exp(-jq)\hat{\mathbf x}\\ \mathbf{F}^2\mathbf x &= \exp(-jq)\mathbf{F}\hat{\mathbf x}\\ \mathbf{F}^2\mathbf x &= \exp(-jq)\hat{\mathbf X}. \end{align} But, $$\mathbf{F}^2\mathbf x = N\big[x[0], x[N-1], x[N-2], \cdots , x[1]\big]^T\tag{5}$$ while \begin{align}\exp(-jq)\hat{\mathbf X} &= \exp(-jq)\big[\hat X[0], \hat X[1], \ldots, \hat X[N-1]\big]^T\\ &= \exp(-jq)\big[X[1], X[2], \ldots, X[N-1], X[0]\big]^T. \tag{6} \end{align} Two takeaways from the fact that the vectors on the right sides of Eqs. $(5)$ and $(6)$ are equal are \begin{align}x[0]&= N^{-1}\exp(-jq)X[1]\tag{7}\\x[1] &= N^{-1}\exp(-jq)X[0]\tag{8}. \end{align} On the other hand, Eqs. $(3)$ and $(4)$ assure us that \begin{align}x[0]&=\exp(jq)X[0]\tag{9}\\x[1] &= \exp(jq)\exp\left(j\frac{\pi}{N}\right)X[1]\tag{10}. \end{align} Now, Eqs. $(7)$and $(9)$ tell us that $$X[1] = N\exp(2jq)X[0]\tag{11}$$ while Eqs. $(8)$and $(10)$ lead to $$X[1] = \frac 1N \exp(-2jq)\exp\left(-j\frac{\pi}{N}\right)X[0]\tag{12}$$ which are contradictory results unless $X[0]=X[1]=0$. Similar arguments can be used to express $X[k+1]$ in terms of $X[k]$ in contradictory ways, leading to the conclusion that the only $\mathbf x$ that can satisfy $(3)$ and $(4)$ is $\mathbf 0$.

The conclusion is that no nonzero vector $\mathbf x$ can satisfy the desired requirement $(3)$.