Is there a natural way to represent all the partitions of an integer set $\{1,2,3,...,n\}$ as a matrix in the similar way permutations can be mapped to group of matrices?
Matrix representation of a partition
-
1How similar? What would the group operation be? What would this be for? – 2010-08-28
-
0@Qiaochu I'm welcome to suggestions on how to improve this question - what I've seen before is a way of mapping permutations onto matrices, a useful tool as it translates things into a language that already has a lot of machinery around it. I was wondering if something like this exists for partitions. Like you mentioned, I have no idea what the group operation would be nor do I even know if it is possible - hence the question. – 2010-08-28
-
1I think Qiaochu is hinting at the fact that there is an obvious one, that is probably not what you are looking for, so he wants to know what you hope to do with it. In particular, the obvious one is send it to nxn matrices where the i'th row is the i step in your partition and the (i,j) entry is 1 if that step of your partition iss greater than or equal to j. For example, the partition of one step would be the nxn matrix with the top row all ones. The partition with two steps (n-1,1) would have the top row all ones but the last column and the second row only the first column has a 1. – 2010-08-28
-
1I can say a little more to make you understand our concern for your action. The permutation matrices are defined specifically by their action on the standard linear basis of your vector space. The image of a permutation is exactly the matrix that acts on the linear basis and permutes the basis elements in the specified way. If we wish to extend this methodology to partitions, maybe you would ask that it partitions the vector space into subspace according to ordered basis elements, but I don't know if this really makes sense. :/ Again, clarifying your desires will help us answer your question. – 2010-08-28
-
1I do not think that the partitions of {1,…,n} form any “natural” group, but they naturally form a lattice, and therefore they form a semigroup using the meet or the join as the operation. If you are asking this question just out of curiosity, you might be interested to matrix representations of the semigroup of the partitions of {1,…,n} under the meet (or the join). I am not sure if there is any interesting representation in this sense, though. – 2010-08-28
-
0What I'm trying to say is that the answer to any question of this type depends heavily on the intended application. – 2010-08-28
-
0@Qiaochu Yuan: It does not seem to me that the questioner has any “intended application” in mind, but needless to say I may be wrong. – 2010-08-28
-
0@ Tsuyoshi - I am indeed asking out of curiosity, hence the initial vagueness of the question. I am interested in the lattice/semigroup and it seems to be what I'm grasping at - can you (or someone else) expand it to an answer (or should I ask a new question)? – 2010-09-01
1 Answers
The important component of the question here seems to be: can we define a natural binary operation on the set P of partitions of $\\{1,2,\ldots,n\\}$ to form a group G? Cayley's Theorem tells us that if G exists, it is isomorphic to a subgroup of the symmetric group on G. So G will be isomorphic to a group of permutation matrices.
However, finding a natural binary operation on P is going to be tricky. Of course, P is just a set, and it would be possible to construct some highly-contrived binary operation on P, but typically it would not preserve the structure of the partitions.
As an off-the-top-of-my-head example of why I think it should be tricky: |P| is given by the Bell Numbers, which can be a prime number, whence G must be a cyclic group and each non-identity element of G must somehow generate G.