Linear Algebra/Definition of Homomorphism

From Wikibooks, open books for an open world
< Linear Algebra
Jump to: navigation, search
Definition 1.1

A function between vector spaces that preserves the operations of addition

if then

and scalar multiplication

if and then

is a homomorphism or linear map.

Example 1.2

The projection map

is a homomorphism.

It preserves addition

and scalar multiplication.

This map is not an isomorphism since it is not one-to-one. For instance, both and in are mapped to the zero vector in .

Example 1.3

Of course, the domain and codomain might be other than spaces of column vectors. Both of these are homomorphisms; the verifications are straightforward.

  1. given by
  2. given by
Example 1.4

Between any two spaces there is a zero homomorphism, mapping every vector in the domain to the zero vector in the codomain.

Example 1.5

These two suggest why we use the term "linear map".

  1. The map given by
    is linear (i.e., is a homomorphism). In contrast, the map given by
    is not; for instance,
    (to show that a map is not linear we need only produce one example of a linear combination that is not preserved).
  2. The first of these two maps is linear while the second is not.
    Finding an example that the second fails to preserve structure is easy.

What distinguishes the homomorphisms is that the coordinate functions are linear combinations of the arguments. See also Problem 7.

Obviously, any isomorphism is a homomorphism— an isomorphism is a homomorphism that is also a correspondence. So, one way to think of the "homomorphism" idea is that it is a generalization of "isomorphism", motivated by the observation that many of the properties of isomorphisms have only to do with the map's structure preservation property and not to do with it being a correspondence. As examples, these two results from the prior section do not use one-to-one-ness or onto-ness in their proof, and therefore apply to any homomorphism.

Lemma 1.6

A homomorphism sends a zero vector to a zero vector.

Lemma 1.7

Each of these is a necessary and sufficient condition for to be a homomorphism.

  1. for any and
  2. for any and

Part 1 is often used to check that a function is linear.

Example 1.8

The map given by

satisfies 1 of the prior result

and so it is a homomorphism.

However, some of the results that we have seen for isomorphisms fail to hold for homomorphisms in general. Consider the theorem that an isomorphism between spaces gives a correspondence between their bases. Homomorphisms do not give any such correspondence; Example 1.2 shows that there is no such correspondence, and another example is the zero map between any two nontrivial spaces. Instead, for homomorphisms a weaker but still very useful result holds.

Theorem 1.9

A homomorphism is determined by its action on a basis. That is, if is a basis of a vector space and are (perhaps not distinct) elements of a vector space then there exists a homomorphism from to sending to , ..., and to , and that homomorphism is unique.

Proof

We will define the map by associating with , etc., and then extending linearly to all of the domain. That is, where , the map is given by . This is well-defined because, with respect to the basis, the representation of each domain vector is unique.

This map is a homomorphism since it preserves linear combinations; where and , we have this.

And, this map is unique since if is another homomorphism such that for each then and agree on all of the vectors in the domain.

Thus, and are the same map.

Example 1.10

This result says that we can construct a homomorphism by fixing a basis for the domain and specifying where the map sends those basis vectors. For instance, if we specify a map that acts on the standard basis in this way

then the action of on any other member of the domain is also specified. For instance, the value of on this argument

is a direct consequence of the value of on the basis vectors.

Later in this chapter we shall develop a scheme, using matrices, that is convienent for computations like this one.

Just as the isomorphisms of a space with itself are useful and interesting, so too are the homomorphisms of a space with itself.

Definition 1.11

A linear map from a space into itself is a linear transformation.

Remark 1.12

In this book we use "linear transformation" only in the case where the codomain equals the domain, but it is widely used in other texts as a general synonym for "homomorphism".

Example 1.13

The map on that projects all vectors down to the -axis

is a linear transformation.

Example 1.14

The derivative map

is a linear transformation, as this result from calculus notes: .

Example 1.15
The matrix transpose map

is a linear transformation of . Note that this transformation is one-to-one and onto, and so in fact it is an automorphism.

