<p>I'm only going to talk about the constraint matrix part of the problem, I don't know much about the linear system (TDI) part.</p>

<p>Call a matrix $A$ <strong>good</strong> if $\{x|Ax\leq b,x\geq 0\}$ is a integral polytope for all integral $b$.
TUM is precisely the set of good integral matrices. This is a result by Hoffman and Kruskal. <a href="https://link.springer.com/chapter/10.1007%2F978-3-540-68279-0_3#page-1" rel="nofollow noreferrer">see this</a> for how the theorem comes about and the original paper.</p>

<p>If we relax the requirement that $A$ is integral, then we get a larger class of matrices. Call a good matrix $A$ trivial, if it is a scaling of a TUM matrix (i.e. $A=\frac{1}{k}B$ for some TUM matrix $B$ and integer $k$).</p>

<p>Sadly, I don't know of any <em>natural</em> non-trivial good matrices.</p>

<p>But there is a characterization of good matrices. A matrix $A$ is <em>$1$-regular</em> if for all non-singular square submatrix $R$, $R^{-1}$ is integral. We have the <a href="http://www.sciencedirect.com/science/article/pii/S0012365X03000955" rel="nofollow noreferrer">following by Appa and Kotnyek</a>. </p>

<blockquote>
  <p>A rational matrix $A$ is good iff $A$ is $1$-regular.</p>
</blockquote>

<p>Here is an example of a non-trivial good matrix.</p>

<p>$$\left(
\begin{array}{cc}
 \frac{1}{2} &amp; -\frac{1}{2} \\
 -\frac{1}{2} &amp; -\frac{1}{2} \\
\end{array}
\right)$$</p>

CC BY-SA 3.0
2017-04-12T08:17:14.797Z
Τhank you for the answer and the references that I was not aware of! This, together with @JoshuaGrochow comment about TDI, answer my question.
PsySp
CC BY-SA 3.0
2017-04-11T21:58:24.350Z
2017-04-11T21:58:24.350Z
Chao Xu
<p>It is well known that if a constraint matrix $A$ is total dual integral or totally unimodular, then this is a sufficient condition of integrality of the polyhedron defined by the system $Ax \leq \beta$ (provided that $\beta$ has integer entries). But it is not a necessary condition.</p>

<p>Thus my question is</p>

<blockquote>
  <p>Are there <em>natural</em> examples (from combinatorial optimization) of integral polyhedra such that their underlying constraint matrix is neither TUM nor TDI? </p>
</blockquote>

CC BY-SA 3.0
2017-04-11T16:03:31.583Z
By "underlying constraint matrix" do you mean the natural matrix defined by the facets of the polyhedron? Or are you just asking for a matrix $A$ that is not totally unimodular nor total dual integral but such that, for some $b$ (or do you want it to hold for all $b$?) $\{x : Ax \leq b\}$ is an integral polytope?
Joshua Grochow
CC BY-SA 3.0
2017-04-11T16:05:25.263Z
Also, I don't think TUM and TDI are standard enough abbreviations that it is good to use them in your title...
Joshua Grochow
CC BY-SA 3.0
2017-04-11T16:16:40.963Z
@JoshuaGrochow As for your first question, I actually ask for both: an example of an integral polyhedron where we cannot formulate it as a TUM/TDI matrix A for any vector b. As for the abbreviations, I will change them.
PsySp
CC BY-SA 3.0
2017-04-11T18:21:47.897Z
I don't think such a thing exists. I believe Giles and Pulleyblank showed that any integral polytope can be written as $\{x : Ax \leq b\}$ for some total dual integral A and integer vector b.
Joshua Grochow
CC BY-SA 3.0
2017-04-11T18:27:00.783Z
@JoshuaGrochow That's a bit surprising to me. So, TDI is  a necessary _and_ sufficient condition for integrality? If so, why it is  mentioned only as sufficient condition?
PsySp
CC BY-SA 3.0
2017-04-11T18:47:45.377Z
Because TDI is a property of a system of linear in equations specified by a pair (A, b), it is not a property of a polytope. For such a system to define an integral polytope, it suffices for the system to be TDI, but there are non-tdi systems that also define integral polytopes.
Joshua Grochow
CC BY-SA 3.0
2017-04-11T19:02:01.047Z
@JoshuaGrochow Thanks for the comments. So, a given TDI system (A,b) defines an integral polytope. That is fine and known. You claim than there are non-TDI systems that define integral polytopes. And my question is which are these polytopes, any reference for that? Same for TUM. Also, in this context, I do not understand the reference to Giles&Pulleyblank (that any integral polytope can be written as a TDI system). I am missing something but I do not know what..
PsySp
CC BY-SA 3.0
2017-04-12T04:49:52.983Z
I still don't think it's a question of "which are those polytopes", since TDI isn't a property of polytopes. Every integral polytope can be written as the solution set of some TDI system. I bet it's not hard to show that every integral polytope can also be written as the solution set of some non-TDI system: you can probably do this by taking an arbitrary linear system that defines $P$ and if it is TDI then just scale it by a random rational number; see the proof of Thm 3.2 in Giles-Pulleyblank.
Joshua Grochow
<co.combinatorics><linear-programming>
Are there specific examples of integral polyhedra that are neither Totally Unimodular nor Total Dual Integral?
PsySp
# Are there specific examples of integral polyhedra that are neither Totally Unimodular nor Total Dual Integral?

