Serlo: EN: Endomorphism and Automorphism

{{#invoke:Mathe für Nicht-Freaks/Seite|oben}} An endomorphism is a linear deformation of a vector space $V$. Formally, an endomorphism is a linear mapping $f$ that sends $V$ to itself, i.e., $f:V\to V$. A bijective endomorphism is called an automorphism. Intuitively, an automorphism is a linear deformation that can be undone.

Derivation

We already know linear maps. These are mappings between two vector spaces which are compatible with the (linear) vector space structure. We now examine a few examples of linear maps that we have already learned about in previous articles.

Examples in the ${ℝ}^2$

Stretching in $x$-direction

First, we consider the stretching of a vector in the plane by a factor of $2$ in the $x$-direction. Our mapping is thus Vorlage:Einrücken One can easily verify that $f$ is a linear map. We can illustrate $f$ as follows: We place a checkerboard pattern in the plane and apply $f$ to this checkerboard pattern.

Stretching of the $x$-axis by a factor of $2$.

The result is that the boxes are stretched by a factor of $2$ in the $x$-direction.

Rotation around the origin

We now consider a rotation $D_{\alpha }$ by the angle $\alpha$ counter-clockwise, with the origin as center of rotation. This is a mapping $D_{\alpha }:{ℝ}^2\to {ℝ}^2$ which assigns to each vector $v\in {ℝ}^2$ the vector $D_{\alpha }(v)\in {ℝ}^2$ rotated by the angle $\alpha$:

Datei:Mfnf-linear-rotation.webm In the introductory article on linear maps we have seen that rotations about the origin are linear. We can visualize $D_{\alpha }$ as in the first example by applying the mapping to the checkerboard pattern. The individual squares then sustain their shape, but they are rotated.

Projection on a line

Application of $P$ to two vectors

At last we consider the map Vorlage:Einrücken The map $P$ "presses" vectors onto the straight line $G=\{a\cdot (1,1{)}^T|a\in ℝ\}$. You can easily check that $P$ is a linear map. We also apply this linear map to the checkerboard pattern to visualize it.

Projection on the diagonal in the plane

The entire grid is "flattened" onto the straight line $G$.

Linear deformations of an arbitrary vector space

In all the above examples, we were able to visualize the linear maps as distortions of the checkerboard pattern in ${ℝ}^2$. This was possible because all of the above functions map from ${ℝ}^2$ into itself. We can illustrate any linear maps ${ℝ}^2\to {ℝ}^2$ as a deformation of a checkerboard. The deformation of the checkerboard shows us how the map acts on the standard basis vectors $(1,0{)}^T$ and $(0,1{)}^T$ of ${ℝ}^2$ and integer multiples of them.

Any linear map ${ℝ}^2\to {ℝ}^2$ is a linear deformation of the space ${ℝ}^2$. Let us generalize this idea to general vector spaces $V$. We can think of linear maps from $V$ to $V$ as linear deformations or transformations of the vector space $V$. In contrast, a linear map $V$ is a transport of the vector space $V$ to $W$. We give a separate name to a linear map which deforms the vector space, i.e., which maps from $V$ to $V$: Such a linear map will be called an endomorphism. So endomorphisms are just those linear maps for which the domain of definition and the target space coincide.

Reversible deformations

In the examples in ${ℝ}^2$ we have seen that some deformations preserve the space and others "flatten" it in a certain sense. The mappings that preserve space can be undone. When the space is flattened, the ma cannot be undone because information is lost. For example, in the above linear map "projection onto a straight line", information is lost about what the $y$-component of the original vector was. It is not possible to recover the vector after applying the transformation. So there are deformations of space that can be undone, and some that cannot. One can undo a deformation exactly if the associated mapping is bijective, i.e., invertible. This gives us the definition of a reversible deformation of space, i.e., an invertible endomorphism. Such a mapping is called an automorphism.

Examples Vorlage:Anker

Examples in ${ℝ}^2$

Reflection

We consider the linear map $f:{ℝ}^2\to {ℝ}^2,(x,y{)}^T\mapsto (-x,y{)}^T$. Since it maps the vector space ${ℝ}^2$ into itself, $f$ is an endomorphism. The mapping $f$ preserves $y$ and sends $x$ to $-x$. Thus, we can think of $f$ as a reflection along the $y$-axis. We can undo a reflection by reflecting a second time. This means $f$ is its own inverse mapping. Formally, this is denoted $f\circ f={\mathrm{id}}_{{ℝ}^2}$ or $f^{-1}=f$. Such a mapping is also called "self-inverse." Because $f$ has an inverse, that is, it is invertible, it follows that $f$ is bijective. Thus, $f$ is also an automorphism.

Rotation by 90°

Next we consider the endomorphism $f:{ℝ}^2\to {ℝ}^2,(x,y{)}^T\mapsto (-y,x{)}^T$. This is a counter-clockwise rotation by $90$ degrees. To convince yourself that $f$ really is such a rotation, you may calculate how $f$ acts on the standard basis vectors $(1,0{)}^T$ and $(0,1{)}^T$. If it is such a rotation on these two vectors, then by linearity, $f$ must be such a rotation everywhere. A short calculation gives $f((1,0{)}^T)=(0,1{)}^T$, as well as $f((0,1{)}^T)=(-1,0{)}^T$, which is exactly the desired rotation. Again, we can easily specify an inverse by "turning back" or rotating clockwise by $90$ degrees. This rotation is given by $g:{ℝ}^2\to {ℝ}^2,(x,y{)}^T\mapsto (y,-x{)}^T$. We briefly check that $g$ is indeed the inverse of $f$: Vorlage:Einrücken for $(x,y{)}^T\in {ℝ}^2$. So $f\circ g={\mathrm{id}}_{{ℝ}^2}=g\circ f$ and $f$ is also an automorphism in this example.

Shears

Let $f:{ℝ}^2\to {ℝ}^2,(x,y{)}^T\mapsto (x+2y,y{)}^T$. The following animation shows how this mapping deforms the plane.

Shear of the plane

The transformation looks reversible, that is, it looks like an automorphism. We can check this by showing that $f$ is both injective and surjective.

To show injectivity, let us look at the kernel of $f$, i.e., the set $\{(x,y{)}^T\in {ℝ}^2\mid f((x,y{)}^T)=(0,0{)}^T\}$. For a vector $(x,y{)}^T$ in the kernel, then $(x+2y,y{)}^T=(0,0{)}^T$ holds. From this we directly get $y=0$ and therefore also $x=x+2y=0$. Thus, the kernel consists only of the zero vector and hence $f$ is injective.

To show surjectivity, we take any $(x^{\prime },y^{\prime }{)}^T\in {ℝ}^2$ and find a suitable preimage. That means, we are looking for some $(x,y{)}^T\in {ℝ}^2$ with $(x+2y,y{)}^T=f((x,y{)}^T)=(x^{\prime },y^{\prime }{)}^T$. It is directly clear that $y=y^{\prime }$ must hold. Furthermore, $x+2y=x+2y^{\prime }=x^{\prime }$ must be true. This can be transformed to $x=(x^{\prime }-2y^{\prime }{)}^T$. So $(x^{\prime }-2y^{\prime },y^{\prime }{)}^T$ is a preimage of $(x^{\prime },y^{\prime }{)}^T$. Since $(x^{\prime },y^{\prime }{)}^T$ was arbitrary, $f$ is surjective.

Linear maps of the form $f((x,y{)}^T)=(x+\lambda y,y{)}^T$ with $\lambda \in K$ are called shears. You can show as an exercise that a shear is always an automorphism, no matter what $\lambda$ is.

Flattening to the $x$-axis

Let us now consider the mapping $f:{ℝ}^2\to {ℝ}^2,(x,y{)}^T\mapsto (x+y,0{)}^T$. This is an endomorphism from ${ℝ}^2$ to ${ℝ}^2$ that maps every point on the plane to a point on the $x$-axis. So we can think of $f$ as "flattening" the 2-dimensional plane onto the 1-dimensional $x$-axis."

Since $f$ maps the points in ${ℝ}^2$ exclusively onto the $x$ axis, $f$ is not a surjective mapping. Nor is it injective, because for every $z\in ℝ$ we can find different $x,y\in ℝ$ such that $x+y=z$ holds, e.g., $x=z,y=0$ and vice versa. So $f$ is not an automorphism.

Flattening to the x-axis

Example in ${ℝ}^3$

Let us now consider an example in ${ℝ}^3$. For this we look at the linear map $f:{ℝ}^3\to {ℝ}^3,(x,y,z{)}^T\mapsto (x+y,x+y,z{)}^T$. Because $f$ maps the vector space ${ℝ}^3$ back to ${ℝ}^3$, the mapping is an endomorphism.

We now want to check whether $f$ is also an automorphism. To do this, we need to check surjectivity and injectivity. For injectivity, we consider the kernel of $f$, that is, the set $\{(x,y,z{)}^T\in {ℝ}^3|f((x,y,z{)}^T)=(0,0,0{)}^T\}$. Thus, for vectors $(x,y,z{)}^T$ from the kernel of $f$, $(x+y,x+y,z{)}^T=(0,0,0{)}^T$ holds. From this we can directly conclude that $z=0$ and $x+y=0$, so $y=-x$, must hold. We thus see that the kernel of $f$ contains not only the zero vector, but also the set of all vectors $\{(x,-x,0{)}^T|x\in ℝ\}$. Hence, $f$ is not injective and therefore cannot be bijective. In particular, $f$ is not an automorphism.

Visually, $f$ compresses vectors onto the plane $\{(x,x,z{)}^T\mid x,z\in ℝ\}$. Thus, information is lost. Given a vector $(x,x,z{)}^T\in {ℝ}^3$, it is no longer possible to say in an unambiguous way from which vector $(a,b,z{)}^T\in {ℝ}^3$ it arose under the mapping $f$, since there are very many ways to represent $x\in ℝ$ as the sum of two numbers $a,b\in ℝ$. For example, $5=2+3=1+4=-1000+1005$.

Example in sequence space

There are also endomorphisms on vector spaces other than ${ℝ}^2$ and ${ℝ}^3$. For instance, we may take an arbitrary field $K$ and consider, as a vector space over it, the sequence space Vorlage:Einrücken Now, we take the mapping Vorlage:Einrücken where Vorlage:Einrücken If we write out the first sequence members, the situation looks like this: Vorlage:Einrücken Thus, the mapping $f$ interchanges even and odd sequence members. We briefly justify why $f$ is linear. Addition and scalar multiplication in the sequence space is understood component-wise, i.e., for $(x_i{)}_i$ and $(y_i{)}_i\in \omega$ and $\lambda \in K$ we have Vorlage:Einrücken Since $f$ only swaps the order of the components, $f$ is linear. We can also check linearity of $f$ explicitly. Mathe für Nicht-Freaks: Vorlage:Frage So $f$ is an endomorphism of $\omega$. Is $f$ also an automorphism? To answer that, we need to verify that $f$ can be undone. The mapping swaps even and odd sequence members. So if we swap the sequence members back, $f$ is undone. This second swap can be done by just applying $f$ again. As with the very first example, $f$ is self-inverse - in formulas this is called $f\circ f={\mathrm{id}}_{\omega }$ or $f=f^{-1}$. Since $f$ is invertible, the mapping is bijective. So $f$ is an automorphism.

Endomorphisms form a ring with unit Vorlage:Anker

In the article Vector space of a linear map we saw that the set of linear maps ${\mathrm{Hom}}_K(V,W)$ between two $K$-vector spaces $V$ and $W$ again forms a vector space. Since ${\mathrm{End}}_K(V)={\mathrm{Hom}}_K(V,V)$ holds, the set of endomorphisms is also a vector space. That is, we can add endomorphisms of a vector space $V$ and multiply them by scalars. In particular, we can link two endomorphisms $f$ and $g\in {\mathrm{End}}_K(V)$ by addition and obtain an endomorphism $f+g\in {\mathrm{End}}_K(V)$. This space is given by Vorlage:Einrücken where ${+}_V$ denotes addition in the vector space $V$.

Can $f$ and $g$ be connected in another way? Intuitively, $f$ and $g$ are two representations of the vector space $V$. We can now deform the space $V$ with $f$ and then deform the result with $g$. This produces a new deformation of the vector space. That is, we again get an endomorphism of $V$. This resulting mapping, that corresponds to applying $f$ and $g$ one after the other, is called composition and denoted $g\circ f$. Thus, the composition of two endomorphisms is always an endomorphism. In summary, we can "connect" two endomorphisms $f$ and $g$ by forming the addition $f+g$ or the composition $g\circ f$.

Because we have composition as an operation in addition to addition, ${\mathrm{End}}_K(V)$ carries more structure than just vector space structure. We will prove later that the set ${\mathrm{End}}_K(V)$ of endomorphisms on $V$ forms a ring with these two operations. Here, the addition in the ring is the addition of the mappings and the multiplication in the ring is the composition of the mappings.

It is now an interesting question, when the ring ${\mathrm{End}}_K(V)$ has a unit element and is commutative. If this was the case, we would even have a field and could build more vector spaces over it. Now, a unit element exists if there is a neutral element of multiplication. That is, if there is a $k\in {\mathrm{End}}_K(V)$ such that $k\circ f=f$ and $f\circ k=f$ holds for all $f\in {\mathrm{End}}_K(V)$. We already know a mapping that satisfies this property: the identity ${\mathrm{id}}_V$. This is a linear map $V\to V$ and so ${\mathrm{id}}_V\in {\mathrm{End}}_K(V)$ holds. So the ring ${\mathrm{End}}_K(V)$ has a unit element.

Is ${\mathrm{End}}_K(V)$ a commutative ring? To answer this, we need to check that $f\circ g=g\circ f$ holds for all $f,g\in {\mathrm{End}}_K(V)$. To get an intuition whether the statement is true or false, we consider again examples with ${ℝ}^2$. Let $f:{ℝ}^2\to {ℝ}^2$ be the projection onto the $y$-axis; that is, for $(x,y)\in {ℝ}^2$, $f(x,y)=(0,y)$ holds. Furthermore, let $g:{ℝ}^2\to {ℝ}^2$ be the rotation by $90^{\circ }$ clockwise (or by $270^{\circ }$ counter-clockwise) about the origin; that is, $g(x,y)=(-y,x)$ holds. We want to investigate whether $f\circ g=g\circ f$. What do the maps $f\circ g$ and $g\circ f$ do visually? The map $g\circ f$ first pushes all space onto the $y$-axis and then rotates it by $90^{\circ }$ in a clockwise direction. So our result is on the $x$-axis.

$g\circ f$

The mapping $f\circ g$ first rotates the space by $90^{\circ }$ clockwise and then pushes everything to the $y$-axis. So the result of the mapping lies on the $y$-axis.

$f\circ g$

Consequently, $f\circ g$ and $g\circ f$ are different mappings. Therefore, ${\mathrm{End}}_{ℝ}({ℝ}^2)$ is not a commutative ring. More generally, for any vector space $V$ with $\dim V\ge 2$, ${\mathrm{End}}_K(V)$ is not a commutative ring. We deal with this below in a corresponding exercise.

As announced above, we now prove that $({\mathrm{End}}_K(V),+,\circ )$ is always a ring:

Automorphisms and flattening

The finite-dimensional case

Above we have already examined some examples of endomorphisms and automorphisms. We have seen that endomorphisms which "flatten" a vector space are not bijective and therefore not automorphisms. On the other hand, endomorphisms which do not "flatten" a vector space are indeed automorphisms.

Mathe für Nicht-Freaks: Vorlage:Frage For endomorphisms of finite-dimensional vector spaces, being "non-flattening" is equivalent to being an automorphism: Let $f:V\to V$ be an endomorphism of an $n$-dimensional vector space $V$. If the mapping $f$ is an automorphism, then it is injective. So $f$ does not flatten $V$. Conversely, if we assume that $f$ does not flatten $V$, it follows that $f$ is injective. Thus, no information from $V$ is lost when mapping with $f$. From this, we can conclude that the image $\mathrm{im}(f)=f(V)$ is also $n$-dimensional. So $\mathrm{im}(f)=V$ must hold. Thus, $f$ is also surjective and therefore an automorphism.

We have seen that an injective endomorphism over a finite-dimensional vector space is automatically surjective. Does the converse statement also hold? In other words: If $f:V\to V$ is a surjective endomorphism of a $n$-dimensional vector space, does it follow that $f$ is injective? If $f$ is surjective, then $f(V)=V$ and hence $\dim (f(V))=n$ holds. Suppose $f$ is not injective. Then there is a vector $0\ne v\in V$ for which $f(v)=0$. Thus, $f$ "flattens the direction" in which $v$ points. This means, when mapping $V$ by $f$, we lose at least one dimension of $V$. Consequently, we would have $\dim (f(V))<n$. This is a contradiction to $\dim (f(V))=n$. Therefore, $f$ must be injective. So if $f$ is surjective, then $f$ is also injective.

We show these statements again formally in the following theorem. Mathe für Nicht-Freaks: Vorlage:Satz

The infinite-dimensional case

In the infinite-dimensional case, the above argument no longer works. We have exploited in the finite-dimensional case that for an $n$-dimensional vector space $V$ and a subspace $U\subseteq V$ it already follows from $\dim (U)=n$ that $V=U$. Above, we used $U=f(V)$. However, in infinite-dimensional vector spaces this does not hold. Here, a paradoxical effect occurs: One can place an infinite-dimensional subspace $U$ into another infinite-dimensional space $V$ of the same size, without filling all of $V$ (This is related to Hilbert's Hotel paradox).

So for endomorphisms $f:V\to V$ of an infinite-dimensional vector space $V$, it does not hold that $f$ is surjective exactly when $f$ is injective. To understand this better, we now examine concrete counterexamples.

Mathe für Nicht-Freaks: Vorlage:Beispiel Mathe für Nicht-Freaks: Vorlage:Hinweis Mathe für Nicht-Freaks: Vorlage:Beispiel

The automorphism group

We know that the endomorphisms form a ring with unit. The automorphisms are exactly all invertible endomorphisms. In other words, the automorphisms of a vector space are exactly the multiplicatively invertible elements, of the endomorphism ring. Recall that the multiplication in the endomorphism ring is just the composition $\circ$ of mappings. In the following theorem we show that ${\mathrm{Aut}}_K(V)$ is indeed a group with respect to this multiplication.

Mathe für Nicht-Freaks: Vorlage:Satz The automorphisms form a group, but are no longer a ring. This is because ${\mathrm{Aut}}_K(V)$ no longer has an additive structure: If we have two automorphisms $f$ and $g$ from a vector space $V$, $f+g$ need not be an automorphism again. And indeed, there are counterexamples for this: Mathe für Nicht-Freaks: Vorlage:Beispiel Mathe für Nicht-Freaks: Vorlage:Hinweis For vector spaces $V$ with $\dim V\ge 2$ the automorphism group is not commutative. As with the endomorphism ring, the composition of the mappings is not commutative. We demonstrate this non--commutativity in an exercise below.

Exercises

{{#invoke:Mathe für Nicht-Freaks/Seite|unten}}