# What are the facets of the Tridiagonal Birkhoff $d$-polytope $\Omega^t_{d+1}$?

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}$?

• Why are you using HTML to format mathematical expressions instead of $\LaTeX$? – abiessu Sep 15 '14 at 18:18
• I thought I was using LaTeX. Edits to improve the format are welcome. – Dan Moore Sep 15 '14 at 18:22
• Please review my edit to ensure that I haven't introduced errors. – abiessu Sep 15 '14 at 18:23
• Looks good to me! – Dan Moore Sep 15 '14 at 18:38

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