Homological Gaussian Elimination — Examples

The lower-left $2\times 2$ block of $d^0$ is $\left(\begin{array}{cc}1& 1\\ 1& 1\end{array}\right)$ in the rows $B,V$ and columns $A,U$, so $a=b=c=\phi =1$ and the pivot is the lower-right identity, invertible with ${\phi }^{-1}=1$.

The Schur complement is $a-b{\phi }^{-1}c=1-1\cdot 1^{-1}\cdot 1=0$, so by [L1] the reduction has differential ${\bar{d}}^0=0:\mathbb{Q}\to \mathbb{Q}$; its neighbouring arrows are ${\bar{d}}^{-1}=p=0$ and ${\bar{d}}^1=r=0$, because $d^{-1}=0$ and $d^1=0$ have no components into or out of the discarded summands. Hence ${\bar{X}}^{\bullet }$ is $\mathbb{Q}\stackrel{0}{\to }\mathbb{Q}$ in degrees $0,1$.

Under the reindexing $C_n=X^{-n}$ the two-term complex becomes the chain complex $\mathbb{Q}\stackrel{d^0}{\to }\mathbb{Q}$ concentrated in degrees $0,-1$, so by [L4] its homology is $H_0=\ker d^0$ and $H_{-1}=\mathrm{coker}{d}^0$, corresponding to cochain degrees $0$ and $1$. For the reduction these are $\ker (0)=\mathbb{Q}$ and $\mathrm{coker}(0)=\mathbb{Q}$; for $X^{\bullet }$ they are $\ker d^0=\mathbb{Q}(1,-1)\cong \mathbb{Q}$, since $\left(\begin{array}{cc}1& 1\\ 1& 1\end{array}\right)\left(\genfrac{}{}{0px}{}{x}{y}\right)=\left(\genfrac{}{}{0px}{}{x+y}{x+y}\right)$, and $\mathrm{coker}{d}^0={\mathbb{Q}}^2\mathrm{/}\mathbb{Q}(1,1)\cong \mathbb{Q}$. The two complexes therefore have isomorphic one-dimensional homology, as [L3] requires.

With the plus sign, the candidate differential would be $a+b{\phi }^{-1}c=1+1=2$, the map $\mathbb{Q}\stackrel{2}{\to }\mathbb{Q}$ with $\ker (2)=0$ and $\mathrm{coker}(2)=\mathbb{Q}\mathrm{/}2\mathbb{Q}=0$; its homology would vanish in both degrees, whereas $X^{\bullet }$ has one-dimensional homology in both degrees and is homotopy equivalent to its reduction by [L3]. The plus sign is therefore impossible, and the example exhibits the minus sign in the Schur complement. ∎

The vanishing composites: $d^1{d}^0=\left(\begin{array}{cc}1& 1\\ 1& 1\end{array}\right)\left(\genfrac{}{}{0px}{}{1}{-1}\right)=\left(\genfrac{}{}{0px}{}{0}{0}\right)$ and $d^2{d}^1=(1-1)\left(\begin{array}{cc}1& 1\\ 1& 1\end{array}\right)=(00)$, so $X^{\bullet }$ is a cochain complex; the blocks of $d^1$ are $a=b=c=\phi =1$ because its lower-right entry is the identity, and the neighbour components are $d^0=(p;q)=(1;-1)$ and $d^2=(rs)=(1-1)$.

The basis changes are $L=\left(\begin{array}{cc}1& -1\\ 0& 1\end{array}\right)$ with inverse $L^{-1}=\left(\begin{array}{cc}1& 1\\ 0& 1\end{array}\right)$, and $R=\left(\begin{array}{cc}1& 0\\ -1& 1\end{array}\right)$ with inverse $R^{-1}=\left(\begin{array}{cc}1& 0\\ 1& 1\end{array}\right)$, all with entries in $k$ and determinant $1$.

The transformed incoming arrow is $R^{-1}(p;q)=\left(\begin{array}{cc}1& 0\\ 1& 1\end{array}\right)\left(\genfrac{}{}{0px}{}{1}{-1}\right)=\left(\genfrac{}{}{0px}{}{1}{0}\right)$; the transformed outgoing arrow is $(rs)L^{-1}=(1-1)\left(\begin{array}{cc}1& 1\\ 0& 1\end{array}\right)=(10)$.

