Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
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. –  linearman Jun 28 '11 at 1:56
    
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.pdf –  linearman Jun 28 '11 at 2:02
    
I mean, $(1 1 | 1 -1)$. –  linearman Jun 28 '11 at 2:09

1 Answer 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

share|improve this answer
    
but is the matrix I presented totally unimodular? or am I right in believing it isn't. –  linearman Jun 28 '11 at 23:54
    
@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$. –  Gerry Myerson Jun 29 '11 at 1:51

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.