2026-09-08

Recall the repair ILP objective $F:{\mathbb{Z}}^n\to \mathbb{R}$ defined by

$$F(d)=\Vert w\odot (Bd-r){\Vert }_1+\lambda \Vert v\odot d{\Vert }_1$$

where

$$r=\lceil x^{+}\rceil -\lceil x^{-}\rceil -B(\lceil y^{+}\rceil -\lceil y^{-}\rceil )-c.$$

Recall that we found that

$$\lambda \Vert v\odot d{\Vert }_1\le \Vert w\odot r{\Vert }_1,$$

i.e.,

$$\lambda \sum _{i=1}^n{v}_i|d_i|\le |w\odot r{\Vert }_1.$$

Notice then that

$$\lambda \Vert v\odot d{\Vert }_1\ge \lambda \sum _{i=1}^n|d_i|\underset{j}{\min }{v}_i⟹\Vert d{\Vert }_1\le \frac{\Vert w\odot r{\Vert }_1}{\lambda {\min }_j{v}_j}⟹|d_i|\le \frac{\Vert w\odot r{\Vert }_1}{n\lambda {\min }_j{v}_j},$$

i.e., $d$ can be restricted to a hyperrectangle.

Proposition: Let $z_{LP}$ be the optimal objective value to the LP relaxation of the flat norm and $z$ the objective value obtained by taking the ceiling of $y^{\pm }$ and recomputing $x$. Then it follows that

$$0\le z-z_{LP}\le w^{\top }|B({\delta }^{+}-{\delta }^{-})|+\lambda v^{\top }({\delta }^{+}+{\delta }^{-}).$$

Proof. Let ${\delta }^{\pm }=\lceil y^{\pm }\rceil -y^{\pm }$ and notice that $0<{\delta }^{\pm }<1$. Moreover,

$$|(B({\delta }^{+}-{\delta }^{-}){)}_i|=\left|\sum _j{B}_{ij}({\delta }_j^{+}-{\delta }_j^{-})\right|\le \sum _j|B_{ij}||{\delta }_j^{+}-{\delta }_j^{-}|=\sum _j|B_{ij}|({\delta }_j^{+}+{\delta }_j^{-}).$$

Therefore, it follows that

$$\begin{array}{rl}z-z_{LP}& =\left[w^{\top }|c+B(\lceil y^{+}\rceil -\lceil y^{-}\rceil )|+\lambda v^{\top }(\lceil y^{+}\rceil +\lceil y^{-}\rceil )\right]-\left[w^{\top }|c+B(y^{+}-y^{-})|+\lambda v^{\top }(y^{+}+y^{-})\right]\\ & =w^{\top }\left[|c+B(\lceil y^{+}\rceil -\lceil y^{-}\rceil )|-|c+B(y^{+}-y^{-})|\right]+\lambda v^{\top }({\delta }^{+}+{\delta }^{-})\\ & \le w^{\top }|B({\delta }^{+}-{\delta }^{-})|+\lambda v^{\top }({\delta }^{+}+{\delta }^{-})\\ & \le w^{\top }|B|({\delta }^{+}+{\delta }^{-})+\lambda v^{\top }({\delta }^{+}+{\delta }^{-})\\ & =(|B{|}^{\top }w+\lambda v{)}^{\top }({\delta }^{+}+{\delta }^{-}).\square \end{array}$$

---

Theorem 1: If $B={\partial }_p$ is totally bimodular, then the flat norm is solvable in strongly polynomial time.

Proof. According to Artmann et al., an ILP of the form $\max \{c^{\top }x:Ax\le b,x\in {\mathbb{Z}}^n\}$ is solveable in strongly polynomial time if every $n\times n$ submatrix of $A$ has absolute determinant at most 2. Write $A=\left[\begin{array}{cc}I& A^{\prime }\end{array}\right]$ with $A^{\prime }=\left[\begin{array}{ccc}-I& -B& B\end{array}\right]$ and set $u=(x^{-},y^{+},y^{-})\in {\mathbb{Z}}^d$ where $d=m+2n$. We can recover $x^{+}$ by $x^{+}=b-A^{\prime }u$. In order to ensure that $x^{+}\ge 0$, we need that $A^{\prime }u\le b$. As a result, we can rewrite the flat norm ILP as

$$\begin{array}{rlr}& \text{minimize}& w^{\top }b+(\left[\begin{array}{ccc}{w}^{\top }& \lambda v^{\top }& \lambda v^{\top }\end{array}\right]-w^{\top }{A}^{\prime })u\\ & \text{subject to}& \left[\begin{array}{c}{A}^{\prime }\\ -I_d\end{array}\right]u\le \left[\begin{array}{c}b\\ 0\end{array}\right]\\ & & u\in {\mathbb{Z}}^d.\end{array}$$

