Ask Your Question
1

general linear group finite field

asked 2017-03-02 11:56:23 -0500

chebolu gravatar image

updated 2017-03-02 12:31:31 -0500

kcrisman gravatar image

I am trying to compute the number of 3 x 3 matrices A over the field of p elements (p prime) such that A^2 = I. I wrote the following code which gives me the answers for p=2 and p=3, but it is taking for ever to compute when for p=5. Is there a better way to do this job which can speed up the computations? Many thanks for help.


def num_invol(n):
    G = GL(n,GF(3));
    sum = 0
    for A in G:
        if A^2 == G.one():
                sum = sum +1
    return sum

for p in (2..11):
    if p.is_prime():
        print (p, num_invol(p))
edit retag flag offensive close merge delete

2 answers

Sort by » oldest newest most voted
0

answered 2017-03-13 20:00:25 -0500

dan_fulea gravatar image

updated 2017-03-13 20:18:06 -0500

After the first read of the post, my impression was also, that the next case concerns $GL_n(\mathbb F_3)$, and i gave up for a while. The case of finding the elements $A$ with $A^2=1$ in $$ G = GL_3(\mathbb F_q)\ , $$ $q$ being and odd prime power, can be restated and solved theoretically. After doing this, the general case can also be solved by the same lines. (Odd characteristic.)

Let us consider such an $A\in G$, a $3\times 3$ matrix for the beginning.

Since $-A\in G$ we can chose now or later the class we want to count. (The $\det:G\to \mathbb{F}_q^\times$ with the image $\pm 1$ separates the cases. This is because our $n=3$ is odd.)

The characteristic polynomial $P$ of $A$ has three non-zero roots.

The minimal polynomial is $X^2-1$ or a divizor, i.e. one among $X\pm1$, (since $A^2=1$).

In case of three equal eigenvalues, we can consider the case with $1,1,1$ being the three ones. Then $P=(X-1)(X-1)(X-1)$. Subtracting from this $(X^2-1)(X-1)$ we see that $2(X-1)(X-1)$ also anihilates $A$. But $2$ is not zero, since $q$ was odd. So $(X-1)(X-1)$ anihilates $A$. Using again $X^2-1=(X-1)(X+1)$, we see that $2(X-1)$ anihilates $A$. So $X-1$ does it, so $A=1$. (This is too pedestrian, but shows where the odd characteristic is needed. In characteristic two, all standard Jordan blocks are idempotents. The solution in this case would be to also consider conjugations of such block compositions. In odd characteristic we have a diagonal shape and less problems.)

The case with $-1,-1,-1$ reduces to the above one, by passing from $A$ to $-A$, so we get $A=-1$.

Let us consier all other cases. Then the eigenvalues of $A$ are the two divisors $\pm1$ of $X^2-1$ and a further value $a$, say. The set of eigenvalues $1,-1,a$ is stable with respect to $x\to1/x$. So $a$ is either $-1$ or $+1$. In both cases we will restrict to the half of the $A$'s by imposing the condition, that the eigenvalues are $$ -1,1,1\ . $$ Since the minimal polynomial $X^2-1=(X+1)(X-1)$ splits in two distinct factors, odd characteristic again, we have a diagonalizable matrix $A$, so there exists an invertible matrix $S$ so that we can write: $$ A = S^{-1}DS\ , $$ $D$ being the diagonal matrix with entries $-1,1,1$. We let $S$ run in the space of all invertible matrices. When do we have the same writing $$ T^{-1} D T = A = S^{-1} D S\ , $$ for $S,T$ invertible? This means that $ST^{-1}$ commutes with $D$, so it is of the shape / is in the $G$--subgroup of matrices

* 0 0
0 * *
0 * *

which has $$ (q-1)\cdot(q^2-1)(q^2-q)=F(q,1)\cdot F(q,2) $$ elements, where $F(q,n)$ is the product over $k$ with $0 \le k < n$ from the factors $q^n-q^k$. $F$ is here inspired from the word factorial.

We may use the convention, that an empty product is one, so $F(q,0)=1$.

So $S,T$ are generating by conjugation as above the same $A$, iff they are in the right classes w.r.t. the above subgroup. (The right classes to be considered are maybe the left sided ones.)

So we expect a number of $A$'a equal to $$ 2 + 2\frac {F(q,3)}{F(q,1)F(q,2)} =2 +2p^2(p²+p+1)\ . $$ And indeed:

def F(q,n):
    return prod( [ q^n - q^k for k in [ 0 .. n-1 ] ] )    # with no checks

