# Totally unimodular towards linear programming relaxation

I'm currently studying about totally unimodular.

'It is clear that when matrix A is totally unimodular, the linear programming relaxation solves the IP: $$\max\{cx:Ax \leq b, x \in Z_{+}^n\}.$$'

Question: However, I still do not know how do I prove the statement above?

What I know: I know that if $$A$$ is TU then $$(A, I)$$ is TU for an identity matrix $$I$$. Also, as stated in the book that

'From linear programming theory, we know that basic feasible solutions take the form:. $$x = (x_B,x_N) = (B^{-1} b, 0)$$ where $$B$$ is an $$m \times m$$ nonsingular submatrix of $$(A, I)$$ and $$I$$ is an $$m \times m$$ identity matrix.

Observation 3.1 (Sufficient Condition) If the optimal basis $$B$$ has $$\det(B) = ±1$$, then the linear programming relaxation solves IP.'

My Hypothesis: Does a TU matrix $$A$$ always have a basis B such that $$\det(B) = \pm 1$$? But if $$A$$ is TU, all its square submatrix is either 0,-1, or 1 and not 1 or -1.

Extra Note: I am working on some shortest path inner problem of a variable $$X_{ij}$$ (the original model is bi-level) where $$(i,j)$$ represents the arc in the graph. The paper stated that since the inner problem (of the bi-level) is unimodular, we can use LP relaxation in order to use KKT to turn the bi-level into single level.

What I don't know: I do not know anything about polyhedron.

• "$X_{ij}$ is unimodular" (meaning the matrix of $X$ values is unimodular) seems unlikely. Is the paper actually saying the coefficient matrix is unimodular (and, if so, is the paper saying the matrix is totally unimodular or just unimodular)?
– prubin
Sep 20, 2022 at 19:24
• You are right. I made a mistake there. What I meant is 'the inner problem is unimodular.' Sep 20, 2022 at 19:38

Does a TUM matrix $$A$$ always have a square submatrix $$B$$ with determinant $$\pm 1?$$ Technically, no. A matrix entirely filled with zeroes is TUM but obviously has no nonsingular submatrices. In the context of a linear program, the logic is as follows. Assume the problem is in canonical form (all constraints other than sign restrictions are equalities, say $$Ax=b$$). If $$A$$ is $$m\times n$$ and has full row rank, it will have at least one nonsingular $$m\times m$$ submatrix. If $$A$$ does not have full row rank, either the constraints $$Ax=b$$ are inconsistent (meaning the problem is infeasible) or you can eliminate redundant constraints until you are left with a smaller constraint matrix that does have full row rank.
Now assume that $$A$$ has full row rank. Since $$A$$ is TUM, any basis matrix $$B$$ is TUM, which means that $$B^{-1}$$ is integer-valued. It then follows that $$B^{-1}b$$ is integer-valued provided that $$b$$ is integer valued.