<jupyter_start><jupyter_text>Computing with generalized morphisms IntroductionA very powerful tool for computing in abelian categories, for example for carrying out diagram chases, are generalized morphisms.Before we start computing with generalized morphisms, we need to understand what generalized morphisms are. DefinitionLet $\mathcal{A}$ be an abelian category and $A,B,X \in \mathrm{Obj}_\mathcal{A}$. A **span** $\phi: A \rightarrow_X B$ is a tuple of morphisms$$A \leftarrow X \rightarrow B,$$consisting of two morphisms with a common source.We call the morphism $X \rightarrow A$ the **reversed arrow** of $\phi$, and $X \rightarrow B$ the **arrow** of $\phi$. A span $\phi: A \rightarrow_X B$ defines a relation between $A$ and $B$, i.e., a subobject of $A \oplus B$. This subobject is defined by the image of the universal morphism into the direct sum $X \rightarrow A \oplus B$.  DefinitionA span $\phi: A \rightarrow_X B$ is **normalized** if the universal morphism $X \rightarrow A \oplus B$ is a monomorphism. Exercise 1> Write a function `is_normalized` that takes two morphisms that form a span and checks if the span is normalized.<jupyter_code>is_normalized := function(reversed_arrow,arrow)
end;<jupyter_output><empty_output><jupyter_text>We provide two test cases for this algorithm, using `LinearAlgebraForCAP`.  Test 1<jupyter_code>LoadPackage( "LinearAlgebraForCAP" );;

QQ := HomalgFieldOfRationals();;

C := VectorSpaceObject( 3, QQ );;

A := 
VectorSpaceMorphism(
VectorSpaceObject( 2, QQ ),
HomalgMatrix( "[1,1,0, 0,1,1]", 2, 3, QQ ), 
C );;

B := 
VectorSpaceMorphism(
VectorSpaceObject( 2, QQ ),
HomalgMatrix( "[1,0,1, 1,1,0]", 2, 3, QQ ), 
C );;

is_normalized(A,B);<jupyter_output><empty_output><jupyter_text>Test 2<jupyter_code>C := VectorSpaceObject( 3, QQ );;

A := 
VectorSpaceMorphism(
C,
HomalgMatrix( "[1,1,0, 0,1,1]", 3, 2, QQ ), 
VectorSpaceObject( 2, QQ ) );;

B := 
VectorSpaceMorphism(
C,
HomalgMatrix( "[1,0,1, 1,1,0]", 3, 2, QQ ), 
VectorSpaceObject( 2, QQ ) );;