The diagonalized middle differential is $L{d}^{1}R$: first $d^{1}R=\left(\begin{array}{cc}1& 1\\ 1& 1\end{array}\right)\left(\begin{array}{cc}1& 0\\ -1& 1\end{array}\right)=\left(\begin{array}{cc}0& 1\\ 0& 1\end{array}\right)$, then $L\left(\begin{array}{cc}0& 1\\ 0& 1\end{array}\right)=\left(\begin{array}{cc}1& -1\\ 0& 1\end{array}\right)\left(\begin{array}{cc}0& 1\\ 0& 1\end{array}\right)=\left(\begin{array}{cc}0& 0\\ 0& 1\end{array}\right)=\mathrm{diag}(a-b{\phi }^{-1}c,\phi )$ with $a-b{\phi }^{-1}c=1-1=0$.

By [L2] the reduced complex has $X^0=k$, $X^1=A=k$, $X^2=B=k$, $X^3=k$ with differentials ${\bar{d}}^0=p=1$, ${\bar{d}}^1=a-b{\phi }^{-1}c=0$ and ${\bar{d}}^2=r=1$, that is the reduced segment $k\stackrel{1}{\to }k\stackrel{0}{\to }k\stackrel{1}{\to }k$; its composites are $0\cdot 1=0$ and $1\cdot 0=0$, so it is a cochain complex, as the lemma guarantees. In the transformed coordinates the discarded components are exactly ${\phi }^{-1}cp+q=1-1=0$ of the incoming arrow and $rb{\phi }^{-1}+s=1-1=0$ of the outgoing arrow, which is why the second entries of the transformed arrows vanish; the entries along the retained summands, namely $p=1$ and $r=1$, pass to the reduction unchanged. ∎

Complex check. The composite $d^2{d}^1$ has $(i,j)$-entry the sum over $D_1,D_2,E$ of the products of entries of $d^2$ and $d^1$, and each of the three displayed matrix identities $d^1{d}^0=0$, $d^2{d}^1=0$, $d^3{d}^2=0$ is exactly the hypothesis that consecutive differentials of $X^{\bullet }$ vanish; the remaining composites are zero because $X^{-1}=X^5=0$.

Cancelling $\psi$ first. Write $X^1=C\oplus B$ and $X^2=(D_2\oplus E)\oplus D_1$, so that the pivot block of $d^1$ is $\psi :B\to D_1$, with $a=(\gamma ;\delta ):C\to D_2\oplus E$, $b=(x;y):B\to D_2\oplus E$ and $c=\beta :C\to D_1$. The Schur complement of the pivot is $a-b{\psi }^{-1}c=(\gamma -x{\psi }^{-1}\beta ;\delta -y{\psi }^{-1}\beta ):C\to D_2\oplus E$; the incoming arrow of the reduction is the $C$-component $q$ of $d^0$, and the outgoing arrow is the restriction of $d^2$ to the rows $D_2,E$, namely $\left(\begin{array}{cc}\mu & \lambda \\ \nu & \phi \end{array}\right)$, in which the pivot $\phi :E\to G$ still appears unchanged.

Cancelling $\phi$ first. In the decomposition $X^2=(D_1\oplus D_2)\oplus (E)$ and $X^3=(F)\oplus (G)$, the pivot $\phi :E\to G$ has complement blocks $z,\mu$ (row $F$) and $w,\nu$, so the Schur complement is the arrow $D_1\oplus D_2\to F$ with entries $z-\lambda {\phi }^{-1}w$ and $\mu -\lambda {\phi }^{-1}\nu$; the incoming arrow is the restriction of $d^1$ to the rows $D_1,D_2$, namely $\left(\begin{array}{cc}\psi & \beta \\ x& \gamma \end{array}\right)$, and the outgoing arrow is $r:F\to H$. Cancelling $\psi$ second gives the middle differential $\gamma -x{\psi }^{-1}\beta$ on $C\to D_2$, the incoming arrow $q$ and the outgoing arrow $r$.

Cancelling $\phi$ second. In the complex of step 1.2 the pivot $\phi :E\to G$ sits in the block of $\left(\begin{array}{cc}\mu & \lambda \\ \nu & \phi \end{array}\right)$ with retained summands $D_2$ of the degree-$2$ object and $F$ of the degree-$3$ object, so the new middle differential is the Schur complement $\mu -\lambda {\phi }^{-1}\nu :D_2\to F$, while the incoming arrow loses its $E$-component and becomes $\gamma -x{\psi }^{-1}\beta :C\to D_2$; the outgoing arrow is $r:F\to H$.

