6
$\begingroup$

How to generate all $ 3 \times 3 $ matrices with $ a,a,a,a,b,b,b,c,c $, which can not be obtained from each other by rotation transformation?

$\endgroup$
6
  • $\begingroup$ Is this different from doing res = Permutations[{a, a, a, a, b, b, b, c, c}]; res = ArrayReshape[#, {3, 3}] & /@ res; MatrixForm[#] & /@ res? To check for the last part which can not be obtained each other by rotation transformation is something not included in the above code. How would you check for this part? $\endgroup$
    – Nasser
    Sep 3, 2019 at 8:02
  • $\begingroup$ @Nasser Yes, it is different. I want to classify these matrices. If the matrices that can be obtained by rotation of one matrix,we will think they are the same category. $\endgroup$
    – King.Max
    Sep 3, 2019 at 8:38
  • 1
    $\begingroup$ Can you clarify what you mean by "rotation transformation" in this case? $\endgroup$
    – TimRias
    Sep 3, 2019 at 8:42
  • $\begingroup$ Whether two diagonalizable matrices can be unitarily transformed into each other if fully defined by their spectrum. If the spectrum is the same, it's possible; otherwise, it is not. You can generate matrices as @Nasser recommends and then filter them numerically by taking a few specific values of a,b,c using Eigenvalues. $\endgroup$
    – Ihor
    Sep 3, 2019 at 9:20
  • $\begingroup$ @mmeent It means that the central element of the matrix is the axis of rotation. If we rotate the matrix [1,2,3;1,2,3;1,2,3] by ninety degrees, we will get [3,3,3;2,2,2;1,1, 1] $\endgroup$
    – King.Max
    Sep 3, 2019 at 9:30

2 Answers 2

11
$\begingroup$

A brute force approach:

For a permutation p, protations[p] constructs the union of permutations obtained by all possible two-step rotations of its 8 elements after dropping its middle element. We use MemberQ[protations[#], #2]& as the test function in DeleteDuplicates. Then using Partition[#, 3]& for all permutations in the resulting list gives the desired list of 3X3 matrices.

lst = {a, a, a, a, b, b, b, c, c};
perms = Permutations[{a, a, a, a, b, b, b, c, c}];

Length @ perms

1260

Borrowing the idea that we can consider the last element of permutation as the center of the matrix from @jose's answer:

ClearAll[protations]
protations[x_] := Module[{l = Length[x]}, 
  Union @ (RotateRight[Most @ x, #] & /@ Range[0, l - 2, 2])]

dupetest = MemberQ[protations[#], Most @ #2] &;

out = DeleteDuplicates[perms, dupetest];

Length @ out

318

10 examples:

Row[MatrixForm[Partition[Insert[Most@#, Last@#, 5], 3]] & /@ RandomSample[out, 10]]

enter image description here

An alternative test function using GroupOrbits (again from jose's answer) of the PermutationGroup of a subset of the group elements of CyclicGroup:

pg = PermutationGroup[GroupElements[CyclicGroup[8]][[;; ;; 2]]]

dupetest2 = MemberQ[First@GroupOrbits[pg, {Most@#}, Permute], Most@#2] &;

out2 = DeleteDuplicates[perms, dupetest2];

out2  == out

True

A much faster approach is to generate GroupOrbits of pg for perms at once (again from jose's answer) and take the first element of each orbit.

out3 = GroupOrbits[pg, perms, Permute][[All, 1]];

out3 == out

True

$\endgroup$
6
  • $\begingroup$ Thank you! What does “@Range[-7,7]” mean in the code? $\endgroup$
    – King.Max
    Sep 3, 2019 at 12:04
  • $\begingroup$ @King.Max,` RotateRight[list, -k]` is the same as RotateLeft[list, k] (rotate to the left k positions). RotateRight[{a, b, c, d}, #] & /@ Range[-3, 3] gives list of all possible rotations of the 4 element list {a, b, c, d}. $\endgroup$
    – kglr
    Sep 3, 2019 at 13:02
  • $\begingroup$ Same as the question I asked below: if one of the matrices is like this:$\left(\begin{array}{lll}{1} & {2} & {3} \\ {8} & {9} & {4} \\ {7} & {6} & {5}\end{array}\right)$ . I know that such a matrix $\left(\begin{array}{lll}{3} & {4} & {5} \\ {2} & {9} & {6} \\ {1} & {8} & {7}\end{array}\right)$ will be treated the same. But such a matrix $\left(\begin{array}{lll}{2} & {3} & {4} \\ {1} & {9} & {5} \\ {8} & {7} & {6}\end{array}\right)$ ,I don't want it to be considered the same. Will it be considered as the same matrix in your code and deleted? $\endgroup$
    – King.Max
    Sep 4, 2019 at 2:42
  • $\begingroup$ I mean, when a matrix is rotated 90,180,270 or 360degrees, we think it is equivalent, and the other we think they are not equivalent. $\endgroup$
    – King.Max
    Sep 4, 2019 at 2:52
  • $\begingroup$ @King.Max, this is important piece of information; you should add this to your question. As is, both answers consider the third matrix sames as the first two. You can change Range[0, l - 2] in protations to Range[0, l - 2, 2] to handle equivalence by "90,180,270 or 360 Degree" rotations. $\endgroup$
    – kglr
    Sep 4, 2019 at 3:13
6
$\begingroup$

Let me give a GroupOrbits approach, imitating many aspects of the accepted solution. Start again with all permutations of the elements:

list = {a, a, a, a, b, b, b, c, c};
perms = Permutations[list];

Again, assume each permutation defines a matrix whose central element is placed last:

makeMatrix[{e1_, e2_, e3_, e4_, e5_, e6_, e7_, e8_, e9_}] := {{e1, e2, e3}, {e8, e9, e4}, {e7, e6, e5}}

Then we can partition the lists into orbits of equivalent cases under cyclic permutation of the first eight elements:

In[]:= Length[orbits = GroupOrbits[CyclicGroup[8], perms, Permute]]
Out[]= 159

Select some examples of orbit representatives with

MatrixForm /@ makeMatrix /@ First /@ RandomSample[orbits, 10]
$\endgroup$
3
  • $\begingroup$ But I have a problem: if one of the matrices is like this:$\left(\begin{array}{lll}{1} & {2} & {3} \\ {8} & {9} & {4} \\ {7} & {6} & {5}\end{array}\right)$ . I know that such a matrix $\left(\begin{array}{lll}{3} & {4} & {5} \\ {2} & {9} & {6} \\ {1} & {8} & {7}\end{array}\right)$ will be treated the same. But such a matrix $\left(\begin{array}{lll}{2} & {3} & {4} \\ {1} & {9} & {5} \\ {8} & {7} & {6}\end{array}\right)$ ,I don't want it to be considered the same. Will it be considered as the same matrix in your code and deleted? $\endgroup$
    – King.Max
    Sep 4, 2019 at 2:40
  • 2
    $\begingroup$ To consider that situation you need a different permutation group: instead of using CyclicGroup[8], use PermutationGroup[{Cycles[{{1,3,5,7}, {2,4,6,8}}]}]. There are then 318 different orbits, because each of the previous 159 orbits breaks in two. $\endgroup$
    – jose
    Sep 4, 2019 at 6:51
  • $\begingroup$ Thanks for your help! $\endgroup$
    – King.Max
    Sep 4, 2019 at 8:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.