2026-05-12

Recall from 2026-05-12:

Let $B_1,B_2,\dots ,B_{\ell }$ be the basis matrices where $|\det B_i|>1$ encountered during simplex method for a given right-hand side vector $b\in {\mathbb{Z}}^m$. Then we found that each $x_{B_i}=B_i^{-1}b$ is integral if there are integral vectors $z_i\in {\mathbb{Z}}^{t_i}$ such that

$$\left[\begin{array}{ccccc}{G}_{B_1}& -k_1{I}_{t_1}& & & \\ G_{B_2}& & -k_2{I}_{t_2}& & \\ ⋮& & & \ddots & \\ G_{B_{\ell }}& & & & -k_{\ell }{I}_{t_{\ell }}\end{array}\right]\left[\begin{array}{c}b\\ z_1\\ ⋮\\ z_{\ell }\end{array}\right]=0,$$

or $Cw=0$ for short.

Consider then the SNF of $C$:

$$U_{C}C{V}_C=D=\text{diag}(d_1,d_2,\dots ,d_r,0,\dots ,0).$$

Let $w\in \ker (C)$. Then it follows that

$$Cw=U_C^{-1}D{V}_C^{-1}w=0.$$

Since $U_C$ is unimodular, this boils down the system

$$Dy=0\text{ where }y=V_C^{-1}w.$$

But $D=\text{diag}(d_1,\dots ,d_r,0,\dots ,0)$, so $Dy=0$ if and only if

$$y_j=0\text{ for }j=1,\dots ,r,$$

i.e.,

$$V_C^{-1}w\in \text{span}\{e_{r+1},\dots ,e_{m+\sum t_i}\}.$$

Therefore,

$${\ker }_{\mathbb{Z}}(C)=V_C\cdot {\text{span}}_{\mathbb{Z}}\{e_{r+1},\dots ,e_{m+\sum t_i}\}.$$

Thus, our condition becomes that there exists some $w\in {\ker }_{\mathbb{Z}}(C)$ where the first $m$-entries are $b$, i.e.,

$$b\in \pi ({\ker }_{\mathbb{Z}}(C))$$

where $\pi :{\mathbb{Z}}^{m+\sum t_i}\to {\mathbb{Z}}^m$ is the projection function onto the first $m$-entries.

---

Let’s instead look at the relation between $b$ and the feasible bases.

Let $K$ be a triangle $[v_1,v_2,v_3]$ and $b=e_{01}+e_{12}$, the chain going partially around the boundary of $K$. There are two cases for constraints:

Case 1: $e_{01}\in \text{supp}(b)$: Then the corresponding constraint in $Ax=b$ is given by

$$x_{01}^{+}-x_{01}^{-}+(\partial y^{+}{)}_{01}-(\partial y^{-}{)}_{01}=1.$$

Thus, the basis must contain $x_{01}^{+}$ or $y_{012}^{+}$. If it selects $y_{012}^{+}$, then we get an issue in another constraint:

$$x_{02}^{+}-x_{02}^{-}+(\partial y^{+}{)}_{02}-(\partial y^{-}{)}_{02}=0.$$

Case 2: $e_{02}\notin \text{supp}(b)$: Then the corresponding constraint in $Ax=b$ is given by

$$x_{02}^{+}-x_{02}^{-}+(\partial y^{+}{)}_{02}-(\partial y^{-}{)}_{02}=0.$$

If the basis chooses $y_{012}^{+}$, then we get

$$x_{02}^{+}-x_{02}^{-}+(-1)-(\partial y^{-}{)}_{02}=0$$

which forces the selection of $y_{012}^{-}$ or $x_{02}^{+}$. But, the simplex method won’t select both $y^{+}$ and $y^{-}$ at the same time. So it must choose $x_{02}^{+}$. So the basic variables are $\{x_{02}^{+},y_{012}^{-},x_{?}^{?}\}$.

Similarly, if the basis chooses $y_{012}^{-}$, then we are forced to take $x_{02}^{-}$.

---

Notice that our basis matrix of the form

$$B=[\pm e_{{\sigma }_1}\mid \cdots \mid \pm e_{{\sigma }_k}\mid \pm {\partial }_{{\tau }_1}\mid \cdots \mid \pm {\partial }_{{\tau }_{m-k}}].$$

Upon performing EROs, we get that

$$B\sim \left[\begin{array}{cc}{I}_S& \pm {\partial }_S\\ 0& {\tilde{\partial }}_S\end{array}\right]$$

where

• $I_S$ is an identity matrix corresponding to the identity columns
• $\pm {\partial }_S$ comes from the boundary matrix consisting of rows covered by $I_S$
• $\widetilde{{\partial }_S}$ is the remaining boundary matrix entries in which $x_i=0$

But further EROs lets us cancel $\pm {\partial }_S$ which leaves us with

$$SNF(B)=SNF(I_S)\oplus SNF({\tilde{\partial }}_S)=\text{diag}(1,\dots ,1)\oplus SNF({\tilde{\partial }}_S).$$

Note that ${\tilde{\partial }}_S$ is simply a submatrix of $\partial$. Since the entries of $\partial$ are of the form $\{-1,0,1\}$, it follows that

$$d_1=\gcd \{\text{all 1×1 minors}\}=1.$$

Thus,

$$SNF({\tilde{\partial }}_S)=\text{diag}(1,d_2,\dots ,d_r).$$

For now we assume (with support of numerical tests) that every square submatrix ${\partial }_S$ of $\partial$ has $|\det {\partial }_S|=p^r$ for some prime $p$ and $r\in {\mathbb{Z}}_{\ge 0}$. Then it would follow that

$$SNF(B)=\text{diag}(1,\dots ,1,k,\dots ,k)$$

where $k$ is a power of $p$.

Unfortunately, the $\mathbb{R}{P}^2$ also satisfies this result, which implies that the SNF condition is not sufficient for the congruence condition. My assumption is that it has to do with $[b]$ having torsion or not.

The homology class $[b]\in H_q(K;\mathbb{Z})$ has torsion of order $n$ if $b\notin B_q(K;\mathbb{Z})$ and

$$n\cdot b=\partial c\text{ for some }c\in C_{q+1}(K;\mathbb{Z}),$$

i.e., $nb\in B_q(K;\mathbb{Z})$.

Let’s assume that there is a feasible basis $B$ such that $G_{B}b\not\equiv 0\mathrm{mod}{k}_B$, i.e., $x_B=B^{-1}b\notin {\mathbb{Z}}^m$. Numerical tests suggest that $k_{B}b=\partial d$ for some $d\in C_{q+1}(K;\mathbb{Z})$. In other words, $[b]$ has torsion of order $k_B$.

Conjecture: If there is a feasible basis $B$ such that $G_{B}b\not\equiv 0\mathrm{mod}{k}_B$, then there is a chain $d\in C_{q+1}(K;\mathbb{Z})$ such that $k_{B}b=\partial d$, i.e., $[b]$ has torsion of order $k_B$.