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

Question

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.

Answer 1

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

Answer 2

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.

Answer 3

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