5
$\begingroup$

As a small example, suppose I have the following list of $3 \times 3$ matrices:

matlist = {{{-1, -1, 0}, {0, 0, 1}, {0, 1, 1}}, {{-(1/3), -1, -(4/3)}, {2/3, 
   0, -(1/3)}, {2/3, 1, -(1/3)}}, {{0, -1, -1}, {0, 0, 1}, {1, 1, 
   0}}, {{-(2/3), -1, -1}, {-(2/3), 0, 1}, {1/3, 1, 0}}, {{-1, -1, 
   0}, {0, 1, 1}, {0, 0, 1}}, {{-(1/3), -1, -(4/3)}, {2/3, 
   1, -(1/3)}, {2/3, 0, -(1/3)}}, {{0, -1, -1}, {1, 1, 0}, {0, 0, 
   1}}, {{-(2/3), -1, -1}, {1/3, 1, 0}, {-(2/3), 0, 1}}, {{-(1/3), -1,
    0}, {2/3, 0, -1}, {2/3, 1, 1}}, {{-1, -1, 0}, {0, 0, -1}, {0, 1, 
   1}}, {{-(2/3), -1, 1/3}, {-(2/3), 0, 1/3}, {1/3, 1, 4/
   3}}, {{0, -1, -1}, {0, 0, -1}, {1, 1, 0}}, {{-(1/3), -1, 0}, {2/3, 
   1, 1}, {2/3, 0, -1}}, {{-1, -1, 0}, {0, 1, 1}, {0, 0, -1}}}

Now I want to define matrices as equivalent (in the same class) to one another if they have the same rows (but allowing for the rows to be interchanged) or some rows are multiplied by -1 (again allowing rows to be interchanged).

In the above list the first and third matrices would be considered equivalent:

$\left( \begin{array}{ccc} -1 & -1 & 0 \\ 0 & 0 & 1 \\ 0 & 1 & 1 \\ \end{array} \right)$

and

$\left( \begin{array}{ccc} 0 & -1 & -1 \\ 0 & 0 & 1 \\ 1 & 1 & 0 \\ \end{array} \right)$

Here the first and third rows have been interchanged and each has been multiplied by -1. (second row is unchanged)

A further example would be the 5th matrix

$\left( \begin{array}{ccc} -1 & -1 & 0 \\ 0 & 1 & 1 \\ 0 & 0 & 1 \\ \end{array} \right)$

which is the first matrix with the last two rows interchanged.

Similarly the second and sixth matrices are equivalent but are a new matrix equivalence class from the prior mentioned examples.

What I want to do is take a list of matrices, matlist in my example above, and kick out one example for each equivalence class of a matrix found in the list. Or at least separate the list into sublists of matrices of the same equivalence class.

I can code this in some messy use of loops but I think I can use a function like GatherBy though I am unsure how to go about this.

Any help would be much appreciated.

$\endgroup$

4 Answers 4

3
$\begingroup$

Using the function sPM from this answer to generate signed permutations of a matrix with GatherBy:

