# 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.

Addendum: A 2016 paper by Dusko Jojic uses a completely equivalent naming convention based on compositions of $$d+1$$, where the first and last part each $$\ge 2$$. Jojic's naming convention should be followed to avoid a proliferation of different naming conventions.

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

2 Dusko Jojic, Some remarks about acyclic and tridiagonal Birkhoff polytopes, Linear Algebra and its Applications 495 (2016) pp. 108-121.