1
$\begingroup$

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))$.

$\endgroup$
1
$\begingroup$

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$. TriBirk face chart

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:

sequence chart

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.