Is there a representational face lattice for the tridiagonal Birkhoff polytope?

Question

Is there a representational face lattice for the tridiagonal Birkhoff polytope of dimension d; i.e., $\Omega^t_{d+1}$? That is, is there a system of representing the faces of $\Omega^t_{d+1}$ so that given the representations of two faces A and B, you can tell whether A is a face of B or not?

Answer 1

Short answer: Yes, there is a representational face lattice. The tridiagonal Birkhoff polytope of dimension d is the polytope of tridiagonal, doubly stochastic $(d+1) \times (d+1)$ matrices $A$. We begin motivating the face representation system by numbering the $f_{d+2}$ vertices of $\Omega^t_{d+1}$ by reading off the values of the superdiagonal entries from upper left to lower right. As the possible values of these superdiagonal entries are 0 and 1, and there can be no pair of consecutive 1's, each vertex is numbered as the fibinary representation of the integers from 0 to $f_{d+2} - 1$ (where $f_n$ is the Fibonacci series). (The fibinary integer representation, which has been used in programming competitions, uses each possible string of 0's and 1's without leading zeroes and with no consecutive pair of 1's, listed in lexicographical order.) We'll retain leading zeroes, so that each vertex is represented by a string of d 0's and 1's - with no consecutive pair of 1's allowed (and each such string represents a vertex). We'll refer to the location of each 0 and 1 as a (fibinary) place, analogous to a decimal place.