We finish this subsection about maps by recalling that we can linearly combine maps. For instance, for these maps from to itself

the linear combination is also a map from to itself.

Lemma 1.16

For vector spaces and , the set of linear functions from to is itself a vector space, a subspace of the space of all functions from to . It is denoted .

Proof

This set is non-empty because it contains the zero homomorphism. So to show that it is a subspace we need only check that it is closed under linear combinations. Let be linear. Then their sum is linear

and any scalar multiple is also linear.

Hence is a subspace.

We started this section by isolating the structure preservation property of isomorphisms. That is, we defined homomorphisms as a generalization of isomorphisms. Some of the properties that we studied for isomorphisms carried over unchanged, while others were adapted to this more general setting.

It would be a mistake, though, to view this new notion of homomorphism as derived from, or somehow secondary to, that of isomorphism. In the rest of this chapter we shall work mostly with homomorphisms, partly because any statement made about homomorphisms is automatically true about isomorphisms, but more because, while the isomorphism concept is perhaps more natural, experience shows that the homomorphism concept is actually more fruitful and more central to further progress.

Exercises[edit]

This exercise is recommended for all readers.
Problem 1

Decide if each is linear.

Answer
  1. Yes. The verification is straightforward.
  2. Yes. The verification is easy.
  3. No. An example of an addition that is not respected is this.
  4. Yes. The verification is straightforward.
This exercise is recommended for all readers.
Problem 2

Decide if each map is linear.

Answer

For each, we must either check that linear combinations are preserved, or give an example of a linear combination that is not.

  1. Yes. The check that it preserves combinations is routine.
  2. No. For instance, not preserved is multiplication by the scalar .
  3. Yes. This is the check that it preserves combinations of two members of the domain.
  4. No. An example of a combination that is not preserved is this.
This exercise is recommended for all readers.
Problem 3

Show that these two maps are homomorphisms.

  1. given by maps to
  2. given by maps to

Are these maps inverse to each other?

Answer

The check that each is a homomorphisms is routine. Here is the check for the differentiation map.

(An alternate proof is to simply note that this is a property of differentiation that is familar from calculus.)

These two maps are not inverses as this composition does not act as the identity map on this element of the domain.

Problem 4

Is (perpendicular) projection from to the -plane a homomorphism? Projection to the -plane? To the -axis? The -axis? The -axis? Projection to the origin?

Answer

Each of these projections is a homomorphism. Projection to the -plane and to the -plane are these maps.

Projection to the -axis, to the -axis, and to the -axis are these maps.

And projection to the origin is this map.

Verification that each is a homomorphism is straightforward. (The last one, of course, is the zero transformation on .)

Problem 5

Show that, while the maps from Example 1.3 preserve linear operations, they are not isomorphisms.

Answer

The first is not onto; for instance, there is no polynomial that is sent the constant polynomial . The second is not one-to-one; both of these members of the domain

are mapped to the same member of the codomain, .

Problem 6

Is an identity map a linear transformation?

Answer

Yes; in any space .

This exercise is recommended for all readers.
Problem 7

Stating that a function is "linear" is different than stating that its graph is a line.

  1. The function given by has a graph that is a line. Show that it is not a linear function.
  2. The function given by
    does not have a graph that is a line. Show that it is a linear function.
Answer
  1. This map does not preserve structure since , while .
  2. The check is routine.
This exercise is recommended for all readers.
Problem 8

Part of the definition of a linear function is that it respects addition. Does a linear function respect subtraction?

Answer

Yes. Where is linear, .

Problem 9

Assume that is a linear transformation of and that is a basis of . Prove each statement.

  1. If for each basis vector then is the zero map.
  2. If for each basis vector then is the identity map.
  3. If there is a scalar such that for each basis vector then for all vectors in .
Answer
  1. Let be represented with respect to the basis as . Then .
  2. This argument is similar to the prior one. Let be represented with respect to the basis as . Then .
  3. As above, only .
This exercise is recommended for all readers.
Problem 10

