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

Let $B[Z,T]$ be a square submatrix of the boundary matrix $B$ with rows $Z$ and columns $T$. Then it follows that $B[Z,T]$ is the relative boundary matrix, i.e., if $L$ is the closure $(p+1)$-simplices of $T$ and $L_0$ is the closure of the $p$-faces of $L$ that are not in $Z$, then $B[Z,T]$ is the matrix representatation of

$${\partial }_{p+1}: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) = \textup{Ker}(\partial_{p})/\textup{Im}(\partial_{p+1})=\Z^{m-r-s}\oplus\bigoplus_{i=1}^r\Z/\alpha_i $$where $m=|Z|$, $r=\textup{rank}(\partial_{p+1})$, $s=\textup{rank}(\partial_p)$ and $\alpha_1,\dots,\alpha_r$ are the invariant factors given by the Smith normal form of $\partial_{p+1}$. **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}) = \textup{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{cases}
	\prod_{i=1}^r\alpha_i & r=|Z| \\
	0 & r < |Z|.
\end{cases}

Because the torsion subgroup of $H_p(L,L_0)$ has order at most 2, it follows that $|\det B[Z,T]|\le2$. $\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: ![[Screenshot_2024-11-14_12-44-36.png]] 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}{c|ccc} 
	& [a,d,e] & [a,b,e] & [b,c,e] & [c,e,f] & [c,d,f] & [a,d,f] \\ \hline 
	[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\sqcup K$ and again choose the interior edges of the two Mobius strips, then we get that

B[Z,T] = \begin{bmatrix}
	B[Z_1,T_1] & 0 \\
	0 & B[Z_2,T_2]
\end{bmatrix} \Longrightarrow \det B[Z,T] = \pm4.

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 $\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 $\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(\R P^2)\rightarrow H_1(L\cap E)\xrightarrow{\varphi}  H_1(L)\oplus H_1(E) \xrightarrow{\psi} H_1(\R P^2).

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

h:H_1(L)\oplus H_1(E)/\textup{im}\varphi\rightarrow H_1(\R P^2) = \Z/2\Z.

Notice that the map $\varphi$ is of the form $(i_*,j_*)$ 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)=\Z\oplus \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{align*} i_(1,0) = \pm2~\text { and }~i_(0,1) = \pm 2. \end{align*}

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

\pi:\Z\oplus\Z\oplus H_1(E)\rightarrow(\Z/2\Z)^2,~(a,b,e)\mapsto(a\bmod 2,b\bmod 2)

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

g:\Z\oplus\Z\oplus H_1(E)/\text{im}\varphi\rightarrow (\Z/2\Z)^2

such that $\pi=g\circ\varphi$. Because $\pi$ is surjective, it follows that $g$ is an isomorphism. Thus, $H_1(L)\oplus H_1(E)\cong(\Z/2\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=\emptyset$) such that $H_p(A,A_0)\cong\Z/2\Z$ and $H_p(B,B_0)\cong\Z/2\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)\rightarrow H_p(A,A_0)\oplus H_p(B,B_0)\rightarrow H_p(L,L_0)\rightarrow H_{p-1}(A\cap B,A_0\cap B_0)=0.

$$Becausethesequenceisexact,itfollowsthat$$

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

Therefore, the square submatrix corresponding to $(L,L_0)$ has determinant 4. $\square$ **Conjecture:** Let $K$ be embeddable in $\R^3$. Then $[\partial_{p+1}]$ is totally bimodular if and only if $K$ has at most one Mobius strip as a subcomplex.