Permuting the incidence matrix of a self-dual

Discuss interdimensional programming, Java applets and so forth.

Permuting the incidence matrix of a self-dual

Postby Keiji » Sat Mar 29, 2014 3:02 pm

Does anyone know of a good algorithm to permute the incidence matrix of a self-dual so that a rotation will result in the same matrix (in cases where this is possible)?

I'm currently struggling with the following one:

Code: Select all
1   *   *   *   *   *   *   *   0   0   0   0   1   1   1   0   0   0   0   0   0   0   0   0   0   1   1   1   0   0
*   1   *   *   *   *   *   *   0   1   0   0   0   0   0   1   1   0   0   0   0   0   1   0   1   0   0   0   1   0
*   *   1   *   *   *   *   *   0   0   0   1   0   0   0   0   1   1   0   0   0   0   0   0   1   0   1   0   1   0
*   *   *   1   *   *   *   *   0   0   0   0   0   0   0   0   0   0   1   1   1   0   0   0   0   0   0   1   1   1
*   *   *   *   1   *   *   *   1   1   1   1   1   0   0   0   0   0   0   0   0   0   1   1   1   1   1   0   0   0
*   *   *   *   *   1   *   *   0   0   0   0   0   0   1   0   0   1   1   0   0   0   0   0   0   0   1   1   1   0
*   *   *   *   *   *   1   *   0   0   1   0   0   1   0   0   0   0   0   1   0   1   0   1   0   1   0   1   0   1
*   *   *   *   *   *   *   1   1   0   0   0   0   0   0   1   0   0   0   0   1   1   1   1   0   0   0   0   1   1
0   0   0   0   1   0   0   1   1   *   *   *   *   *   *   *   *   *   *   *   *   *   1   1   0   0   0   0   0   0
0   1   0   0   1   0   0   0   *   1   *   *   *   *   *   *   *   *   *   *   *   *   1   0   1   0   0   0   0   0
0   0   0   0   1   0   1   0   *   *   1   *   *   *   *   *   *   *   *   *   *   *   0   1   0   1   0   0   0   0
0   0   1   0   1   0   0   0   *   *   *   1   *   *   *   *   *   *   *   *   *   *   0   0   1   0   1   0   0   0
1   0   0   0   1   0   0   0   *   *   *   *   1   *   *   *   *   *   *   *   *   *   0   0   0   1   1   0   0   0
1   0   0   0   0   0   1   0   *   *   *   *   *   1   *   *   *   *   *   *   *   *   0   0   0   1   0   1   0   0
1   0   0   0   0   1   0   0   *   *   *   *   *   *   1   *   *   *   *   *   *   *   0   0   0   0   1   1   0   0
0   1   0   0   0   0   0   1   *   *   *   *   *   *   *   1   *   *   *   *   *   *   1   0   0   0   0   0   1   0
0   1   1   0   0   0   0   0   *   *   *   *   *   *   *   *   1   *   *   *   *   *   0   0   1   0   0   0   1   0
0   0   1   0   0   1   0   0   *   *   *   *   *   *   *   *   *   1   *   *   *   *   0   0   0   0   1   0   1   0
0   0   0   1   0   1   0   0   *   *   *   *   *   *   *   *   *   *   1   *   *   *   0   0   0   0   0   1   1   0
0   0   0   1   0   0   1   0   *   *   *   *   *   *   *   *   *   *   *   1   *   *   0   0   0   0   0   1   0   1
0   0   0   1   0   0   0   1   *   *   *   *   *   *   *   *   *   *   *   *   1   *   0   0   0   0   0   0   1   1
0   0   0   0   0   0   1   1   *   *   *   *   *   *   *   *   *   *   *   *   *   1   0   1   0   0   0   0   0   1
0   1   0   0   1   0   0   1   1   1   0   0   0   0   0   1   0   0   0   0   0   0   1   *   *   *   *   *   *   *
0   0   0   0   1   0   1   1   1   0   1   0   0   0   0   0   0   0   0   0   0   1   *   1   *   *   *   *   *   *
0   1   1   0   1   0   0   0   0   1   0   1   0   0   0   0   1   0   0   0   0   0   *   *   1   *   *   *   *   *
1   0   0   0   1   0   1   0   0   0   1   0   1   1   0   0   0   0   0   0   0   0   *   *   *   1   *   *   *   *
1   0   1   0   1   1   0   0   0   0   0   1   1   0   1   0   0   1   0   0   0   0   *   *   *   *   1   *   *   *
1   0   0   1   0   1   1   0   0   0   0   0   0   1   1   0   0   0   1   1   0   0   *   *   *   *   *   1   *   *
0   1   1   1   0   1   0   1   0   0   0   0   0   0   0   1   1   1   1   0   1   0   *   *   *   *   *   *   1   *
0   0   0   1   0   0   1   1   0   0   0   0   0   0   0   0   0   0   0   1   1   1   *   *   *   *   *   *   *   1


