We are interested in instances of this linear program (LP) that have integer optimal solutions, which hence are optimal solutions for the original ILP (Equation 2.8) as well. Totally unimodular matrices yield a prime class of linear programming problems with integral solutions. Recall that a matrix is totally unimodular if all its subdeterminants equal − 1 , 0 , or 1; in particular, each entry is − 1 , 0 , or 1. The connection between total unimodularity and linear programming is specified by the following theorem. Theorem 2.3.1. [44] Let A be an m × n totally unimodular matrix, and b ∈ Z $^{m}$. Then the polyhedron P = { x ∈ R $^{n}$| A x = b , x ≥ 0 } has integral vertices. Notice that the feasible set of the multiscale simplicial flat norm LP (Equation 2.9) has the form specified in the theorem above, with the variable vector ( x $^{+}$, x $^{−}$, s $^{+}$, s $^{−}$) in place of x . The corresponding equality constraint matrix A has the form$^{[}$ I − I B − B$^{]}$ , where I is the identity matrix and B = [ ∂$_{d}$$_{+1}$ ]. The input d -chain t is in place of the right-hand side vector b . In order to use Theorem 2.3.1 for computing the multiscale simplicial flat norm, we connect the total unimodularity of constraint matrix A and that of boundary matrix B . Lemma 2.3.2. If B = [ ∂$_{d}$$_{+1}$ ] is totally unimodular, then so is the matrix A = [ I − I B − B$^{]}$ . Proof. Starting with B , we get the matrix A by appending columns of B scaled by − 1 to its right, and appending columns with a single nonzero entry of ± 1 to its left. Both these classes of operations preserve total unimodularity [37, pg. 280]. Consequently, we get the following result on polynomial time computability of the mul- tiscale simplicial flat norm. Theorem 2.3.3. If the boundary matrix [ ∂$_{d}$$_{+1}$ ] of the finite oriented simplicial complex K is totally unimodular, then the multiscale simplicial flat norm of the set T specified as a d -chain t ∈ Z m of K can be computed in polynomial time. 24