Lobachevskii Journal of Mathematics

http://ljm.ksu.ru

Vol. 17, 2005, 211 – 228 \begin{matrix}c \\ ◯ \end{matrix} V. Rechnoi

V. Rechnoi

EXISTENCE THEOREMS FOR COMMUTATIVE DIAGRAMS

(submitted by B. Shapukov)

Abstract. Given a relation f ⊂ A × B, there exist two symmetric relations (see [1], Chapter 2) f^{−1}f ⊂ A^{2}, ff^{−1} ⊂ B^{2}. These relations make it possible to formalize definitions and proofs of existence theorems. For example, the equation h = gf, where h and g (or h and f) are given maps, admits a solution f (g, respectively.) if and only if hh^{−1} ⊂ gg^{−1}(h^{−1}h ⊃ f^{−1}f). Well-known ,,homomorphism theorems” get more general interpretation. Namely, any map can be represented up to bijection as a composition of surjection and injection, and any morphism of diagrams can be represented up to isomorphism as a composition of epimorphism and monomorphism. In this paper we further develop the scheme from [2] and consider it as an application in category of vector spaces and linear maps.

1. Introduction and Preliminaries

We use the symbol ,,⇒” instead of the conditional sentence ,,if ..., then ...” or instead of ,,from ... it follows ...”, and we use the symbol ,,⇔” instead of ,, ... if and only if ...”.

Suppose A and B be two sets. We say that any subset of the direct product A × B (also an empty set and the set A × B itself) is called a

2000 Mathematical Subject Classification. 03E20, 15A23, 37C10. Key words and phrases. Existence of absent maps in commutative diag-

rams, Map iterations.

relation between sets A and B and is denoted by

f ⊂ A × B.

If (a, b) ∈ f, then we say that elements a ∈ A and b ∈ B are connected by relation f or simply f-connected.

The inverse relation f^{−1} ⊂ B × A is defined by

(a, b) ∈ f ⇔ (b, a) ∈ f^{−1}.

It is clear that (f^{−1})^{−1} = f.

Given a relation f ⊂ A × B, let us define for element a ∈ A the image f(a) in B and for element b ∈ B the original f^{−1}(b) in A by

(a, b) ∈ f ⇔ b ∈ f(a) ⇔ a ∈ f^{−1}(b),

and also define for subset U ⊂ A the image f(U) = ⋃_{a∈U} f(a) and for

subset V ⊂ B the original f^{−1}(V) = ⋃_{b∈V} f^{−1}(b).

A relation f can be defined in the product A × A = A^{2}. Then it is possible that f = f^{−1}. In this case the relation f is called symmetric. For example, the diagonal of the set A^{2}, denoted

1_{A} = {(a_{1}, a_{2}) ∈ A^{2}|a_{1} = a_{2}} ,

is a symmetric relation.

For any two relations f ⊂ A × B and g ⊂ B × C there exists the composition h ⊂ A × C (denoted by h = gf and read: h is composition of relations f and g) such that

(a, c) ∈ h ⇔ f(a) ∩ g^{−1}(c) ≠ ∅.

It follows that elements a ∈ A and c ∈ C are h-connected if and only if the element a is f-connected to some element b ∈ B and the elements b and c are g-connected.

The composition of relations has the following properties.

1) For any three relations f_{1} ⊂ A_{1}×A_{2}, f_{2} ⊂ A_{2}×A_{3} and f_{3} ⊂ A_{3}×A_{4} (associativity of compositions)

(f_{3}f_{2})f_{1} = f_{3}(f_{2}f_{1})

is valid in the set A_{1} ×A_{4}. From this follows, that the composition f_{3}f_{2}f_{1} is understood uniquely.

2) The rule of inversion of composition:

h = gf ⇔ h^{−1} = (gf)^{−1} = f^{−1}g^{−1}.

3) Given a relation f ⊂ A × B, there exist two symmetric relations

f^{−1}f ⊂ A^{2}, ff^{−1} ⊂ B^{2}

such that

(a_{1}, a_{2}) ∈ f^{−1}f ⇔ f(a_{1}) ∩ f(a_{2}) ≠ ∅,
(b_{1}, b_{2}) ∈ ff^{−1} ⇔ f^{−1}(b_{1}) ∩ f^{−1}(b_{2}) ≠ ∅.

Proposition 1.1. Suppose a relation f ⊂ A × B satisfies one of inclusions

(1)  ff^{−1} ⊂ 1_{B},  (2)  f^{−1}f ⊃ 1_{A},
(3)  f^{−1}f ⊂ 1_{A},  (4)  ff^{−1} ⊃ 1_{B}.

If inclusion (1) holds (inclusion (2), respectively), then for any element a ∈ A the image f(a) contains at most (at least) one element from set B. If inclusion (3) holds (inclusion (4), respectively), then for any element b ∈ B the original f^{−1}(b) contains at most (at least) one element from A.

Proof. First, we have

(1) ⇒ ∀b_{1}, b_{2} ∈ f(a), (b_{1}, b_{2}) ∈ ff^{−1} ⊂ 1_{B} ⇒ b_{1} = b_{2};

