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

114 Views Asked by At

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

1

There are 1 best solutions below

0
On BEST ANSWER

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.