# Which permutation matrix is this diagonal matrix similar to?

I was trying to solve this question from GATE exam 2015.

Q 4) Two sequences $$[a,b,c]$$ and $$[A,B,C]$$ are related as, $$\left [ \begin{matrix}A \\B \\C \\\end{matrix} \right ] = \left [ \begin{matrix}1 & 1 & 1 \\1 & W_3^{-1} & W_3^{-2} \\1 & W_3^{-2} & W_3^{-4}\\\end{matrix} \right ] \left [ \begin{matrix}a \\b \\c \\\end{matrix} \right ] \ \ \ \ \ \ \ \ \ \ \ (1)$$ Where $$W_3 = e^{j\frac{2\pi}{3}}$$. If another sequence $$[p,q,r]$$ is derived as, $$\left [ \begin{matrix}p \\q \\r \\\end{matrix} \right ] = \left [ \begin{matrix}1 & 1 & 1 \\1 & W_3^{1} & W_3^{2} \\1 & W_3^{2} & W_3^{4}\\\end{matrix} \right ] \left [ \begin{matrix}1 & 0 & 0 \\0 & W_3^{2} & 0 \\0 & 0 & W_3^{4}\\\end{matrix} \right ] \left [ \begin{matrix}\frac{A}{3} \\\frac{B}{3} \\\frac{C}{3} \\\end{matrix} \right ] \ \ \ \ \ \ \ \ \ \ \ (2)$$

The the relationship between the sequences $$[p,q,r]$$ and $$[a,b,c]$$ is,

(a) $$[p,q,r] = [b,a,c]$$ (b) $$[p,q,r] = [b,c,a]$$ (c) $$[p,q,r] = [c,a,b]$$ (d) $$[p,q,r] = [c,b,a]$$

I think the answer is (b), the official answer key says it is (c). (page 19 of the pdf) Can you find the mistake in my solution or confirm that I am right?

## My solution

First we notice $$W_3$$ is the 3rd root of unity. Next if we take $$\frac{1}{3}$$ out of the vector on the right of (2) we can substitute (1) into (2). $$\left [ \begin{matrix}p \\q \\r \\\end{matrix} \right ] = \left [ \begin{matrix}1 & 1 & 1 \\1 & W_3^{1} & W_3^{2} \\1 & W_3^{2} & W_3^{4}\\\end{matrix} \right ] \left [ \begin{matrix}\frac{1}{3} & 0 & 0 \\0 & \frac{W_3^{2} }{3}& 0 \\0 & 0 & \frac{W_3^{4}}{3}\\\end{matrix} \right ] \left [ \begin{matrix}1 & 1 & 1 \\1 & W_3^{-1} & W_3^{-2} \\1 & W_3^{-2} & W_3^{-4}\\\end{matrix} \right ] \left [ \begin{matrix}a \\b \\c \\\end{matrix} \right ] \ \ \ \ \ \ \ \ \ \ \ (3)$$ At this point it should be clear that what we are seeing is a similarity transform on a diagonal matrix, which would turn it into a permutation matrix (based on the options). Since its a diagonalisation we can see how the eigenvector matrix used to diagonalize the permutation matrix is actually the 3 point DFT matrix. Since this matrix is unitary, the inverse is just the conjugate transpose. So now we know the eigenvalues of that permutation matrix are the diagonal elements and the eigenvectors are the column vectors. $$\left [ \begin{matrix}p \\q \\r \\\end{matrix} \right ] = \frac{1}{\sqrt{3}}\left [ \begin{matrix}1 & 1 & 1 \\1 & \omega^{-1} & \omega ^{-2} \\1 & \omega ^{-2} & \omega ^{-4}\\\end{matrix} \right ] \left [ \begin{matrix}1 & 0 & 0 \\0 & \omega ^{-2} & 0 \\0 & 0 & \omega ^{-4}\\\end{matrix} \right ] \frac{1}{\sqrt{3}} \left [ \begin{matrix}1 & 1 & 1 \\1 & \omega & \omega ^{2} \\1 & \omega ^{2} & \omega ^{4}\\\end{matrix} \right ] \left [ \begin{matrix}a \\b \\c \\\end{matrix} \right ] \ \ \ \ \ \ \ \ \ \ \ (3)$$

Now we can use the fact that the roots of unity are n-periodic. $$\omega^{-5}, \omega ^{-4}, \omega^{-3}, \omega ^{-2}, \omega^{-1}, \omega ^{0}, \omega^{1}, \omega ^{2}, \omega^{3}, \omega ^{4}, \omega^{5}, \omega ^{6}$$ Since we are dealing with the 3rd root of unity the above sequence is the same as, $$\omega^{1}, \omega ^{2}, 1, \omega ^{1}, \omega^{2}, 1, \omega, \omega ^{2}, 1, \omega, \omega^{2}, 1$$ Now the crucial observation is that $$\omega^{-2}$$ or $$\omega$$ is the eigenvalue for the 2nd column in the eigenvector matrix. So multiplying the second column with $$\omega$$ is the same as applying that permutation matrix $$P_\pi$$. $$P_\pi \left [ \begin{matrix} 1 \\ \omega \\ \omega ^{2}\\\end{matrix} \right ] = \omega \left [ \begin{matrix} 1 \\ \omega \\ \omega ^{2}\\\end{matrix} \right ] = \left [ \begin{matrix}\omega \\ \omega^{2} \\ 1 \\\end{matrix} \right ]$$ We can say the same for the 3rd eigenvector too. $$P_\pi \left [ \begin{matrix} 1 \\\omega ^{2} \\ \omega ^{4}\\\end{matrix} \right ] = \omega^2 \left [ \begin{matrix} 1 \\\omega ^{2} \\ \omega ^{4}\\\end{matrix} \right ] = \left [ \begin{matrix}\omega ^{2} \\ \omega \\ 1 \\\end{matrix} \right ]$$ So we can conclude the permutation matrix is,