from (1) it follows that for any element a ∈ A the image f(a) is empty or contains only one element from B. Second,

(2) ⇒ ∀a ∈ A, (a, a) ∈ 1_{A} ⊂ f^{−1}f ⇒ f(a) ≠ ∅;

from (2) it follows that for any element a ∈ A the image f(a) is nonempty, i.e., contains at least one element from B. The inclusions (3) and (4) for relation f coincide with inclusions (1) and (2) for inverse relation f^{−1}, respectively. □

These inclusions are the basis for the following definitions.

Definition 1.1. The relation f ⊂ A × B is said to be

– a function from set A to set B, if inclusion (1) holds;

– a map from set A to set B, if inclusions (1) and (2) hold;

– an injection from set A to set B, if inclusions (1), (2) and (3) hold;

– a surjection from set A onto set B, if inclusions (1), (2) and (4) hold;

– a bijection between sets A and B, if inclusions (1), (2), (3) and (4) hold;

– a multi-valued map from set A to set B, if inclusion (2) holds.

There are also other names: for example, a bijection is also called an one-to-one correspondence between sets A and B, an injection is called an one-to-one map from A to B and a surjection is also called a map from A onto B.

We say that the relation f ⊂ A × B is left-invertible, if f^{−1}f = 1_{A}, see inclusions (2) and (3), or right-invertible, if ff^{−1} = 1_{B}, see inclusions (1) and (4). Thus, an injection is a left-invertible map and a surjection is a right-invertible map. A bijection is both left-invertible and rightinvertible.

It follows that an equality of relations is reducible by injection from left and by surjection from right, i.e., if g is injection, then gf_{1} = gf_{2} ⇒ g^{−1}gf_{1} = g^{−1}gf_{2} ⇒ f_{1} = f_{2}; if f is surjection, then g_{1}f = g_{2}f ⇒ g_{1}ff^{−1} = g_{2}ff^{−1} ⇒ g_{1} = g_{2}.

A map from one set to another is the most important relation since any function can be expanded to a map and any multi-valued map can be restricted to a map, i.e., if g is a function, then there always exists the map f such that f ⊃ g; if g is a multi-valued map, then there always exists the map f such that f ⊂ g.

Inclusions (1)–(4) allow to prove some statements without using elements. Let us prove, that for any map f the following equalities hold (we use them below in the proof of Theorem 2.1):

ff^{−1}f = f, f^{−1}ff^{−1} = f^{−1}.

By definition, the map f satisfies the inclusions (1) and (2). Then we have

(1) ⇒ ff^{−1}f = (ff^{−1})f ⊂ f,
(2) ⇒ ff^{−1}f = f(f^{−1}f) ⊃ f.

Hence, it follows that ff^{−1}f = f. From (ff^{−1}f)^{−1} = f^{−1}ff^{−1} = f^{−1} we obtain the second equality.

For a map f the relation f^{−1}f ⊂ A^{2} is an equivalence relation on a set A since f^{−1}f satisfies

(i) reflexivity: f^{−1}f ⊃ 1_{A},

(ii) symmetry: (f^{−1}f)^{−1} = f^{−1}f,

(iii) transitivity: (f^{−1}f)^{2} = f^{−1}ff^{−1}f = f^{−1}f. Thus we have a partition of A into equivalence classes.

2. Existence Theorems

Throughout this paper we use the following notation: f : A → B or A ⟶^{f} B denotes a map f from a set A to a set B, while the arrows

[figure]and [figure]are used for an injection and a surjection, respectively.

Suppose the map h is a composition of the maps f and g, i.e. h = gf, then a triangular diagram

\xymatrix{A \ar[rr]^{h} \ar[dr]_{f} &  & C \\  & B \ar@{-->}[ur]_{g}}

is called commutative.

If one of the maps f and g is missing how we can find the absent map such that the diagram is commutative? Namely, how to solve the equation h = gf with respect to f, if the maps g and h are given, or with respect to g, if f and h are given. The inclusions

(5) hh^{−1} ⊂ gg^{−1}  (6) h^{−1}h ⊃ f^{−1}f

give us an answer to this question.

Theorem 2.1. a) Suppose the maps g and h are given. Let the inclusion (5) hold. Then there exists a map f such that h = gf. Moreover, the map f is obtained by restriction of the multi-valued map g^{−1}h.

b) Suppose the maps f and h are given. Let the inclusion (6) hold. Then there exists a map g such that h = gf. Moreover, the map g is obtained by extension of the function hf^{−1}.

Proof. a) First, consider the relation g^{−1}h. From (5) it follows that

(g^{−1}h)^{−1}g^{−1}h = h^{−1}gg^{−1}h ⊃ h^{−1}hh^{−1}h = h^{−1}h ⊃ 1_{A}.

It means that g^{−1}h satisfies inclusion (2). Hence, the relation g^{−1}h is a multi-valued map which we may restrict to a map f. Then we have

f ⊂ g^{−1}h ⇒ gf ⊂ gg^{−1}h ⊂ h

