[seqfan] Re: A generalization of the matrix permanent: question

Simone Severini simoseve at gmail.com
Tue Apr 7 06:41:14 CEST 2009

Thank you for your kind replay.

I would like to see whether there is a hierarchy defined by the
complexity of computing the permanent over different groups.

Possibly it's already #P for the dihedral group.

Do you have any feeling about this?

Thanks again,

On Thu, Apr 2, 2009 at 6:52 PM,  <franktaw at netscape.net> wrote:
> Well, if you sum over the alternating group, you get the average (mean)
> of the permanent and the determinant.
> Summing over the cyclic group just includes each term in the matrix in
> a single product, one product for each modular diagonal; I doubt that
> there's much interest there.  There may be some value in summing over
> the dihedral group.
> (As to your question, I have no idea if there's any literature on this.)
> Franklin T. Adams-Watters
> -----Original Message-----
> From: Simone Severini <simoseve at gmail.com>
> Dear SeqFans,
> I have a question concerning matrix permanents.
> The definition of the permanent contains a product and a sum. The sum
> is taken over all elements of the full symmetric group on n symbols,
> where n is the size of the matrix.
> Do you know of any generalization in which the sum is taken over a
> subset, or possibly a subgroup, of the full symmetric group?
> I have quickly searched the literature, but I could not find much,
> probably because I did not look for the right thing.
> If this generalization of the permanent has not been studied, it may
> be worth a look.
> _______________________________________________
> Seqfan Mailing list - http://list.seqfan.eu/

Simone Severini

More information about the SeqFan mailing list