Below are the vertices of \( \Omega^{xx}_{n}\) for n = 1 thru 5.

Theorem 1: \( \Omega^{xx}_{n}\) has \( 2^{n-1} \) vertices.
Corollary 1: The vertices of \( \Omega^{xx}_{n}\) have a natural naming convention which is a binary representation of n - 1 characters.

This will be a math induction proof. Clearly, the theorem is true for n = 1 & 2. We will assume that for all positive integers through n, \( \Omega^{xx}_{n}\) has \( 2^{n-1} \) vertices; we need to prove the case n+1.
Notice that for the first column of any vertex of \( \Omega^{xx}_{n+1}\), there are just two possibilities for where to place the 1 in that column; i.e., row 1 and row n+1. Consider the following operations from the set of vertices of \( \Omega^{xx}_{n}\) to the set of (n+1) x (n+1) permutation matrices:

L; which rotates the n x n matrix 90 degrees to the left, and then adds a row to the top and a column to the left, placing all 0s in them except for a 1 in position (1,1).

R; which rotates the n x n matrix 90 degrees to the right, and adds a row to the bottom and a column to the left, placing all 0s in them, except for a 1 in position (n+1,1).

For L: The 90 degree left rotation moves position (r,c) to (n+1-c,r); so the rows & columns of the rotated matrix are r' = n+1-c and c' = r (in terms of the original position). In the augmented matrix, we have r" = r'+1 = n+2-c; c" = c'+1 = r+1. Going through the four equations for the diagonals in the n x n matrix:
c=r solves to r"+c"=(n+1)+2
c=r+1 solves to r"+c" = (n+1)+1
r+c=n+1 solves to c"=r"
r+c=n+2 solves to c"=r"+1.
So, the result of the L operation is a \( \Omega^{xx}_{n+1}\) vertex. Similar reasoning yields the same conclusion for the result of R.
Also, distinct \( \Omega^{xx}_{n}\) vertices lead to distinct \( \Omega^{xx}_{n+1}\) vertices under both the L and R operations, and the results of L and R operations are disjoint sets. We've shown that \( \Omega^{xx}_{n+1}\) has at least \( 2^{n} \) vertices.

We've shown that L & R operations of all the vertices of \( \Omega^{xx}_{n}\) are to sufficient to produce \( 2^{n} \) vertices of \( \Omega^{xx}_{n+1}\). Now, we must show that a \( \Omega^{xx}_{n+1}\) vertex is necessarily the result of an L or R operation on a \( \Omega^{xx}_{n}\) vertex.

So, take a \( \Omega^{xx}_{n+1}\) vertex with 1 in the upper left position. We know at least one of these 4
equations must be true:
c"=r"
c"=r"+1
r"+c"=(n+1)+1
r"+c"=(n+1)+2.

Looking at the result of \( L^{-1} \) of this matrix, we solve to the corresponding equations:
r+c=n+1
r+c=n+2
c=r+1
c=r

So, the result of \( L^{-1} \) on the \( \Omega^{xx}_{n+1}\) vertex is a \( \Omega^{xx}_{n}\) vertex. A similar argument works for R.

So, we've proven that \( \Omega^{xx}_{n+1}\) has exactly \( 2^{n} \) vertices; which are the result of L and R operations on all the \( 2^{n-1} \) vertices of \( \Omega^{xx}_{n}\).

As to Corollary 1: Using left-to-right (Reverse Polish) notation, the vertices of \( \Omega^{xx}_{2}\) can be represented by [1]L = \( I_{2}\) , and [1]R = (12), where \( I_{2}\) is the identity matrix.

Then, the vertices of \( \Omega^{xx}_{3}\) can be represented by [1]LL = (23), [1]RL = \( I_{3}\) , [1]LR = (13), and [1]RR = (123),

I'll stop with the specific examples out of an abundance of caution against inadvertently causing a global rice shortage. But, I will point out the induction step that given that you can represent all vertices of \( \Omega^{xx}_{n}\) by [1] followed by all possible strings of (n-1) Ls and Rs, it follows that by adding an L to the end of these expressions, and separately, an R to the end of the expressions, you represent all the vertices of \( \Omega^{xx}_{n+1}\).

