# Count and description of vertices of certain faces - called MTBFs - of the Tridiagonal Birkhoff polytope $\Omega^t_{d+k}$

For $k \ge 1$, $d \ge 2$ and $k \le d - 1$, let ${}^f_d\Omega^t_{d+k} (d;c_k(d - 1))$ be the intersection of $k - 1$ facets of the Tridiagonal Birkhoff polytope $\Omega^t_{d+k}$ with equations:

$a_{n_i,n_i} = 0$ for $i = 1, ... k - 1$, where:

$n_1 \gt 2$; $n_{i+1} \gt n_i + 1$ for i = 1, ... k - 2; $n_{k-1} \lt d + k - 1$

$c_k(d - 1)$ is a composition (i.e., ordered partition) of $d - 1$ with k parts; the first part equal to $n_1 - 2$ (the number of unconstrained main diagonal elements from $a_{2,2}$ through $a_{n_1-1,n_1-1})$, the last ($k$th) part equal to $d + k - 1 - n_{k-1}$, and otherwise, the $i$th part equal to $n_i - n_{i-1} - 1$.

In the case $k = 1$, ${}^f_d\Omega^t_{d+k} (d;c_k(d - 1))$ = $\Omega^t_{d+1}$ and $c_1(d - 1) = (d - 1)$ (a composition with one part).

Thus, this question proposes a naming convention for the described faces of $\Omega^t_{d+k}$ based on compositions of $d - 1$. To facilitate reference, we will call these faces the Main Tridiagonal Birkhoff Faces, or MTBFs, for two reasons:

• they are associated with the main diagonal; and
• it is conjectured that all Tridiagonal Birkhoff faces are MTBFs, or rectangular products of MTBFs.

Of the $d + k - 2$ main diagonal elements associated with facets, $d - 1$ are unconstrained and there are $k - 1$ isolated separations within the unconstrained main diagonal elements, which uniquely corresponds to a composition of $d - 1$ with k parts. The question is to:

a) Show that ${}^f_d\Omega^t_{d+k} (d;c_k(d - 1))$ has dimension d.

b) Ennumerate and describe the vertices of ${}^f_d\Omega^t_{d+k} (d;c_k(d - 1))$.

We can answer the question in the reverse order, using a description of the vertices to ennumerate them using math induction, and then to show that ${}^f_d\Omega^t_{d+k} (d;c_k(d - 1))$ has dimension d.

Dahl 1 has pointed out that the vertices of the tridiagonal Birkhoff polytope can be written as direct sums of J and K, where:

$J$ = $\begin{bmatrix} 1 \\ \end{bmatrix}$

$K$ = $\begin{bmatrix} 0 & 1 \\ 1 & 0 \\ \end{bmatrix}$

To represent such a direct sum, we'll use a string of $J$'s & $K$'s - e.g., $JKJ$ represents the direct sum of $J$, $K$ and $J$. We'll say that $J$ has length $1$ and $K$ has length $2$ - i.e., the number of positions taken on the main diagonal. Thus, the vertices of $\Omega^t_{n}$ are represented by all strings of $J$ and $K$ of length $n$.

Given the constraint $a_{n,n} = 0$ for $2 \lt n \lt d + k - 1$ in $\Omega^t_{d+k}$, we note that a vertex of the resulting face cannot have $J$ in position $n$ - in that case $a_{n,n} = 1$. Equivalently, it must be the case that either $K$ occupies positions $n - 1$ and $n$, or $K$ occupies positions $n$ and $n + 1$. We note that any composition of a positive integer can be uniquely derived from a sequence of compositions developed using two operations:

$\bullet$ Append, where a part equal to $1$ is appended to the end of the preceding composition - the composition obtained by appending a new part to $c_k(n)$ is denoted $c_k(n)A$; and

$\bullet$ Extend, where the last part of the preceding composition is incremented by $1$ - the composition obtained by extending the last part of $c_k(n)$ is denoted $c_k(n)E$.

(This sequence of compositions begins with an append operation, producing $(1)$ - the composition of $1$ with $1$ part.)