sPM = Join @@ Map[Permutations @* DiagonalMatrix] @ Tuples[{-1, 1}, #] &;


grouped = GatherBy[matlist, Sort[sPM[3].#] &];


Map[MatrixForm] /@ grouped // Column

enter image description here

$\endgroup$
5
  • 1
    $\begingroup$ Yeah I should have thought of that myself since I knew about the sPM function from my question the other day. Much appreciated. - I'll accept this as an answer since it ties in with the earlier stuff. $\endgroup$
    – 1729taxi
    Feb 2 at 19:11
  • $\begingroup$ I think your updated version returns an incorrect result for {{{0, 1, 1}, {0, 1, 1}, {1, 0, 1}}, {{0, 1, 1}, {1, 0, 1}, {1, 0, 1}}} $\endgroup$
    – Carl Woll
    Feb 2 at 21:21
  • $\begingroup$ Thank you @CarlWoll. Replaced it with something that works. $\endgroup$
    – kglr
    Feb 2 at 21:29
  • $\begingroup$ I believe you're code still returns an incorrect result for something like {{{1, 1, 1}, {1, 1, -1}, {1, 1, 1}}, {{1, 1, 1}, {1, 1, 1}, {1, 1, 1}}} $\endgroup$
    – Carl Woll
    Feb 2 at 21:40
  • $\begingroup$ Thank you again @CarlWoll. Deleted the updated version. $\endgroup$
    – kglr
    Feb 2 at 21:59
4
$\begingroup$

You can use a function to canonicalize the matrices, and then GatherBy with this function. Here is a function that sorts the rows, after changing the sign of the first nonzero element to positive:

canon[matrix_] := Sort[fixsign /@ matrix]
fixsign[vector_] := Sign[FirstCase[vector, Except[0], 0]] vector

Then, using GatherBy:

First /@ GatherBy[matlist, canon]

{{{-1, -1, 0}, {0, 0, 1}, {0, 1, 1}}, {{-(1/3), -1, -(4/3)}, {2/3, 0, -(1/3)}, {2/3, 1, -(1/3)}}, {{-(2/3), -1, -1}, {-(2/3), 0, 1}, {1/3, 1, 0}}}

$\endgroup$
3
  • $\begingroup$ This procedure fails for matrices with an all-zero row. Example: matlist = {{{0, 0, 0}, {0, 0, 1}, {1, 1, 1}}}. $\endgroup$
    – Domen
    Feb 2 at 16:30
  • $\begingroup$ @Domen Thanks! Fixed. $\endgroup$
    – Carl Woll
    Feb 2 at 16:38
  • $\begingroup$ I like that. Learn something everyday on here. Thanks. $\endgroup$
    – 1729taxi
    Feb 2 at 19:12
4
$\begingroup$

Write a function to compare two sets:

Method 1

ClearAll[customCompare];
customCompare[a_, b_] := 
  Block[{temp = a}, 
   Scan[(temp = DeleteCases[temp, # | (-1*#), 1, 1]) &, b]; 
   temp === {}];

Method 2

Which is basically a refined version of Method 1 that is faster and uses less memory.

ClearAll[customCompare2];
customCompare2[a_, b_] := Fold[DeleteCases[#, #2 | (-1*#2), 1, 1] &, a, b] === {};

Test & Comparison

Gather[matlist, customCompare]; // MaxMemoryUsed // RepeatedTiming

(*     | RepeatedTiming | MaxMemoryUsed | *)
(* Out: {0.000399017, 2096} *)

Gather[matlist, customCompare2]; // MaxMemoryUsed // RepeatedTiming
(* Out: {0.000300972, 1624} *)

(* Domen's answer *)
(* Out: {0.00104433, 18216} *)

(* kglr's answer *)
(* Out: {0.00218543, 220480} *)

(* Carl Woll's answer*)
(* Out: {0.000152117, 5560} *)

Interestingly all the answers are the same.

$\endgroup$
1
  • $\begingroup$ Thank you. Nice to see the different ways of doing the same task. I'll file this one away. Regards. $\endgroup$
    – 1729taxi
    Feb 2 at 19:13
2
$\begingroup$

If you don't really care much about the performance, you can make a brute-force comparision test for two matrices. This involves generating all $2^3 \times 6 = 48$ possible equivalent matrices.

matEquiv[m1_, m2_] := 
 MemberQ[Catenate[
   Permutations /@ 
    Diagonal /@ Tuples[{m1, -m1}, {First@Dimensions@m1}]], m2]

Gather[matlist, matEquiv]
(* ... *)

Length[%]
(* 3 *)

So there are 3 equivalence classes in your list.

$\endgroup$
2
  • $\begingroup$ Thanks for that. I'll do some testing - my example was a bit of a toy example. My list of matrices can be several thousands long and with maybe dozens of equivalence classes. Appreciate the input. $\endgroup$
    – 1729taxi
    Feb 2 at 16:15
  • $\begingroup$ @1729taxi, great! Also note that it is usually useful for others if you mention the actual "scale" of your problem (i.e. aproximate matrix dimensions and the list length) in the initial question :-) This will affect the choice of algorithm in the answers. $\endgroup$
    – Domen
    Feb 2 at 16:22

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.