Questions tagged [total-unimodularity]

A totally unimodular matrix is a matrix for which every square non-singular submatrix is unimodular.

0
votes
0answers
46 views

Is this matrix TU?

Is the following matrix $A$ totally unimodular? $$A = \begin{pmatrix} 1 & 1 & 1 & 0 \\ 0 & 1 & 1 & 1 \\ 1 & 1 & 0 &1 \end{pmatrix}$$ Recall that a matrix is ...
1
vote
1answer
52 views

General solution to linear program?

Source of the Problem The problem comes from an application in economics concerning trade between agents to maximize aggregate "wealth". More exactly, there are $m$ agents and $n$ groups and we ...
0
votes
1answer
50 views

Total Unimodularity in Integer QP

I have a Quadratic Programming problem with linear constraints. My objective is Quadratic-Convex, the constraint matrix is Totally Unimodular (similar to assignment or network flow problems), and the ...
0
votes
0answers
38 views

On Matrices that are close to Total Unimodularity

Assume we have some matrix $A$ which is totally unimodular(TU). By a well known results we have that the polyhedron $P = \{Ax\le b\}$ has integer vertices for all $b \in \mathbb{Z}^n$. My question is ...
1
vote
2answers
68 views

Is f1+f2 unimodal if f1 and f2 is monotonic?

I have recently encountered one programming problem which was reduced to find minimum value of function.Function f was sum of two functions f1 and f2 and f1 is strictly increasing and f2 is strictly ...
0
votes
0answers
32 views

Characterizations of total unimodularity

Suppose a constraint matrix $A \in \{-1,0,1\}^{m \times n}$ is totally unimodular. Then we know that every square submatrix consisting of exactly two non-zero entries per row and per column is totally ...
0
votes
1answer
309 views

If matrix $A$ is totally unimodular, then matrix $\begin{bmatrix} A &\pm A\end{bmatrix}$ is also totally unimodular

Given a totally unimodular matrix $A \in\{-1,0,1\}^{m\times n}$, show that the matrix $$\begin{bmatrix} A &\pm A\end{bmatrix}$$ is also totally unimodular. I want to prove that exchanging any two ...
0
votes
1answer
165 views

Consecutive One's and Identities, resulting on Totally Unimodular Matrix…

I'm trying to prove that a linear problem has integer extreme points. Looking at the matrix structures, I guess the easiest way to prove this is by showing that this matrix is totally unimodular. My ...
4
votes
1answer
118 views

Is this block matrix totally unimodular?