$$P_\pi = \left [ \begin{matrix}0 & 1 & 0 \\0 & 0 & 1 \\1 & 0 & 0 \\\end{matrix} \right ]$$ So the answer is (b) $$[p,q,r] = [b,c,a]$$. I write so much for the sake of clarity. If you want to solve this quickly we can just quickly check what the eigenvalue $$W_3^{2} = W_3^{2} W_3^{-3} = W_3^{-1}$$ does to the second eigenvector. $$P_\pi \left [ \begin{matrix} 1 \\W_3^{-1}\\W_3^{-2}\\\end{matrix} \right ] = W_3^{-1} \left [ \begin{matrix} 1 \\W_3^{-1}\\W_3^{-2}\\\end{matrix} \right ] = \left [ \begin{matrix} W_3^{-1} \\W_3^{-2}\\1\\\end{matrix} \right ]$$ So we immediately see how the second element becomes the first, 3rd becomes 2nd and 1st becomes last.

We can confirm the answer is indeed (c) by multiplying the 3 matrices in equation (3). We will need to use the fact that the sum of the roots of unity is zero.

$$\left [ \begin{matrix}p \\q \\r \\\end{matrix} \right ] = \frac{1}{\sqrt{3}}\left [ \begin{matrix}1 & 1 & 1 \\1 & \omega & \omega ^{2} \\1 & \omega ^{2} & \omega ^{4}\\\end{matrix} \right ] \left [ \begin{matrix}1 & 0 & 0 \\0 & \omega ^{2} & 0 \\0 & 0 & \omega ^{4}\\\end{matrix} \right ] \frac{1}{\sqrt{3}} \left [ \begin{matrix}1 & 1 & 1 \\1 & \omega^{-1} & \omega ^{-2} \\1 & \omega ^{-2} & \omega ^{-4}\\\end{matrix} \right ]\left [ \begin{matrix}a \\b \\c \\\end{matrix} \right ]$$

The diagonal elements scale the rows when you right multiply,

$$\left [ \begin{matrix}p \\q \\r \\\end{matrix} \right ] = \frac{1}{3}\left [ \begin{matrix}1 & 1 & 1 \\1 & \omega & \omega ^{2} \\1 & \omega ^{2} & \omega ^{4}\\\end{matrix} \right ] \left [ \begin{matrix}1 & 1 & 1 \\ \omega ^{2} & \omega ^{1} & \omega ^{0}\\ \omega ^{4} & \omega ^{2} & \omega ^{0}\\\end{matrix} \right ] \left [ \begin{matrix}a \\b \\c \\\end{matrix} \right ]$$

$$\left [ \begin{matrix}p \\q \\r \\\end{matrix} \right ] = \frac{1}{3}\left [ \begin{matrix}1+\omega^{2} +\omega^{4} & 1+\omega+\omega^{2} & 3 \\1+\omega^{3}+\omega^{6} & 1+\omega^{2}+\omega^{4} & 1+\omega+\omega^{2} \\ 1+\omega^{4}+\omega^{8} & 1+\omega^{3}+\omega^{6} & 1+\omega^{2}+\omega^{4} \end{matrix} \right ] \left [ \begin{matrix}a \\b \\c \\\end{matrix} \right ]$$

$$\left [ \begin{matrix}p \\q \\r \\\end{matrix} \right ] = \frac{1}{3}\left [ \begin{matrix}1+\omega^{2} +\omega & 1+\omega+\omega^{2} & 3 \\3 & 1+\omega^{2}+\omega & 1+\omega+\omega^{2} \\ 1+\omega+\omega^{2} & 3 & 1+\omega^{2}+\omega \end{matrix} \right ] \left [ \begin{matrix}a \\b \\c \\\end{matrix} \right ]$$

Since we know $$1,\omega,\omega^2$$ are 3 roots of unity, their sum is zero.

$$\left [ \begin{matrix}p \\q \\r \\\end{matrix} \right ] = \left [ \begin{matrix} 0 & 0 & 1 \\ 1 & 0 & 0 \\ 0 & 1 & 0 \end{matrix} \right ] \left [ \begin{matrix}a \\b \\c \\\end{matrix} \right ] = \left [ \begin{matrix}c \\a \\b \\\end{matrix} \right ]$$

Your answer was wrong because you took the wrong matrix as the eigenvector matrix. The first matrix on the left is the eigen vector matrix. When you diagonalize a matrix then the matrix is on the right.

$$P_\pi = W\Lambda W^{-1}$$

$$P_\pi W = W\Lambda$$

$$\Lambda = W^{-1}P_\pi W$$