# Problem in Matrix

Consider a matrix $U$ such that

$U = \left[\begin{array}{rrrrr} 1 & 1 & 1 &1&1\\ 1 &o & o^2 &o^3 & o^4\\ 1 & o^2 & o^4& o &o^3 \\ 1 & o^3 & o& o^4 & o^2\\ 1 & o^4 & o^3 &o^2 &o \\ \end{array}\right]$, where $1+o+o^2+o^3+o^4=0$.

Prove that if $(i,j)$ entry $u_{ij}$ of $U$ is same as $(k,l)$ entry $u_{kl}$ of $U$, for any power $U^n$ of $U$ $(i,j)$th entry and $(k,l)$th entry will be same.

-
Is this an exercise from a book, or something like that? – Mariano Suárez-Alvarez Jul 2 '11 at 2:24
Without doing the actual calculations (busy right now) - induction seems to be a good start. – M.B. Jul 2 '11 at 2:28
This is the discrete Fourier transform matrix (en.wikipedia.org/wiki/DFT_matrix) where each of your $o$'s are primitive roots of unity. Try searching for these keywords to get an idea of what's going on here. – Gareth Dec 17 '13 at 13:38

Hint #1: Clearly $o\neq1$ (assuming that $o$ is a complex number), but $$0=(1-o)(1+o+o^2+o^3+o^4)=1-o^5,$$ so...

Hint #2: Start computing the powers of $U$. Use the result of the previous hint. Read the comment by M.B.

-

The second power $U^2$ is 5 times a permutation matrix $P_{\pi}$, with the permutation specifically being, in one-line notation, $\pi = ( 1 \, 5 \, 4 \, 3 \, 2 )$. We know that the $ij$-entry of $U$ is $\sigma^{(i-1)(j-1)}$ by definition. You can make two small tables to check by brute force that $(i-1)(j-1) \equiv (k - 1)(l-1)$ implies $(\pi(i)-1) (\pi(j)-1) \equiv (\pi(k)-1)(\pi(l)-1)$ modulo 5. Hence if two entries of $U$ are equal, their exponents in $\sigma$ are equal, and therefore their exponents will be equal under any number of applications of $\pi$ to the indices.

-
Check your permutation, please. The top left entry of $U^2$ seems to be equal to 5. IOW $\pi(1)=1$. The correct permutation has a lower order, which helps here actually. – Jyrki Lahtonen Jul 2 '11 at 7:12
Like I said explicitly, I'm using one-line notation - not cycle notation. So according to what I've stated above, $\pi(1) = 1$, $\pi(2) = 5$, $\pi(3) = 4$, $\pi(4) = 3$, and $\pi(5) = 2$. See en.wikipedia.org/wiki/Permutation#Notation. Note that the order is actually irrelevant because if congruence is invariant under one application of $\pi$ then it is invariant under any number of applications. – anon Jul 2 '11 at 7:19
Ok. Sorry about the misunderstanding. I would use a list notation (with commas in-between), if I don't use the cycle notation. I think that without commas, the cycle notation is the default, so I do find your notation confusing. The Wikipedia-article says that on-line notation would be 15432, without the ()s. I guess we just saw the reason, why it is necessary to make the distinction with the cycle notation clearer :-). – Jyrki Lahtonen Jul 2 '11 at 8:17
I read one-line notation used as I use it somewhere or other years ago and it's been stuck in my brain ever since. My condolences to those who don't share my idiosyncrasy. – anon Jul 2 '11 at 8:50
Thank you all for the effort. – user12290 Jul 23 '11 at 15:06