# is there a generalization of unimodular matrices for non-square matrices?

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.

• 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

• @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