I have a question about the solution of Pell-equation over a prime field. I want prove that the matrix $M$ is of rank $\frac{p-1}{2}$, with $M=(m_{i,j})\in\left(\mathbb{Z}/(p^p-1)\mathbb{Z} \right)^{(p-1)\times(p-1)}$ defined as:
$$m_{i,j}=\left\{\begin{array}{ll} p^t+p^{-t},&\text{ if }i+j^2\theta\equiv t^2(\bmod p)\\ 0, & \text{ otherwise}\end{array}\right.$$ where $\theta$ is a quadratic non-residue of $\mathbb{F}_p$.
It is easy to verify that $M$ is of rank less than $\frac{p-1}{2}$, since $m_{i,j}=m_{i,p-j}=m_{p-i,j}=m_{p-i,p-j}$.
The point is how to prove that the rank of $M$ is exactly $\frac{p-1}{2}$.
If we consider the Pell equation $1+y^2\theta\equiv x^2(\bmod p)$, then we may figure out the first row of $M$. And the rest rows seem to be a rotation of the first row, and the values turn to be $p^{it}+p^{-it}$ from $p^{t}+p^{-t}$. It looks like a mixture of circulant-Vandermonde matrix.
Have anybody seen this kind of matrices before? Or any ideas to figure out the rank?
