2026-02-24

I investigated the basis matrix of each iteration in which the objective improved. While the basis matrices were generally not TU, if you took the submatrix consisting of columns in which $x_i>0$, then that submatrix was TU. Moreover, the columns in which $x_i=0$ were skipped as $d_i\ge 0$.

Full details:

   743: [B=(540x540)][theta=-1/-1] (0:0) (1:1) (2:2) (5:545) (6:6) (7:547) (8:8) (16:556) (17:17) (18:558) (19:19) (23:23) (27:567) (30:30) (33:573) (34:574) (35:575) (61:601) (63:63) (67:67) (97:637) (98:638) (102:642)
 | d_B = (0:-1) (5:-1) (6:-1) (11:1)
 | d_B^P = (0:-1) (3:-1) (4:-1)
 | d_B^Z = (4:1)
 | Pd_B^P = (0:-1) (5:-1) (6:-1)
 | Zd_B^Z = (11:1)
 | -Aj = (0:-1) (5:-1) (6:-1) (11:1)
 | det(B) = 1
 | det(B(i:-A_j)) = { (0:-1)! (1:0) (2:0) (5:-1) (6:-1) (7:0) (8:0) (16:0) (17:0) (18:0) (19:0) (23:0) (27:0) (30:0) (33:0) (34:0) (35:0) (61:0) (63:0) (67:0) (97:0) (98:0) (102:0)}
   751: [B=(540x540)][theta=-1/-1] (0:1524) (1:1) (2:2) (6:6) (7:547) (8:8) (11:11) (16:556) (17:17) (18:558) (19:19) (23:23) (27:567) (30:30) (33:573) (34:574) (35:575) (61:601) (63:63) (67:67) (97:637) (98:638) (102:642)
 | d_B = (2:-1) (7:-1) (8:-1) (13:1)
 | d_B^P = (2:-1) (4:-1) (5:-1)
 | d_B^Z = (6:1)
 | Pd_B^P = (2:-1) (7:-1) (8:-1)
 | Zd_B^Z = (13:1)
 | -Aj = (2:-1) (7:-1) (8:-1) (13:1)
 | det(B) = 1
 | det(B(i:-A_j)) = { (0:0) (1:0) (2:-1) (6:0) (7:-1) (8:-1)! (11:0) (16:0) (17:0) (18:0) (19:0) (23:0) (27:0) (30:0) (33:0) (34:0) (35:0) (61:0) (63:0) (67:0) (97:0) (98:0) (102:0)}
   753: [B=(540x540)][theta=-1/-1] (0:1524) (1:1) (2:2) (6:6) (8:1526) (11:11) (13:13) (16:556) (17:17) (18:558) (19:19) (23:23) (27:567) (30:30) (33:573) (34:574) (35:575) (61:601) (63:63) (67:67) (97:637) (98:638) (102:642)
 | d_B = (11:-1) (16:-1) (17:-1) (22:1)
 | d_B^P = (5:-1) (7:-1) (8:-1)
 | d_B^Z = (11:1)
 | Pd_B^P = (11:-1) (16:-1) (17:-1)
 | Zd_B^Z = (22:1)
 | -Aj = (11:-1) (16:-1) (17:-1) (22:1)
 | det(B) = 1
 | det(B(i:-A_j)) = { (0:0) (1:0) (2:0) (6:0) (8:0) (11:-1)! (13:0) (16:-1) (17:-1) (18:0) (19:0) (23:0) (27:0) (30:0) (33:0) (34:0) (35:0) (61:0) (63:0) (67:0) (97:0) (98:0) (102:0)}
   762: [B=(540x540)][theta=-1/-1] (0:1524) (1:1) (2:2) (6:6) (8:1526) (11:1529) (13:13) (18:558) (19:19) (22:22) (23:23) (27:567) (30:30) (33:573) (34:574) (35:575) (61:601) (63:63) (67:67) (97:637) (98:638) (102:642)
 | d_B = (13:-1) (18:-1) (19:-1) (24:1)
 | d_B^P = (6:-1) (7:-1) (8:-1)
 | d_B^Z = (13:1)
 | Pd_B^P = (13:-1) (18:-1) (19:-1)
 | Zd_B^Z = (24:1)
 | -Aj = (13:-1) (18:-1) (19:-1) (24:1)
 | det(B) = 1
 | det(B(i:-A_j)) = { (0:0) (1:0) (2:0) (6:0) (8:0) (11:0) (13:-1)! (18:-1) (19:-1) (22:0) (23:0) (27:0) (30:0) (33:0) (34:0) (35:0) (61:0) (63:0) (67:0) (97:0) (98:0) (102:0)}
   774: [B=(540x540)][theta=-1/-1] (0:1524) (1:1) (2:2) (6:6) (8:1526) (11:1529) (13:1530) (22:22) (23:23) (24:24) (27:567) (30:30) (33:573) (34:574) (35:575) (61:601) (63:63) (67:67) (97:637) (98:638) (102:642)
 | d_B = (22:-1) (27:-1) (28:1) (33:-1)
 | d_B^P = (7:-1) (10:-1) (12:-1)
 | d_B^Z = (17:1)
 | Pd_B^P = (22:-1) (27:-1) (33:-1)
 | Zd_B^Z = (22:1) (27:1) (28:1) (33:1)
 | -Aj = (28:1)
 | det(B) = 1
 | det(B(i:-A_j)) = { (0:0) (1:0) (2:0) (6:0) (8:0) (11:0) (13:0) (22:-1)! (23:0) (24:0) (27:-1) (30:0) (33:-1) (34:0) (35:0) (61:0) (63:0) (67:0) (97:0) (98:0) (102:0)}
   794: [B=(540x540)][theta=-1/-1] (0:1524) (1:1) (2:2) (6:6) (8:1526) (11:1529) (13:1530) (22:568) (23:23) (24:24) (28:1533) (30:30) (34:574) (35:575) (61:601) (63:63) (67:67) (97:637) (98:638) (102:642)
 | d_B = (19:1) (22:-1) (23:-1) (34:-1)
 | d_B^P = (7:-1) (8:-1) (12:-1)
 | d_B^Z = (12:1)
 | Pd_B^P = (23:-1) (28:1) (34:-1)
 | Zd_B^Z = (29:-1)
 | -Aj = (23:-1) (28:1) (29:-1) (34:-1)
 | det(B) = 1
 | det(B(i:-A_j)) = { (0:0) (1:0) (2:0) (6:0) (8:0) (11:0) (13:0) (22:-1) (23:-1)! (24:0) (28:0) (30:0) (34:-1) (35:0) (61:0) (63:0) (67:0) (97:0) (98:0) (102:0)}
   795: [B=(540x540)][theta=-1/-1] (0:1524) (1:1) (2:2) (6:6) (8:1526) (11:1529) (13:1530) (19:569) (23:1534) (24:24) (28:1533) (30:30) (35:575) (61:601) (63:63) (67:67) (97:637) (98:638) (102:642)
 | d_B = (19:-1) (24:-1) (30:-1) (35:-1)
 | d_B^P = (7:-1) (9:-1) (11:-1) (12:-1)
 | d_B^Z =
 | Pd_B^P = (24:-1) (29:1) (30:-1) (35:-1)
 | Zd_B^Z =
 | -Aj = (24:-1) (29:1) (30:-1) (35:-1)
 | det(B) = 1
 | det(B(i:-A_j)) = { (0:0) (1:0) (2:0) (6:0) (8:0) (11:0) (13:0) (19:-1) (23:0) (24:-1)! (28:0) (30:-1) (35:-1) (61:0) (63:0) (67:0) (97:0) (98:0) (102:0)}
   851: [B=(540x540)][theta=-1/-1] (0:1524) (1:1) (2:2) (6:6) (8:1526) (11:1529) (13:1530) (23:1534) (24:1535) (28:1533) (61:601) (63:63) (67:67) (97:637) (98:638) (102:642)
 | d_B = (1:-1) (61:-1) (97:-1) (126:1)
 | d_B^P = (1:-1) (10:-1) (13:-1)
 | d_B^Z = (110:1)
 | Pd_B^P = (1:-1) (61:-1) (97:-1)
 | Zd_B^Z = (1:1) (61:1) (62:1) (97:1)
 | -Aj = (62:1)
 | det(B) = 1
 | det(B(i:-A_j)) = { (0:0) (1:-1)! (2:0) (6:0) (8:0) (11:0) (13:0) (23:0) (24:0) (28:0) (61:-1) (63:0) (67:0) (97:-1) (98:0) (102:0)}
   852: [B=(540x540)][theta=-1/-1] (0:1524) (1:602) (2:2) (6:6) (8:1526) (11:1529) (13:1530) (23:1534) (24:1535) (28:1533) (61:601) (63:63) (67:67) (98:638) (102:642) (126:1549)
 | d_B = (1:-1) (2:-1) (63:-1) (98:-1)
 | d_B^P = (1:-1) (2:-1) (11:-1) (13:-1)
 | d_B^Z =
 | Pd_B^P = (2:-1) (62:1) (63:-1) (98:-1)
 | Zd_B^Z =
 | -Aj = (2:-1) (62:1) (63:-1) (98:-1)
 | det(B) = 1
 | det(B(i:-A_j)) = { (0:0) (1:-1) (2:-1)! (6:0) (8:0) (11:0) (13:0) (23:0) (24:0) (28:0) (61:0) (63:-1) (67:0) (98:-1) (102:0) (126:0)}
   966: [B=(540x540)][theta=-1/-1] (0:1524) (2:1550) (6:6) (8:1526) (11:1529) (13:1530) (23:1534) (24:1535) (28:1533) (61:601) (67:67) (102:642) (126:1549)
 | d_B = (6:-1) (61:-1) (67:-1) (102:-1)
 | d_B^P = (2:-1) (9:-1) (10:-1) (11:-1)
 | d_B^Z =
 | Pd_B^P = (6:-1) (61:-1) (67:-1) (102:-1)
 | Zd_B^Z =
 | -Aj = (6:-1) (61:-1) (67:-1) (102:-1)
 | det(B) = 1
 | det(B(i:-A_j)) = { (0:0) (2:0) (6:-1)! (8:0) (11:0) (13:0) (23:0) (24:0) (28:0) (61:-1) (67:-1) (102:-1) (126:0)}

