# 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
@user12290: Many of us consider questions posted purely in the imperative ("Prove.." "Solve..." etc) to be rather impolite. You may want to edit the question, so that instead of it reading as if you are giving us an assignment, you (i) explain why you are considering this problem (self-study? Homework assignment? [in the latter case, please be sure to add the [homework] tag to the question), and (ii) What you have tried and where you are having trouble. Thank you. – Arturo Magidin Jul 2 '11 at 2:34
Adding my voice to Arturo's (beyond the +1) it seems unnatural-why do you care? The pattern of powers of $o$ is reminiscent of a Vandermonde matrix (but from both directions). Maybe en.wikipedia.org/wiki/Vandermonde_matrix will help – Ross Millikan Jul 2 '11 at 4:15
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