1
$\begingroup$

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?

$\endgroup$
2
  • $\begingroup$ Is $p^p-1$ typo or on purpose? $\endgroup$
    – joro
    Sep 9, 2015 at 8:36
  • $\begingroup$ Since the index is considered as a solution in $\mathbf{F}_p$, we consider the $M$ as a modulo matrix over $\mathbb{Z}/(p^p-1)\mathbb{Z}$. $\endgroup$
    – Diane
    Sep 9, 2015 at 8:43

0

Your Answer

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