Beginning with the problem's initial case as stated ($d$ = $2$, $k$ = $1$), we have ${}^f_2\Omega^t_{3} (2;1)$ = $\Omega^t_{3}$, a triangle with vertices $JJJ$, $JK$, and $KJ$. We will recursively define a function $v$ mapping the set of all compositions of a (positive) integer to $\mathbb{Z}^+$, giving the number of vertices of the tridiagonal Birkhoff face associated with each composition of a positive integer. We have $v(1) = 3$. We also define functions $v_J$ and $v_K$ giving the number of vertices of the tridiagonal Birkhoff face associated with each composition of a positive integer ending with $J$, and ending with $K$, respectively. So, $v(c) = v_J(c) + v_K(c)$ for all compositions $c$. We have $v_J(1) = 2$ and $v_K(1) = 1$.

Say we have determined the vertices of the tridiagonal Birkhoff face ${}^f_{d}\Omega^t_{d+k} (d;c_k(d-1))$. Based on the discussion above, the vertices of ${}^f_{d}\Omega^t_{d+k} (d;c_k(d-1))$ are all the vertices of $\Omega^t_{d+k}$ which do not have $J$ in position $n_i$ for $i = 1$ through $k - 1$ - alternatively, either positions $n_i - 1$ and $n_i$ are occupied by $K$, or positions $n_i$ and $n_i + 1$ are occupied by $K$.

We select a vertex $v_1 \in \mathbb{R}^{(d+k+1)^2}$ of ${}^f_{d+1}\Omega^t_{d+1+k} (d+1;c_k(d-1)E)$, considering two cases:

Case 1) $v_1$ ends with $J$ - i.e., position $d + k + 1$ is $J$. Position $n_i$ of $v_1$ is not $J$ for $i = 1$ through $k - 1$; therefore, the first $d + k$ positions of $v_1$ must match exactly with a vertex of ${}^f_{d}\Omega^t_{d+k} (d;c_k(d-1))$. Conversely, starting with a vertex of ${}^f_{d}\Omega^t_{d+k} (d;c_k(d-1))$, adding $J$ to the end produces a vertex of ${}^f_{d+1}\Omega^t_{d+1+k} (d+1;c_k(d-1)E)$. Therefore $v_J(c_k(d-1)E)$ = $v(c_k(d-1))$.

Case 2) $v_1$ ends with $K$- i.e., positions $d + k$ through $d + k + 1$ are $K$. First, we note that the maximum value for $n_{k-1}$ is $d + k - 2$, corresponding to the case where the final part of $c_k(d-1)$ is $1$. Either $K$ occupies positions $n_i-1$ and $n_i$, or $K$ occupies positions $n_i$ and $n_i+1$ for $i = 1$ through $k - 1$; therefore, the first $d + k - 1$ positions of $v_1$ must match exactly with those of a vertex of ${}^f_{d}\Omega^t_{d+k} (d;c_k(d-1))$. As only the final position $d + k$ remains in the identified vertex of ${}^f_{d}\Omega^t_{d+k} (d;c_k(d-1))$, this final position $d + k$ must be $J$. Conversely, starting with a vertex of ${}^f_{d}\Omega^t_{d+k} (n;c_k(d-1))$ which ends with $J$, replacing the final $J$ with $K$ produces a vertex of ${}^f_{d+1}\Omega^t_{d+1+k} (d+1;c_k(d-1)E)$. Therefore $v_K(c_k(d-1)E)$ = $v_J(c_k(d-1))$.

Combining the two cases, $v(c_k(d-1)E)$ = $v_J(c_k(d-1)E) + v_K(c_k(d-1)E)$ = $v(c_k(d-1)) + v_J(c_k(d-1))$

Now we select a vertex $v_2 \in \mathbb{R}^{(d+k+2)^2}$ of ${}^f_{d+1}\Omega^t_{d+1+k+1} (d+1;c_k(d-1)A)$. We note that $a_{d+k,d+k} = 0$, with $a_{d+k+1,d+k+1}$ representing the final part of $c_k(d-1)A$ equal to $1$. Therefore, position $d + k$ is not occupied by $J$; equivalently either positions $d + k - 1$ through $d + k$ are occupied by $K$, or positions $d + k$ through $d + k + 1$ are occupied by $K$. We consider three cases:

Case 1) $v_2$ ends with $JJ$ - i.e., positions $d + k + 1$ and $d + k + 2$ are both $J$. Position $n_i$ of $v_2$ is not $J$ for $i = 1$ through $k - 1$; therefore, the first $d + k$ positions of $v_2$ must match exactly with a vertex of ${}^f_{d}\Omega^t_{d+k} (n;c_k(d-1))$. Furthermore, positions $d + k - 1$ and $d + k$ must be occupied by $K$, because position $d + k + 1$ is $J$. Conversely, starting with a vertex of ${}^f_{d}\Omega^t_{d+k} (n;c_k(d-1))$ ending with $K$, adding $JJ$ to the end produces a vertex of ${}^f_{d+1}\Omega^t_{d+1+k+1} (d+1;c_k(d-1)A)$.

Case 2) $v_2$ ends with $KJ$ - i.e., positions $d + k$ through $d + k + 1$ are occupied by $K$ and position $d + k + 2$ by $J$. First, we note that the maximum value for $n_{k-1}$ is $d + k - 2$, corresponding to the case where the final part of $c_k(d-1)$ is $1$. Either $K$ occupies positions $n_i-1$ and $n_i$, or $K$ occupies positions $n_i$ and $n_i+1$ for $i = 1$ through $k - 1$; therefore, the first $d + k - 1$ positions of $v_2$ must match exactly with those of a vertex of ${}^f_{n}\Omega^t_{n+k} (n;c_k(n-1))$. As only the final position $d + k$ remains in the identified vertex of ${}^f_{n}\Omega^t_{n+k} (n;c_k(n-1))$, this final position $d + k$ must be $J$. Note that position $d + k -1$ can be $J$ or not; the $k$th constraint is satisfied by having positions $d + k$ through $d + k + 1$ occupied by $K$. Conversely, starting with a vertex of ${}^f_{d}\Omega^t_{d+k} (n;c_k(d-1))$ which ends with $J$, replacing the final $J$ with $KJ$ produces a vertex of ${}^f_{d+1}\Omega^t_{d+1+k+1} (d+1;c_k(d-1)A)$.

Combining the first two cases, we have $v_J(c_k(d-1)A)$ = $v_K(c_k(d-1)) + v_J(c_k(d-1))$ = $v(c_k(d-1))$.

Case 3) $v_2$ ends with $K$ - i.e., positions $d + k + 1$ and $d + k + 2$ are occupied by $K$. Position $n_i$ of $v_2$ is not $J$ for $i = 1$ through $k - 1$; therefore, the first $d + k$ positions of $v_2$ must match exactly with a vertex of ${}^f_{d}\Omega^t_{d+k} (n;c_k(d-1))$. Furthermore, positions $d + k - 1$ and $d + k$ must be occupied by $K$, because positions $d + k$ through $d + k + 1$ are not occupied by a $K$-block. Conversely, starting with a vertex of ${}^f_{d}\Omega^t_{d+k} (n;c_k(d-1))$ ending with $K$, adding $K$ to the end produces a vertex of ${}^f_{d+1}\Omega^t_{d+1+k+1} (d+1;c_k(d-1)A)$. Therefore, $v_K(c_k(d-1)A)$ = $v_K(c_k(d-1))$.

Combining all cases, we first note that $v_J(c_k(d-1)E) = v_J(c_k(d-1)A) = v(c_k(d-1))$. As a result, for all $d \ge 2$, ${}^f_{d}\Omega^t_{d+k} (n;c_k(d-1))$ has at least one vertex ending with $J$. Combining the three append cases, $v(c_k(d-1)A)$ = $v_J(c_k(d-1)A) + v_K(c_k(d-1)A)$ = $v(c_k(d-1)) + v_K(c_k(d-1))$. Combining Extend Case $2$ and Append Case $3$, plus the fact that ${}^f_2\Omega^t_{3} (2;1)$ has vertex $JK$ ending with a $K$, we conclude that for all $d \ge 2$, ${}^f_{d}\Omega^t_{d+k} (n;c_k(d-1))$ has at least one vertex ending with $K$.

Thus far, the smallest tridiagonal Birkhoff face identified is the triangle ${}^f_2\Omega^t_{3} (2;1)$; we are in need of a point and a line segment to include in the set of (nonempty) tridiagonal Birkhoff faces. We will extrapolate the naming convention by defining ${}^f_0\Omega^t_{1} (0;-1)$ = $\Omega^t_{1}$ (a point), and ${}^f_1\Omega^t_{2} (1;0)$ = $\Omega^t_{2}$ (a line segment).We will add (-1) and (0) to the domain of $v$, $v_J$ and $v_K$.

