0
$\begingroup$

How to prove the Birkhoff-von Neumann theorem using total unimodularity? Especially the following sufficiency condition (source):

$\begin{array}{l}{\text { A matrix } A \text { is totally unimodular if no more than } 2 \text { nonzeros are in }} \\ {\text { each column, and if the rows (corresponding to an element) can be partitioned into two sets } l_{1}} \\ {\text { and } l_{2} \text { such that }} \\ {\text { – If a column (corresponding to a constraint) has two entries of the same sign, their rows are in }} \\ {\text { different sets of the partition }} \\ {\text { – If a column has two entries of different sign, their rows are in }} \\ {\text { the same set of the partition }}\end{array}$

I currently think the following partitioning of the elements satisfies the above sufficiency condition:

$\left[\begin{array}{llll}{+} & {-} & {+} & {-} \\ {-} & {+} & {-} & {+} \\ {+} & {-} & {+} & {-} \\ {-} & {+} & {-} & {+}\end{array}\right]$

where $+ $ and $-$ correspond to sets $l_1$and $l_2$ respectively.

But my confusion is the following: Elements $(1,1)$ and $(1,3)$ have the same sign in the doubly stochastic constraint which stipulates that the sum of the elements of the first row has to be exactly 1. However they are part of the same set in the above partition. So does that work?

Thank you for your help.

$\endgroup$

Your Answer

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

Browse other questions tagged or ask your own question.