Finally, let's drop the [1] from the beginning of these expressions, as it appears in all of them. ([1] was meant to indicate the single vertex of \( \Omega^{xx}_{1}\).)

I jump ahead to discuss an XX Birkhoff-adjacent topic: What about the polytopes you get just using the even permutations in the XX Birkhoff vertex set? So, for n >= 4, these are Birkhoff non-faces (i.e., subpolytopes that aren't faces). I think I'll be able to show that half of the XX Birkhoff vertices are even permutations; this is the case for low values of n.

A compelling motivation for looking at these is a 2004 paper by Jeffrey Hood and David Perkinson, finding that the polytope associated with the Alternating Group \(\mathscr{A}_{6}\) has over 4 million facets (and 360 vertices). https://www.sciencedirect.com/science/article/pii/S0024379503008644?ref=cra_js_challenge&fr=RR-1

For n as low as 6, there's already a ton of facets for this polytope family - it's kind of a monster. I don't think they finished fully describing this polytope as a result.

Now, I'm not sure whether the polytope of even permutations in the XX Birkhoff vertex set is a face of \(P(\mathscr{A}_{n}\)). I looked at these through n = 7, and I call them \(\omega^{xx,e}_{n}\), departing from Hood & Perkinson's notation, as I'm not working with the whole Alternating Group, just a subset (not a subgroup). I use lower-case omega because these are Birkhoff non-faces, not Birkhoff faces. For n = 2, you just have a vertex, for n = 3, a line segment, and for n = 4, a tetrahedron.

For n = 5, you have a six-dimensional neighborly polytope with 8 vertices, which I believe has combinatorial type C(8,6), the cyclic polytope. This polytope has two tetrahedral non-faces, whose vertices are:
LLLL/(245), RRRL/(234),LLLR/(15)(34), RRRR/(125); and
LRLL/(25)(34), RLRL/I, LRLR/(15)(24), RLRR/(12345).
(I've given the permutations both their 'LR' name and regular name.)

\(\omega^{xx,e}_{6}\) has 16 vertices, which subtend four disjoint parallelograms:
a1: LLLLL/(256), a2: LRLLL(23456), a3: LLRLR/(16)(25), a4: LRRLR/(16)(2345);
b1: RRLLR/(16)(34), b2: RLLLR/(16)(35), b3: RRRLL/(26)(34), b4: RLRLL/(26)(35);
c1: LLRRR/(126)(345), c2: LRRRR/(126), c3: LLLRL/(345), c4: LRLRL/I;
d1: RRRRL/(235), d2: RLRRL/(25)(34), d3: RRLRR/(12356), d4: RLLRR/(1256)(34)

These parallelograms are not arranged in general position (i.e., having maximum degrees of freedom), as \(\omega^{xx,e}_{6}\) is a full-dimensional non-face of the nine-dimensional \(\Omega^{xx}_{6}\). General position would require 11 dimensions.

However, as kind of a magic of trick, \(\omega^{xx,e}_{6}\) has four facets (of the 28 facets, each with 12 vertices) consisting of three of the parallelograms in general position! \(\omega^{xx,e}_{6}\) has the same 16 facets as \(\Omega^{xx}_{6}\), plus 12 more.)

Given the structure of these four facets, conclude that all tetrahedral subpolytopes containing an edge of a parallelogram are faces (as the parallelograms are in general position). But, there must be some non-faces between the parallelograms, as the four parallelograms are not in general position.

Turns out there are 60 tetrahedral non-faces, where each of the vertices is on the same corresponding edge of the parallelograms (i.e., v1v2, v1v3, v2v4, v2v4). 56 of these are associated with 28 peaks of type \(\omega^{xx,e}_{5}\). The other four are tetrahedral non-faces with the same corresponding vertex from each parallelogram; these roll up to \(\omega^{xx,e}_{6}\); i.e., they're not contained in any proper face.