(Asked by: username_0 on 2017-04-11)

It is well known that if a constraint matrix $A$ is total dual integral or totally unimodular, then this is a sufficient condition of integrality of the polyhedron defined by the system $Ax \leq \beta$ (provided that $\beta$ has integer entries). But it is not a necessary condition.

Thus my question is

> Are there *natural* examples (from combinatorial optimization) of integral polyhedra such that their underlying constraint matrix is neither TUM nor TDI?

**Tags:** co.combinatorics, linear-programming

> **Comments:**
> **username_1**: By "underlying constraint matrix" do you mean the natural matrix defined by the facets of the polyhedron? Or are you just asking for a matrix $A$ that is not totally unimodular nor total dual integral but such that, for some $b$ (or do you want it to hold for all $b$?) $\{x : Ax \leq b\}$ is an integral polytope?  
> **username_1**: Also, I don't think TUM and TDI are standard enough abbreviations that it is good to use them in your title...  
> **username_0**: @JoshuaGrochow As for your first question, I actually ask for both: an example of an integral polyhedron where we cannot formulate it as a TUM/TDI matrix A for any vector b. As for the abbreviations, I will change them.  
> **username_1**: I don't think such a thing exists. I believe Giles and Pulleyblank showed that any integral polytope can be written as $\{x : Ax \leq b\}$ for some total dual integral A and integer vector b.  
> **username_0**: @JoshuaGrochow That's a bit surprising to me. So, TDI is  a necessary _and_ sufficient condition for integrality? If so, why it is  mentioned only as sufficient condition?  
> **username_1**: Because TDI is a property of a system of linear in equations specified by a pair (A, b), it is not a property of a polytope. For such a system to define an integral polytope, it suffices for the system to be TDI, but there are non-tdi systems that also define integral polytopes.  
> **username_0**: @JoshuaGrochow Thanks for the comments. So, a given TDI system (A,b) defines an integral polytope. That is fine and known. You claim than there are non-TDI systems that define integral polytopes. And my question is which are these polytopes, any reference for that? Same for TUM. Also, in this context, I do not understand the reference to Giles&Pulleyblank (that any integral polytope can be written as a TDI system). I am missing something but I do not know what..  
> **username_1**: I still don't think it's a question of "which are those polytopes", since TDI isn't a property of polytopes. Every integral polytope can be written as the solution set of some TDI system. I bet it's not hard to show that every integral polytope can also be written as the solution set of some non-TDI system: you can probably do this by taking an arbitrary linear system that defines $P$ and if it is TDI then just scale it by a random rational number; see the proof of Thm 3.2 in Giles-Pulleyblank.  

---

## 1 answers

### Answer by username_2 on 2017-04-11. Score: 4 | Accepted answer

I'm only going to talk about the constraint matrix part of the problem, I don't know much about the linear system (TDI) part.

Call a matrix $A$ **good** if $\{x|Ax\leq b,x\geq 0\}$ is a integral polytope for all integral $b$.
TUM is precisely the set of good integral matrices. This is a result by Hoffman and Kruskal. [see this](https://link.springer.com/chapter/10.1007%2F978-3-540-68279-0_3#page-1) for how the theorem comes about and the original paper.

If we relax the requirement that $A$ is integral, then we get a larger class of matrices. Call a good matrix $A$ trivial, if it is a scaling of a TUM matrix (i.e. $A=\frac{1}{k}B$ for some TUM matrix $B$ and integer $k$).

Sadly, I don't know of any *natural* non-trivial good matrices.

But there is a characterization of good matrices. A matrix $A$ is *$1$-regular* if for all non-singular square submatrix $R$, $R^{-1}$ is integral. We have the [following by Appa and Kotnyek](http://www.sciencedirect.com/science/article/pii/S0012365X03000955).

> A rational matrix $A$ is good iff $A$ is $1$-regular.

Here is an example of a non-trivial good matrix.

$$\left(
\begin{array}{cc}
\frac{1}{2} & -\frac{1}{2} \\
-\frac{1}{2} & -\frac{1}{2} \\
\end{array}
\right)$$

> **Comments:**
> **username_0**: Τhank you for the answer and the references that I was not aware of! This, together with @JoshuaGrochow comment about TDI, answer my question.  

---