Now, we will allow variables to occur in each place instead of 0's and 1's (retaining the rule about no consecutive pair of 1's). The variable X has possible values 0 or 1. $\Omega^t_{d+1}$ is represented by a string of d X's, meaning that $\Omega^t_{d+1}$ is the convex hull of all of the $f_{d+2}$ vertices - the solution space of the string of $d$ X's.

Consider the facets of $\Omega^t_{d+1}$ given by setting superdiagonal entries equal to zero. The facet given by $a_{i,i+1} = 0$ is represented by a string of X's, except with a 0 in the $i_{th}$ place - this facet is the convex hull of all vertices that have 0 in the $i_{th}$ place of their fibinary representation. Call these facets $Z_i$, $i$ = 1 to $d$.

Next consider the facets given by setting the main diagonal entries equal to zero. Because A is doubly stochastic, symmetric and tridiagonal, for 2 $\le$ $i$ $\le$ $d$, $a_{i,i} = 0$ if and only if ($a_{i-1,i} = 1$ or $a_{i,i+1} = 1$). The facet $a_{i,i} = 0$ is represented by a string of X's, except with YY in places $i - 1$ and $i$. Call these facets $Y_i$, $i$ = 2 to d. A string of Y's (of length two or more) is evaluated as a single zebra-striped field. That is, a Y-field represents alternating 1's and 0's, and thus has two possible solutions (beginning with 0 and beginning with 1, and alternating for the rest of the field). We have now represented all $2d - 1$ facets of $\Omega^t_{d+1}$.

More generally, the representations of all $\Omega^t_{d+1}$ faces are all the strings of $d$ symbols which may be 0, 1, X or Y, with Y occurring in fields comprising two or more places, with no pair of consecutive 1's and with 1 not adjoining any variable field. Each 'X' is called an X-field, and X and Y-fields are called variable fields. Each '0' and '1' is called a numeric field. (Adjoining Y-fields are separated by a comma. Field separation between X-fields, between X and Y-fields, and between an X or Y-field and a numeric field are implied; a comma is not needed.) The numeral 1 cannot adjoin a variable field (i.e., X or Y-field), because it is known that the adjacent place to 1 in any solution must be 0 (hence, the variable field would not be variable). Finally, we define a variable region as a maximal sub-string of adjoining variable fields with no numeric fields included.

Regarding the first sentence of the preceding paragraph, we will first prove by math induction that the representation of each $\Omega^t_{d+1}$ face is a string as described. The representations of $\Omega^t_{d+1}$ itself and its facets (dimension $d - 1$) are strings of $d$ symbols as described. Assume that all faces of dimension $d$ through $d - k$ have representations that are strings of d symbols which are 0, 1, X or Y, with Y occurring in fields of two or more places, with no pair of consecutive 1's, and with 1 not adjoining any variable field. To prove: faces of dimension $d - k - 1$ have such representations too. We'll evaluate all non-empty intersections of a ($d - k$)-face and a facet of $\Omega^t_{d+1}$, and thus evaluate all ($d - k - 1$)-faces along with (possibly) some lower dimensional faces.

Let F be a ($d - k$)-face of $\Omega^t_{d+1}$ (we'll use the same name for a face and its representation). Begin by considering non-empty intersections of F and facet $Z_i$, where F is not a face of $Z_i$. The $i_{th}$ place of F can't be a 0 (this would imply that F is a face of $Z_i$), and it can't be a 1 (this would produce an empty intersection). If the $i_{th}$ place of F is an X, the intersection $F \cap Z_i$ has the same representation as F, but with a 0 in the $i_{th}$ place - the representation criteria are met. If the $i_{th}$ place of F is a Y, we know that the $i_{th}$ place is within a Y-field (we'll call this F's Y-field); setting the $i_{th}$ place to 0 determines a zebra-striped numeric string of 0's and 1's in $F \cap Z_i$ to occupy the places of F's Y-field. We have some cases to consider:

Case 1: F's Y-field covers an even number of places. In Case 1a, the zebra-striped numeric string in $F \cap Z_i$ occupying the places of F's Y-field begins with 0 and ends with 1. If there are no additional variable fields adjoining F's Y-field to the right in the variable region, no further changes are necessary - $F \cap Z_i$ has the same representation as F, except with the zebra-striped numeric string beginning with 0 occupying the same places as F's Y-field. The criteria are met because the right end of F's Y-field is either the end of the representation, or a numeric region begins just to the right, starting with 0. If there are additional variable fields to the right of F's Y-field in the variable region, first consider the case that they are all even-length. In that case, each variable field to the right must be converted to a zebra-striped numeric string beginning with 0 and ending with 1, because the variable field just to its left was converted to a zebra-striped numeric string ending in 1. Again, the criteria are met because the right end of F's Y-field is either the end of the representation, or a numeric region begins just to the right, starting with 0. Say that one or more of the additional variable fields to the right of F's Y-field in the variable region is odd-length. Moving to the right from F's Y-field, each subsequent variable field must be converted to a zebra-striped numeric field beginning with 0, up to and including the first odd-length variable field encountered, which ends in a 0. Thus, the criteria are met. In Case 1b, the zebra-striped numeric string in $F \cap Z_i$ occupying the places of F's Y-field begins with 1 and ends with 0. This case proceeds exactly like Case 1a, except moving to the left from F's Y-field instead of to the right. We conclude that the criteria are met in this case.

Case 2: F's Y-field covers an odd number of places. For Case 2a, both ends of the zebra-striped string occupying the places of F's Y-field are 0's. In this case, the representation of $F \cap Z_i$, is the same as that of F, except with the zebra-striped numeric string replacing the Y-field; the representation criteria are met. For Case 2b, both ends of the zebra-striped numeric string occupying the places of F's Y-field are 1's. The argument for Case 2b is essentially a combination of Case 1a and 1b; conversion to zebra-striped numeric strings must occur both to the left and to the right. We conclude that the criteria are met in this case.

Now, consider non-empty intersections of F and facet $Y_i$, where F is not a face of $Y_i$. The $i_{th}$ and preceding place of F can't be 'YY', '01', or '10' (these would imply that F is a face of $Y_i$), and it can't be '00' (this would produce an empty intersection). If the $i_{th}$ and preceding place of F is 'XX', the intersection $F \cap Y_i$ has the same representation as F, but with a 'YY' in the $i_{th}$ and preceding place - the representation criteria are met (add a comma if this new Y-field adjoins another Y-field). If the $i_{th}$ and preceding place of F is 'XY', then the $i_{th}$ place is at the beginning of a Y-field in F. Solutions producing a 0 in the $i_{th}$ place imply that place $i - 1$ must be a 1 in the intersection (by definition of $Y_i$); solutions producing a 1 in the $i_{th}$ place imply that place $i - 1$ is 0 (by the prohibition on consecutive 1's). Thus, in $F \cap Y_i$, the string from place $i - 1$ to the end of the Y-string (in F) is zebra-striped. Thus, the representation of $F \cap Y_i$ has the same representation as F, but with the Y-field starting in the $i_{th}$ place extended back to begin in place $i - 1$ - the representation criteria are met (add a comma if this expanded Y-field adjoins another Y-field to the left). If the $i_{th}$ and preceding place of F is 'YX', then a similar argument applies; the representation of $F \cap Y_i$ has the same representation as F, but with the Y-field ending in place $i - 1$ extended forward to end in the $i_{th}$ place - the representation criteria are met (add a comma if this expanded Y-field adjoins another Y-field to the right).

Next case: the $i_{th}$ and preceding place if F is '0X'. The $i_{th}$ place of $F \cap Y_i$ must be 1, and the $(i+1)_{th}$ place must then be 0. If place $(i+1)$ was already a 0 in F, then we've determined $F \cap Y_i$ and the criteria are met. (Note that place $(i+1)$ can't be 1, as the $i_{th}$ place is X.) If there is a variable field beginning with the $(i+1)_{th}$ place of F, we proceed with a similar argument as Case 1a of $F \cap Z_i$; conclude that the criteria are met. If the $i_{th}$ and preceding place of F is 'X0', we make a similar argument, working to the left instead of to the right, and conclude that the criteria are met.

Next case: the $i_{th}$ and preceding place if F is '0Y'. The $i_{th}$ place of $F \cap Y_i$ must be 1. A Y-field of F begins in place $i$; if it is even-length it ends in 0, and the representation of $F \cap Y_i$ is the same as F, except with a zebra-striped numeric string beginning with 1 occupying the same places as F's Y-field. If the Y-field of F beginning in place $i$ is odd-length, it ends in 1. We proceed with a similar argument as Case 1a of $F \cap Z_i$; conclude that the criteria are met. If the $i_{th}$ and preceding place of F is 'Y0', we make a similar argument, working to the left instead of to the right, and conclude that the criteria are met.

Having exhausted all cases, we proceed to the converse of the preceding argument by showing that each described representation corresponds to a face:

$\circ$ Each Y-field occupying places $i$ to $j$ is from the intersection of $Y_{i+1}$ to $Y_j$.

$\circ$ Each '010' in places $i$ through $i + 2$ is from the intersection of $Z_i$, $Z_{i+2}$, $Y_{i+1}$, and $Y_{i+2}$ (note that this case also covers longer zebra-striped strings beginning and ending with 0's, such as '01010').

$\circ$ '10' in places $1$ through $2$ is from the intersection of $Z_2$ and $Y_2$.

$\circ$ '01' in places $d - 1$ through $d$ is from the intersection of $Y_d$ and $Z_{d-1}$.

$\circ$ Each other '0' is from the corresponding $Z_i$.

$\circ$ Each 'X' place results from no $Z_i$ or $Y_i$ facet containing a '0' or 'Y' in that place being included in the intersection.

We turn to the evaluation of whether one $\Omega^t_{d+1}$ face is a face of another $\Omega^t_{d+1}$ face. Given representations of faces A and B of $\Omega^t_{d+1}$, A is a face of B if and only if all three of the following are true:

1. For each Y-field of B, the corresponding places of A are either all Y's, or zebra-striped numeric.

2. For each 0 (1) in B, there is a 0 (1) in the corresponding place of A.

3. For each comma in A's representation (between two Y-fields) there is a field separation in the corresponding place of B.

First we'll assume A is a face of B and prove statements 1 - 3.

1. '00' cannot appear within the places of A corresponding to B's Y-field, because any numeric solution to the Y-field must be zebra-striped. Say 'X' appears within the places of A corresponding to B's Y-field. The 'X' and an adjoining place within the places corresponding to B's Y-field could both be 0; the adjoining place is either one end of a variable field, or a 0; thus, a contradiction as any numeric solution to B's Y-field must be zebra-striped. Say both a Y and a 0 appear within the places corresponding to B's Y-field. The last place in the variable region between the Y and the 0 could be a 0, and it adjoins a 0 (at the near end of the numeric region next to the variable region). Likewise, this is a contradiction. The only remaining possibilities are for the corresponding places of A to be all Y's or zebra-striped numeric.

2. For each 0 in B, the corresponding place in A can't include the possibility of being solved as 1; thus the corresponding place can't be 1, X or Y; therefore, it must be 0. For each 1 in B, the corresponding place in A can't include the possibility of being solved as 0; thus the corresponding place can't be 0, X or Y; therefore, it must be 1.

3. Say there is a comma separating Y-fields in A ending in place $i$ and beginning in place $i + 1$, but there not a field separation between places $i$ and $i + 1$ in B; thus, places $i$ and $i + 1$ in B must be within a Y-field. Hence, there are two possible solutions of places $i$ and $i + 1$ in B; that is '01' and '10'. However, as they are in separate Y-fields in A, places $i$ and $i + 1$ could be '00', leading to a contradiction.

For the converse, we will assume that statements 1 - 3 are true. We'll show that every $\Omega^t_{d+1}$ facet that B is a face of, A is also a face of, implying that A is a face of B.

$\circ$ Each Y-field in B occupying places $i$ to $j$ is from the intersection of $Y_{i+1}$ to $Y_j$. There are two cases for A: If places $i$ through $j$ are zebra-striped numeric, then A is a face of each of $Y_{i+1}$ through $Y_j$ (plus a face of some Z-facets). If places $i$ through $j$ are all Y's, we know that these places are taken up by one or more Y-fields in A. Also, we know that there are no commas within places $i$ through $j$ in A, because we know that there aren't any field separations within places $i$ through $j$ in B. Therefore, places $i$ through $j$ lie within a single Y-field, and A is a face of each of $Y_{i+1}$ through $Y_j$.

$\circ$ Each '010' in places $i$ through $i + 2$ of B is from the intersection of $Z_i$, $Z_{i+2}$, $Y_{i+1}$, and $Y_{i+2}$. '10' in places $1$ through $2$ (if it occurs in B) is from the intersection of $Z_2$ and $Y_2$. '01' in places $d - 1$ through $d$ (if it occurs in B) is from the intersection of $Y_d$ and $Z_{d-1}$. Each other '0' in B is from the corresponding $Z_i$. Because the numeric places of B are identical in A, A is also a face of each of the facets described in this paragraph that B is a face of.

$\circ$ We have described every $\Omega^t_{d+1}$ facet that B is a face of, and shown that A is also a facet of these. Therefore, A is a face of B.