Order comparison. By steps 1.2 and 2.1, cancelling $\psi$ then $\phi$ leaves the cochain complex $A\stackrel{q}{\to }C\stackrel{\gamma -x{\psi }^{-1}\beta }{\to }{D}_2\stackrel{\mu -\lambda {\phi }^{-1}\nu }{\to }F\stackrel{r}{\to }H$; by step 1.3, cancelling $\phi$ then $\psi$ leaves the same objects and the same four arrows. In each order the composite of the single-cancellation data is by [L3] the strong deformation retract data $p=p_2{p}_1$, $\mathrm{ı}={\mathrm{ı}}_1{\mathrm{ı}}_2$, $h=h_1+{\mathrm{ı}}_1{h}_2{p}_1$ of $X^{\bullet }$ onto that reduction, satisfying $p\mathrm{ı}=1$, $1-\mathrm{ı}p=dh+hd$, $ph=0$, $h\mathrm{ı}=0$ and $h^2=0$; [L3] also gives that the two reductions are homotopy equivalent.

A concrete instance over $\mathbb{Q}$. Take every entry of $d^1$ equal to $1$, so $\psi =\beta =x=\gamma =y=\delta =1$; take $d^2=\left(\begin{array}{ccc}1& 1& -2\\ 1& -2& 1\end{array}\right)$, $d^0=(1;-1)$ and $d^3=(00)$. Then $d^1{d}^0=(1-1;1-1;1-1)=0$, $d^2{d}^1=\left(\begin{array}{cc}1+1-2& 1+1-2\\ 1-2+1& 1-2+1\end{array}\right)=0$ and $d^3{d}^2=(00)$, so $X^{\bullet }$ is a complex. The two reduced middle arrows are $\gamma -x{\psi }^{-1}\beta =1-1=0$ and $\mu -\lambda {\phi }^{-1}\nu =1-(-2)(1{)}^{-1}(-2)=1-4=-3$, and the end arrows are $q=-1$ and $r=0$; both orders give the reduced complex $\mathbb{Q}\stackrel{-1}{\to }\mathbb{Q}\stackrel{0}{\to }\mathbb{Q}\stackrel{-3}{\to }\mathbb{Q}\stackrel{0}{\to }\mathbb{Q}$, whose composites $0\cdot (-1)=0$ and $(-3)\cdot 0=0$ vanish. ∎

The entry $2$ has no inverse in the category of abelian groups. If $u:\mathbb{Z}\to \mathbb{Z}$ satisfied $2u=1$ or $u\cdot 2=1$, then evaluating at $1$ gives $2u(1)=1$ with $u(1)\in \mathbb{Z}$, which is impossible because $1$ is odd; equivalently $\mathbb{Z}$ has no element $m$ with $2m=1$. Since $2$ is not invertible, it is not a pivot in the sense of [L1], and the Schur complement $a-b{\phi }^{-1}c$ of the block $(\phi )=(2)$ is not defined on its own.

The complex nonetheless has nonzero homology. Reindexing by $C_m:=X^{-m}$ gives the chain complex $\mathbb{Z}\stackrel{2}{\to }\mathbb{Z}$ concentrated in degrees $-n$ and $-n-1$. There $Z_{-n-1}=\ker (d_{-n-1}=0)=\mathbb{Z}$ and $B_{-n-1}=\mathrm{im}(d_{-n})=\mathrm{im}(2)=2\mathbb{Z}$, so the boundary-to-cycle map is the inclusion $2\mathbb{Z}\hookrightarrow \mathbb{Z}$ and, by [L4], $H_{-n-1}\cong \mathbb{Z}\mathrm{/}2\mathbb{Z}\mathrm{\ne }0$; this is the homology in cochain degree $n+1$ of $X^{\bullet }$.

The complex is not contractible. If it were, [L3] would give a homomorphism $h^{n+1}:\mathbb{Z}\to \mathbb{Z}$ with $1_{X^n}=d^{n-1}{h}^n+h^{n+1}{d}^n=0+h^{n+1}\cdot 2$ in degree $n$, because $d^{n-1}=0$ and $d^n=\cdot 2$; evaluating at $1$ would produce an integer $h^{n+1}(1)$ with $2h^{n+1}(1)=1$, which is impossible by step 1.1. Hence $X^{\bullet }$ is not homotopy equivalent to the zero complex, and deleting both terms would not be a homotopy equivalence.

Consequently the pivot hypothesis of [L1] and [L2] is genuinely needed: the deleted terms carry the nonzero homology object $H_{-n-1}\cong \mathbb{Z}\mathrm{/}2\mathbb{Z}$ of step 1.2, which the zero complex does not have, and no two-sided inverse of $2$ exists in $\mathbb{Z}$. The claim refuted is therefore false; the theorem's conclusion is not available here because its hypothesis fails. ∎