(since the map g satisfies inclusion (1)) and, on the other hand,

f^{−1} ⊂ h^{−1}g ⇒ h ⊂ hf^{−1}f ⊂ hh^{−1}gf ⊂ gg^{−1}gf ⊂ gf

(since the condition (5) holds and the map f satisfies inclusion (2)). Finally, from the inclusions h ⊃ gf and h ⊂ gf we obtain the equality h = gf. b) Consider the relation hf^{−1}. From (6) it follows that

hf^{−1}(hf^{−1})^{−1} = hf^{−1}fh^{−1} ⊂ hh^{−1}hh^{−1} = hh^{−1} ⊂ 1_{C}.

It means that hf^{−1} satisfies inclusion (1). Therefore, the relation hf^{−1} is a function which is possible to extend to a map g. Then we have

g ⊃ hf^{−1} ⇒ gf ⊃ hf^{−1}f ⊃ h

(since the map f satisfies inclusion (2)) and, on the other hand,

g^{−1} ⊃ fh^{−1} ⇒ h ⊃ gg^{−1}h ⊃ gfh^{−1}h ⊃ gff^{−1}f ⊃ gf

(since the condition (6) holds and the map g satisfies inclusion (1)). Similarly, from the inclusions h ⊃ gf and h ⊂ gf we obtain the equality h = gf. □

Remark. Notice, that we don’t use elements in proof of Theorem 2.1. But if we use elements, then in the case a) the inclusion (5) is equivalent to the inclusion h(A) ⊂ g(B). We construct the map f : A → B so that for element a ∈ A the image f(a) ∈ B has to satisfy the condition g(f(a)) ∈ h(A). Because of h(A) ⊂ g(B) it is possible that the condition g(f(a)) ∈ h(A) holds for each element a ∈ A. In the case b) the set A has two equivalence relations f^{−1}f and h^{−1}h. Thus we have two partitions of A into equivalence classes. From (6) it follows that the first partition is a refinement of the second one. For b ∈ f(A) we have g(b) = hf^{−1}(b) since hf^{−1} is a function. For b ∈ B outside f(A) we choose g(b) arbitrary.

However, it is preferable to use the inclusions (1)–(6) instead of using elements of the sets. As they say, these inclusions formalize proofs.

Consecuence 1. Suppose the inclusion (5) holds and the map g is an injection. Then the relation g^{−1}h is a map: g^{−1}h(g^{−1}h)^{−1} = g^{−1}hh^{−1}g ⊂ g^{−1}g = 1_{B} (besides (2) inclusion (1) also holds for this relation), and the map f is defined uniquely by f = g^{−1}h.

Consecuence 2. Suppose the inclusion (6) holds and the map f is a surjection. Then the relation hf^{−1} is a map: (hf^{−1})^{−1}hf^{−1} = fh^{−1}hf^{−1} ⊃ ff^{−1} = 1_{B} (besides (1) inclusion (2) also holds for this relation), and the map g is defined uniquely by g = hf^{−1}.

Consecuence 3. If g is a surjection, gg^{−1} = 1_{C}, then inclusion (5) is valid automatically and there always exists the map f such that h = gf.

Consecuence 4. If f is an injection, f^{−1}f = 1_{A}, then inclusion (6) is valid automatically and there always exists the map g such that h = gf.

Consecuence 5. For a composition h = gf with h injective it follows that f is also injective:

h^{−1}h ⊂ 1_{A} ⇒ f^{−1}f ⊂ f^{−1}g^{−1}gf = h^{−1}h ⊂ 1_{A}.

Similarly, if h is a surjection, then g is a surjection too:

hh^{−1} ⊃ 1_{C} ⇒ gg^{−1} ⊃ gff^{−1}g^{−1} = hh^{−1} ⊃ 1_{C}.

In particular, if gf = 1_{A}, then the map f is always injection and the map g is always surjection. In this case f is called a section of the surjection g, while g is called a retraction of the injection f.

Definition 2.1. If in the composition h = gf the map f is a surjection and g is an injection, the commutative diagram

[figure: A; h; f; C; B; g]

is said to represent a canonical representation of the map h.

Theorem 2.2. For any map h : A → C the canonical representation is defined up to natural bijection. It means if h has two canonical representations h = g_{1}f_{1} and h = g_{2}f_{2}, see diagram below, then there exists the unique bijection β : B_{1} → B_{2} such that the entire diagram

[figure: A; f_{2}; h; f_{1}; C; B_{1}; g_{1}; β; B_{2}; g_{2}]

is commutative, i.e., f_{2} = βf_{1} and g_{1} = g_{2}β.

Proof. Since h = g_{1}f_{1} = g_{2}f_{2} we have

hh^{−1} = g_{1}f_{1}f_{1}^{−1}g_{1}^{−1} = g_{2}f_{2}f_{2}^{−1}g_{2}^{−1} ⇔ g_{1}g_{1}^{−1} = g_{2}g_{2}^{−1}

(since f_{1} and f_{2} are surjections) and

