# the largest eigenvalue of the matrix A with A_{ij}=(i \times j) mod p for p is a prime.

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.

• 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$. – Anthony Quas Mar 22 '12 at 6:05
• en.wikipedia.org/wiki/Perron%E2%80%93Frobenius_theorem – zeb Mar 22 '12 at 6:08
• 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. – Bo_Y Mar 22 '12 at 17:49
• 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 – Greg Martin Mar 23 '12 at 0:57

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$.

• 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? – David E Speyer Mar 26 '12 at 18:48
• 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$. – Anthony Quas Mar 26 '12 at 19:19
• 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! – Bo_Y May 11 '12 at 21:37

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.

• Wow! That's quite wonderful... – Anthony Quas Mar 26 '12 at 20:32

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$.

• 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. – Felipe Voloch Mar 23 '12 at 1:46