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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – linearman Jun 28 '11 at 1:56
  • $\begingroup$ 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 $\endgroup$ – linearman Jun 28 '11 at 2:02
  • $\begingroup$ I mean, $(1 1 | 1 -1)$. $\endgroup$ – linearman Jun 28 '11 at 2:09
1
$\begingroup$

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

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

Your Answer

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

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