Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question
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 ( 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.

share|cite|improve this answer

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.

share|cite|improve this answer
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 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

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.