Matrices over Finite Prime Fields - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-19T01:32:42Z http://mathoverflow.net/feeds/question/115310 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/115310/matrices-over-finite-prime-fields Matrices over Finite Prime Fields zacarias 2012-12-03T16:24:08Z 2012-12-03T17:03:53Z <p>Let $p$ be an odd prime and $\mathbb Z_p$ be the prime field of order $p$. Consider the matrix ring $R=M_n(\mathbb Z_p)$. Is there any method to count the solutions of the equation (in the ring $R$)</p> <p>$$X^2=I.$$ Where $I$ is the identity matrix?</p> http://mathoverflow.net/questions/115310/matrices-over-finite-prime-fields/115314#115314 Answer by Jason Starr for Matrices over Finite Prime Fields Jason Starr 2012-12-03T16:55:11Z 2012-12-03T16:55:11Z <p>Because $p$ is different from $2$, the solutions are the same as direct sum decompositions <code>$\mathbb{Z}_p^{\oplus n} = E_{+1} \oplus E_{-1}$</code> as <code>$\mathbb{Z}_p$</code>-vector spaces. You can index these by the dimensions, say $r$ and $n-r$. For each, the number of solutions is <code>$$\frac{(p^n-1)(p^n-p) \cdot \dots \cdot (p^n-p^{r-1})}{(p^r-1)(p^r-p) \cdot \dots \cdot (p^r-p^{r-1})} \cdot p^{r(n-r)}$$</code> So the final answer is the sum over $r$ from $0$ to $n$ of this factor.</p> http://mathoverflow.net/questions/115310/matrices-over-finite-prime-fields/115315#115315 Answer by Denis Serre for Matrices over Finite Prime Fields Denis Serre 2012-12-03T17:01:36Z 2012-12-03T17:01:36Z <p>Denote $k:=Z_p$. If $p\ne2$, the matrix $X$ is in one-to-one correspondence with a decomposition $k^n=E_+ \oplus E_-$, where $E_\pm$ is the eigenspace associated with the eigenvalue $\pm1$.</p> <p>Given the dimension $m$ of $E_+$ ($n-m$ for $E_-$), these decompositions are in one-to-one correspondence with the bases of $k^n$, quotiented by the action of $GL_m\times GL_{n-m}$. Therefore, their number is $$\frac{|GL_n(Z_p)|}{|GL_m(Z_p)|\cdot|GL_{n-m}(Z_p)|}=p^{m(n-m)}\frac{(p-1)\cdots(p^n-1)}{(p-1)\cdots(p^m-1)(p-1)\cdots(p^{n-m}-1)}.$$ Summing up over all the possible $m$'s, the number of solutions to $X^2=I$ is $$\sum_{m=0}^np^{m(n-m)}\frac{(p^{m+1}-1)\cdots(p^n-1)}{(p-1)\cdots(p^{n-m}-1)}.$$</p> http://mathoverflow.net/questions/115310/matrices-over-finite-prime-fields/115316#115316 Answer by labirintas for Matrices over Finite Prime Fields labirintas 2012-12-03T17:03:53Z 2012-12-03T17:03:53Z <p>There are $\displaystyle \sum_{i=0}^n \frac{N(n)}{N(i)N(n-i)}$ solutions to your problem, where $N(r)$ is the number of elements in $GL_r(\mathbb{F}_p)$.</p> <p>Any such $X$ is invertible, and $X\in GL_n(\mathbb{F}_p)$ is a solution if and only if it is conjugate in $GL_n(\mathbb{F}_p)$ to a diagonal matrix with the first $i$ entries equal to $1$ and last $n-i$ entries equal to $-1$. This explains the number of summands. Now $g\in GL_n(\mathbb{F}_p)$ commutes with such diagonal matrix if and only if it preserves both eigenspaces. Hence, there are $\frac{N(n)}{N(i)N(n-i)}$ elements in the conjugacy class. </p> <p>The formula can be made even more explicit by substituting a formula for $N(r)$.</p>