h^{−1}h = f_{1}^{−1}g_{1}^{−1}g_{1}f_{1} = f_{2}^{−1}g_{2}^{−1}g_{2}f_{2} ⇔ f_{1}^{−1}f_{1} = f_{2}^{−1}f_{2}

(since g_{1} and g_{2} are injections). The first relation means that for triangle B_{1}B_{2}C the inclusion (5) holds, i.e., g_{1}g_{1}^{−1} ⊂ g_{2}g_{2}^{−1}. Analogously, the second relation means that for triangle AB_{1}B_{2} the inclusion (6) holds, i.e., f_{2}^{−1}f_{2} ⊃ f_{1}^{−1}f_{1}. Hence, from Theorem 2.1 it follows that the maps β_{1} : B_{1} → B_{2} and β_{2} : B_{1} → B_{2} are defined in triangles B_{1}B_{2}C and AB_{1}B_{2}, respectively. Thus we have

g_{1} = g_{2}β_{1}, f_{2} = β_{2}f_{1}, h = g_{2}β_{1}f_{1} = g_{2}β_{2}f_{1}.

If we now reduce the last equality by surjection f_{1} from right and by injection g_{2} from left, then we obtain β_{1} = β_{2} = β. From Consequences 1 and 5 it follows that β is uniquely defined bijection. □

The next two theorems are generalizations of Theorem 2.

Theorem 2.3. Suppose we have a prism diagram with faces I, II and III:

[figure: A; α; h; f; C; γ; B; g; β; III; II; I; A′; h′; f′; C′; B′; g′]

where the face I is a commutative square, i.e., γh = h′α. The maps h and h′ have canonical representations h = gf and h′ = g′f′, respectively. Then there exists the unique map β such that the faces II and III are commutative.

Proof. First, let us consider the commutative triangle AA′C′ on the face I, where arrow AC′ is a composition γh. The inclusion (5) is valid for this triangle, i.e.,

γh(γh)^{−1} ⊂ h′h^{′−1}
⇔ γhh^{−1}γ^{−1} ⊂ h′h^{′−1}
⇔ γgff^{−1}g^{−1}γ^{−1} ⊂ g′f′f^{′−1}g^{′−1}
⇔ γgg^{−1}γ^{−1} ⊂ g′g^{′−1}
⇔ γg(γg)^{−1} ⊂ g′g^{′−1}

(since f and f′ are surjections, ff^{−1} = 1_{B}, f′f^{′−1} = 1_{B′}). Moreover, this inclusion is also inclusion (5) for triangle BB′C′, where arrow BC′ is a composition γg. Hence, there exists the unique map β_{1} such that

γg = g′β_{1}

(see Theorem 2.1 and Consequence 1).

Second, let us consider the commutative triangle ACC′ on the face I, where arrow AC′ is a composition h′α. The inclusion (6) is valid for this triangle, i.e.,

(h′α)^{−1}h′α ⊃ h^{−1}h
⇔ α^{−1}h^{′−1}h′α ⊃ h^{−1}h
⇔ α^{−1}f^{′−1}g^{′−1}g′f′α ⊃ f^{−1}g^{−1}gf
⇔ α^{−1}f^{′−1}f′α ⊃ f^{−1}f
⇔ (f′α)^{−1}f′α ⊃ f^{−1}f

(since g and g′ are injections, g^{−1}g = 1_{B}, g^{′−1}g′ = 1_{B′}). Moreover, this inclusion is also inclusion (6) for triangle ABB′, where arrow AB′ is a composition f′α. Hence, there exists the unique map β_{2} such that

f′α = β_{2}f

(see Theorem 2.1 and Consequence 2).

Now we write f on the right of the both sides of equality γg = g′β_{1} and g′ on the left of the both sides of equality f′α = β_{2}f. From γgf = g′f′α (or γh = h′α) it follows that

g′β_{1}f = g′β_{2}f.

By using reduction we obtain β_{1} = β_{2} = β (since f is a surjection and g′ – an injection). □

Definition 2.2. If in the prism diagram from Theorem 3 the faces I, II and III are commutative, a triple (α, β, γ) is said to define the morphism of two diagrams ABC and A′B′C′. A morphism is a monomorphism (epimorphism) of diagrams, if α, β and γ are injections (surjections, respectively). A morphism, which is both epi- and monomorphism, is called an isomorphism of diagrams. A canonical representation of morphism of diagrams ABC and A′B′C′ is it presentation in composition of epimorphism and monomorphism.

Theorem 2.4. The canonical representation of morphism of diagrams ABC and A′B′C′ exists up to isomorphism. It means that there exists a commutative diagram UV W such that the entire diagram

[figure: A; α; h; f; C; β; B; g; γ; U; h′′; f′′; W; A′; h′; f′; C′; V; g′′; B′; g′]

is commutative and the diagram UV W is defined up to isomorphism.

Proof. The sets U, V and W are obtained up to isomorphism by canonical representation of the maps α, β and γ, respectively, see Theorem 2.2. Applying Theorem 2.3 for each prism diagram AUA′BV B′, BV B′CW C′ and AUA′CW C′ separately we obtain maps f′′, g′′ and h′′. It is easily proved that h′′ = g′′f′′ and the triangle UV W is defined up to isomorphism. □

