TITLE: What are the facets of the Tridiagonal Birkhoff $d$-polytope $\Omega^t_{d+1}$?
QUESTION [1 upvotes]: The Birkhoff $d$-polytope $\Omega_{d+1}$ is the convex polytope in $\mathbb{R}^{d+1}$ $\times$ $\mathbb{R}^{d+1}$ of doubly stochastic matrices:
•   All matrices contained in $\Omega_{d+1}$ have non-negative entries;
•   All matrices contained in $\Omega_{d+1}$ have column and row sums equal to 1; and
•   $\Omega_{d+1}$ has $(d+1)^2$ facets given by the equations $\{A|a_{ij} = 0; 1 \le i,j \le d+1\}$
The Tridiagonal Birkhoff polytope $\Omega^t_{d+1}$ is a face of the Birkhoff polytope $\Omega_{d+1}$, such that matrix entries off the main diagonal, superdiagonal and subdiagonal are zero.
What are the facets of the Tridiagonal Birkhoff $d$-polytope $\Omega^t_{d+1}$?

REPLY [2 votes]: Every point of $\Omega_{d+1}^t$ is of the form
$$
A = \begin{bmatrix}
1 - \mu_1 & \mu_1 & 0 & 0 & \cdots & 0 \\
\mu_1 & 1 - \mu_1 - \mu_2 & \mu_2 & 0 & \cdots & 0 \\
0 & \mu_2 & 1 - \mu_2 - \mu_3 & \mu_3 & \cdots & 0 \\
\vdots & \vdots & \vdots & \ddots & \vdots & \vdots \\
0 & 0 & \cdots & \mu_{d-1} & 1 - \mu_{d-1} - \mu_d & \mu_d \\
0 & 0 & \cdots & 0 & \mu_{d} & 1 - \mu_d
\end{bmatrix}
$$
where
each $\mu_i \geq 0$ and
$\mu_i + \mu_{i+1} \leq 1$ for $1 \leq i \leq d - 1$.
The facet-defining equalities are $\mu_i = 0$ ($d$ of these)
and $\mu_i + \mu_{i+1} = 1$ ($d-1$ of these.)
(This is for $d \geq 2$. For $d = 1$, the facets are $\mu_1 = 0$ and $\mu_1 = 1$.)
I found this description in G. Dahl, "Tridiagonal doubly stochastic matrices," Linear Algebra and its Applications 390 (2004) 197–208.
{"set_name": "stack_exchange", "score": 1, "question_id": 932621}