Finding all invertible square matrices

user_12818651 0
Viewed 183

I want to write a function where given the two integers "n" and "p", it generates all the invertible matrices of order n where the elements come from {0,1,...,p-1}. I have the following code :

import itertools 
import numpy as np 

def invertible_matrices(n, p):
    invertibleMatrices = set()
    # generates all the possible matrices
    x = [y for y in range(p)]
    a = [j for j in itertools.product(x, repeat=n)]
    b = {k for k in itertools.product(a, repeat=n)}
    for each in b:
        if np.linalg.det(each) != 0:
            invertibleMatrices.add(each)
    return invertibleMatrices

for n=2 and p=2 it works fine but for n=2 and p=3 I get 50 while the answer is 48. any help would be appreciated.

p.s: if you're familiar with group theory I'm trying to find all the elements of GL(n, p) (the general linear group over a finite field with p elements)

algebra matrix numpy python
2 Answers

I guess you want the determinant modulo p (which is the determinant in the context of GL(n,p), i.e. over the finite field with p elements).

if not np.isclose((np.linalg.det(each)+1)%p,1):
    invertibleMatrices.add(each)

Note: the +1 is to avoid wrap around of small numerical errors.

user_72073920

Use inspect_matrix() for debugging, get_invertible_matrices() for using a set comprehension to determine all invertible matrices, and get_determinant_1_matrices() to get the ones with determinant 1:

import itertools
import numpy as np


def inspect_matrix(n, p):
    """Examine a single, square matrix."""
    a = list(itertools.product(list(range(p)), repeat=n))
    matrices = {k
                for k in itertools.product(a, repeat=n)
               }
    matrix = next(iter(matrices))  # Inspect one of the matrices
    determinant = np.linalg.det(matrix)
    print(f"{matrix = }\n{determinant = }")
    print(f"inverse = {(inverse:=np.linalg.inv(matrix))}") if determinant != 0.0 else print("Matrix is not invertible")
    return inverse 


def get_invertible_matrices(n, p):
    """Generates all the possible matrices."""
    a = list(itertools.product(list(range(p)), repeat=n))
    invertible_matrices = {k
                           for k in itertools.product(a, repeat=n)
                           if not np.isclose((np.linalg.det(k) + 1) % p, 1)
                           }
    print(f"{len(invertible_matrices) = }")
    return invertible_matrices


def get_determinant_1_matrices(n, p):
    """Generates all the square matrices with determinant 1."""
    a = list(itertools.product(list(range(p)), repeat=n))
    if p==2:
            det_1_matrices = {k
                              for k in itertools.product(a, repeat=n)
                              if np.isclose((np.linalg.det(k))%p,1)
                              }
    else:
            det_1_matrices = {k
                              for k in itertools.product(a, repeat=n)
                              if np.isclose((np.linalg.det(k)+1)%p,2)
                              }
    print(f"{len(det_1_matrices) = }")
    return det_1_matrices


def main():
    print(get_invertible_matrices(n=2, p=2))
    print(get_invertible_matrices(n=2, p=3))
    print(get_determinant_1_matrices(n=2, p=2))
    print(get_determinant_1_matrices(n=2, p=3))


if __name__ == '__main__':
    main()

returns:

len(invertible_matrices) = 6
{((1, 1), (0, 1)), ((1, 0), (0, 1)), ((1, 0), (1, 1)), ((0, 1), (1, 0)), ((0, 1), (1, 1)), ((1, 1), (1, 0))}
len(invertible_matrices) = 48
{((1, 0), (0, 1)), ((1, 2), (0, 2)), ((2, 1), (1, 0)), ((0, 2), (2, 0)), ((0, 1), (2, 0)), ((1, 1), (1, 0)), ((2, 1), (1, 1)), ((2, 2), (2, 0)), ((1, 1), (2, 1)), ((1, 2), (1, 0)), ((2, 1), (2, 2)), ((2, 0), (0, 2)), ((1, 2), (1, 1)), ((2, 2), (0, 2)), ((1, 0), (0, 2)), ((1, 1), (1, 2)), ((1, 2), (2, 2)), ((2, 1), (0, 1)), ((1, 1), (0, 1)), ((0, 2), (1, 0)), ((0, 1), (1, 0)), ((2, 0), (2, 1)), ((0, 2), (2, 1)), ((2, 2), (1, 0)), ((0, 1), (2, 1)), ((1, 2), (0, 1)), ((0, 2), (1, 1)), ((2, 0), (1, 1)), ((0, 1), (1, 1)), ((2, 2), (2, 1)), ((2, 0), (2, 2)), ((0, 2), (2, 2)), ((2, 1), (2, 0)), ((0, 1), (2, 2)), ((1, 0), (2, 1)), ((1, 0), (1, 1)), ((1, 1), (2, 0)), ((2, 0), (1, 2)), ((0, 2), (1, 2)), ((0, 1), (1, 2)), ((1, 0), (2, 2)), ((2, 0), (0, 1)), ((1, 2), (2, 0)), ((2, 2), (1, 2)), ((2, 1), (0, 2)), ((1, 0), (1, 2)), ((2, 2), (0, 1)), ((1, 1), (0, 2))}
len(det_1_matrices) = 6
{((0, 1), (1, 1)), ((0, 1), (1, 0)), ((1, 0), (0, 1)), ((1, 0), (1, 1)), ((1, 1), (0, 1)), ((1, 1), (1, 0))}
len(det_1_matrices) = 24
{((2, 2), (0, 2)), ((0, 2), (1, 2)), ((1, 1), (0, 1)), ((1, 2), (2, 2)), ((2, 1), (2, 0)), ((1, 0), (0, 1)), ((2, 0), (2, 2)), ((2, 1), (1, 1)), ((1, 1), (2, 0)), ((1, 0), (2, 1)), ((1, 2), (0, 1)), ((1, 2), (1, 0)), ((2, 0), (0, 2)), ((1, 0), (1, 1)), ((1, 1), (1, 2)), ((0, 2), (1, 0)), ((0, 1), (2, 2)), ((0, 2), (1, 1)), ((0, 1), (2, 1)), ((2, 0), (1, 2)), ((0, 1), (2, 0)), ((2, 2), (2, 1)), ((2, 2), (1, 0)), ((2, 1), (0, 2))}
user_74455280
Related