Totally unimodular towards linear programming relaxation

Question

I'm currently studying about totally unimodular.

I was reading this link: https://ostad.nit.ac.ir/upload/Integer_Programming_1.pdf, from page 38-41 and I came across the statement:

'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\}.$'

I've read and understand about TU (totally unimodular) based on the link above and about LP relaxation.

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.

Answer 1

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.