Suppose matrix $A \in \mathbb{R}^{m×n}$ has the consecutive ones property and, thus, is totally unimodular. Is the following block matrix also totally unimodular (TU)? \begin{equation} B = \begin{...
0
votes
1answer
64 views

Minors of a particular matrix?

Take an $\frac{n(n-1)}2\times n$ matrix $M$ with $0/1$ entries each row distinct each row having two $1$s. Take an $\frac{n(n-1)}2\times \frac{n(n-1)}2$ matrix $N$ with $0/1$ entries each row ...
1
vote
2answers
183 views

A totally unimodular matrix

Is there a way to test whether the following rank-$6$ matrix is totally unimodular? $$\begin{bmatrix}1& 0& -1& 0& 0& 0& 0& 0\\0& 0& 0& 0& 1& 0& -1&...
1
vote
0answers
44 views

Does this property imply total unimodularity?

I have a matrix $M$ such that every entry in $M$ is $1,-1$ or $0$. My matrix also has the following property. Let $v_i$ and $v_j$ be two columns of $M$, and let $S$ be the set of row indices $s$ such ...
0
votes
1answer
55 views

Generating a totally unimodular matrix

Is there any method to randomly generate a totally unimodular matrix? Any algorithm or code will be appreciated.
1
vote
0answers
159 views

How to prove if the following matrix is totally unimodular (TU)?

I've already solved the linear relaxation of the problem and note that a relaxed version of the problem (without integral variables) results in integer solutions. \begin{matrix}1&1&0&0&...
1
vote
1answer
62 views

Is a matrix of subset indicator totally unimodular?

Let $S=\{1,\ldots, m\}$ and $A_1, \ldots, A_n$ be subsets of S. Let $B=(b_{ij})_{m\times n} = \{0,1\}_{m\times n}$ be a matrix such that $$ b_{ij}= \begin{cases} 1 & i \in A_j \\ ...
1
vote
1answer
302 views

Is this matrix totally unimodular?

Check whether the following matrix is totally unimodular. $$A=\pmatrix{0&0&0&1&0&0&0\\ 1&-1&0&0&1&0&1\\ 0&1&-1&-1&0&0&0\\ ...
1
vote
1answer
411 views

LP relaxation solves the integer program but the constraint matrix is not totally unimodular

I am solving an integer program (IP) whose constraint matrix is not totally unimodular (TU). The linear programming (LP) relaxation and the original IP always have the same optimal solution, or the LP ...
3
votes
1answer
237 views

Adapting a proof to show that a polyhedron has integer extreme points

Prove that the polyhedron $$P =\{(x_1, \ldots , x_m, x_{m+1}): 0\leq x_m \leq 1, 0 \leq x_i \leq x_{m+1} \text{ for } i = 1, \ldots , m \}$$ has integer extreme points. My Attempt: I have a similar ...
0
votes
1answer
476 views

Proof that the incidence matrix of a laminar family is TU.

A friend and I wrote a proof for this using the consecutive ones property that I haven't seen anywhere, so I thought I would share it here. $\textit{Def:}$ A matrix has the Total-Unimodularity (TU) ...
0
votes
1answer
186 views

Total Unimodularity and partition of the rows

I have a question regarding a theorem about total unimodularity and partition of the rows of a matrix. The theorem says that given a matrix $A \in \mathbb{Z}^{m\times n}$ , A is totally unimodular ...
2
votes
1answer
277 views

Prove that a certain block combination of totally unimodular matrices is totally unimodular

I conjecture the following. Given three rectangular matrices $A$, $B$ and $C$ such that the following two block matrices $ \begin{bmatrix} A & B \\ \end{bmatrix} $ and $ \begin{bmatrix} ...
1
vote
0answers
75 views

Block matrix containing incidence matrix of bipartite graph is TU?

I have the following question: Let A by a TU matrix, then the following matrix is TU $$ \begin{pmatrix}A&&-I\\-1&\cdots&-1\end{pmatrix} $$ i.e. the block matrix composed by $A$,...
1
vote
1answer
190 views

On the definition of totally unimodular matrix

I'm a bit confused about the definition of a totally unimodular matrix, since my lecture notes states that this matrix is not totally unimodular: $$\begin{pmatrix} 1 && 0 \\ 1 && -1 \...
4
votes
2answers
318 views

Is this block matrix also totally unimodular?

Suppose matrix $A\in \mathbb R^{m\times n}$ is totally unimodular (TUM). Is the following matrix also TUM? $$ \begin{pmatrix} A & 0 & 0 \\ 0 & A & 0 \\ ...
0
votes
1answer
306 views

Adjacency matrix is totally unimodular

Prove that the adjacence matrix of a simple graph is totally unimodular... I know incidence matrices are totally unimodular because in every column there is a 1 and a -1... makes things easier. Any ...
2
votes
1answer
400 views

Show that matrix is totally unimodular

I want to show that this matrix is totally unimodular: \begin{bmatrix} 1 & 0 & 0 & 0 & 0 & 0 \\ 0 & 1 & 0 & 1 & 0 & 1 \\ 0 & 0 & 1 & 1 & ...
4
votes
1answer
9k views

Prove that the matrix is totally unimodular

Is there any (theoretic) way I can prove the matrix is totally unimodular? I have tested it by Matlab and know it is TU, however I cannot prove it. ...
0
votes
1answer
479 views

Is the product of two totally unimodular matrices again totally unimodular?

For unimodular matrices this is the case. It seems reasonable that this is also the case for totally unimodular matrices, but I couldn't find a reference for this. Does someone know why it is true ...
4
votes
1answer
2k views

How to prove in a graph $G$, its incidence matrix $A$ is totally unimodular if and only if $G$ is a bipartite graph?

I'm learning network and transportation model. The question is not from my homework. I'm just curious about: In a graph $G$, its incidence matrix $A$ is totally unimodular if and only if $G$ is a ...
0
votes
1answer
926 views

Totally unimodular matrices and identity matrices

I know that if a matrix $A$ is Totally Unimodular (TU), then the matrix $(A\; I)$ is unimodular. Can I then say that the matrix $(A\; -I)$ is also TU? ($I$ is the identity block matrix)