Questions tagged [total-unimodularity]

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

30 questions
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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{...
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 ...
183 views

302 views

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 \\ ...
306 views

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 ...
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 & ...
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. ...
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 ...
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 ...
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)