is_normalized(A,B);<jupyter_output><empty_output><jupyter_text>Remark1. With a certain equivalence relation, for a given abelian category $\mathcal{A}$ one can define the category of generalized morphisms of $\mathcal{A}$, where the objects are the same as in $\mathcal{A},$ and the morphisms are equivalence classes of spans. The definitions can be found in [SP1](https://dokumentix.ub.uni-siegen.de/opus/volltexte/2017/1179/) and [SG1](https://dokumentix.ub.uni-siegen.de/opus/volltexte/2017/1241/). We will restrict ourselves to just computing with spans, without taking care of the equivalence relation.2. There are other data structures for generalized morphisms are described in the literature above. It is often necessary to compute a normalized span out of a span. Given a span $\phi: A \rightarrow_X B$, an **equivalent normalized span** is computed by first computing the pushout of the two morphisms the span consists of, and then computing the fiber product of the resulting two morphisms.  Exercise 2> Write a function `normalized_representative` that takes two morphisms that form a span and computes the two morphisms that compute a normalized representative. Use test case two from above to check your function.>> To compute a pushout, you can use the GAP commands `Pushout` and `InjectionOfCofactorOfPushout`. The pullback iscomputed using the commands `Pullback` and `ProjectionInFactorOfFiberProduct`.<jupyter_code>normalized_representative := function(reversed_arrow,arrow)
end;<jupyter_output><empty_output><jupyter_text>We call a span **honest** if the reversed arrow of a normalized representative is an isomorphism. Honest spans correspond to morphisms in $\mathcal{A}$, and their **honest representative**, a morphism in $\mathcal{A}$, can be computed by composing the inverse of the reversed arrow with the arrow.  Generalized morphisms in diagram chases Generalized morphisms are a powerful tool to compute in abelian categories, specially for constructing morphisms via diagram chases. To carry out diagram chases, one needs to know how to represent morphisms from $\mathcal{A}$ as spans, how to invert spans, and how to compose spans. Given a morphism $\psi: A \rightarrow B \in \mathrm{Mor}_\mathcal{A}$, the corresponding **honest span** of $\psi$ is the span $$ A \stackrel{\mathrm{id}}{\leftarrow} A \stackrel{\psi}{\rightarrow} B.$$The **pseudo-inverse** of a span $ A \stackrel{\mathrm{\phi}}{\leftarrow} X \stackrel{\psi}{\rightarrow} B$ is the span$$ B \stackrel{\mathrm{\psi}}{\leftarrow} X \stackrel{\phi}{\rightarrow} A.$$ The composition of two given spans can be carried out as follows: Suppose we have two spans$$ A \stackrel{\mathrm{\alpha_1}}{\leftarrow} X \stackrel{\alpha_2}{\rightarrow} B \text{ and } B \stackrel{\mathrm{\beta_1}}{\leftarrow} Y \stackrel{\beta_2}{\rightarrow} C.$$Their composition is a span$$ A \stackrel{\mathrm{\gamma_1}}{\leftarrow} Z \stackrel{\gamma_2}{\rightarrow} C $$with$$ \gamma_1 := \mathrm{ProjectionInFactorOfFiberproduct}(\alpha_2,\beta_1,1) \cdot \alpha_1 $$$$ \gamma_2 := \mathrm{ProjectionInFactorOfFiberproduct}(\alpha_2,\beta_1,2) \cdot \beta_2. $$  Exercise 3> Write a function that computes the composition of two generalized morphisms, given as two lists of two morphisms.<jupyter_code>precompose := function(phi,psi)
    ## composition phi*psi
end;<jupyter_output><empty_output><jupyter_text>Test case<jupyter_code>O1 := VectorSpaceObject(1,QQ);;
O2 := VectorSpaceObject(2,QQ);;
O3 := VectorSpaceObject(3,QQ);;

psi := [ VectorSpaceMorphism( O2, [[-1,1,0],[-1,0,1]], O3 ), IdentityMorphism( O2 ) ];;
phi := [ IdentityMorphism( O1 ), VectorSpaceMorphism(O1,[[1,-1,0]],O3) ];;

# precompose(phi,psi);<jupyter_output><empty_output><jupyter_text>Generalized morphisms in CAP All commands mentioned above are already implemented in the GAP package `GeneralizedMorphismsForCAP`. In this section, we will see how we can use generalized morphisms in `CAP`. As above, we use spans as data structure. The equality of generalized morphisms is the equivalence relation mentioned above, i.e., the equality of morphisms in the generalized morphism category.We start by loading the package.<jupyter_code>LoadPackage("GeneralizedMorphismsForCAP");<jupyter_output><empty_output><jupyter_text>To create the generalized morphism of a morphism, we first need to define an abelian category. For demonstration purposes, we use the category of finite dimensional vector spaces implemented in the `LinearAlgebraForCAP` package.<jupyter_code>LoadPackage("LinearAlgebraForCAP");
QQ := HomalgFieldOfRationals();
vec := MatrixCategory(QQ);<jupyter_output><empty_output><jupyter_text>We can now create morphisms and their generalized counterparts<jupyter_code>O1 := VectorSpaceObject(1,QQ);;
O2 := VectorSpaceObject(2,QQ);;
O3 := VectorSpaceObject(3,QQ);;
m1 := VectorSpaceMorphism(O1,[1,2],O2);;
m2 := VectorSpaceMorphism(O2,[[1,2,3],[1,1,1]],O3);;
m3 := VectorSpaceMorphism(O3,[[1,0],[0,1],[1,1]],O2);;
gm1 := AsGeneralizedMorphismBySpan(m1);;
gm2 := AsGeneralizedMorphismBySpan(m2);;
gm3 := AsGeneralizedMorphismBySpan(m3);;<jupyter_output><empty_output><jupyter_text>We can not only lift morphisms from $\mathcal{A}$ to their generalized counterparts, we can also create a generalized morphism out of two morphisms from $\mathcal{A}$<jupyter_code>m4 := VectorSpaceMorphism(O1,[1,2],O2);;
m5 := VectorSpaceMorphism(O1,[1,2,3],O3);;

GeneralizedMorphismBySpan(m4,m5);<jupyter_output><empty_output><jupyter_text>To compose two generalized morphisms, use the usual `PreCompose` command.<jupyter_code>gm4 := PreCompose(gm1,gm2);<jupyter_output><empty_output><jupyter_text>You can check for honesty using `IsHonest`, and compute a honest representative via `HonestRepresentative`<jupyter_code>IsHonest(gm4);
hon := HonestRepresentative(gm4);<jupyter_output><empty_output><jupyter_text>Please note that the honest representative is the composition of `m1` and `m2`.<jupyter_code>Display(hon);
Display(PreCompose(m1,m2));<jupyter_output>[ [  3,  4,  5 ] ]

A morphism in Category of matrices over Q
[ [  3,  4,  5 ] ]

A morphism in Category of matrices over Q<jupyter_text>To compute the pseudo-inverse, use the `PseudoInverse` command<jupyter_code>pgm3 := PseudoInverse(gm3);<jupyter_output><empty_output><jupyter_text>Note that the pseudo-inverse of a non-isomorphism is not a honest morphism<jupyter_code>IsHonest(pgm3);<jupyter_output><empty_output><jupyter_text>As a first example to emphasize the use of the pseudo-inverse we demonstrate how one can use the generalized morphisms to compute a kernel lift.<jupyter_code>phi := VectorSpaceMorphism(O3,[[1,0,0],[1,0,0],[1,0,0]],O3);
tau := VectorSpaceMorphism(O1,[[1,-1,0]],O3);<jupyter_output><empty_output><jupyter_text>The compostion of `tau` and `phi` is zero, so we can compute a kernel lift.<jupyter_code>IsZero(PreCompose(tau,phi));
Display(KernelLift(phi,tau));<jupyter_output>[ [  -1,   0 ] ]

A morphism in Category of matrices over Q<jupyter_text>To compute the kernel lift via generalized morphisms, we take the pseudo inverse of the kernel embedding of `phi`, compose it with `tau`, and compute the honest representative.<jupyter_code>kappa_inv := PseudoInverse( AsGeneralizedMorphismBySpan( KernelEmbedding( phi )));
lift_gen := PreCompose( AsGeneralizedMorphismBySpan( tau ), kappa_inv );
Display( HonestRepresentative( lift_gen ) );<jupyter_output>[ [  -1,   0 ] ]

A morphism in Category of matrices over Q<jupyter_text>Computing with generalized morphisms We will now learn how to carry out more demanding computations using generalized morphisms.None of the computations in this chapter will depend on the actual category we are working with, and can be carried out in any computable abelian category.We will first look at homology. Given a chain complex $C_\bullet$ in an abelian category$$ \cdots \leftarrow C_{i-1} \stackrel{\partial_i}{\leftarrow} C_i \stackrel{\partial_{i+1}}{\leftarrow} C_{i+1}  \leftarrow \cdots$$the $i$-th homology is defined as$$ H_i( C_\bullet) := \mathrm{KernelObject}(\partial_i) / \mathrm{ImageObject}(\partial_{i+1}). $$We call the span$$ H_i( C_\bullet) \leftarrow \mathrm{KernelObject}(\partial_i) \rightarrow C_i $$that arises from the computation of the homology the **$i$-th homology embedding.**  Exercise 4> Write a function that computes the homology embedding, given two morphisms $\partial_0$ and $\partial_1$ in a complex. To do so, you first need to find out how the homology is computed in terms of abelian categories.<jupyter_code>homology_embedding := function(delta_i_p_1, delta_i)
end;<jupyter_output><empty_output><jupyter_text>Test case<jupyter_code>delta_i_p_1 := VectorSpaceMorphism(
O2, [[1,1,1],[1,1,1]], O3);;
delta_i := VectorSpaceMorphism(
O3, [[2],[-1],[-1]],O1);;

c := PreCompose( delta_i_p_1, delta_i );;
Display(c);

# homology_embedding(delta_i_p_1, delta_i);<jupyter_output>[ [  0 ],
  [  0 ] ]

