2026-06-01

Recall the example from 2026-05-26 had

U B V = diag (I_{17}, 2)

where $B$ is the optimal basis matrix. If we recall the congruence condition (see 2026-05-14), we get integral solutions if

G b \equiv 0 mod 2

where $G$ is the last row of $U$ , i.e.,

G = [0000000000000 - 1 1001] .

This leads to the following question: can we find a right-hand side vector $b$ such that $G b \equiv 1 mod 2$ and $B^{- 1} b \geq 0$ ?

Starting with the first condition, we want

b \in {x \in Z^{18} : G x \equiv 1 mod 2} \supset {α e_{14} + β e_{15} + γ e_{18} : - α + β + γ \equiv 1 mod 2} .

Computing $B^{- 1}$ gives us:

B^{- 1} = 11 - 1 1 - 1 0000000000000 - 1 00 - 1 10000000000000 001000000000000000000100000000000000000010000000000000 000011 - 1 00000000000 000000100000000000 - 1 - 1 1 - 1 1001 - 1 000000000 000000001000000000000000000100000000000000000010000000000000000001000000 0000000000000 - 1 0000 000000000000 0.5 0 - 0.5 - 0.5 1 0.5 000000000000 0.5 1 0.5 0.5 - 1 - 0.5 0000000000000101 - 1 0 000000000000000010 000000000000 - 0.5 - 1 0.5 - 0.5 0 0.5 .

Thus,

B^{- 1} (α e_{14} + β e_{15} + γ e_{18}) = 0 \frac{1}{2} α + \frac{1}{2} β - \frac{1}{2} γ β - γ - \frac{1}{2} α + \frac{1}{2} β + \frac{1}{2} γ - \frac{1}{2} α + \frac{1}{2} β - \frac{1}{2} γ α - β \frac{1}{2} α - \frac{1}{2} β + \frac{1}{2} γ

This product is non-negative if and only if

α + β β β + γ β α α + γ \geq γ \geq γ \geq α \geq α + γ \geq β \geq β (C 1) (C 2) (C 3) (C 4) (C 5) (C 6)

Notice that

C 4 \land C 5 C 3 \land C 5 C 7 \land C 8 C 4 \land C 9 C 10 \land C 5 \Rightarrow α \geq β \geq α + γ \Rightarrow γ \leq 0 \Rightarrow β + γ \geq α \geq β \Rightarrow γ \geq 0 \Rightarrow γ = 0 \Rightarrow β \geq α \Rightarrow α = β (C 7) (C 8) (C 9) (C 10) (C 11) .

Therefore, we have that $α = β$ and $γ = 0$ are the only feasible cases. This leaves us with

b \in {α e_{14} + β e_{15} + γ e_{18} : - α + β + γ \equiv 1 mod 2, α = β, γ = 0} = {α e_{14} + α e_{15} : - α + α \equiv 1 mod 2} = \emptyset.

Therefore, there is no right-hand side vector $b$ , in which $B$ is feasible and $B^{- 1} b$ is fractional.

Conjecture: Let $B$ be an $m \times m$ submatrix of $[I - I \partial - \partial]$ . Then there are unimodular matrices $U$ and $V$ such that

U B V = diag (1, \dots, 1, d_{1}, d_{2}, \dots, d_{j})

where $d_{1} ∣ d_{2} ∣ \dots ∣ d_{j}$ . Denote by $G_{i}$ the row of $U$ corresponding to $d_{i}$ . Then the intersection

{b \in Z^{m} : \exists i where G_{i} b \neq \equiv 0 mod d_{i}} \cap {b \in Z^{m} : B^{- 1} b \geq 0}

is empty.

Notes