For a given composition $c_k(d - 1)$, define the unique sequence $c_n$ as the sequence beginning with $(-1), (0), (1)$ ($n$ taking the values $-1$, $0$ and $1$), which proceeds via the append and extend operations to produce $c_k(d-1)$. After $(-1), (0), (1)$, the number of vertices equals the sum of the vertices from two of the preceding compositions; which two depending on whether append or extend operations are applied.

Combining preceding cases, if the operation acting on $c_n$ is extend, then $v(c_{n+1}) = v(c_n) + v(c_{n-1})$. If, however, the operation acting on $c_n$ is append, then $v(c_{n+1})$ equals $v(c_n)$ plus the number of vertices added in the second term the most recent time the sequence had an extend operation. Thus, we write the needed formulas by introducing a placeholder variable $p_{i}$.

Begin with $p_{1}$ = $-1$. We have:

$v(c_{n+1}) = v(c_n) + v(c_{p_{n+1}})$.

(For both extend and append, the first term $v(c_n) = v_J(c_{n+1})$, while the second term $v(c_{p_{n+1}}) = v_K(c_{n+1})$).

If the operation acting on $c_n$ is extend, then $p_{n+1}$ = $n - 1$.

If the operation acting on $c_n$ is append, then $p_{n+1}$ = $p_n$.

Possible composition sequence elements through $n = 4$ are shown below, along with the number of vertices, the terms of the recursive formula, and the placeholder $p_n$.

Some sequences of vertex counts associated with periodic compositions of integers are in the Online Encyclopedia of Integer Series (OEIS). For example, starting with $v(0)$ = $2$, and continuing with compositions whose parts are all $2$ produces the sequence $2$, $5$, $12$, $29$, $70$, $169$... (i.e., the Pell numbers - OEIS sequence A000129). Here is a chart of sequences of vertex counts produces by repeating the same part sequences in compositions of integers:

We will now address question part (a). We note that as the intersection of $k - 1$ facets of $\Omega^t_{d+k}$, ${}^f_d\Omega^t_{d+k} (d;c_k(d - 1))$ has dimension at most $d$. We will show that ${}^f_d\Omega^t_{d+k} (d;c_k(d - 1))$ has dimension at least $d$ by math induction. ${}^f_0\Omega^t_{1} (0;-1)$, ${}^f_1\Omega^t_{2} (1;0)$, and ${}^f_2\Omega^t_{3} (2;1)$ have dimension 0, 1 and 2, respectively. Say we have proven that ${}^f_d\Omega^t_{d+k} (d;c_k(d - 1))$ has dimension $d$ for all compositions of $d - 1$ $c_k(d-1)$, where $d \ge 2$. Then two cases cover all compositions of $d$; given a composition of $d$ with $k$ parts, it's either $c_k(d-1)E$ or $c_{k-1}(d-1)A$ for some composition of $d - 1$.

Case $c_k(d-1)E$: The operation of adding a $J$ to the end is an isomorphism mapping the vertices of ${}^f_d\Omega^t_{d+k} (d;c_k(d - 1))$ to a subset of the vertices of ${}^f_{d+1}\Omega^t_{d+1+k} (d+1;c_k(d - 1)E)$; hence ${}^f_{d+1}\Omega^t_{d+1+k} (d+1;c_k(d - 1)E)$ has at least dimension $d$. Additionally, ${}^f_{d+1}\Omega^t_{d+1+k} (d+1;c_k(d - 1)E)$ has at least one vertex ending with $K$, which is affine to the set of previously determined vertices, so ${}^f_{d+1}\Omega^t_{d+1+k} (d+1;c_k(d - 1)E)$ has dimension at least $d + 1$.

Case $c_{k-1}(d-1)A$: In this case, $k \ge 2$. Like the preceding case, we'll identify a set of ${}^f_{d+1}\Omega^t_{d+1+k} (d+1;c_{k-1}(d - 1)A)$ vertices mapped via an isomorphism from the vertices of ${}^f_d\Omega^t_{d+k-1} (d;c_{k-1}(d - 1))$. Begin by representing ${}^f_d\Omega^t_{d+k-1} (d;c_{k-1}(d - 1))$ in $\mathbb{R}^{(d+1+k)^2}$ with its nonzero coordinates confined to the first $d + k - 1$ rows and columns; the last two rows and columns all zero.