By Cramer’s rule,

$$B{d}_B=-A_j\Rightarrow d_i=\frac{\det (B(i:-A_j))}{\det (B)}$$

where $B(i:-A_j)$ is the matrix formed by replacing the $i$-th column of $B$ by $-A_j$. Thus, $d_i$ is integral if

$$\det (B)\mid \det (B(i:-A_j)).$$

Based on the above log:

$$\det (B(i:-A_j))=-\det (B)=-1.$$

whenever $x_i>0$.

Moreover, based on further logs we get the following conjecture:

Conjecture: Assume doing the current iteration, the minimum-ratio test gives ${\theta }^{\ast }>0$. Then $\det (B)=1$.

Note that $\det (B)$ is not always 1. In some iterations, $\det (B)>1$, but they had ${\theta }^{\ast }=0$. Thus, we could rewrite the conjecture as follows:

Conjecture: If $\det (B)\ne 1$, then there is a basic variable $i$ such that $x_i=0$.

Note that $\det (B)=1$ directly implies that $d$ is integral as

$$d_B=-B^{-1}{A}_j=-\frac{1}{\det (B)}\text{adj}(B)A_j$$

where $\text{adj}(B)$ and $A_j$ are both integral. Further work would be necessary to show that ${\theta }^{\ast }\in \mathbb{Z}$ is integral when $\det (B)=1$. One might be able to argue that $\det (B)=1$ implies that $d\in \{-1,0,1{\}}^n$.

Again by Cramer’s rule,

$$x_i=\frac{\det (B(i:b))}{\det (B)}.$$

So the question is, what causes $B(i:b)$ to become singular? Naturally, if $B(i:b)$ is singular, then $b\in \text{span}\{B_j:j\ne i\}$, i.e., there are coefficients $c_1,\dots ,c_m\in \mathbb{R}$ such that

$$\sum _{j\ne i}{c}_j{B}_j=b.$$

It is not clear how $\det (B)\ne 1$ relates to this. Some ideas:

• Zero would be an eigenvalue of $B(i:b{)}^{\top }$:
  • There is some vector $v\in {\mathbb{R}}^n$ such that $B_j^{\top }v=0$ for all $j\ne i$ and $B_i^{\top }v\ne 0$.
  • $b\perp \text{span}\{B_j:j\ne i\}$
• Expansion along column $i$ for $B(i:b)$ and $B$
• Anything to say about the lattice $B{\mathbb{Z}}^n=\{Bx\mid x\in {\mathbb{Z}}^n\}$?