7
$\begingroup$

For a prime p, consider the $(p-1) \times (p-1)$ matrix A with entry to be $A_{ij}=(i \times j) mod$ $p$. every row (column) is permutation of 1 to p-1, such a permutation is useful in one version of proof of Fermat's little theorem. Here the question is if the largest eigenvalue is always p(p-1)/2. also anything happens for the rank of it. except for p=2,3, the rank might always be p-2.

the student taking a course (general intro to math) I am TAing asked me it. but it is embarrassing to say I don't know how to work it out. I know almost zero about primes and I believe this might be a standard result. I am grateful if anyone suggests a hint or any reference.

$\endgroup$
4
  • 13
    $\begingroup$ By the Perron Frobenius theorem, there is a unique eigenvector with all positive entries for any matrix with positive entries. The corresponding eigenvalue dominates all the others. In this case, the eigenvector is the vector of 1's (and has eigenvalue $p(p-1)/2$. $\endgroup$ Mar 22, 2012 at 6:05
  • 2
    $\begingroup$ en.wikipedia.org/wiki/Perron%E2%80%93Frobenius_theorem $\endgroup$
    – zeb
    Mar 22, 2012 at 6:08
  • $\begingroup$ Thank both of you for the help! still not sure if the rank is also always p-2 for $p \geq 5$ Maybe I will run some numeric test. $\endgroup$
    – Bo_Y
    Mar 22, 2012 at 17:49
  • $\begingroup$ The fact that the largest possible modulus of an eigenvalue is $p(p-1)/2$ also follows from Gershgorin's theorem: en.wikipedia.org/wiki/Gershgorin_circle_theorem $\endgroup$ Mar 23, 2012 at 0:57

3 Answers 3

7
$\begingroup$

I still don't know about the rank, but here's a step that might let you make some progress on it.

Since $\mathbb Z_p^*$ is the multiplicative subgroup of a finite field, it's known to be cyclic, so that there is an $a$ such that $1=a^0,a,a^2,\ldots,a^{p-2}$ exhaust the subgroup ($a^{p-1}$ being 1 again).

Rearrange the rows and columns of the matrix so that the $i$th row of the matrix corresponds to $a^{i-1}$ and the $j$th row of the matrix corresponds to $a^{j-1}$. This is just conjugation of the original matrix by the permutation matrix arising from the permutation $1\to 1$, $2\to a$, $3\to a^2$ etc and so has the same rank. Let this matrix be $B$.

Once you've done this, the matrix $B$ has entries (labelling from 0 to $p-2$ for simplicity) $b_{ij}=a^{i+j}\bmod p$. In particular, $B$ is a circulant matrix. For any generator, we have $a^{(p-1)/2}=-1\bmod p$, which implies (essentially as noted by Gerry Myerson) that the sum of the first half of each row and the second half of each row is the vector of all $p$'s. This guarantees (as before) that the rank is at most $1+(p-1)/2=(p+1)/2$.

However, the fact that $B$ is circulant means that its eigenvalues are known and easily expressed in terms of the elements of the first row. Finding the rank amounts to checking for how many $k$'s, the quantity $$ \sum_{j=0}^{p-2}(a^j\bmod p)\exp\left(\frac{2\pi ijk}{p-1}\right) $$ is non-zero. Notice that if $k$ is even and non-zero, then the sum vanishes: if you write the row as the sum of the vector whose entries are all $p/2$ and a vector $u$, then the asymmetry mentioned above in $u$ implies that the sum vanishes with $u$, as it does for the constant vector. So the rank of the matrix is $(p+1)/2$ if and only if the sum is non-zero for all odd $k < p$.

$\endgroup$
3
  • $\begingroup$ Observation: If $p \equiv 3 \mod 4$ and $k = (p-1)/2$, then this sum is $\sum_{b=0}^{p-1} b \left( \frac{b}{p} \right)$, which is positive by the class number formula. Any chance that there is a generalization of the class number formula which deals with the general case? $\endgroup$ Mar 26, 2012 at 18:48
  • $\begingroup$ That's cool. I had observed that the sum appeared to be non-zero in this case, but didn't know how to prove it. It now follows that if $(p-1)/2$ and $p$ are a Sophie Germain prime pair, then the rank is $(p+1)/2$. $\endgroup$ Mar 26, 2012 at 19:19
  • $\begingroup$ sorry have not been on for a while, surprised to see that you two developed the problem to a new level, I will try to learn it! Many thanks! $\endgroup$
    – Bo_Y
    May 11, 2012 at 21:37
9
$\begingroup$

Anthony Quas shows that your matrix has rank $(p+1)/2$ if and only if the sum $$\sum_{j=0}^{p-2} (a^j \bmod p) \beta^{jk}$$ is nonzero for all odd $k$. Here $a$ is a primitive root of unity modulo $p$ and $\beta$ is a primitive $(p-1)$-th root of unity.

Take a look at Section 6.5 of Edward's book Fermat's Last Theorem. He establishes the formula (equation 8) $$L(1, \chi) = \frac{ i \pi m_k}{p} \sum_{j=0}^{p-2} (a^j \bmod p) \beta^{jk}$$ where $k$ is odd, $\chi$ is the character $a^j \mapsto \beta^{jk}$ from $\mathbb{F}_p^{\times}$ to $\mathbb{C}^{\times}$ and $m_k = \frac{1}{p} \sum_{j=0}^{p-2} \beta^{jk} \zeta^{a^j}$, for $\zeta$ a primitive $p$-th root of unity. (Warning: I have tried to change Edward's notation to match Quas's. In particular, Edwards uses $k$ and $j$ to mean the exact opposite of what Quas does! Hope I haven't introduced any errors.)

The key point is that $L(1,\chi)$ is known to be nonzero! So the result on the rank of your matrix is true, and for quite a nontrivial reason.

$\endgroup$
1
  • $\begingroup$ Wow! That's quite wonderful... $\endgroup$ Mar 26, 2012 at 20:32
2
$\begingroup$

When $p=7$ the rank is 4, which is not $p-2$.

If you add row $i$ to row $p-i$ you get a row in which every entry is $p$. This means the rank can't be any bigger than $(p+1)/2$. My guess is that for $p\ne2$ the rank will be $(p+1)/2$, but I haven't thought through a proof, nor have I done any calculations beyond $p=7$.

$\endgroup$
1
  • $\begingroup$ FWIW, my computer reports that the rank is (p+1)/2 for all primes up to 53. It could be run a lot further but there is no point. $\endgroup$ Mar 23, 2012 at 1:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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