# How can I construct an equivalence relation in the form of a 0-1 matrix from a set partition?

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


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


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.

If yes, you may write:

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


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


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