5
$\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$
  • $\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 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 at 8:38
  • 1
    $\begingroup$ Can you clarify what you mean by "rotation transformation" in this case? $\endgroup$ – mmeent Sep 3 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 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 at 9:30
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$
  • $\begingroup$ Thank you! What does “@Range[-7,7]” mean in the code? $\endgroup$ – King.Max Sep 3 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 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 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 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 at 3:13
5
$\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$
  • $\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 at 2:40
  • 1
    $\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 at 6:51
  • $\begingroup$ Thanks for your help! $\endgroup$ – King.Max Sep 4 at 8:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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