Consider the vector space where vector addition and scalar multiplication are not the ones inherited from but rather are these: is the product of and , and is the -th power of . (This was shown to be a vector space in an earlier exercise.) Verify that the natural logarithm map is a homomorphism between these two spaces. Is it an isomorphism?

Answer

That it is a homomorphism follows from the familiar rules that the logarithm of a product is the sum of the logarithms and that the logarithm of a power is the multiple of the logarithm . This map is an isomorphism because it has an inverse, namely, the exponential map, so it is a correspondence, and therefore it is an isomorphism.

This exercise is recommended for all readers.
Problem 11

Consider this transformation of .

Find the image under this map of this ellipse.

Answer

Where and , the image set is

the unit circle in the -plane.

This exercise is recommended for all readers.
Problem 12

Imagine a rope wound around the earth's equator so that it fits snugly (suppose that the earth is a sphere). How much extra rope must be added to raise the circle to a constant six feet off the ground?

Answer

The circumference function is linear. Thus we have . Observe that it takes the same amount of extra rope to raise the circle from tightly wound around a basketball to six feet above that basketball as it does to raise it from tightly wound around the earth to six feet above the earth.

This exercise is recommended for all readers.
Problem 13

Verify that this map

is linear. Generalize.

Answer

Verifying that it is linear is routine.

The natural guess at a generalization is that for any fixed the map is linear. This statement is true. It follows from properties of the dot product we have seen earlier: and . (The natural guess at a generalization of this generalization, that the map from to whose action consists of taking the dot product of its argument with a fixed vector is linear, is also true.)

Problem 14

Show that every homomorphism from to acts via multiplication by a scalar. Conclude that every nontrivial linear transformation of is an isomorphism. Is that true for transformations of ? ?

Answer

Let be linear. A linear map is determined by its action on a basis, so fix the basis for . For any we have that and so acts on any argument by multiplying it by the constant . If is not zero then the map is a correspondence— its inverse is division by — so any nontrivial transformation of is an isomorphism.

This projection map is an example that shows that not every transformation of acts via multiplication by a constant when , including when .

Problem 15
  1. Show that for any scalars this map is a homomorphism.
  2. Show that for each , the -th derivative operator is a linear transformation of . Conclude that for any scalars this map is a linear transformation of that space.
Answer
  1. Where and are scalars, we have this.
  2. Each power of the derivative operator is linear because of these rules familiar from calculus.
    Thus the given map is a linear transformation of because any linear combination of linear maps is also a linear map.
Problem 16

Lemma 1.16 shows that a sum of linear functions is linear and that a scalar multiple of a linear function is linear. Show also that a composition of linear functions is linear.

Answer

(This argument has already appeared, as part of the proof that isomorphism is an equivalence.) Let and be linear. For any and scalars combinations are preserved.

This exercise is recommended for all readers.
Problem 17

Where is linear, suppose that , ..., for some vectors , ..., from .

  1. If the set of 's is independent, must the set of 's also be independent?
  2. If the set of 's is independent, must the set of 's also be independent?
  3. If the set of 's spans , must the set of 's span ?
  4. If the set of 's spans , must the set of 's span ?