for p in [ 3,5 ]:
    print "%s -> %s" % ( p, 2 + 2*F(p,3) / F(p,1) / F(p,2) )

print "... or simply"

for p in [ 3,5 ]:
    print "%s -> %s" % ( p, 2 + 2 * p^2 * (p^2+p+1) )

And we get:

3 -> 236
5 -> 1552
... or simply
3 -> 236
5 -> 1552

For a general $n$ we have to implement over the field with (odd) $q$ elements the following lines, some $q$--combinatorial / factorial formula: $$ \sum_{0\le s, t\le n\ ,\ s+t=n} \frac{F(q,n)}{F(q,s)F(q,t)} =2+ \sum_{0< s, t< n\ ,\ s+t=n} \frac{F(q,n)}{F(q,s)F(q,t)} \ . $$ For four, $n=4$, just an example, the terms in the sum correspond to diagonal matrices $D$ with diagonal $(-1,-1,-1,-1)$, and $(-1,-1,-1,1)$ and $(-1,-1,1,1)$ and $(-1,1,1,1)$ and $(1,1,1,1)$, and the corresponding cosets have to be taken with respect to diagonal block matrices for the splittings $4=4+0=3+1=2+2=1+3=0+4$, correspondingly

****    *000    **00    ***0    ****
****    0***    **00    ***0    ****
****    0***    00**    ***0    ****
****    0***    00**    000*    ****

and it is also possible to construct the matrices $A$ after constructing coset representatives.

edit flag offensive delete link more
0

answered 2017-03-05 12:40:21 -0500

tmonteil gravatar image

updated 2017-03-06 07:29:59 -0500

First, what num_invol(n) computes is the number of matrices M of size n x n on GF(3) such that M^2=1, not the number of matrices M of size 3 x 3 on GF(n) such that M^2=1, so, you should instead write:

def num_invol(p):
    G = GL(3,GF(p));
    sum = 0
    for A in G:
        if A^2 == G.one():
            sum = sum +1
    return sum

So, you can get:

sage: num_invol(3)
236
sage: num_invol(5) # takes about 10 minutes
1552

For larger p, since the space to scan becomes too large, we could try to describe the set of solutions algebraically as follows. We define an unknown matrix whose entries are polynomial indeterminates:

sage: p = 5 ; K = GF(p) ; K
Finite Field of size 5
sage: R = PolynomialRing(K,'x',9) ; R
Multivariate Polynomial Ring in x0, x1, x2, x3, x4, x5, x6, x7, x8 over Finite Field of size 5
sage: M = matrix(R,3,3,R.gens()) ; M
[x0 x1 x2]
[x3 x4 x5]
[x6 x7 x8]

Then, your problem is reduced to a system of polynomial (quadratic) equations:

sage: E = (M^2 - M.parent().one()).list() ; E
[x0^2 + x1*x3 + x2*x6 - 1,
 x0*x1 + x1*x4 + x2*x7,
 x0*x2 + x1*x5 + x2*x8,
 x0*x3 + x3*x4 + x5*x6,
 x1*x3 + x4^2 + x5*x7 - 1,
 x2*x3 + x4*x5 + x5*x8,
 x0*x6 + x3*x7 + x6*x8,
 x1*x6 + x4*x7 + x7*x8,
 x2*x6 + x5*x7 + x8^2 - 1]

So, your goal reduces to evaluating the cardinal of the variety of the associated ideal:

sage: I = R.ideal(E) ; I
Ideal (x0^2 + x1*x3 + x2*x6 - 1, x0*x1 + x1*x4 + x2*x7, x0*x2 + x1*x5 + x2*x8, x0*x3 + x3*x4 + x5*x6, x1*x3 + x4^2 + x5*x7 - 1, x2*x3 + x4*x5 + x5*x8, x0*x6 + x3*x7 + x6*x8, x1*x6 + x4*x7 + x7*x8, x2*x6 + x5*x7 + x8^2 - 1) of Multivariate Polynomial Ring in x0, x1, x2, x3, x4, x5, x6, x7, x8 over Finite Field of size 5
sage: I.variety()
ValueError: The dimension of the ideal is 4, but it should be 0

Indeed, Sage is only able to describe the variety of an ideal only when the dimension of the ideal is 0, but:

sage: I.dimension()
4

We can do as follows:

sage: Aff = AffineSpace(K,9)
sage: S = Aff.subscheme(I)
sage: S.count_points(1)[0]

