# Questions tagged [total-unimodularity]

The total-unimodularity tag has no usage guidance.

13
questions

**2**

votes

**0**answers

68 views

### Linear forms and the second Voronoi decomposition

This is not my area of expertise, so forgive me if the question is a bit naive. Given a collection of vectors $v_1,\ldots,v_d$ in $\mathbb{R}^n$ (with $d\geq n$), there is a corresponding set of ...

**3**

votes

**0**answers

44 views

### Modular counting of integral points under sparse non-negativity

Given a polyhedron
$$Ax\geq b$$
where every entry of $A,b$ are non-negative and $A\in\{0,1\}^{m\times n}$ and there are $O(1)$ (say $\leq8$) non-negative entries per row of $A$ is it possible to ...

**1**

vote

**2**answers

122 views

### Examples of matrices with all subdeterminants bounded away from $0$

Does there exist examples of $m \times n$ matrices with $m > n$ with the property that the determinant of every $n \times n$ submatrix is at least $1$ in absolute value? (The $1$ can be replaced by ...

**1**

vote

**0**answers

121 views

### total unimodularity of a matrix

Let G be the node-arc incidence matrix of a given directed network (rows of $G$ correspond to nodes and its columns correspond to arcs). Let $B_1,\dots, B_K$ denote a partition of the nodes of the ...

**4**

votes

**0**answers

86 views

### Totally Unimodular matrix edited from ordinary matrix

Given a matrix $M\in\{0,1\}^{m\times n}$ is there an algorithm to tell if we can convert some of $1$s to $-1$s and make $M$ Totally Unimodular and output such a Totally Unimodular in polynomial in $mn$...

**1**

vote

**1**answer

194 views

### Is this totally unimodular family?

Is it possible to prove this matrix family only contains totally unimodular matrices?
The matrix has dimensions $\frac{3n(n-1)}2$ rows and $n+\frac{n(n-1)}2$ columns.
To every pair $(i,i')$ with $1\...

**3**

votes

**1**answer

700 views

### Under what conditions does an Integer Programming problem run in polynomial time?

Given $AX\leq B$ where $A\in\Bbb Z^{m\times n}$,$B\in\Bbb Z^m$ finding $X\in\Bbb Z^n$ where $m\geq n$ is the integer programming problem. If $A$ is totally unimodular then the problem is solvable in ...

**2**

votes

**1**answer

622 views

### What does the basis of the null space of the constraint matrix of a flow problem look like?

Consider a directed graph $G=(V,\mathbb{A})$ and a set of flow constraints of the following form:
$$ \sum_{(u,v)\in\mathbb{A}}x_{u,v} - \sum_{(v,u)\in \mathbb{A}}x_{v,u} = 0 \forall v \in V$$
...

**9**

votes

**1**answer

3k views

### Inverse of a totally unimodular matrix

A unimodular matrix $M$ is a square integer matrix having determinant $+1$ or $−1$.
A totally unimodular matrix (TU matrix) is a matrix for which every square non-singular submatrix is unimodular. A ...

**1**

vote

**0**answers

489 views

### Totally unimodular Matrices

A matrix is totally uni-modular if the determinant of any (square) sub-matrix is {+1, 0, -1}. My question is, "Is there a way to transform(linear or non) a general matrix into a totally uni-modular ...

**8**

votes

**1**answer

5k views

### Proving that a binary matrix is totally unimodular

I'm working on a set of problems for which I can formulate binary integer programs. When I solve the linear relaxations of these problems, I always get integer solutions. I would like to prove that ...

**3**

votes

**1**answer

704 views

### When is a triangular matrix totally unimodular?

I have an {0,1}, invertible, triangular matrix, that I would like to show to be totally unimodular. Are there any known results on the total unimodularity of classes of triangular matrices?

**16**

votes

**2**answers

2k views

### Has anyone implemented a recognition algorithm for totally unimodular matrices?

One of the consequences of Seymour's characterization of regular matroids is the existence of a polynomial time recognition algorithm for totally unimodular matrices (i.e. matrices for which every ...