0
$\begingroup$

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.

  • 1
    This is the discrete Fourier transform matrix (https://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.2013-12-17

2 Answers 2

2

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.

  • 0
    Thank you all for the effort.2011-07-23
1

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.