In the past I've done the permuting by hand, with some intuition and a lot of trial and error, but this is a large matrix with no symmetry whatsoever and that method just won't work here. I thought about a brute-force approach, but there are 8! * 14! * 8! = ~141 pentillion valid permutations of this matrix, so I'd need a supercomputer for that.

I'm vaguely thinking that a real algorithm to solve this would work from the bottom-left corner outwards, making it the same as the top right corner, permuting rows and columns that don't match, however I'm thinking it might get stuck when there are numbers the same in rows/columns that actually need to be swapped. So I figured I'd ask if anyone else has come up with such an algorithm already.

For reference, here's the figure this imat represents:

Image

At the moment I've posted the above matrix on the triangulated pinched triangular cupola page, just so that I'm able to post the imat for the J92 rhombochoron on the wiki. It's not very neat though that a self-dual is marked as not self-dual by my (rather strict) polytope explorer.
User avatar
Keiji
Administrator
 
Posts: 1962
Joined: Mon Nov 10, 2003 6:33 pm
Location: Torquay, England

Re: Permuting the incidence matrix of a self-dual

Postby Klitzing » Sat Mar 29, 2014 4:23 pm

Hmmm, you could investigate a bit deeper:
- you have 1 pentavalent vertex, 2 tetravalent ones, and 5 trivalent ones.
- Similarily you have 1 pentagonal face, 2 tetragonal ones, and 5 trigonal ones.

Thus you could reduce your rough estimate just by this tiny observation from 8! * 14! * 8! down to (1! * 2! * 5!) * 14! * (5! * 2! * 1!), i.e. by a factor 28224. 8)

Then investigate the edges too, falling into 2 dual classifications:
- either according to the valences of the connected vertices,
- or according to the joined polygons.

Then use a new still finer classification according to both splittings. Now arrange simply those classes according to duality pairings, e.g. if the class of the single square-square edge would be placed at some position x, then the class of the single edge, joining the 2 tetravalent vertices should be placed at the same position when counted from the other end. That is, this arranges at least the edge classes as desired. And the counts of all these classes would be much smaller.

Thus you should get down that 14! to some 1! * ... * 1!

You get what I'm after here?

--- rk
Klitzing
Pentonian
 
Posts: 1377
Joined: Sun Aug 19, 2012 11:16 am
Location: Heidenheim, Germany

Re: Permuting the incidence matrix of a self-dual

Postby Keiji » Sat Mar 29, 2014 6:18 pm

Aha, thank you very much indeed for the suggestion! I realised I could color the faces and vertices on my original graph simultaneously following that logic, and ended up with this:

Image

Which generated the imat you now see on the wiki which is validated and marked as self-dual. :D
User avatar
Keiji
Administrator
 
Posts: 1962
Joined: Mon Nov 10, 2003 6:33 pm
Location: Torquay, England


Return to Programming

Who is online

Users browsing this forum: No registered users and 1 guest

cron