Theorem 2.5. For any commutative square ACC′A′ there exists a decomposition on blocks:

[figure: A; B; C; U; V; W; A′; B′; C′]

where the northwest block ABV U consists of surjections, while the southeast block V W C′B′ consists of injections. This decomposition is defined up to isomorphism.

Proof. This diagram is a particular case of diagram from Theorem 2.4, if triangles ABC, A′B′C′ and UV W define the canonical distributions of the maps h, h′ and h′′, respectively. □

Let us apply the map h : A → A repeatedly to the set A. Let h = g_{1}f_{1} be a canonical representation of h. Then we may construct a map h_{1} = f_{1}g_{1}, which has a canonical representation h_{1} = g_{2}f_{2}. Thus, the canonical representation of the second iteration is

h^{2} = g_{1}f_{1}g_{1}f_{1} = g_{1}h_{1}f_{1} = g_{1}g_{2}f_{2}f_{1}.

Continuing in the same way, we see that the result of iterations m times is

h^{m} = g_{1}g_{2}...g_{m}f_{m}...f_{2}f_{1},

where f_{m}...f_{2}f_{1} and g_{1}g_{2}...g_{m} are compositions of surjections and injections, respectively.

Theorem 2.6. Let h be a map from set A to itself:

h : A → A.

Let us form the sequence of maps

h, h_{1}, h_{2}, ..., h_{k−1}, h_{k}, ...,

where h_{1} = f_{1}g_{1} : B_{1} → B_{1} is defined after canonical representation h = g_{1}f_{1}, and h_{k} = f_{k}g_{k} : B_{k} → B_{k} after canonical representation h_{k−1} = g_{k}f_{k}, k = 2, 3, ... If A is a finite set, then there exist the minimal integers m and n, such that

h^{m+n} = h^{m} ⇔ (h_{m})^{n} = 1_{B_{m}}
[figure: A; h; f_{1}; A; h; f_{1}; A; h; f_{1}; ...; h; A; h; ...; h; A; B_{1}; h_{1}; g_{1}; f_{2}; B_{1}; h_{1}; g_{1}; f_{2}; ...; h_{1}; B_{1}; h_{1}; g_{1}; ...; h_{1}; B_{1}; g_{1}; B_{2}; h_{2}; f_{3}; g_{2}; ...; h_{2}; B_{2}; h_{2}; g_{2}; ...; h_{2}; B_{2}; g_{2}; ...; f_{m}; ...; g_{3}; ...; g_{3}; B_{m}; g_{m}; h_{m}; (h_{m})^{n}; ...; h_{m}; B_{m}; g_{m}]

It means, that after n steps the iteration h^{m} repeats if and only if h_{m} : B_{m} → B_{m} is a bijection and (h_{m})^{n} is identical map.

Proof. Let us show using mathematical induction, that the iteration h^{m} admits the canonical representation

h^{m} = g_{1}g_{2}...g_{m}f_{m}...f_{2}f_{1}.

Suppose it is true for h^{m−1}. Then from g_{k}f_{k} = f_{k−1}g_{k−1}, k = 2, 3, ..., m, it follows that

h^{m} = h^{m−1}h = g_{1}g_{2}...g_{m−1}f_{m−1}...f_{2}f_{1}(g_{1}f_{1}) =
= g_{1}g_{2}...g_{m−1}f_{m−1}...f_{2}(f_{1}g_{1})f_{1} = g_{1}g_{2}...g_{m−1}f_{m−1}...f_{2}(g_{2}f_{2})f_{1} =

= g_{1}g_{2}...g_{m−1}f_{m−1}...(f_{2}g_{2})f_{2}f_{1} = g_{1}g_{2}...g_{m−1}f_{m−1}...(g_{3}f_{3})f_{2}f_{1} = ... =

= g_{1}g_{2}...g_{m}f_{m}...f_{2}f_{1}.

The iteration h^{m+n} admits the canonical representation

h^{m+n} = g_{1}g_{2}...g_{m}(h_{m})^{n}f_{m}...f_{2}f_{1}.

The equality h^{m+n} = h^{m} means that

g_{1}g_{2}...g_{m}(h_{m})^{n}f_{m}...f_{2}f_{1} = g_{1}g_{2}...g_{m}f_{m}...f_{2}f_{1}.

If we reduce both sides of the last equality by surjections f_{1}, f_{2}, ..., f_{m} from right and by injections g_{1}, g_{2}, ..., g_{m} from left, we obtain (h_{m})^{n} = 1_{B_{m}}.

Such integers m and n exist, since the number of elements in the sets A, B_{1}, B_{2}, ... not increase. □

3. Canonical representation of matrix

Let us show, that a linear map between two finite-dimensional vector spaces has a canonical representation to composition of epimorphism and monomorphism, and this representation is defined up to isomorphism. It means, that the diagram from Theorem 2.2 remains the same for vector spaces and linear maps.

