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
    I mean, $(1 1 | 1 -1)$.2011-06-28

1 Answers 1

1

I think that in your comments you are referring to the notion of total unimodularity; as Wikipedia (http://en.wikipedia.org/wiki/Unimodular_matrix) puts it, "A totally unimodular matrix is a matrix for which every square non-singular submatrix is unimodular." A weaker extension of unimodularity to non-square matrices would be to ask that the matrix be of full rank (that is to say, rank equal to the smaller of the number of rows and the number of columns), and that every square submatrix of that rank should be unimodular. This is consistent with the definition given at http://www.ams.jhu.edu/~castello/362/Handouts/UnimodularMatrices.pdf

  • 0
    @linearman, I think you are right. One row of your matrix is $(1\ 1\ -1\ 0\dots0)$, another is $(1\ -1\ 1\ 0\dots0)$, and as you note you get a submatrix \pmatrix{1&1\cr1&-1\cr} with determinant $-2$.2011-06-29