Because it's tridiagonal and symmetric, we can represent the points of ${}^f_{d+1}\Omega^t_{d+1+k} (d+1;c_{k-1}(d - 1)A)$ by taking the $2d + 2k + 1$ elements from the zigzag line covering the main diagonal and superdiagonal (in the order $a_{1,1}$, $a_{1,2}$, $a_{2,2}$, $a_{2,3}$, ... $a_{d+k,d+k+1}$, $a_{d+k+1,d+k+1}$); calling this representation $T$, mapping symmetric tridiagonal $(d+1+k)^2$ matrices over $\mathbb{R}$ to $\mathbb{R}^{2d+2k+1}$. $T^{-1}$ sets the subdiagonal elements equal to the corresponding superdiagonal elements, producing a tridiagonal symmetric matrix.

Let $L_0$ = $\begin{bmatrix} 1&0&0&0&1&0 \\ 0&0&1&0&0&1 \\ 0&0&0&1&0&1 \\ 0&1&0&1&0&0 \\ 0&0&0&0&1&0 \\ 0&0&0&0&0&1 \\ \end{bmatrix}$

Let $L$ be the direct sum $I_{2d+2k-5} \oplus L_0$, where $I$ is the identity matrix. $L_0$ is nonsingular, and of course $I_{2d+2k-5}$ is nonsingular; thus $L$ is nonsingular, and thus represents an isomorphism on $\mathbb{R}^{2d+2k+1}$.

The first row of $L_0$ corresponds to taking ${}^f_d\Omega^t_{d+k-1} (d;c_{k-1}(d - 1))$ vertices ending with $K$ and just adding a $K$ to the end. The second row of $L_0$ corresponds to taking ${}^f_d\Omega^t_{d+k-1} (d;c_{k-1}(d - 1))$ vertices ending with $J$ and replacing the final $J$ with $KJ$. All $J$'s and $K$'s preceding the final character in each vertex are preserved. As discussed in Append cases $2$ and $3$, the mapped vertices $vTLT^{-1}$ are vertices of ${}^f_{d+1}\Omega^t_{d+1+k} (d+1;c_{k-1}(d - 1)A)$. Because isomorphisms preserve combinatorial type, the image of ${}^f_d\Omega^t_{d+k-1} (d;c_{k-1}(d - 1))$ under $TLT^{-1}$ has the combinatorial type of ${}^f_d\Omega^t_{d+k-1} (d;c_{k-1}(d - 1))$, and thus has dimension $d$.

All of the vertices of ${}^f_{d+1}\Omega^t_{d+1+k} (d+1;c_{k-1}(d - 1)A)$ in the image of ${}^f_d\Omega^t_{d+k-1} (d;c_{k-1}(d - 1))$ under $TLT^{-1}$ have $a_{d+k,d+k} = 0$. As we know that ${}^f_d\Omega^t_{d+k-1} (d;c_{k-1}(d - 1))$ has a vertex ending with $K$, we know that taking that vertex and adding $JJ$ to the end produces a vertex of ${}^f_{d+1}\Omega^t_{d+1+k} (d+1;c_{k-1}(d - 1)A)$. This vertex is affine to the previously identified vertices of ${}^f_{d+1}\Omega^t_{d+1+k} (d+1;c_{k-1}(d - 1)A)$; hence ${}^f_{d+1}\Omega^t_{d+1+k} (d+1;c_{k-1}(d - 1)A)$ has dimension at least $d + 1$.

Finally, there are two notable special cases. First, as noted in the question, when $k = 1$, you have ${}^f_d\Omega^t_{d+k} (d;c_k(d - 1))$ = $\Omega^t_{d+1}$, corresponding to a single-part composition of $d - 1$. In the case $k = d - 1$, $c_k(d - 1)$ is a composition of $d - 1$ into $d - 1$ parts each equal to $1$. In that case, ${}^f_d\Omega^t_{d+k} (d;c_k(d - 1))$ has $d + 1$ vertices and dimension $d$, and is thus a simplex.

1 Geir Dahl, Tridiagonal doubly stochastic matrices, Linear Algebra and its Applications 390 (2004) pp. 197-208.