Let A and C be vector spaces of dimensions n and m, respectively. Then the linear map h : A → C is defined by m × n-matrix H. If h is an epimorphism (monomorphism), then the rows (columns, respectively) of H are linearly independent. If h is an isomorphism, then the matrix H is nonsingular.

Theorem 3.1. Suppose p is the rank of matrix H. Then the matrix H can be represented as a product H = GF, where F is a surjective p × nmatrix and G is an injective m × p-matrix. Therefore, for any other product of surjective p × n-matrix F′ and injective m × p-matrix G′ such that H = G′F′, there exists a non-degenerated p × p-matrix Q such that G′ = GQ^{−1}, F′ = QF and H = (GQ^{−1})(QF).

Proof. Without loss of generality it can be assumed that the matrix H is a block matrix

H = (\begin{matrix}U & | & Y \\ − − − & | & − − − \\ X & | & V \end{matrix}) ,

where block U is a rank minor. The blocks U, X, Y and V are matrices of orders p×p, (m−p)×p, p×(n−p) and (m−p)×(n−p), respectively, with respect to the order of m × n-matrix H. The southeast block V may be expressed by the blocks X, U and Y:

V = XU^{−1}Y.

Indeed, the columns (\begin{matrix}Y \\ − − − \\ V \end{matrix}) may be written as linear combinations

of the columns (\begin{matrix}U \\ − − − \\ X \end{matrix}). In other words, there exist p × (n − p)-matrix

Z, such that

(\begin{matrix}Y \\ − − − \\ V \end{matrix}) = (\begin{matrix}U \\ − − − \\ X \end{matrix}) (Z)

or Y = UZ and V = XZ. Since U is nonsingular, we have Z = U^{−1}Y and V = XU^{−1}Y. By the way, the rows (X | V ) may be written as linear combinations of the rows (U | Y ):

(X | V ) = (XU^{−1}) (U | Y ) .

Thus, we have

H = (\begin{matrix}U \\ − − − \\ X \end{matrix}) · (E_{p} | U^{−1}Y ) = (\begin{matrix}E_{p} \\ − − − \\ XU^{−1} \end{matrix}) · (U | Y ) ,

where E_{p} is a unit matrix of order p. In both expressions of H the right matrices are surjective and the left matrices are injective.

Let us consider the diagram from Theorem 2.2. Now the arrows h, f, g, f′, g′ and β are expressed by the matrices H, F, G, F′ = QF, G′ = GQ^{−1} and Q, respectively:

\xymatrix{A \ar[ddr]_{F′} \ar[rr]^{H} \ar[dr]^{F} &  & C \\  & B_{1} \ar@{-->}[ur]^{G} \ar[d]^{Q} \\  & B_{2} \ar[uur]_{G′}}

where Q is non-degenerated matrix. Thus, from H = GF we obtain any other decomposition H = (GQ^{−1})(QF) with respect to arbitrary non-degenerated matrix Q. □

The following table shows the especial role of matrices XU^{−1} and U^{−1}Y:

Rows  Columns
Imh^{∗} ⊂ A^{∗}  Kerh ⊂ A
(E_{p} | U^{−1}Y ) (\begin{matrix}−U^{−1}Y \\ − − − \\ E_{m−p} \end{matrix} )
Kerh^{∗} ⊂ C^{∗}  Imh ⊂ C
(−XU^{−1} | E_{n−p}) (\begin{matrix}E_{p} \\ − − − \\ XU^{−1} \end{matrix})

The basis of kernel Kerh and image Imh of a linear map h : A → C are represented by the columns of right hand side matrices. It is clear that the matrices from the second column annihilate the matrices from the first column. It means that the image Imh^{∗} and kernel Kerh^{∗} of the dual map h^{∗} : C^{∗} → A^{∗} are represented by the rows of the left hand side matrices, respectively.

4. Exponential of matrix

For any square matrix H of order n (as an element of Lie algebra gl(n, ℝ) of a Lie group GL(n, ℝ)) there exists the exponential

e^{tH} = ∑_{k=0}^{∞} \frac{(tH)^{k}}{k!} ,

which is a one-parameter subgroup of GL(n, ℝ). Moreover, in space ℝ^{n} there exists a linear vector field X (dynamic system) generated by the matrix H. The flow of the vector field X is defined by the exponential law (see [3])

U′ = HU ⇒ U_{t} = e^{tH}U

and is denoted by a_{t} : U ↦ U_{t}. It means, that an arbitrary point U ∈ ℝ^{n} moves along its own trajectory U_{t} with initial velocity U′.

The canonical representation of the matrix H (see Theorem 3.1) allows to find the exponential e^{tH} and the flow a_{t} (see the next example).

Example. Let

h = (\begin{matrix}1 & 2 & 3 & 4 & 5 \\ 2 & 1 & 1 & 3 & 2 \end{matrix})

be a map from set A = {1, 2, 3, 4, 5} to itself. Let us represent the map h as a square matrix H = (h_{ij}) by

h_{ij} = \begin{cases}1, & if j = h(i), \\ 0, & if j ≠ h(i), \end{cases} i, j = 1, ..., 5.