Answer
  1. Yes. The set of 's cannot be linearly independent if the set of 's is linearly dependent because any nontrivial relationship in the domain would give a nontrivial relationship in the range .
  2. Not necessarily. For instance, the transformation of given by
    sends this linearly independent set in the domain to a linearly dependent image.
  3. Not necessarily. An example is the projection map
    and this set that does not span the domain but maps to a set that does span the codomain.
  4. Not necessarily. For instance, the injection map sends the standard basis for the domain to a set that does not span the codomain. (Remark. However, the set of 's does span the range. A proof is easy.)
Problem 18

Generalize Example 1.15 by proving that the matrix transpose map is linear. What is the domain and codomain?

Answer

Recall that the entry in row and column of the transpose of is the entry from row and column of . Now, the check is routine.

The domain is while the codomain is .

Problem 19
  1. Where , the line segment connecting them is defined to be the set . Show that the image, under a homomorphism , of the segment between and is the segment between and .
  2. A subset of is convex if, for any two points in that set, the line segment joining them lies entirely in that set. (The inside of a sphere is convex while the skin of a sphere is not.) Prove that linear maps from to preserve the property of set convexity.
Answer
  1. For any homomorphism we have
    which is the line segment from to .
  2. We must show that if a subset of the domain is convex then its image, as a subset of the range, is also convex. Suppose that is convex and consider its image . To show is convex we must show that for any two of its members, and , the line segment connecting them
    is a subset of . Fix any member of that line segment. Because the endpoints of are in the image of , there are members of that map to them, say and . Now, where is the scalar that is fixed in the first sentence of this paragraph, observe that Thus, any member of is a member of , and so is convex.
This exercise is recommended for all readers.
Problem 20

Let be a homomorphism.

  1. Show that the image under of a line in is a (possibly degenerate) line in .
  2. What happens to a -dimensional linear surface?
Answer
  1. For , the line through with direction is the set . The image under of that line is the line through with direction . If is the zero vector then this line is degenerate.
  2. A -dimensional linear surface in maps to a (possibly degenerate) -dimensional linear surface in . The proof is just like that the one for the line.
Problem 21

Prove that the restriction of a homomorphism to a subspace of its domain is another homomorphism.

Answer

Suppose that is a homomorphism and suppose that is a subspace of . Consider the map defined by . (The only difference between and is the difference in domain.) Then this new map is linear: .

Problem 22

Assume that is linear.

  1. Show that the rangespace of this map is a subspace of the codomain .
  2. Show that the nullspace of this map is a subspace of the domain .
  3. Show that if is a subspace of the domain then its image is a subspace of the codomain . This generalizes the first item.
  4. Generalize the second item.
Answer

This will appear as a lemma in the next subsection.

  1. The range is nonempty because is nonempty. To finish we need to show that it is closed under combinations. A combination of range vectors has the form, where ,
    which is itself in the range as is a member of domain . Therefore the range is a subspace.
  2. The nullspace is nonempty since it contains , as maps to . It is closed under linear combinations because, where are elements of the inverse image set , for
    and so is also in the inverse image of .
  3. This image of nonempty because is nonempty. For closure under combinations, where ,
    which is itself in as is in . Thus this set is a subspace.
  4. The natural generalization is that the inverse image of a subspace of is a subspace. Suppose that is a subspace of . Note that so the set is not empty. To show that this set is closed under combinations, let be elements of such that , ..., and note that
    so a linear combination of elements of is also in .
Problem 23

Consider the set of isomorphisms from a vector space to itself. Is this a subspace of the space of homomorphisms from the space to itself?

Answer

No; the set of isomorphisms does not contain the zero map (unless the space is trivial).

Problem 24

Does Theorem 1.9 need that is a basis? That is, can we still get a well-defined and unique homomorphism if we drop either the condition that the set of 's be linearly independent, or the condition that it span the domain?

Answer

If doesn't span the space then the map needn't be unique. For instance, if we try to define a map from to itself by specifying only that is sent to itself, then there is more than one homomorphism possible; both the identity map and the projection map onto the first component fit this condition.

If we drop the condition that is linearly independent then we risk an inconsistent specification (i.e, there could be no such map). An example is if we consider , and try to define a map from to itself that sends to itself, and sends both and to . No homomorphism can satisfy these three conditions.

Problem 25

Let be a vector space and assume that the maps are linear.

  1. Define a map whose component functions are the given linear ones.
    Show that is linear.
  2. Does the converse hold— is any linear map from to made up of two linear component maps to ?
  3. Generalize.
Answer
  1. Briefly, the check of linearity is this.
  2. Yes. Let and be the projections
    onto the two axes. Now, where and we have the desired component functions.
    They are linear because they are the composition of linear functions, and the fact that the compoistion of linear functions is linear was shown as part of the proof that isomorphism is an equivalence relation (alternatively, the check that they are linear is straightforward).
  3. In general, a map from a vector space to an is linear if and only if each of the component functions is linear. The verification is as in the prior item.