A morphism in Category of matrices over Q<jupyter_text>The homology embedding provides a way to compute the functoriality of the homology. Given two chain complexes $(C_\bullet,\partial)$ and $(D_\bullet,\delta)$, a chain map $\alpha_\bullet: C_\bullet \rightarrow D_\bullet$ is a collection of morphisms $\alpha_i: C_i \rightarrow D_i$ such that$$ \alpha_i \cdot \delta_i = \partial_i \cdot \alpha_{i-1}.$$A chain map defines a morphism between the $i$-th homologies of the two complexes. We can compute this by composing the homology embedding of $C_\bullet$ with $\alpha_i$ and the pseudo-inverse of the homology embedding of $D_\bullet$, and then taking the honest representative of the composition.  Exercise 5> Write a function that, given two parts of a complex and a chain morphism, computes the functoriality between the two homologies.<jupyter_code>homology_functor := function(partial_i, partial_i_1,alpha_i,delta_i,delta_i_1)
end;<jupyter_output><empty_output><jupyter_text>Test case<jupyter_code>partial_i_p_1 := VectorSpaceMorphism(
O2, [[1,1,1],[1,1,1]], O3);;
partial_i := VectorSpaceMorphism(
O3, [[2],[-1],[-1]],O1);;

delta_i_p_1 := VectorSpaceMorphism(
O3,[[1,1,1],[0,1,0],[1,-1,1]],O3);;
delta_i := UniversalMorphismIntoZeroObject( O3 );;

alpha_i := IdentityMorphism( O3 );;

# homology_functor(partial_i, partial_i_p_1,alpha_i,delta_i,delta_i_p_1)<jupyter_output><empty_output>
{'fraction_non_alphanumeric': 0.11949276540399935, 'fraction_numerical': 0.019996748496179485, 'mean_word_length': 6.318857822724569, 'pattern_counts': {'":': 0, '<': 85, '<?xml version=': 0, '>': 92, 'https://': 2, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '22', 'dir': 'jupyter-structured-clean-dedup', 'id': '521684', 'license': 'MIT', 'n_tokens_mistral': 4104, 'n_tokens_neox': 3800, 'n_words': 1280, 'path': 'materials/Generalized morphisms.ipynb', 'repo_name': 'homalg-project/capdays-2018', 'size': '12302'}