Corresponding to the scheme from Theorem 2.6 the equality of iterations h^{4} = h^{2} can be written

h^{4} = g_{1}g_{2}h_{2}^{2}f_{2}f_{1},
H^{4} = G_{1}G_{2}H_{2}^{2}F_{2}F_{1},

(\begin{matrix}0 & 1 & 0 & 0 & 0 \\ 1 & 0 & 0 & 0 & 0 \\ 1 & 0 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 \\ 0 & 1 & 0 & 0 & 0 \end{matrix})^{4} = (\begin{matrix}0 & 1 & 0 \\ 1 & 0 & 0 \\ 1 & 0 & 0 \\ 0 & 0 & 1 \\ 0 & 1 & 0 \end{matrix})·(\begin{matrix}0 & 1 \\ 1 & 0 \\ 1 & 0 \end{matrix})·(\begin{matrix}0 & 1 \\ 1 & 0 \end{matrix})^{2}·(\begin{matrix}1 & 0 & 0 \\ 0 & 1 & 0 \end{matrix})·(\begin{matrix}1 & 0 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 \end{matrix}) .

Each matrix from the last equality corresponds to a linear map: endomorphism H : ℝ^{5} → ℝ^{5}, two epimorphisms F_{1} : ℝ^{5} → ℝ^{3}, F_{2} : ℝ^{3} → ℝ^{2}, automorphism H_{2} : ℝ^{2} → ℝ^{2} and two monomorphisms G_{2} : ℝ^{2} → ℝ^{3}, G_{1} : ℝ^{3} → ℝ^{5} (in this paper, matrices and corresponding linear maps are denoted by the same symbol). After two iterations we have

KerH ⊂ KerH^{2} = KerH^{3}, ImH ⊃ ImH^{2} = ImH^{3}.

Let {x^{i}} be the coordinates of space ℝ^{5} according to the usual basis {e_{i}}, i = 1, ..., 5. Then the kernel KerH is a two-dimensional coordinate plane x^{1} = x^{2} = x^{3} = 0, the kernel KerH^{2} is a three-dimensional coordinate space x^{1} = x^{2} = 0, the image ImH is a three-dimensional hyperplane spanned by vectors {e_{2} + e_{3}, e_{1} + e_{5}, e_{4}} and ImH^{2} is a twodimensional plane spanned by vectors {e_{2} + e_{3}, e_{1} + e_{4} + e_{5}}.The second iteration of the automorphism H_{2} is the identical map of the plane ImH^{2}. Thus, from Theorem 2.6 it follows that

H^{4} = H^{2} ⇔ H_{2}^{2} = E_{2},

where E_{2} is a unit matrix of order 2.

This result is useful in the next situation. Let us consider the matrix H as an element of Lie algebra gl(5, ℝ). Then the exponential e^{tH} is a one-parameter subgroup of Lie group GL(5, ℝ). Since H^{4} = H^{2} we have

e^{tH} = E_{5} − H^{2} + (H − H^{3})t + H^{2} cosh t + H^{3} sinh t.

The linear vector field corresponding to the matrix H is

X = x^{1}(\frac{∂}{∂x^{2}} + \frac{∂}{∂x^{3}} ) + x^{2}(\frac{∂}{∂x^{1}} + \frac{∂}{∂x^{5}} ) + x^{3} \frac{∂}{∂x^{4}} .

Note that all vectors in X are parallel to ImH. The field X has a canonical parameter

s = \frac{x^{1} − x^{4}}{x^{2} − x^{3}}

and four invariants

I_{1} = x^{1}−x^{5}, I_{2} = x^{2}−x^{3}, I_{3} = \frac{1}{2} ln|(x^{1})^{2}−(x^{2})^{2}|, I_{4} = s−\frac{1}{2} ln|\frac{x^{1} + x^{2}}{x^{1} − x^{2}} |.

The exponential law U′ = HU ⇒ U_{t} = e^{tH}U defines a flow a_{t} : U ↦ U_{t} (see e^{tH}),

U_{t} = U − U′′ + (U′ − U′′′)t + U′′ cosh t + U′′′ sinh t,

generated by vector field X. In particular, the points, represented by basis vectors, move along trajectories

(e_{1})_{t} = −e_{4} − e_{5} + (e_{1} + e_{4} + e_{5}) cosh t + (e_{2} + e_{3}) sinh t,
(e_{2})_{t} = −e_{3} − e_{4}t + (e_{2} + e_{3}) cosh t + (e_{1} + e_{4} + e_{5}) sinh t,
(e_{3})_{t} = e_{3} + e_{4}t,
(e_{4})_{t} = e_{4},
(e_{5})_{t} = e_{5}.

It means that under the action of a_{t} the points U ∈KerH are fixed (see (e_{4})_{t} and (e_{5})_{t}), the points U ∈ KerH^{2}\KerH move along the straight lines (see (e_{3})_{t}) and the points U ∈ ℝ^{2}\KerH^{2} participate in a hyperbolic rotation in the plane ImH^{2} (see (e_{1})_{t} and (e_{2})_{t}). Note that the hyperbolic rotation in the plane ImH^{2} can be described using the basis vectors:

(e_{1} + e_{4} + e_{5})_{t} = (e_{1} + e_{4} + e_{5}) cosh t + (e_{2} + e_{3}) sinh t,
(e_{2} + e_{3})_{t} = (e_{2} + e_{3}) cosh t + (e_{1} + e_{4} + e_{5}) sinh t.

The coordinate transformation (x^{1}, x^{2}, x^{3}, x^{4}, x^{5}) ↦ (s, I_{1}, I_{2}, I_{3}, I_{4}) transforms the basis {e_{i}} into another invariant basis: a coframe (ds, dI_{1}, dI_{2}, dI_{3}, dI_{4}) and a frame

\frac{∂}{∂s} = X,
\frac{∂}{∂I_{1}} = −\frac{∂}{∂x^{5}} ,
\frac{∂}{∂I_{2}} = −\frac{∂}{∂x^{3}} − s\frac{∂}{∂x^{4}} ,
\frac{∂}{∂I_{3}} = x^{1}(\frac{∂}{∂x^{1}} + \frac{∂}{∂x^{5}} ) + x^{2}(\frac{∂}{∂x^{2}} + \frac{∂}{∂x^{3}} + \frac{∂}{∂x^{4}} ),
\frac{∂}{∂I_{4}} = −x^{1}(\frac{∂}{∂x^{2}} + \frac{∂}{∂x^{3}} ) − x^{2}(\frac{∂}{∂x^{1}} + \frac{∂}{∂x^{4}} + \frac{∂}{∂x^{5}} ).

This transformation follows from Jacobi matrix and its inverse:

(\begin{matrix}\frac{1}{I_{2}} & −\frac{s}{I_{2}} & \frac{s}{I_{2}} & −\frac{1}{I_{2}} & 0 \\ 1 & 0 & 0 & 0 & −1 \\ 0 & 1 & −1 & 0 & 0 \\ \frac{x^{1}}{(x^{1})^{2}−(x^{2})^{2}} & −\frac{x^{2}}{(x^{1})^{2}−(x^{2})^{2}} & 0 & 0 & 0 \\ \frac{1}{I_{2}} + \frac{x^{2}}{(x^{1})^{2}−(x^{2})^{2}} & −\frac{s}{I_{2}} − \frac{x^{1}}{(x^{1})^{2}−(x^{2})^{2}} & \frac{s}{I_{2}} & −\frac{1}{I_{2}} & 0 \end{matrix})^{−1} =

= (\begin{matrix}x^{2} & 0 & 0 & x^{1} & −x^{2} \\ x^{1} & 0 & 0 & x^{2} & −x^{1} \\ x^{1} & 0 & −1 & x^{2} & −x^{1} \\ x^{3} & 0 & −s & x^{2} & −x^{2} \\ x^{2} & −1 & 0 & x^{1} & −x^{2} \end{matrix}) .

The operators (\frac{∂}{∂s}, \frac{∂}{∂I_{1}} , \frac{∂}{∂I_{2}} , \frac{∂}{∂I_{3}} , \frac{∂}{∂I_{4}} ) commute with vector field X.

Hence, these operators are infinitesimal symmetries of X. From \frac{∂}{∂s} = X it follows that the flow generated by X becomes a group of translations s ↦ s+t. In the coordinates (s, I_{1}, I_{2}, I_{3}, I_{4}) the trajectories are the lines s and the classification of these trajectories makes no sense.

We have done the following seven steps:

a) took a map h from set A (consists of 5 elements) to itself;

b) represented the map h as 5 × 5-matrix H with the rank 3;

c) considered the matrix H as an element of Lie algebra gl(5, ℝ);

d) found the one-parameter subgroup e^{tH} of Lie group GL(5, ℝ);

e) in space ℝ^{5} the exponential e^{tH} defines a flow a_{t} generated by corresponding vector field X;

f) the classification of the trajectories depends on kernels KerH and KerH^{2}; g) in curvilinear coordinates such as the invariant coordinates (s, I_{1}, I_{2}, I_{3}, I_{4}) the flow simplifies, but the classification makes no sense.

The steps b)–g) can be applied to any square matrix with an arbitrary rank.

Acknowledgment

I want to thank my supervisor Prof. M. Rahula for his support.

References

[1] N. Bourbaki, Éléments de mathématique, Fasc. XVII, 1\underline{ère} partie, livre I, Théorie des ensembles, Paris, Hermann, 1960.

[2] M. Rahula, ,,About Theory of Maps”, Webs and Quasigroups, University of Kalinin, (1981), pp 136-153. (in Russian).

[3] M. Rahula, Vector Fields and Symmetries, Tartu University press, Tartu, 2004 (in Russian).

Institute of Pure Mathematics, Faculty of Mathematics and Computer Science, University of Tartu, J. Liivi Str., 2-218, 50409 Tartu, Estonia E-mail address: vitali@math.ut.ee

Received December 24, 2004