Denote by $G$ the constraint matrix, which has full column rank. Consider a $d\times d$ submatrix $G^{\prime }$ by choosing rows $Z$ of $A^{\prime }$ and rows $S$ of $-I_d$ where $|Z|+|S|=d$ and $Z\ne \varnothing$. We claim that

$$\det G^{\prime }=\pm \det A^{\prime }[Z,[d]\setminus S].$$

Indeed, proceed via induction on $d$. If $d=3$, then it follows that

$$G=\left[\begin{array}{ccc}-1& -\sigma & \sigma \\ -1& 0& 0\\ 0& -1& 0\\ 0& 0& -1\end{array}\right]$$

for some $\sigma \in \mathbb{Z}$. The result follows by expanding along rows of $S$ until we get a $1\times 1$ matrix. Consider then a $(d+1)\times (d+1)$ submatrix $G^{\prime }$ of $G$. Select any identity row to expand upon, resulting in a $d\times d$ submatrix $H$. Thus, it follows by the induction hypothesis that

$$\det G^{\prime }=\pm \det H=\pm \det A^{\prime }[Z,[d]\setminus S].$$

A similar argument may be done on the columns of $A^{\prime }$. Thus, we get that

$$\max |\text{m×m minor of G}|=\max |\text{m×m minor of A}|=\underset{Z,T}{\max }|\det B[Z,T]|.$$

Therefore, the flat norm is solveable in strongly polynomial time if $B$ is totally bimodular. $\square$

Question: Under what conditions can we ensure that $A$ is totally bimodular?

Quick Recap of Relative Homology

Consider a subcomplex $A\subset X$ of a simplicial complex $X$. Then $C_p(A)$ is the subgroup of $C_p(X)$ consisting of chains that live in $A$. We define the quotient chain group

$$C_p(X,A)=C_p(X)/C_p(A)$$

which is the free abelian group generated by the $p$-simplices of $X$ that are not in $A$. Because $\partial C_p(A)\subseteq C_{p-1}(A)$, it follows that

$$\cdots \to C_p(X,A)\stackrel{{\partial }_p}{\to }{C}_{p-1}(X,A)\to \cdots$$

forms a chain complex. Thus, we can define

$$H_p(X,A)=\text{Ker}({\partial }_p)/\text{Im}({\partial }_{p+1})$$

to be the $p$-th relative homology group of the pair $(X,A)$. More concretely, a class in $H_p(X,A)$ is represented by a chain $c\in C_p(X)$ with $\partial c\in C_{p-1}(A)$ and is identified with $c^{\prime }\in C_p(X)$ if

$$c-c^{\prime }=\partial b+a$$

for some $b\in C_{p+1}(X)$ and $a\in C_p(A)$. The relative homology is directly related to reduced homology:

$$H_p(X,A)\cong {\tilde{H}}_p(X/A).$$

One may construct the short exact sequence

$$0\to C_p(A)\stackrel{i}{\to }{C}_p(X)\stackrel{j}{\to }{C}_p(X,A)\to 0$$

where $i$ is given by inclusion and $j$ is given by quotient. Using the snake lemma, this can be extended into a long exact sequence of homology groups:

$$\cdots \to H_p(A)\stackrel{i_{\ast }}{\to }{H}_p(X)\stackrel{j_{\ast }}{\to }{H}_p(X,A)\stackrel{{\partial }_p}{\to }{H}_{p-1}(A)\stackrel{i_{\ast }}{\to }{H}_{p-1}(X)\to \cdots \to H_0(X,A)\to 0.$$

The exact sequences are often used to determine the relative homology groups.

A commonly used result is that of excision. If $Z\subseteq A\subseteq X$ such that $Z$ is a subspace of $A$, then

$$H_p(X-Z,A-Z)\cong H_p(X,A).$$

In simpler terms, if the closure of $Z$ is contained in the interior of $A$, then one may cut out $U$ without changing the relative homology.

Example: Consider $S^{n-1}\subset D^n$ with $n\ge 1$. Because $D^n$ is contractible we get that ${\tilde{H}}_k(D^n)=0$ for all $k$ which gives that

$$0={\tilde{H}}_k(D^n)\to H_k(D^n,S^{n-1})\stackrel{\partial }{\to }{\tilde{H}}_{k-1}(S^{n-1})\to {\tilde{H}}_{k-1}(D^n)=0.$$

Because this forms a short exact sequence, $\partial$ is an isomorphism. Hence

