Matrix Permutations

asked 2017-12-15 18:34:07 +0100

Asg
13 ●1 ●1 ●3

updated 2018-01-24 20:48:05 +0100

FrédéricC

5261 ●3 ●44 ●117

Hello,

how do I get all permutations of a Matrix?

For the following exercise I would like to get all permutations of a Matrix with integer values in the range $0$ to $9$. There should be $10^4$ permutations. And then generate the permutations of tuples with three matrices. $10^{12}$ permutations and then I would filter the list somehow for the invertible matrices.

Is there a better way?

Exercise: Let $S, T, U \in \mathbb{R}^{2x2}$ such that, $S_{i, j}, T_{i, j}, U_{i, j} \in {0,1, \cdots, 9}$ How many of the products $S \cdot T \cdot U$ are invertible?

In the Sage reference for permutation I couldn't find any thing.

Thanks

PS: The curly braces couldn't be escaped properly in the LaTex part ... \{0,1, \cdots, 9\}

edit retag flag offensive close merge delete

add a comment

2 Answers

Sort by » oldest newest most voted

answered 2017-12-16 15:22:24 +0100

dan_fulea
5537 ●5 ●43 ●95

For the exercise, to loop among the list of all 2x2 matrices with entries in [0..9] the suitable mathematical construction is the cartesian product of four copies of [0..9]. This may be achieved like this:

sage: R = [0..9]
sage: C = cartesian_product( (R,R,R,R) )
sage: len(C)
10000
sage: C.random_element()
(6, 5, 4, 7)

One can build the matrix with the las entries (last value is _ in the sage interpreter) like this:

sage: _
(6, 5, 4, 7)
sage: matrix( ZZ, 2, 2, list(_) )

[6 5]
[4 7]

So the number of invertible matrices $S$ of the given shape is:

sage: R = [0..9]
sage: C = cartesian_product( (R,R,R,R) )
sage: len( [ c for c in C if matrix( ZZ, 2, 2, list(c) ).det() ] ) 
9430

The product $STU$ is invertible iff each matrix in it is invertible. So the exercise is solved in one more line. It is a good idea to use structure in mathematics, when it is possible. Brute force can then confirm the result.

Note: Permutations are not involved in the exercise. Inn order to get info on this or an other mathematical object, just try the first letters of it in the sage interpreter, which has autocompletion. We can try here perm[TAB] and/or Perm[TAB]. In the second case we get a list of classes / constructors, among them we can put a question mark before or after...

sage: Permutation?

to get more information on this. The sage interpreter is a good tool to learn sage.

edit flag offensive delete link

Comments

Thanks for your help.

I tried it as follow based on your code, but it doesn't work. I use CoCalc. It shows the green bar for computation, but it doesn't stop and doesn't return any results.

R = [0,1,2,3,4,5,6,7,8,9]

C = cartesian_product((R,R,R,R)).list()

invertibleMatrices = [matrix(ZZ, 2,2,list(c)) for c in C if matrix(ZZ, 2,2,list(c)).det()]

invertibleMatrices3Tuples = cartesian_product((invertibleMatrices, invertibleMatrices, invertibleMatrices)).list()

invertibleSTUProducts = [c for c in invertibleMatrices3Tuples if c[0]*c[1]*c[2].det()]
len(invertibleSTUProducts)

BTW: What do you mean by "It is a good idea to use structure in mathematics"?

Asg ( 2017-12-16 19:19:34 +0100 )edit

As it is written: "The product STU is invertible if and only if each of the matrices S, T and U is invertible." So there is no need to compute all the products (that would be too long to terminate anyway).

vdelecroix ( 2017-12-16 21:07:40 +0100 )edit

I don't think that I do so.

I perform the following steps:

I put all invertible Matrices in the variable invertibleMatrices.
I try to build all tuple-combinations with 3 matrices and put it in the variable invertibleMatrices3Tuples.
I build the products of matrices in each tuple and see if the product is invertible and put them all in the variable invertibleSTUProducts.

Did I miss something?

Asg ( 2017-12-16 21:55:27 +0100 )edit

yes you did

vdelecroix ( 2017-12-16 22:00:53 +0100 )edit

I think, now I get your point:

The 1st step remains and the I'll do this:

CountOfInvertibleMatrices3Tuples = len(invertibleMatrices)^3
CountOfInvertibleMatrices3Tuples
838561807000

Is it now ok?

Thanks

Asg ( 2017-12-16 22:19:56 +0100 )edit

see more comments

answered 2017-12-17 11:14:46 +0100

vdelecroix
7645 ●20 ●85 ●168 http://www.labri.fr/pe...

updated 2017-12-17 11:27:27 +0100

It is possible to make an even less computational solution than in @dan_fulea answer. As already mentioned, we simply want to count the solutions of a d - b c != 0 where a, b, c, d are elements of {0, 1, ..., 9}. This is easily obtained from the number of solutions of ad - bc = 0 which itself can be obtained by solving x y = s for all possible values of s. For example

xy = 0 has 19 solutions (from which we get 19 * 19 = 361 matrices)
xy = 1 has 1 solution (from which we get 1 matrix)
xy = 6 has 4 solutions (from which we get 6 * 6 = 36 matrices)
etc

In Sage

sage: P = set(i * j for i in range(10) for j in range(10))
sage: sum(sum(x * y == s for x in range(10) for y in range(10))**2 for s in P)
570
sage: 10**4 - 570
9430

Here 570 is the number of non-invertible matrices with entries in {0, 1, ..., 9}. Now, we can even be more clever. The number of solutions for xy = s is, excepted for s = 0, the number of divisors d of s that belongs to {1, ..., 9} and so that s/d also beongs to {1, ..., 9}. We recover 570 with

sage: Q = set(i * j for i in range(1, 10) for j in range(1, 10))
sage: 19^2 + sum(sum(s%d == 0 and s < 10*d for d in range(1,10))**2 for s in Q)
570

edit flag offensive delete link

Comments

Thanks for the post! I must confess, this was the first solution i wanted to type, then saw that there is a little combinatorial point to explain when we place the a,b,c,d elements with ad == bc on the two diagonals in case a == d and/or b == c. Since the cartesian product was already an issue, i decided to avoid combinatorics. This means then to compute for each possible product the number of the ways to produce it. Of course, we do not have $10^4$ cases, since for each possible product we can count the pairs. At most $10^2$ cases. But then i was generous to get all $10^4$. The argument is not better, but it better illustrates the cartesian product as a construction. I was really glad to see it in action for $S,T,U$ again. (Although the bits needed are too many.)

dan_fulea ( 2017-12-17 18:33:29 +0100 )edit

It is a good homework to try to implement this idea for counting $3\times 3$ invertible matrices with entries among $0,1,2,3,4,5,6,7,8,9$. The $10^9$-steps loop would not be my solution. (Of course, there is no structural meaning for the number obtained after much work, just an exercise. The experience will eventually pay later many times the dividends...)

dan_fulea ( 2017-12-17 18:37:42 +0100 )edit

Thanks for your help. @vdelecroix I'll try to comprehend your solution ...

Asg ( 2017-12-19 13:51:53 +0100 )edit

add a comment

Your Answer

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

Add Answer

Matrix Permutations

2 Answers

Comments

Comments

Your Answer

Question Tools

Stats

Related questions

Matrix Permutations edit

2 Answers

Comments

Comments

Your Answer

Question Tools

Stats

Related questions

Matrix Permutations