It leads to the same result as the naive method for p=3 with basically the same computation time (slightly slower), while there are almost 2 times more cases to test, since your method restricts the search to invertivble matrices (there are 19683 3x3 matrices on GF(3) and 11232 are invertible, but the ratio should reduce when p increases). Actually, this methods finally rely on enum_affine_finite_field, whose source code can be read as:

sage: from sage.schemes.affine.affine_rational_point import enum_affine_finite_field
sage: enum_affine_finite_field??

As you can see it is basically a loop over all possible 9-uples (silimar to yours).

Perhaps could the knowledge of a Groebner basis for the ideal allow us to find a parametrization of the solution space so that we can iterate on it from the inside. We can access to it as follows:

sage: B = I.groebner_basis() ; B
Polynomial Sequence with 25 Polynomials in 9 Variables
sage: list(B)
[x5^2*x6^2 - 2*x3*x5*x6*x8 + x3^2*x8^2 - x3^2,
 x5^2*x6*x7 - 2*x3*x5*x7*x8 + x3*x4*x8^2 + x5*x6*x8^2 - x3*x8^3 - x3*x4 - x5*x6 + x3*x8,
 x2^2*x7^2 - 2*x1*x2*x7*x8 + x1^2*x8^2 - x1^2,
 x2*x5*x7^2 - 2*x1*x5*x7*x8 + x1*x4*x8^2 + x2*x7*x8^2 - x1*x8^3 - x1*x4 - x2*x7 + x1*x8,
 x5^2*x7^2 - 2*x4*x5*x7*x8 + x4^2*x8^2 - x4^2 - 2*x5*x7 - x8^2 + 1,
 x0*x4*x8^2 + x4^2*x8^2 + x5*x7*x8^2 + x0*x8^3 + x4*x8^3 + x8^4 - x0*x4 - x4^2 - x5*x7 - x0*x8 - x4*x8 - 2*x8^2 + 1,
 x1*x2*x4 - x1^2*x5 + x2^2*x7 - x1*x2*x8,
 x0*x4^2 + x4^3 + x4*x5*x7 - x5*x7*x8 - x0*x8^2 - x8^3 - x4 + x8,
 x2*x4^2 - x1*x4*x5 + x2*x5*x7 - x1*x5*x8 - x2,
 x0*x4*x5 + x4^2*x5 + x5^2*x7 + x0*x5*x8 + x4*x5*x8 + x5*x8^2 - x5,
 x3*x4*x6 + x5*x6^2 - x3^2*x7 - x3*x6*x8,
 x4^2*x6 - x3*x4*x7 + x5*x6*x7 - x3*x7*x8 - x6,
 x4*x5*x6 - x3*x5*x7 + x5*x6*x8 - x3*x8^2 + x3,
 x0*x4*x7 + x4^2*x7 + x5*x7^2 + x0*x7*x8 + x4*x7*x8 + x7*x8^2 - x7,
 x2*x4*x7 - x1*x5*x7 + x2*x7*x8 - x1*x8^2 + x1,
 x0*x5*x7 + x4*x5*x7 + 2*x5*x7*x8 + x0*x8^2 + x8^3 - x0 - x8,
 x0^2 - x4^2 - 2*x5*x7 - x8^2 + 1,
 x0*x1 + x1*x4 + x2*x7,
 x0*x2 + x1*x5 + x2*x8,
 x0*x3 + x3*x4 + x5*x6,
 x1*x3 + x4^2 + x5*x7 - 1,
 x2*x3 + x4*x5 + x5*x8,
 x0*x6 + x3*x7 + x6*x8,
 x1*x6 + x4*x7 + x7*x8,
 x2*x6 + x5*x7 + x8^2 - 1]

It might be worth investigating further into that direction (to all readers, please do not hesitate to post an answer if you know how to).

edit flag offensive delete link more

Comments

We can group the matrices $A$ with $A^2=1$ w.r.t. the image via $\det$, so we can restrict to the half of the cases, those with $\det A=1$. Then the condition can be restated as $A=A^{-1}$, and the inverse is the adjoint matrix. The obtained nine + one (det) equations are an alternative. (In both cases we need the det equation.)

dan_fulea gravatar imagedan_fulea ( 2017-03-13 18:48:47 -0500 )edit

Your Answer

Please start posting anonymously - your entry will be published after you log in or create a new account.

Add Answer

Question Tools

Stats

Asked: 2017-03-02 11:56:23 -0500

Seen: 99 times

Last updated: Mar 13