Retract data for $X^{\bullet }$ onto $Y^{\bullet }$. Write elements of $X^j=k\oplus k$ as pairs with the first coordinate in $Y^j$ and the second in $K^j$, and let $\mathrm{ı}=\left(\genfrac{}{}{0px}{}{1}{0}\right)$, $p=(10)$ in both degrees, with $h^1=\left(\begin{array}{cc}0& 0\\ 0& 1\end{array}\right)$, $h^0=0$ and $h^2=0$. Then $p\mathrm{ı}=1_k$ and $1-\mathrm{ı}p=\left(\begin{array}{cc}0& 0\\ 0& 1\end{array}\right)$. Here $d^0=1_{k^2}$ and $d^1=0$: in degree $1$, $d^0{h}^1+h^2{d}^1=1_{k^2}{h}^1+0=\left(\begin{array}{cc}0& 0\\ 0& 1\end{array}\right)$, and in degree $0$, $d^{-1}{h}^0+h^1{d}^0=0+h^1{1}_{k^2}=\left(\begin{array}{cc}0& 0\\ 0& 1\end{array}\right)$. Thus $1-\mathrm{ı}p=dh+hd$, and the displayed data is a strong deformation retract of $X^{\bullet }$ onto $Y^{\bullet }$.

Two cochain maps. In both nonzero degrees set $f=\left(\begin{array}{cc}0& 0\\ 1& 0\end{array}\right)$ and $g=\left(\begin{array}{cc}0& 1\\ 0& 0\end{array}\right)$. At the only nonzero differential $d^0=1_{k^2}$, $f^1=f^0$ and $g^1=g^0$, so $f^1{d}^0=d^0{f}^0$ and $g^1{d}^0=d^0{g}^0$; at $d^1=0$ the cochain-map equations hold trivially. Thus $f$ and $g$ are cochain maps. Here $f$ sends the $Y$-coordinate isomorphically onto the $K$-coordinate and kills the $K$-coordinate, while $g$ sends the $K$-coordinate isomorphically onto the $Y$-coordinate and kills the $Y$-coordinate.

The individual transfers vanish. Since $\mathrm{ı}=\left(\genfrac{}{}{0px}{}{1}{0}\right)$, one has $f\mathrm{ı}=\left(\genfrac{}{}{0px}{}{0}{1}\right)$ and $g\mathrm{ı}=0$; applying $p=(10)$ gives $\bar{f}=pf\mathrm{ı}=0$ and $\bar{g}=pg\mathrm{ı}=0$ as cochain maps $Y^{\bullet }\to Y^{\bullet }$.

The transfer of the composite does not vanish. Since $gf=\left(\begin{array}{cc}0& 1\\ 0& 0\end{array}\right)\left(\begin{array}{cc}0& 0\\ 1& 0\end{array}\right)=\left(\begin{array}{cc}1& 0\\ 0& 0\end{array}\right)=\mathrm{ı}p$, one has $\overline{(gf)}=p(gf)\mathrm{ı}=p\mathrm{ı}p\mathrm{ı}=p\mathrm{ı}=1_{Y^{\bullet }}$, the identity cochain map of $Y^{\bullet }$, which is nonzero. Hence $\overline{(gf)}-\bar{g}\bar{f}=1_{Y^{\bullet }}\mathrm{\ne }0$, so transfer is not strictly functorial on cochain maps, and the statement refuted is false.

The failure is consistent with the proposition. The complex $Y^{\bullet }$ is contractible, with contracting homotopy ${\bar{h}}^1=1_k$ and ${\bar{h}}^0={\bar{h}}^2=0$, because in degree $0$ one has $d^{-1}{\bar{h}}^0+{\bar{h}}^1{d}^0=1_k$ and in degree $1$ one has $d^0{\bar{h}}^1+{\bar{h}}^2{d}^1=1_k$. Consequently every endomorphism $u$ of $Y^{\bullet }$, in particular the discrepancy $\overline{(gf)}-\bar{g}\bar{f}$ of step 3.1, is null-homotopic: from $1_{Y^{\bullet }}-0=d\bar{h}+\bar{h}d$ and $ud=du$ one obtains $u=u(d\bar{h}+\bar{h}d)=d(u\bar{h})+(u\bar{h})d$, so $u\simeq 0$ with homotopy $u\bar{h}$. This is exactly the up-to-homotopy functoriality asserted by [L1], so the counterexample refutes strictness only, not the homotopy-class statement. ∎