A simple modification would be to not create the list of matrices:

```
n = M.nrows()
for t in Tuples((1,-1), n^2):
a = matrix(n, n, t)
if 3*a^2 == M:
show(a)
```

With `n=5`

, this at least enters the loop immediately, whereas the original code spends a while creating the list of matrices. I gave up waiting for the original code after about 5 minutes. (You can add some print statements to see its progress.)

By the way, you can see that `Tuples`

is fast, but creating a list from its entries can be slow:

```
sage: %time Tuples((1, -1), 16)
CPU times: user 24 µs, sys: 8 µs, total: 32 µs
Wall time: 46 µs
Tuples of (1, -1) of length 16
sage: %time L = [t for t in Tuples((1, -1), 16)] # slow
CPU times: user 453 ms, sys: 23.6 ms, total: 477 ms
Wall time: 479 ms
sage: %time L = [matrix(4, 4, t) for t in Tuples((1, -1), 16)] # slower
CPU times: user 988 ms, sys: 15.6 ms, total: 1 s
Wall time: 1.01 s
```

Going through all of these matrices is going to take a long time, in any case:

```
sage: len(Tuples((1, -1), 25))
33554432
sage: len(Tuples((1, -1), 36))
68719476736
```

Edit: here is a modified version of your code:

```
def f(M):
results = []
n = M.nrows()
j = 0
for t in Tuples((1,-1), n^2):
a = matrix(n, n, t)
if j % 10000 == 0:
print(j)
j += 1
if 3*a^2 == M:
results.append(a)
# if you want to stop after finding one solution, you could add "break" here to stop the loop.
return(results)
```

You can then call `f(M)`

for any given matrix `M`

. It prints something after every 10,000 matrices, and it saves the results and returns them at the end.

Can you give an example of matrix

`M`

resulting in an error?As for speeding up the code it may be worth to compute the square root of matrix

`M/3`

and check if it composed of $\pm1$.An example of M is: