4
$\begingroup$

I have a partition of a set {1, 2, ..., n}. I would like to construct the equivalence relation that corresponds to the set partition in the form of an $n \times n$ 0-1 matrix. How can I construct such matrix?

For example:

(* Input *)
{{1, 4}, {2, 3}}

(* Expected Output *)
{{1, 0, 0, 1}, {0, 1, 1, 0}, {0, 1, 1, 0}, {1, 0, 0, 1}}
$\endgroup$

3 Answers 3

5
$\begingroup$

You can first create all pairs of elements in each of the equivalence classes by Tuples, then feed these indices to a SparseArray:

partition = {{1, 4}, {2, 3}} 
Normal@SparseArray[Catenate[Tuples[#, {2}] & /@ partition] -> 1]
(* {{1, 0, 0, 1}, {0, 1, 1, 0}, {0, 1, 1, 0}, {1, 0, 0, 1}} *)
$\endgroup$
1
$\begingroup$

The code

parts = {{4, 7, 6}, {5}, {8, 1}, {9, 2, 3}}
perm = PermutationMatrix @ Flatten @ parts; 
mat = Transpose[perm] . BlockDiagonalMatrix[
         (Table[1, {Length[#1]}, {Length[#1]}] & ) /@ parts] . perm; 
MatrixForm[mat]

results in

1   0   0   0   0   0   0   1   0
0   1   1   0   0   0   0   0   1
0   1   1   0   0   0   0   0   1
0   0   0   1   0   1   1   0   0
0   0   0   0   1   0   0   0   0
0   0   0   1   0   1   1   0   0
0   0   0   1   0   1   1   0   0
1   0   0   0   0   0   0   1   0
0   1   1   0   0   0   0   0   1

For a larger example instead of conjugating by the permutation matrix it is probably faster to actually permute the rows and the columns using the permutation that sorts the entries in Flatten @ parts.

$\endgroup$
0
$\begingroup$

Should your example not read: {{1,0,0,1},{0,1,1,0},{0,1,1,0},{0,0,0,1}}

If yes, you may write:

n = 4;
pos = {{1, 4}, {2, 3}};
Normal[SparseArray[Thread[pos -> 1], {n, n}]] + 
  IdentityMatrix[n]  // MatrixForm

enter image description here

Addendum

To make the matrix symmetrical, write:

n = 4;
pos = {{1, 4}, {2, 3}};
pos = Join[pos, Reverse /@ pos];
Normal[SparseArray[Thread[pos -> 1], {n, n}]] + 
  IdentityMatrix[n]  // MatrixForm

enter image description here

$\endgroup$
4
  • 1
    $\begingroup$ The matrix has to be symmetric, as it is supposed to represent an equivalence relation $\endgroup$ Feb 22 at 18:09
  • $\begingroup$ Look at the addendum in my answer. $\endgroup$ Feb 22 at 19:21
  • $\begingroup$ In any case, I think you misunderstood the meaning of the input. It could well be {{1,2,3},{4,5,6,7}}. $\endgroup$ Feb 22 at 19:26
  • 1
    $\begingroup$ I understood {1,4} to mean row 1 and column 4 is "1". Or element 1 and 4 are equivalent $\endgroup$ Feb 22 at 19:36

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.