Selecting matrices from a list of matrices that are "equivalent"

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.

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


• 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. Commented Feb 2, 2022 at 19:11
• 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}}} Commented Feb 2, 2022 at 21:21
• Thank you @CarlWoll. Replaced it with something that works.
– kglr
Commented Feb 2, 2022 at 21:29
• 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}}} Commented Feb 2, 2022 at 21:40
• Thank you again @CarlWoll. Deleted the updated version.
– kglr
Commented Feb 2, 2022 at 21:59

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}}}

• This procedure fails for matrices with an all-zero row. Example: matlist = {{{0, 0, 0}, {0, 0, 1}, {1, 1, 1}}}. Commented Feb 2, 2022 at 16:30
• @Domen Thanks! Fixed. Commented Feb 2, 2022 at 16:38
• I like that. Learn something everyday on here. Thanks. Commented Feb 2, 2022 at 19:12

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} *)

(* Out: {0.00104433, 18216} *)

(* Out: {0.00218543, 220480} *)

(* Out: {0.000152117, 5560} *)


Interestingly all the answers are the same.

• Thank you. Nice to see the different ways of doing the same task. I'll file this one away. Regards. Commented Feb 2, 2022 at 19:13

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.

• 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. Commented Feb 2, 2022 at 16:15
• @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. Commented Feb 2, 2022 at 16:22