1
$\begingroup$

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

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

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.

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