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

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
    but is the matrix I presented totally unimodular? or am I right in believing it isn't.2011-06-28
  • 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