2
$\begingroup$

Is there a generalization of unimodular matrices for non-square matrices? It is well-known that unimodular matrices guarantee an integral solution for a linear program (if the constraint matrix is unimodular).

More specifically:

Let $S$ be a discrete set $S = \{ 1,\ldots,n\}$. Define $X$ to be the set of all possible triplets $(i,j,k)$ where $i,j,k \in S$ and $i < j$ and $k \neq i$ and $k \neq j$.

For each triplet define the vector $v \in \{ 0,1\}^n$ such that $v_i = 1$, $v_j = 1$ and $v_k = -1$. Define $A$ to be the matrix of the $v$s stacked on each other. It should be of size $|X| \times n$.

Am I guaranteed to get an integral solution for a linear program:

$\max c\cdot x$ such that $Ax \le \overline{1}$ and $0 \le x \le 1$

where $\overline{1}$ is a column vector of $1$s of length $|X|$?

Maybe there is some generalization for unimodular matrices that can show this for $A$.

Thanks.

  • 0
    apparently there is a generalization -- every submatrix should be unimodular (i.e. have determinant +-1) or have determinant 0. but I am not sure if $A$ that I mention is totally unimodular.2011-06-28
  • 0
    I think it is not unimodular. You can have an Eulirean submatrix such as $(1 1 | 0 0)$ where the sum of elements is not a multiple of 4. See www.acsu.buffalo.edu/~nagi/courses/684/Unimodularity.pdf2011-06-28
  • 0
    I mean, $(1 1 | 1 -1)$.2011-06-28

1 Answers 1