$$H_k(D^n,S^{n-1})\cong {\tilde{H}}_{k-1}(S^{n-1})=\{\begin{array}{ll}\mathbb{Z}& k=n\\ 0& \text{otherwise.}\end{array}$$

One particular area that may be use to use is with embeddings. Let $A\subseteq X$ be embeddable in $Y$ by a continuous, injective map $f:X\to Y$ and let $B\subseteq Y$ such that $f(A)\subseteq B$. Then there is an induced map $f_{\#}:C_n(X)\to C_n(Y)$ and homomorphism $\phi :C_n(X,A)\to C_n(Y,B)$ such that the diagram below commutes:

where ${\pi }_A$ and ${\pi }_B$ are the natural projections $x\mapsto [x]$.

Relative Homology and Total Bimodularity

Claim: For submatrix $B[Z,T]$ of $B=[{\partial }_{p+1}]$ with rows $Z$ and columns $T$, define

$$\begin{array}{rl}L& =\text{Cl}(T)=\{\sigma \in K:\exists \tau \in T,\sigma \subseteq \tau \}\\ L_0& =\text{Cl}(L^{(p)}\setminus Z)=\{\sigma \in K:\exists \tau \in L^{(p)}\setminus Z,\sigma \subseteq \tau \}.\end{array}$$

Then $B[Z,T]$ is the matrix representation of ${\partial }_{p+1}^{\prime }:C_{p+1}(L,L_0)\to C_p(L,L_0)$ where $C_{\ast }(L,L_0):=C_{\ast }(L)/C_{\ast }(L_0)$.

We are thus interested in the homology

$$H_p(L,L_0)=\text{Ker}({\partial }_p^{\prime })/\text{Im}({\partial }_{p+1}^{\prime })\cong {\mathbb{Z}}^{m-r-s}\oplus \underset{i=1}{\overset{r}{⨁}}\mathbb{Z}/{\alpha }_i$$

where $m=|Z|$, $r=\text{rank}({\partial }_{p+1}^{\prime })$, $s=\text{rank}({\partial }_p^{\prime })$ and ${\alpha }_1,\dots ,{\alpha }_r$ are the invariant factors given by the Smith normal form of $[{\partial }_{p+1}^{\prime }]$.

Lemma 2: $B=[{\partial }_{p+1}]$ is totally bimodular if and only if, for every pair of pure subcomplexes $L_0\subseteq L\subseteq K$ of dimensions $p$ and $p+1$, the torsion subgroup of $H_p(L,L_0)$ has order at most 2.

Proof.

($\Rightarrow$): Consider an arbitrary pair $(L,L_0)$ and set $T=L^{(p+1)}$ and $Z=L^{(p)}\setminus L_0$. Then $H_p(L,L_0)$ has torsion of order

$$\prod _{i=1}^r{\alpha }_i=d_r({\partial }_{p+1}^{\prime })=\text{gcd}\{r\times r\text{ minors of B[Z,T]}\}\le 2.$$

($\Leftarrow$): Let $B[Z,T]$ be a square submatrix of $B$. Then it follows that

$$|\det B[Z,T]|=\{\begin{array}{ll}{\prod }_{i=1}^r{\alpha }_i& r=|Z|\\ 0& r<|Z|.\end{array}$$

Because the torsion subgroup of $H_p(L,L_0)$ has order at most 2, it follows that $|\det B[Z,T]|\le 2$. $\square$

Motivating Example: If $K$ has two or more disjoint Mobius strips, then $B$ is not totally bimodular.

Consider the following motivating example: Let $K$ be the 6-vertex Mobius strip triangulation given below:

Take the submatrix of $B={\partial }_2$ given by the interior edges $Z=\{[a,d]$, $[a,e]$, $[b,e]$, $[c,e]$, $[c,f]$, $[d,f]\}$ and the triangles. Then it follows that

$$B[Z,T]=\begin{array}{ccccccc}& [a,d,e]& [a,b,e]& [b,c,e]& [c,e,f]& [c,d,f]& [a,d,f]\\ [a,d]& 1& 0& 0& 0& 0& 1\\ [a,e]& -1& -1& 0& 0& 0& 0\\ [b,e]& 0& 1& -1& 0& 0& 0\\ [c,e]& 0& 0& 1& 1& 0& 0\\ [c,f]& 0& 0& 0& -1& -1& 0\\ [d,f]& 0& 0& 0& 0& 1& 1\end{array}$$

which has determinant $-2$. If we then take $K\bigsqcup K$ and again choose the interior edges of the two Mobius strips, then we get that

$$B[Z,T]=\left[\begin{array}{cc}B[Z_1,T_1]& 0\\ 0& B[Z_2,T_2]\end{array}\right]⟹\det B[Z,T]=\pm 4.$$

Thus, in general if there are $n$ disjoint Mobius strips, then one may find a minor of $\pm 2^n$.

Question: Can we say anything about the solvability if every minor is of the form $\pm 2^n$?

Theorem 4: If $K$ is a 2-complex that embeds into $\mathbb{R}{P}^2$, then $B=[{\partial }_2]$ is totally bimodular.

Proof. Assume for the sake of contradiction that $K$ has at least two disjoint Mobius strips $N_1,N_2$. Let $L=N_1\cup N_2$ and $E$ be the closure such that $\mathbb{R}{P}^2=L\cup E$. Because $N_1$ and $N_2$ are disjoint, it follows that $L\cap E=\partial N_1\cup \partial N_2$. Then the Mayer-Vietoris sequence contains

$$H_2(\mathbb{R}{P}^2)\to H_1(L\cap E)\stackrel{\phi }{\to }{H}_1(L)\oplus H_1(E)\stackrel{\psi }{\to }{H}_1(\mathbb{R}{P}^2).$$

Due to exactness, we get that $\text{ker}\psi =\text{im}\phi$ which implies by the fundamental theorem of homomorphisms that there is a unique injective homomorphism

$$h:H_1(L)\oplus H_1(E)/\text{im}\phi \to H_1(\mathbb{R}{P}^2)=\mathbb{Z}/2\mathbb{Z}.$$

Notice that the map $\phi$ is of the form $(i_{\ast },j_{\ast })$ where $i:L\cap E\hookrightarrow L$ and $j:L\cap E\hookrightarrow E$. Because $L\cap E=\partial N_1\cup \partial N_2$, an element $(x,y)\in H_1(L\cap E)=\mathbb{Z}\oplus \mathbb{Z}$ implies wrapping $x$ times around $\partial N_1$ and $y$ times around $\partial N_2$. Thus a loop around $\partial N_1$ is recorded twice, once in $L$ and once in $E$. Thus,

$$\begin{array}{r}{i}_{\ast }(1,0)=\pm 2\text{ and }{i}_{\ast }(0,1)=\pm 2.\end{array}$$

So $\phi (x,y)=(\pm 2,\pm 2,e)$ for some $e\in H_1(E)$. Consider then the map

$$\pi :\mathbb{Z}\oplus \mathbb{Z}\oplus H_1(E)\to (\mathbb{Z}/2\mathbb{Z}{)}^2,(a,b,e)\mapsto (a\mathrm{mod}2,b\mathrm{mod}2)$$

which has $\text{ker}\pi =\text{im}\phi$. Then $\pi$ induces an injective map

$$g:\mathbb{Z}\oplus \mathbb{Z}\oplus H_1(E)/\text{im}\phi \to (\mathbb{Z}/2\mathbb{Z}{)}^2$$

such that $\pi =g\circ \phi$. Because $\pi$ is surjective, it follows that $g$ is an isomorphism. Thus, $H_1(L)\oplus H_1(E)\cong (\mathbb{Z}/2\mathbb{Z}{)}^2$, which contradicts $h$. $\square$

I am unsure if the above result is correct. I’m trying to argue that $K$ has at worst a single Mobius strip.

Proposition 5: If $K$ has two disjoint pure subcomplexes with relative torsion, then $[{\partial }_{p+1}]$ is not totally bimodular.

Proof. Let $A_0\subseteq A\subseteq K$ and $B_0\subseteq B\subseteq K$ be two disjoint pairs of pure subcomplexes (i.e. $A\cap B=\varnothing$) such that $H_p(A,A_0)\cong \mathbb{Z}/2\mathbb{Z}$ and $H_p(B,B_0)\cong \mathbb{Z}/2\mathbb{Z}$. Consider then $L_0=A_0\cup B_0$ and $L=A\cup B$. Then the Mayer-Vietoris sequence is

$$0=H_p(A\cap B,A_0\cap B_0)\to H_p(A,A_0)\oplus H_p(B,B_0)\to H_p(L,L_0)\to H_{p-1}(A\cap B,A_0\cap B_0)=0.$$

Because the sequence is exact, it follows that

$$H_p(L,L_0)\cong H_p(A,A_0)\oplus H_p(B,B_0)\cong \mathbb{Z}/2\mathbb{Z}\oplus \mathbb{Z}/2\mathbb{Z}.$$

Therefore, the square submatrix corresponding to $(L,L_0)$ has determinant 4. $\square$

Conjecture: Let $K$ be embeddable in ${\mathbb{R}}^3$. Then $[{\partial }_{p+1}]$ is totally bimodular if and only if $K$ has at most one Mobius strip as a subcomplex.