Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
1  
How similar? What would the group operation be? What would this be for? –  Qiaochu Yuan Aug 28 '10 at 4:08
    
@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. –  Hooked Aug 28 '10 at 4:14
1  
I 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. –  BBischof Aug 28 '10 at 5:35
1  
I 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. –  BBischof Aug 28 '10 at 5:38
1  
I 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. –  Tsuyoshi Ito Aug 28 '10 at 12:15

1 Answer 1

up vote 1 down vote accepted

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.