LINEAR
ALGEBRA

LICENSE, DISCLAIMER OF LIABILITY, AND LIMITED WARRANTY

By purchasing or using this book (the “Work”), you agree that this license grants permission to use the contents contained herein, but does not give you the right of ownership to any of the textual content in the book or ownership to any of the information or products contained in it. This license does not permit uploading of the Work onto the Internet or on a network (of any kind) without the written consent of the Publisher. Duplication or dissemination of any text, code, simulations, images, etc. contained herein is limited to and subject to licensing terms for the respective products, and permission must be obtained from the Publisher or the owner of the content, etc., in order to reproduce or network any portion of the textual material (in any media) that is contained in the Work.

MERCURY LEARNING AND INFORMATION (“MLI” or “the Publisher”) and anyone involved in the creation, writing, or production of the companion disc, accompanying algorithms, code, or computer programs (“the software”), and any accompanying Web site or software of the Work, cannot and do not warrant the performance or results that might be obtained by using the contents of the Work. The author, developers, and the Publisher have used their best efforts to insure the accuracy and functionality of the textual material and/or programs contained in this package; we, however, make no warranty of any kind, express or implied, regarding the performance of these contents or programs. The Work is sold “as is” without warranty (except for defective materials used in manufacturing the book or due to faulty workmanship).

The author, developers, and the publisher of any accompanying content, and anyone involved in the composition, production, and manufacturing of this work will not be liable for damages of any kind arising out of the use of (or the inability to use) the algorithms, source code, computer programs, or textual material contained in this publication. This includes, but is not limited to, loss of revenue or profit, or other incidental, physical, or consequential damages arising out of the use of this Work.

The sole remedy in the event of a claim of any kind is expressly limited to replacement of the book, and only at the discretion of the Publisher. The use of “implied warranty” and certain “exclusions” vary from state to state, and might not apply to the purchaser of this product.

LINEAR
ALGEBRA

Li-Yong Shen, PhD

(University of the Chinese Academy of Sciences)

Haohao Wang, PhD

(Southeast Missouri State University)

Jerzy Wojdylo, PhD

(Southeast Missouri State University)

Dulles, Virginia
Boston, Massachusetts
New Delhi

Copyright ©2019 by MERCURY LEARNING AND INFORMATION LLC. All rights reserved.

Original Title and Copyright: Linear Algebra. Copyright ©2018 by.

Overseas Press India Private Limited. All rights reserved.

This publication, portions of it, or any accompanying software may not be reproduced in any way, stored in a retrieval system of any type, or transmitted by any means, media, electronic display or mechanical display, including, but not limited to, photocopy, recording, Internet postings, or scanning, without prior permission in writing from the publisher.

Publisher: David Pallai

MERCURY LEARNING AND INFORMATION

22841 Quicksilver Drive

Dulles, VA 20166

info@merclearning.com

www.merclearning.com

(800) 232-0223

Li-Yong Shen, H. Wang, J. Wojdylo. Linear Algebra.

ISBN: 978-1-683923-76-3

The publisher recognizes and respects all marks used by companies, manufacturers, and developers as a means to distinguish their products. All brand names and product names mentioned in this book are trademarks or service marks of their respective companies. Any omission or misuse (of any kind) of service marks or trademarks, etc. is not an attempt to infringe on the property of others.

Library of Congress Control Number: 2018962730

181920321 This book is printed on acid-free paper in the USA.

Our titles are available for adoption, license, or bulk purchase by institutions, corporations, etc.

For additional information, please contact the Customer Service Dept. at 800-232-0223(toll free).

All of our titles are available in digital format at authorcloudware.com and other digital vendors. The sole obligation of MERCURY LEARNING AND INFORMATION to the purchaser is to replace the book, based on defective materials or faulty workmanship, but not based on the operation or functionality of the product.

CONTENTS

Prefaces

List of Figures

Chapter 1Vector Spaces

1.1Vector Spaces

1.2Linear Span and Linearly Independence

1.3Bases for Vector Spaces

1.4Linear System of Equations

1.5A First Look of Determinants

1.6Using Computer Algebra Systems to Perform Computations

1.7Applications of Vector Spaces

1.7.1Code

1.7.2Hamming Code

1.7.3Linear Code

1.7.4Golay Code

1.8Exercises

Chapter 2Linear Transformations

2.1Linear Transformations

2.2Rank and Nullity of a Linear Transformation

2.3Representation of Linear Transformations by Matrices

2.4The Algebra of Linear Transformation

2.5Applications of Linear Transformation

2.5.1Affine Transformations

2.5.2Projective Transformations

2.6Exercises

Chapter 3Linear Operators

3.1Characteristic and Minimal Polynomials

3.2Eigenspaces and Diagonalizability

3.3Jordan Canonical Form

3.4Trace

3.5Determinants

3.6Generalized Companion Matrix

3.7Solution of Linear System of Equations

3.8Some Applications of Matrices

3.8.1Linear Programming

3.8.2Geometric Transformation

3.8.3Matrices in Graph Theory

3.8.4Positional Relationship of Two Ellipsoids

3.9Exercises

Chapter 4Orthogonal Bases

4.1Inner Product Spaces

4.2Gram-Schmidt Process to Produce Orthonormal Basis

4.3Orthogonal Complements and Projections

4.4Orthogonal Projections and Reflections

4.4.1Orthogonal Projection Matrix

4.4.2Reflection Matrix

4.5Properties of Symmetric Matrices

4.6QR Factorization

4.7Singular Value Decomposition

4.8Applications of SVD and QR Decompositions

4.8.1Image Processing

4.8.2QR decomposition and GCD

4.9Exercises

Chapter 5Matrix Decomposition

5.1Decomposition over or

5.1.1Decompositions to Solve Linear Systems

5.1.2Decompositions Based on Eigenvalues

5.1.3Examples

5.2Iterative Methods to Solve Linear Systems Numerically

5.2.1Jacobi Iterative Method

5.2.2Gauss-Seidel Iterative Method

5.3Matrix over Principle Ideal Domain

5.3.1Matrix Decomposition over PID

5.4Exercises

Bibliography

Index

PREFACE

Linear algebra is one of the most widely used mathematical theories and has applications in virtually every area of mathematics, including multivariate calculus, differential equations, and probability theory. The purpose of this book is to bridge the gap between the abstract theoretical aspects and the computational applications of linear algebra. The aim of this book is two-fold: to introduce the fundamental concepts of linear algebra and to apply the theorems in computation-oriented applications. There are many good introductory texts on linear algebra, and the intention of this book is to be a supplement to those texts, or to serve as a text for senior undergraduate students or first year graduate students, whose interests are computational mathematics, science, engineering, and computer science. The presentation of the material combines definitions and proofs with an emphasis on computational applications. We provide examples that illustrate the use of software packages such as Mathematica, Maple, and Sage.

This book has evolved from our experience over several years of teaching linear algebra to mixed audiences of upper division mathematics majors, beginning graduate students, and students from the fields of science and engineering that rely heavily on mathematical methods. Our goal in writing this book has been to develop a text that addresses the exceptional diversity of the audience, and introduce some of the most essential topics about the subject of linear algebra to these groups. To accomplish our goal, we have selected material that covers both the theory and applications, while emphasizing topics useful in other disciplines.

Throughout the text, we present a brief introduction to some aspects of abstract algebra that relate directly to linear algebra, such as groups, rings, modules, fields and polynomials over fields. In particular, the last section of this book is dedicated to the matrix decomposition over principle ideal domains, because this structure theorem is a generalization of the fundamental theorem of finitely-generated abelian groups, and this result provides a simple framework to understand various canonical form results for square matrices over fields.

We use the material from the book to teach our own elective linear algebra course, and some of the solutions to the exercises are provided by our students. It is our hope that this book will help a general reader appreciate the abstract mathematics behind the real applications.

By design, each chapter consists of two parts: the theoretical background and the applications, which make the book suitable for a one semester course in linear algebra that can be used in a variety of contexts. For an audience composed primarily of mathematics undergraduate majors, the material on the theories of abstract vector spaces, linear transformations, linear operators, orthogonal bases, and decomposition over rings can be covered in depth. For an applied mathematics course with students from the fields of science and engineering that rely heavily on mathematical methods, the material on applications of these areas such as linear codes, affine or projective transformations, geometry of transformations, matrix in graph theory, image processing, and QR decomposition, can be treated with more emphasis. In the applications, we allow ourselves to present a number of results from a wide range of sources, and sometimes without detailed proofs. The applications portion of the chapter is suitable for a reader who knows some linear algebra and a particular related area such as coding theory, geometric modeling, or graph theory. Some of the applications can serve as a guide to some interesting research topics.

The prerequisite for this book is a standard first year undergraduate course in linear algebra. In Chapter 1 and Chapter 2 we start with a quick review of the fundamental concepts of vector spaces and linear transformations. To better understand the behavior of a linear transformation, we discuss the eigenvectors in Chapter 3, where the eigenvectors act as the “axes” along which linear transformations behave simply as stretching, compressing, or flipping, and hopefully make understanding of linear transformations easier. Because one can perform some operations on vectors by performing the same operations on the basis, we study orthogonal bases in Chapter 4. In particular, we study linear transformations relative to orthonormal bases that faithfully preserve the linear properties and the metric properties. Finally, in Chapter 5, we focus on the matrix decomposition over real or complex numbers and over principle ideal domains.

This book should be thought of as an introduction to more advanced texts and research topics. The novelty of this book, we hope, is that the material presented here is a unique combination of the essential theory of linear algebra and computational methods in a variety of applications.

LIST OF FIGURES

3.1: A simple graph

4.1: Image compression

4.2: Image compression (cont.)

C H A P T E R 1

VECTOR SPACES

1.1Vector Spaces

Linear algebra is an area of mathematics which deals with vector spaces and linear mappings between vector spaces. The fundamental subjects studied in linear algebra includes lines, planes, and subspaces. For example, the condition under which a set of n hyperplanes intersect in a single point can be investigated via finding the condition for a system of linear equations to have a unique non-trivial solution. This system of linear equation can be represented by vectors and matrices. In this section, we will focus on the vector spaces.

We will first recall the notation of a set. A set is a collection of distinct objects, the objects are called elements of the set. For instance, all integer numbers form a set = {..., −2, −1, 0, 1, 2, ...}.

A set X is called an empty set, denoted by ∅, if X has no elements. We denote x ∈ X if an element x is included in a set X, otherwise denote x ∈ X. For two sets X and Y, we call X a subset of Y (or Y a superset of X), denoted by X ⊆ Y (or Y ⊇ X), if all the elements of X are included in Y. Note that the empty set is a subset of any set. We say X is a strict (alternatively proper in some references) subset of Y (or Y is a strict superset of X), denoted by X ⊂ Y (or Y ⊃ X) if X ⊂ Y and there is an element y such that y ∈ Y and y ∉ X.

We give three basic operations for two sets:

1.Union of two sets X and Y is the set of elements which are in X, in Y, or in both X and Y, denoted by X ∪ Y = {a | a ∈ X or a ∈ Y};

2.Intersection of two sets X and Y is the set of elements which are in both X and Y, denoted by X ∩ Y = {a | a ∈ X and a ∈ Y};

3.Difference of two sets X and Y is the set of elements in X but not in Y, denoted by X\Y = {a | a ∈ X and a ∉ Y}.

Definition 1.1.1

A ring R consists of a set with two operations (+, *) : R × R → R with the properties:

1.Addition is commutative and associative.

2.There is a unique element 0 ∈ R, such that x + 0 = x for all x ∈ R.

3.To each x ∈ R, there corresponds a unique element −x ∈ R such that x + (−x) = 0.

4.Multiplication is associative.

5.Multiplication is distributive over addition on the left (and/or right).

If the multiplication is commutative, then R is called a commutative ring. If there is a unique non-zero element 1 ∈ R such that x * 1 = 1 * x = x for all x ∈ R, then the ring is called a ring with identity. If for each non-zero element x ∈ R, there corresponds a unique element y ∈ R such that x * y = y * x = 1, then we say R is a division ring.

For a ring R, if R satisfies the first three conditions, then (R, +) is a commutative or abelian additive group. When a ring R is with unity, then (R, *) is a commutative multiplicative group.

Basically, a field is an algebraic structure in which every linear equation in a single variable can be solved.

Definition 1.1.2

Let be a set with two operations (+, *) : × → with the following properties, then is a field.

1.Addition is commutative and associative.

2.There is a unique element 0 ∈ , such that x + 0 = x for all x ∈ .

3.To each x ∈ , there corresponds a unique element −x ∈ such that x + (−x) = 0.

4.Multiplication is commutative and associative.

5.There is a unique non-0 element 1 ∈ such that x * 1 = x for all x ∈ .

6.To each non-zero x ∈ , there corresponds a unique element x−1 ∈ such that x * x−1 = 1.

7.Multiplication is distributive over addition.

We recall that the set of rational numbers , the set of real numbers , and the set of complex numbers , are all fields with the usual addition and multiplication, and ⊂ ⊂ .

We know that the difference between rings and fields is that fields are commutative division rings. The main difference between rings and fields is that one can divide in fields, but in general one cannot always divide in rings. For instance, the set of integers is a commutative ring; if we include all the multiplicative inverses of non-zero integers, then we get a field, the field of rational numbers. A polynomial ring is a commutative ring formed from the set of polynomials in one or more indeterminates, or variables, with coefficients in another ring. For example [x] is a polynomial ring in one variable with coefficients in . If we include all the multiplicative inverses of non-zero polynomials, then we get a field, the field of rational functions, (x).

One can verify that the set of n × n matrices over is a ring, but not a commutative ring. This ring has identity, i.e., the n × n identity matrix, but this is not a ring with unity.

A vector space, or sometimes called a linear space, is a collection of objects called vectors that satisfies certain properties.

Definition 1.1.3

A vector space or linear space V over a field consists of a nonempty set V together with two operations + : V × V → V, and * : × V → V which satisfy the following:

1.A rule (or operation) +, called vector addition, which associates with each pair of vectors a, b ∈ V a vector a + b ∈ V, called the sum of a, b, in such a way that

(a)addition is commutative

(b)addition is associative

(c)there is a zero vector 0 which is additive identity

(d)for each vector a ∈ V, there is –a ∈ V, such that a + (−a) = 0.

2.A rule (or operation) ∗, called scalar multiplication, which associates with each c ∈ and a vector a ∈ V a vector ca ∈ V, called the product, such that for all a, b ∈ V and c_1, c_2 ∈

(a)1 * a = a

(b)(c_1c_2) * a = c_1 * c_2 * a)

(c)c*(a + b)= c * a + c * b

(d)(c_1 + c_2) * a = c_1 * a + c_2 * a.

Definition 1.1.4

A subset W of a vector space V is called a subspace of V if W itself is a vector space under the addition and scalar multiplication inherited from V.

EXAMPLE 1.1.1

Let [x] be the collection of all polynomials in one variable x, i.e., the polynomial ring with one variable with coefficients over the field . Then [x] with the usual polynomial addition and multiplication by constants is a vector space over . Polynomials of degree n are completely determined, by the coefficient of xk for k = 0, …, n. To check that is a vector space, one needs to know how addition and scalar multiplication by elements of [x] are defined.

A matrix is an important object in linear algebra. A matrix is a rectangular array of numbers or expressions, called entries of the matrix, arranged in rows and columns.

EXAMPLE 1.1.2

Let Mn×n() be the set of n × n matrices with entries in . Then Mn×n() is a vector space over with the usual addition and scalar multiplication. Moreover, if we let Dn() and Un() be the set of diagonal matrices and upper triangular matrices in Mn×n(), then Dn() and Un() are subspaces of Mn×n().

EXAMPLE 1.1.3

An n × n matrix A = (ajk) where aij denotes the entry of the i-th row and j-th column over the field of complex numbers is Hermitian or self-adjoint if

for each j, k; the bar denoting complex conjugation.

The set of all Hermitian matrices is not a subspace of the space of all n × n matrices over .

EXAMPLE 1.1.4

Let Mm×n([x]) be the set of m × n matrices with entries in [x]. Then Mm×n([x]) is a vector space over [x] with the usual addition and scalar multiplication. In fact, Mm×n([x]) is isomorphic to (Mm×n())[x]. For instance, 3 × 3 polynomial matrix of degree 2:

Definition 1.1.5

Suppose that R is a ring and 1 is its multiplicative identity. A left R-module M is a set together with two operations + : M × M → M with an abelian group (M, +), and an operation * : R × M → M such that for all r, s ∈ R and x, y ∈ M, we have:

The operation * of the ring on M is called scalar multiplication. The notation RM indicates a left R-module M. A right R-module M or MR is defined similarly, except that the ring acts on the right; i.e., scalar multiplication takes the form * : M × R → M, and the above axioms are written with scalars r and s on the right of x and y.

If a ring is non-commutative there is a difference between a left and right action. A given left action does not in general define a right action. Over a commutative ring there is no difference between a left and right module.

A module is abstractly similar to a vector space, but it uses a ring to define coefficients instead of the field used for vector spaces. In fact, a vector space is a module over a field, but in general, modules have coefficients in much more general algebraic objects. It is easy to see that Hermitian matrices is not a module over .

Following are a few theorems which can be verified by the definition directly.

Theorem 1.1.1

A non-empty set W ⊂ V is a subspace of a vector space V if and only if the following hold:

1.For all x, y ∈ W, x + y ∈ W;

2.For every x ∈ W, and scalar a, the vector αx ∈ W.

Definition 1.1.6

If U, W are subspaces of the vector space V, then we define the sum of U, W to be

Similarly, if Ui are subspaces of V, then the sum of Ui is

Remark: We note that the union of two vector subspaces is not a vector or subspace.

Theorem 1.1.2

Suppose U, W are subspaces of the vector space V. Then U ∩ W, and U + W are subspaces of V.

Definition 1.1.7

Let U_1,...,Uk be subspaces of a vector space V. We say V is a direct sum of U_1, ... ,Uk and write V = U_1 ⊕ U_2 ⊕ ... ⊕ Uk if

1.Every vector x ∈ V can be written as x = y_1 + y_2 + ...+ yk with yi ∈ Ui;

2.If yi, wi ∈ Ui, and y_1 + ... + yk = w_1 + ... + wk, then yi = wi for all i = 1,..., k.

There is a similar definition, namely, the direct product Πi∈I Vi of a family of vector spaces V consists of the set of all tuples xi ∈ Vi with i ∈ I where addition and scalar multiplication is performed component wise, and I is either a finite or infinite index set. For example, the direct product is the same as Cartesian product. If X and Y are two sets, then X × Y, the Cartesian product of X and Y is a set made up of all ordered pairs of elements of X and Y, i.e., if x ∈ X, y ∈ Y, then (x, y) ∈ X × Y.

EXAMPLE 1.1.5

Take V = 3. We can describe all subspaces: {0}, 3, all lines and planes through the origin.

Given any two distinct lines U_1 and U_2 through the origin, we can take the plane U_1 + U_2 that they span.

Given a plane U through the origin, and a line W through the origin not in that plane, then U + W = 3. Furthermore, every vector v ∈ 3 is a unique sum of a vector of U and another vector in W, that is 3 = U ⊕ W.

Using the definition of direct sum, one can verify the following theorem:

Theorem 1.1.3

Let U_1,...,Uk be subspaces of a vector space V. Let i.e., sum of all Uj for j ≠ i. Then V = U_1 ⊕ … ⊕ Ui ⊕ …⊕ Uk if and only if

1.V = U_1 + … + Uk;

2.Ui ∩ Wi = {0} where 0 ∈ V for each i.

EXAMPLE 1.1.6

Let = {Wi | i ∈ I} be a collection of subspaces of V where the index set I can be finite or infinite. It is clear that ∩|i∈I Wi is a subspace of V. If I is a finite set, then the set of all finite sums of the vectors from Σi∈IWi is also a subspace of V, and denote this as Σi∈IWi. If I is an infinite set, let

where Σi∈Iwi means that all wi = 0 except possibly for finitely many i ∈ I. Therefore, regardless whether I is a finite or infinite set, with the above notation Σi∈IWi is a subspace of V.

Theorem 1.1.4

Let be an infinite field and V be a vector space over . Then V cannot be the union of a finite number of proper subspaces (subspaces that are strictly contained in V).

Proof: We will prove the claim by contradiction. Let Wi ⊆ V for i = 1,...,n be proper subspaces of V. Suppose Without loss of generality, we assume that

Let w ∈ W1 and let v ∈ V\W_1. Consider the set U = {w + av | a ∈ }. Since is infinite, U is infinite. Hence U ∩ Wk is infinite for some index k where k = 1, 2,…, n.

Suppose k ≠ 1. If (w + av), (w + bv) ∈ U ∩ Wk for some distinct a, b ∈ , then b(w + av) −a(w + bv) = (b − a)w ∈ Wk. And hence w ∈ Wk, con-tradicting the assumption that Thus, k = 1. But this is not possible, since Wk = W_1 is a subspace, (w + av) − (w + bv) = (a − b) v ∈ W_1, which yields v ∈ W1. This contradicts v ∈ V\W1. Therefore, we proved the original claim.

Notice that the above theorem may not be true if is a finite field. For example, let = 2, and the elements of the vector space is coming from the finite field 2. Then V = {(0, 0), (1, 0), (0, 1), (1, 1)}. Let subspaces V_1 = {(0, 0), (1, 0)}, V_2 = {(0, 0), (0, 1)}, and V_3 = {(0, 0), (1, 1)}, then V = V_1 ∪ V_2 ∪ V_3.

1.2Linear Span and Linear Independence

Definition 1.2.1

A vector b ∈ V is said to be a linear combination of the vectors a_1, …, an in V if there exist scalars c_1, …, cn in such that

The set of all linear combinations of a_1,…,an is called the span of a_1,…,an, and it is denoted by Span (a_1,…,an).

If a vector space V = Span(a_1, …, an), then we say that (a_1, …,an) spans V, and (a_1, …,an) is a spanning sequence for V.

A vector space V is finitely generated if it is possible to find a finite sequence of vectors (a_1, …,an) such that V = Span(a_1, …,an).

EXAMPLE 1.2.1

The real vector space 3 has {(2, 0, 0), (0, 1, 0), (0, 0, 1)} as a spanning set. {(1, 2, 3), (0, 1, 2), (−1, 0.5, 3), (1, 1, 1)} is also a spanning set for 3. But, the set {(1, 0, 0), (0, 1, 0), (1, 1, 0)} is not a spanning set of 3, since (0, 0, 1) ∈ 3 is not in the span of this set. The span of this set is the space of all vectors in 3 whose last component is zero.

EXAMPLE 1.2.2

Let A = (a_1,…,am), and B = (b_1,…,bm) be two spanning sequences of a vector space V. Define the union of the two sequences A and B by A ∪ B = (a_1,…,am, b_1,…,bn). It is easy to check that Span(A) ∪ Span(B) ⊂ Span(A ∪ B).

Theorem 1.2.1

Let A = (a_1,…,am) be a sequence such that ai ∈ V. Then

1.Span(A) is a subspace of V;

2.If W is a subspace of V, and A ⊂ W, then Span(A) ⊂ W.

Proof: One can check the claim by using the definition of span. The second claim says that Span(A) is the “smallest” subspace of V which contains A. If W contains A, and W ⊆ C Span(A), then W = Span(A).

Theorem 1.2.2

Let A = (a_1,…,am) be a sequence such that ai ∈ V are distinct vectors. If there exists a vector ai for some i such that then Span(A) = Span(A \ {ai}).

Proof: It is easy to see that Span(A) ⊇ Span(A \ {ai}). To see Span(A) ⊆ Span(A \ {ai}), let b ∈ Span(A), then

Thus, Span(A) = Span(A \ {ai}).

So far, we have seen that any finite subset A of a vector space V determines a subspace Span(A) of V. If we let A denote the set of all subsets of V, and denote the set of all subspaces of V, then there is a function Span : A → which sends a subset A ∈ A to Span(A) ∈ . One can show that Span is a function with the following properties:

1.If A_1 ⊆ A_2 ∈ A, then Span(A_1) ⊆ Span(A_2) ∈

2.If w ∈ Span(A), then there exists a subset A′ ⊆ A such that w ∈ Span(A′).

3.A ⊆ Span(A) for all A ∈ A.

4.For every A ∈ A, Span(Span(A)) = Span(A).

5.Let v, w ∈ V, if v ∈ Span(Au{w})\Span(A), then w ∈ Span(A∪{v}).

We observe that if a certain element of a spanning set can be spanned by the other elements of the spanning set, then one can reduce the number of elements in the spanning set. This introduces the following concept.

Definition 1.2.2

A finite sequence of vectors a_1,…,an from a vector space V is linearly dependent if there are scalars c_1, ... ,cn, not all zero, such that The sequence is said to be linearly independent if

An infinite set of vectors is linearly dependent if it contains a finite subset that is linearly dependent. Otherwise, this infinite set of vectors is called linearly independent.

It is easy to check that if a spanning set contains repeated vectors, or if one of the vectors is a linear combination of the other vectors, then the spanning set is linearly dependent.

Theorem 1.2.3

Let A − (a_1,…,an) be a linearly independent sequence of vectors of a vector space V. Then

1.If b ∉ Span(A), then A ∪ {b} − {a_1,…, an, b} is a linearly independent set.

2.If x ∈ Span(A), then x can be uniquely expressed as

Proof: We will prove the linearly independent relation by contradiction, that is, suppose there exists c, c_1, …, cn not all zero such that Since A is a linearly independent sequence, we must have that c ≠ 0,

This is impossible since b ∉ Span(A).

To show the second claim, suppose

Since A is a linearly independent set

Hence, the expression is unique.

EXAMPLE 1.2.3

Let V = Mm×n(). For any 1 ≤ i < m and 1 ≤ j ≤ n, let ei,j be the m × n matrix whose (i, j)-th entry is 1, and all other entries are zero. It is easy to see that eij for 1 ≤ i ≤ m and 1 ≤ j ≤ n are linearly independent since

where 0 is the m × n matrix with entries all zero. Moreover, Mm×n() is spanned by the eij for 1 ≤ i ≤ m and 1 ≤ j ≤ n.

1.3Bases for Vector Spaces

Definition 1.3.1

A finite set subset = {v_1, ..., vn} of a vector space V is called a finite basis for V provided

1.v_1,…, vn are linearly independent, and

2.v_1,…, vn span V.

Consequently, if v_1, ..., vn is a list of vectors in V, then these vectors form a basis if and only if every v ∈ V can be uniquely written as

If there is an infinite set of linearly independent and spanning elements, then this set is called an infinite basis. This basis is called a Hamel basis.

EXAMPLE 1.3.1

We see in Example 1.2.3,

form a basis for the vector space V = Mm×n().

EXAMPLE 1.3.2

Let V = [x]. Then = {1 = x^0, x, x^2,…} form a basis of V.

Theorem 1.3.1

If V is generated by n vectors v_1,…,vn, then any sequence of vectors with more than n vectors is linearly dependent.

Proof: Let (a_1, …, ak) with k > n be a sequence of vectors of V. If a_1 ∈ V, then a_1,v_1,…,vn are linearly dependent. There exists a vector say vn ∈ V = Span(a_1,v_1,…,vn-1). We repeat this process, and obtain V = Span(an, an-1,…,a_1). Then an+1 ∈ V, and an+1, an, an−1,…, a_1 are linearly dependent. Thus, we conclude that any sequence of vectors with more than n vectors is linearly dependent.

Theorem 1.3.2

Let V = Span(v_1,…,vn) be a finitely generated vector space. Then V has a basis with at most n elements.

Proof: Let v_1,…,vn generate V, that is V = Span(v_1,…,vn). If v_1,…,vn are linearly independent, then = {v_1,…,vn} is a basis for V. If v_1,…,vn are linearly dependent, then there exists a vector say vn such that vn ∈ Span(v_1,…, vn−1). Then by Theorem 1.2.5, V = Span(v_1,…, vn−1). We repeat the process to obtain a set = {v_1,…,vm} with m < n such that is a basis of V. Therefore, if V = Span(v_1,…,vn), then the basis = {v_1,…,vm} of V is such that m ≤ n.

From this proof, we see that one can obtain a basis from a spanning set. It is also easy to see that if V is a finitely generated vector space such that every linearly independent sequence from V has at most n vectors. Then V has a basis with at most n vectors. Moreover, if a vector space V has a basis with n elements, then any subspace of V has a basis with at most n elements.

Theorem 1.3.3

If and are two bases of a finitely generated vector space V, then i.e., the two bases contain the same number of elements.

Proof: Let − {a_1, …, am} and − {b1,..., bn}. Then V − Span(), hence V has a basis with at most m elements, thus n ≤ m. On the other hand, V − Span(), hence V has a basis with at most n elements, thus m ≤ n. Therefore, we must have that m = n. Hence, i.e., the two bases contain the same number of elements.

Suppose V is not finitely generated, i.e., has no finite basis. Let and be two bases with infinitely many elements. Consider the function f : → Span(). For any w ∈ there exists a unique finite subset such that where {v_1, …, vn} − By cardinal arithmetic, where Since and both span V, we must have that Therefore, Exchange the two bases, and with the same proof, we can show that Hence, when V has no finite bases, we still have We can conclude that the cardinality of any bases (finite or infinite) for a vector space over are the same.

Definition 1.3.2

If V is a finitely generated vector space, then n, the number of vectors in a basis of V is called the dimension of V. We write dim V = n. If V is not finitely generated, we denote dim V = ∞.

It is easy to check the following results:

Theorem 1.3.4

Let V be a vector space and dim V − n, and W is a subspace of V. Let S = (v_1, …, vm) be a sequence of vectors from V. Then

1.If S is linearly independent, then m ≤ n.

2.If S spans V, then m ≥ n.

3.If S is linearly independent and m < n, then S can be extended to a basis.

4.If S spans V and m > n, then some subsequence of S can form a basis.

5.If m = n and S is linearly independent, then S spans V and S is a basis.

6.If m = n and S spans V, then S is linearly independent and S is a basis.

7.dim(W) ≤ n; and dim W = n if and only if W = V.

8.There exists a subspace U of V such that W + U = V and W ∩ U = {0}.

9.If W, U are subspaces of V, then dim(W) + dim(U) = dim(W + U) + dim(W ∩ U).

Definition 1.3.3

If V is a finite-dimensional vector space, an ordered basis for V is a finite sequence of vectors which is linearly independent and spans V. If = {b_1, …, bn} is an ordered basis for V. Given v ∈ V, then there is a unique n-tuple (c_1, …, cn) such that Then ci is called the i-th coordinate of v relative to the ordered basis The coordinate vector of v relative to the ordered basis To indicate the dependence of this vector c on the basis, we denote this coordinate vector as

From this definition, one can proof the following results.

Theorem 1.3.5

Let V be an n-dimensional vector space over the field , and let = {b_1,…, bn} and be two ordered bases of V, where bi = [bi_1,…,bin]T and Then there is a unique, necessarily invertible, n × n matrix P with entries in such that

The columns of P are given by

where means the inverse of the matrix formed by the basis elements.

Proof: We observe

Theorem 1.3.6

Suppose P is an n × n invertible matrix over . Let V be an n-dimensional vector space over , and let be an ordered basis of V. Then there exits a unique ordered basis of V such that

Proof: Let this is a basis since P and are invertible matrices. By Theorem 1.3.10, satisfies the two stated conditions.

Suppose there exist two bases and and both satisfy the two stated conditions, then

Again by Theorem 1.3.5

Thus such basis is unique.

EXAMPLE 1.3.3

Any finite set of vectors can be represented by a matrix in which its columns are the coordinates of the given vectors. As an example in dimension 2, consider a pair of vectors obtained by rotating the standard basis counterclockwise for 45°. The matrix whose columns are the coordinates of these vectors is

1.4Linear System of Equations

A linear equation is given as

where x_1, x_2, … , xn are variables, a_1, a_2, … , an ∈ are coefficients of the equation and b ∈ is the constant term. The coefficients of the equation can also be written in the form of the coefficient vector a = (a_1, a_2, …, an). The linear equation is called a homogeneous linear equation if the constant term is zero.

A linear system of equations consists of m linear equations

where x_1, x_2, … , xn are variables of the linear system. For an xi, we assume there at least exists a k such that aki ≠ 0, otherwise the variable xi can be eliminated from the linear system. A set of number s_1,.…,sn is a solution of the linear system (1.1), if all the linear equations become identical equations by substituting s_1, … ,sn for xi, …, xn. The linear system is called a homogeneous linear system if all the constant terms are zero.

EXAMPLE 1.4.1

Consider three simple linear systems over a field

The first linear system has the unique solution x_1 = 2, x_2 = 1, the second linear system has the solution x_1 = c, x_2 = 2 − c where c ∈ can be any constant, this solution has a free variable c and means infinite number of numerical solutions. The third linear system has no solution.

To solve a linear system of equations, a well known method is to transform the linear system to an equivalent simple linear system, a trapezoidal linear system based on Gaussian elimination. We consider three elementary transformations:

(i)Exchange two equations in the linear system;

(ii)Multiple by a non-zero constant to an equation in the linear system;

(iii)Add an equation to another equation in the linear system.

Theorem 1.4.1

For a linear system of equations, the solution set is invariant under any elementary transformations on the original linear system.

Proof: The elementary transformation (i) only changes the order of the individual equations, but the system is the same. Hence, the solution set stays the same under such transformation.

The elementary transformation (ii) only multiplies one individual equation by a non-zero scalar, producing an equivalent equation. Hence, the new system is equivalent to the original system, and the solution set is invariant under such transformation.

To show that the solution set is the same under elementary transformation (iii), we first let c_1, …, cn be a solution of the original linear system. Suppose we add the i-th equation to the j-th equation, i.e., the j-the equation is updated as

We need only show that c_1, …, cn is the solution of this new equation. In fact from ai_1c_1 + … + aincn − bi and aj_1c_1 + …+ ajncn = bj we have

Conversely, we start with the updated linear system. Update the i-th equation by multiplying by −1, using elementary transformation (II), we get a new linear system having the same solution. Update this new linear system by adding the j-th equation to the updated i-th equation, we get back the original linear system having the same solution similar to the above discussion.

Notice that ai_1 ≠ 0 for some i and one can exchange the first equation and the i-the equation if a_11 = 0. Therefore, we may assume a_11 ≠ 0 in linear system (1.1), we multiple −aj_1/a_11 to the first equation and add the result to the j-th equation for j = 2, … ,n. After the transformation, we obtain a new linear system (to avoid many symbols we here still use the aij and bj to represent the updated coefficients).

where k is the least number associated to xk whose coefficient a2k is nonzero in the updated m − 1 equations and k ≥ 2. Note that if there is no such k, then the system is equivalent to the first equation. Otherwise, repeat the similar transformation process for the updated m − 1 equations, we obtain

where l ≥ k + 1 and a3l ≠ 0. Repeat the transformation process and we finally can get the linear system in the trapezoidal form

where a_11, a2k, a3l, …, ars are all non-zero and 1 < k < l < … < s ≤ n, r ≤ m. Notice that there is no equation of the form 0 = bi if r = m. For this trapezoidal linear system, variables xs+i, … , xn are free or independent variables, and the variables xi, xk, xl, …, xs are the dependent variables with nonzero coefficients, which can be expressed in terms of the free variables.

Theorem 1.4.2

The linear system of equations (1.2) has solutions if and only if br+1i = …= bm = 0. Furthermore, the solution is unique if and only if r = n and br+i = … = bm = 0; there are an infinite number of solutions if and only if r < n and br+1 = … = bm = 0.

Proof: Suppose br+1i = … = bm = 0. Fix the free variables with random values cr+i, …,cn and substitute them into the r-th equation, we have where is a number in . Then is solved easy. Similarly, substitute cr, cr+1, … , cn into the r − 1-th equation we solve xl − cr−1 for some variable xl. Repeat the similar process for i-th equation i = r − 2, …, 1 we will find a solution c_1, …, cr, cr+1, …, cn of (1.2).

If one of br+1, …, bm is non-zero w.l.o.g, bm ≠ 0, then the equation 0 = bm is a contradictory equation and leads to no solution for (1.2).

If r = n and br+1 = … = bm = 0, then there is no free variables and the above solving process shows that the solution is unique.

If r < n and br+1 = … = bm = 0, then then free variables can be any value, i.e., there are infinite number of solutions.

Two linear systems are equivalent if they have the same solutions or no solution simultaneously. By Theorem 1.4.1 and Theorem 1.4.2, we have

Corollary 1.4.1. A linear system is equivalent to a trapezoid linear system.

1.5A First Look at Determinants

Consider a simple linear system

Multiply the first equation by a_22, and multiply the second equation by a_12, we have

Subtracting the second equation from the first equation, we get a new equation with x_2 being eliminated

Similarly, xi can be eliminated in the system (1.3) to get

Then we can solve for x_1 and x_2 if a_11a_22 − a_12a_21 ≠ 0. Precisely,

For numbers a, b, c, d, we can consider that ad − bc is a value computed from the matrix We call this value the determinant of the matrix and denote it by

Proposition 1.5.1. If a_11a_22 ≠ a_12a_21 ≠ 0, then the solution of (1.3) is

The matrix consisting of the coefficients of a linear system and its determinant play import roles in solving the linear system, more details can be found in following chapters.

1.6Using Computer Algebra Systems to Perform Computations

Computer software programs such as Mathematica [Wol15], Maple [Map16], Sage [SJ05], and R [R C13] incorporate algorithms to simplify and compute linear systems. In this section, we include some of the computational examples provided by students using a variety of software programs.

For example, to perform a row reduction on a rectangular matrix, “Row Reduce” function gives the row reduced matrix of any matrix.

In[1]:= RowReduce[{{1, 2, 3, 1, 0, 0}, {4, 5, 6, 0, 1, 0},

{7, 8, 9, 0, 0,1}}]

Out[1]= {{1, 0, -1, 0, -8/3, 5/3}, {0, 1, 2, 0, 7/3, -4/3},

{0, 0, 0, 1, -2, 1}};

One of the most important uses of matrices is to represent and solve linear systems. This section will discuss how to solve linear systems with Mathematica [Wol15].

Solving a linear system involves solving a matrix equation Ax = b, where A = {aij} is an m × n matrix and b = {bi} is a column vector given in (1.1). This is a set of m linear equations in n unknowns. If m = n, then the system is said to be square. If m > n, i.e., there are more equations than unknowns, then the system is said to be over determined. If m < n, i.e., there are fewer equations than unknowns, then the system is said to be under determined.

The “LinearSolve” function in Mathematica [Wol15] is designed to solve linear systems directly.

Find the solution to Ax = b where A is a square matrix with exact arithmetic:

In[1]:= A = {{1, 1, 1}, {1, 2, 3}, {1, 4, 9}};

b = {1, 2, 3};

LinearSolve[A, b]

Out[1]={-1/2, 2, -1/2}

Find a solution for a rectangular matrix:

In[1]:= A={{1, 2, 3, 4}, {5, 6, 7, 8}, {9, 10, 11, 12}};

b={13, 14, 15};

LinearSolve[A, b]

Out[1]= {-25/2,51/4,0,0}

The “Linear Solve” function is not limited to solve a system when b is a column vector, it also solves Ax = b for x when b is a matrix:

In[1]:= A = {{1, 1, 1}, {1, 2, 3}, {1, 4, 9}};

b = {{1, 2}, {3, 4}, {5, 6}};

LinearSolve[A, b]

Out[1]={{-2,-1},{4,4},{-1,-1}}

Sage [SJ05] is a free computer algebra system. Following is an example to obtain an echelon form of a given matrix.

M = random_matrix(ZZ, 3, 4)

print M

[-2 -1  1  2]

[ 6  1  3  0]

[-2  2  1 -7]

M.echelon_form()

[ 2  0  11  1]

[ 0  1   6 -3]

[ 0  0  18  0]

Three elementary row operations to a given matrix can also be obtained via Sage. The following example shows how to multiply a non-zero constant to an equation in the linear system, exchange two equations in the linear system, or add an equation to another equation in the linear system.

C=matrix(QQ, [[2,3,5,7],[9,3,4,6],[7,9,2,1],[3,0,4,8]]); C

[2  3  5  7]

[9  3  4  6]

[7  9  2  1]

[3  0  4  8]

D=C.with_rescaled_row(0,3); D

[ 6  9 15 21]

[ 9  3  4  6]

[ 7  9  2  1]

[ 3  0  4  8]

E=C.with_swapped_rows(0,2); E

[7  9  2  1]

[9  3  4  6]

[2  3  5  7]

[3  0  4  8]

F=C.with_added_multiple_of_row(1,3,2); F

[ 2  3  5  7]

[15  3 12 22]

[ 7  9  2  1]

[ 3  0  4  8]

Another potential use of Sage is looking at the basis of vector spaces along with looking at the basis of the intersection of vector spaces.

V = (QQ^3).span([vector(QQ,[1,2,3]),vector(QQ,[3,4,9])])

W = (QQ^3).span([vector(QQ,[4,6,12]),vector(QQ,[3,2,12])])

print("Basis of V")

V.basis_matrix()

print("Basis of W")

W.basis_matrix()

print("Basis of the intersection")

V.intersection(W).basis_matrix()

Basis of V

[1 0 3]

[0 1 0]

Basis of W

[ 1 0 24/5]

[ 0 1 -6/5]

Basis of the intersection

[ 1 3/2 3]

R [R C13] is a programming language and free software environment for statistical computing and graphics that is supported by the R Foundation for Statistical Computing. We may use R in linear algebra. For example, we may compute the determinate of a matrix by R.

[language=R]

M=matrix(c(7,4,6,3,8,4,7,15,2,6,3,9,-3,6,-17,3),nrow=4,ncol=4)

M

[,1]  [,2]  [,3]  [,4]

[1,]  7     8     2    -3

[2,]  4     4     6     6

[3,]  6     7     3   -17

[4,]  3    15     9     3

det(M)

[1] -6930

Using R, one can also test linear independence relationships among given vectors, and determine the rank of the vector spaces.

[language=R]

N = matrix(c(1,0,0,0,2,5,4,-1,-1,0,1,2,0,-10,7,3,-4,-10,-8,2),

nrow=4,ncol=5,dimnames=list(c("A","B","C","D"),

paste("v",1:5,sep="")))

N

v1  v2  v3  v4  v5

A  1   2  -1   0  -4

B  0   5   0 -10 -10

C  0   4   1   7  -8

D  0  -1   2   3   2

mN <- N[,q$pivot[seq(q$rank)]]

mN

v1  v2  v3  v4

A  1   2  -1   0

B  0   5   0 -10

C  0   4   1   7

D  0  -1   2   3

qr(N)$rank

[1] 4

1.7Applications of Vector Spaces

Vector spaces are applied throughout mathematics, science, and engineering. Vector spaces may be generalized in several ways, leading to more advanced notions in geometry and abstract algebra. In this section, we will discuss a few applications.

1.7.1Code

In this section, we will see how vectors can be used to design codes for detecting errors that may occur in data transmission. A linear code of length n and rank k is a linear subspace C with dimension k of the vector space where is the finite field with q elements. Such a code is called a q-ary code. If q = 2 or q = 3, the code is described as a binary code or a ternary code, respectively. The vectors in C are called codewords. The size of a code is the number of codewords and equals qk.

In practice, to transmit a message consisting of words, numbers, or symbols, one begins by encoding each “word” of the message as a binary vector, that is, a vector with entries in 2. A binary code is a set of binary vectors of the same length called code vectors. The process of converting a message into code vectors is called encoding, and the reverse process is called decoding.

For example, a message “buy” is represented by a binary code 1011. One way of encoding is to attach a binary “tail” to the binary code to detect the error—attaching a “1” if the binary code contains an odd number of 1s, otherwise, attaching a “0”. Thus, all encoded binary words have an even number of 1’s. Therefore, 1011 will be encoded as 10111, and we know that an error has occurred if the word is distorted to 00111. Therefore, the message to be transmitted consists of binary vectors and a simple error-detecting code called a parity check code. A parity check code is created by appending an extra component, called a check digit, to each vector so that the parity, i.e., the total number of 1’s is even.

To generalize this process in terms of vectors, let the message be the binary vector a = [a_1, …,an] ∈ and the parity check code vector is v = [a_1, … ,an,a] ∈ where the check digit a is chosen such that

a_1 + … + an + a ≡ 0 ∈ 2, equivalently 1 ∙ v ≡ 0, 1 = [1, …, 1] ∈

The vector 1 = [1,1, … , 1], is called a check vector. Parity check codes are special cases of the more general check digit codes in a q-ary code.

For example, let a message be represented by a vector a = [a_1, …, an] = [2, 2, 0, 1, 2] ∈ and the parity check code vector is v = [2, 2, 0, 1, 2, a] ∈ then the check digit must be

Thus the parity check code becomes v = [2, 2, 0, 1, 2, 2].

Simple check digit code may detect a single error, but it will not be able to detect other types of common errors such as the accidental permuting of two digits. For example, the binary codes 1011 and 0111 both contain an odd number of 1’s so the added parity check code cannot detect the error if the message “buy” represented by a binary code 1011 is distorted to 0111. Next, we will discuss how to use matrices to design codes that can correct as well as detect certain types of errors.

First, we encode a message represented by a vector by using a matrix transformation for some n > k. The vector T(a) = Ga = v is called the code vector, and the matrix G is called the generator matrix for the code. To exam whether a received vector b is a code vector, we define a parity check matrix P to be such that Pv = 0 for the code.

For example, a message “sell” represented by a binary code vector a = [0101]T is encode by the generator matrix G to get the code vector v as the following

The parity check matrix

If the vector v is received then Pv = 0, and it is correct. On the other hand, if v′ = [0111010]T is received, then compute

Since Pv′ ≠ 0, the code is distorted. Furthermore, Pv′ = [0 1 1]T is the same as the third column of the parity check matrix P, and this tells us the error is in the third component of the received message v′. Thus, by changing the third component of v′, we recover the correct code vector v.

1.7.2Hamming Code

In telecommunication, Hamming codes are a family of linear error-correcting codes that were invented by Richard Hamming in 1950. The binary Hamming code first introduced has check matrix

The elements of this matrix are in 2. The Hamming code C of length 7 is the space of H, i.e.,

The Hamming distance dH between any two words of the same length is defined as the number of coordinates in which they differ.

Proposition 1.7.1. The minimum distance between binary Hamming codewords is 3.

Proof: Suppose x, y ∈ C are two code words from a Hamming code. Then x − y ∈ C.

If dH (x, y) = 1, then H(x − y) is a column of H, which is non-zero. But this is not possible since if (x − y) is a Hamming code word, then H(x − y) = 0.

If dH(x, y) = 2, then H(x − y) = 0 if and only if there are two columns of H which are linearly dependent. But this is not the case.

Hence dH(x, y) ≥ 3 for all code words x, y. Every check matrix for a binary Hamming code will have three columns that are linearly dependent, so in fact some code words are of distance 3.

Linear codes like C are identified by their length, dimension, and minimal distance. Thus C is referred as (7, 4, 3), because its length is 7, its dimension is 4, and its minimum distance is 3.

1.7.3Linear Code

Below, we give formal definition and theorem to generalize this idea.

Definition 1.7.1.

If k < n, then any n × k matrix of the form where A is an (n − k) × k matrix over 2 is called a standard generator matrix for an [n, k] binary code Any (n − k) × n matrix of the form where B is an (n−k) × k matrix over 2 is called a standard parity check matrix. The code is said to have length n and dimension k.

The following theorem will help us to identify when G can be a standard generator matrix for an error-correcting binary code, and also, given G, tell us how to find an associated standard parity check matrix P.

Theorem 1.7.1

If is a standard generator matrix and is a standard parity check matrix, then P is the parity check matrix associate with G if and only if A = B. The corresponding binary code [n, k] is (single) error-correcting if and only if the columns of P are non-zeros and distinct.

Proof: Let ai be the i-th column of A.

(⇒) Let P be the standard parity check matrix associated with G for the same binary code a. Then for every we have PGx = 0. Thus,

Hence

Let x = ei, the i-th standard basis vector in then we have

(⇐) If B = A, then

Thus, P is the standard parity check matrix associated with G for the same binary code a.

Finally, to see that the pair G, P determines an error-correcting code if the columns of P are non-zeros and distinct, let x be a message vector in and let the corresponding code vector be v = Gx, and Pv = 0.

(⇐) Suppose there is an error in the i-th component of the received code vector v′. Then v′ = v + ei, and

where pi is the i-th column of P, which indicates exact component that the error occurs.

(⇒) If P has a zero column, say pi = 0, then an error in the i-th column will not be detected, since Pv′ = 0. Moreover, if pi = pj, then we cannot pinpoint the column that the error occurs.

We observer that and guarantee that the columns of G and the rows of P are linearly independent. Theorem 1.7.3 states that G and P are associated with the same code if and only if A = B, which is equivalent to the condition that PG = . Moreover, PG = means that Pgi = 0 for every column gi of the matrix G. Thus, vector v is a code vector if and only if v is in the column space of the matrix G, that is v = Ga for some vector Since elementary row or column operations do not affect the row or column spaces of the given matrix. Therefore, if P is a parity check matrix, E is an elementary matrix, and v a code vector, then

and EP is also a parity check matrix. Therefore, any parity check matrix can be converted into another one by means of a sequence of row operations.

The properties of row or column operation of a matrix in linear algebra provide ways of construction new code. Below, we give a new definition:

Definition 1.7.2

For n > k, and an n × k matrix G and an (n − k) × n matrix P over are generator matrix and a parity check matrix, for an [n, k] binary code C if the following conditions are all satisfied:

1.The columns of G are linearly independent.

2.The rows of P are linearly independent.

3.PG = .

We call two codes C_1 and C_2 equivalent if there is a permutation matrix M such that

1.7.4Golay Code

Golay codes are the most interesting codes constructed up to 1996. In mathematics and electronics engineering, a binary Golay code is a type of linear error-correcting code used in digital communications. Golay codes were used to transmit the color images of Jupiter and Saturn within a constrained telecommunications bandwidth by the Voyager 1 and 2 spacecraft.

Definition 1.7.3

(Extended binary Golay codes) Let G be the matrix where is the 12 × 12 identity matrix and A is the 12 × 12 matrix

The binary linear code with generator matrix G is called the extended binary Golay code and will be denoted by G_24.

Proposition 1.7.1 (Properties of the extended binary Golay code)

1.The length of G_24 is 24 and its dimension is 12.

2.A parity-check matrix for G_24 is the 12 × 24 matrix

3.The code G_24 is self-dual, i.e.,

4.Another parity-check matrix for G_24 is

5.Another generator matrix for G_24 is matrix

6.The minimum distance of G_24 is 8.

Proof: We will leave the proof as an exercise for the readers. Observed that a generator matrix for the dual code is a parity-check matrix for the original code and vice versa. The dual of the dual code is always the original code. For more details concerning item 3, please see the following discussion concerning dual code.

In coding theory, the dual code of a linear code C is the linear code defined by

Proposition 1.7.2 Let C be an [n, k] binary code with generator matrix G Then C⊥ is an [n, n − k] code with parity check matrix GT.

Proof: for all

But

This means that C^ is the null space of GT, and GT is an k × n matrix of rank k. Hence C⊥ has dimension n − k. GT is a parity check matrix of C⊥.

As a conclusion, vector spaces are very important in coding theory. The theory of error-correcting codes is a relatively recent application of mathematics to information and communication systems. It turns out that a rich set of mathematical ideas and tools from linear and abstract algebra can be used to design good codes.

1.8Exercises

1.Identify which of the following sets are subspaces of 3, and state the reasons.

(a)V = {(x, y, z) ∈ 3 | x + 2y = 11}.

(b)V = {(x, y, z) ∈ 3 | x + 2y + 5z = 0}.

(c)V = {(r, r + 2,0) ∈ 3}.

(d)The set of all polynomials f(x), with f(7) = 0.

2.Assume that v and w are linear independent vectors. Prove that v, w, (v + w) are linear dependent vectors.

3.Prove that all polynomials f(x) with degree not greater than 3 constitute a vector space.

4.Given V = {(2, 5, 3), (1, 0, 2)} and W = {(2, 0, 5), (3, 5, 5)}. Is the intersection of Span(V) and Span(W) a vector space? If so, what is the dimension?

5.Let B = {(1, 0, 1), (0, 2, 0), (1, 2, 3)} and C = {(1, 0, 0), (2, 0,1), (0,1, 3)} be two bases of 3. Let the coordinates of a vector v relative to B and C be (x, y, z) and (a, b, c). Write the relation between these coordinates in matrix notation.

6.Let U and V both be 2-dimensional subspaces of 5, and let W = U ∩ V. Find all possible values for the dimension of W.

7.Let U and V both be 2-dimensional subspaces of 5, and define W = U + V = {w | w = u + v, u ∈ U, v ∈ V}. Show that W is a linear space, and find all possible values for the dimension of W.

8.Let A : n → k be a real matrix, not necessarily square. Show that if the columns of A are linearly dependent, then A is not one-to-one.

9.Find a 3 × 3 matrix that acts on 3 as follows: it keeps the x-axis fixed but rotates the yz-plane by 60 degrees.

10.Let Find all 2 × 2 matrices, B such that AB = 0. Does {B ∈ M2×2 | AB = 0} form a subspace of 2 × 2 matrices? If so, find a basis.

11.Let V be the vector space over all real 2 × 2 matrices. Let W be the subset of V consisting of all symmetric matrices. (a) Prove that W is a subspace of V. (b) Find a basis of W. (c) Determine the dimension of W.

12.A matrix A is called skew-symmetric if AT = A. Let V be the vector space over all real 2 × 2 matrices. Let W be the subset of V consisting of all skew-symmetric matrices. (a) Prove that W is a subspace of V. (b) Find a basis of W. (c) Determine the dimension of W.

13.A Vandermonde matrix is often used in applications. Calculate the square of the Vandermonde matrix

14.Calculate the images resp. the pre-images of the line

and the conic section

under the affine mapping

where a_11a_22 −a_12a_21 = 0.

15.Show that if f : 2 → 2 is an injective, affine mapping, then f maps conic sections onto conic sections. For which f is the image of a circle also a circle?

16.If Q is the conic

and

Show that the conic has the form

17.Show that if z_1 and z_2 are distinct complex numbers, then

is the equation of the straight line through z_1 and z_2

18.For which values of t do the following 4-vectors form a basis of 4?

19.For which values of t the following matrices form a basis in M2×2

C H A P T E R 2

LINEAR TRANSFORMATIONS

2.1Linear Transformations

In mathematics, a linear map, or a linear transformation, or, in some contexts, a linear function, is a mapping V a W between two algebraic structures, that preserves the operations of addition and scalar multiplication. Linear maps can often be represented as matrices, and simple examples include rotation and reflection linear transformations. One of the important special cases is that when V = W, the map is called a linear operator, or an endomorphism of V. In the language of abstract algebra, a linear map is a module homomorphism of modules over a given ring. In fact, ring and module are regarded as one of the most important subjects in abstract algebra and the theory of ring and module is so extensive which includes that vector spaces. In this chapter, we will focus on linear transformations of vector spaces, and touch a few topics in ring and module homomorphisms.

Recall, if a function f maps from a set X, namely the domain into a set Y, codomain, then for each x ∈ X, the element f(x) ∈ Y is called the image of x, and {x ∈ X | f(x) = y} is the pre-image of y. The range of f, denoted by range(f), is the set of all images, range(f) = {f(x) | x ∈ X}. A linear function, or linear transformation, or a linear map between vector spaces is a function that preserves some of the algebraic properties of vector spaces.

Definition 2.1.1

Let V and W be vector spaces over the field F. A linear transformation from V into W is a function T from V into W such that

The set of all linear transformation from V to W will be denoted by (V, W).

EXAMPLE 2.1.1

Consider L : 2 → 3, a linear transformation, defined by L([x, y]T) = [y, −2x + 2y, x]T, then this linear transformation can be given as a matrix multiplication such that

In algebra, a module homomorphism is a function between modules that preserves module structure.

Definition 2.1.2

Let M and N be left modules over a ring R, then a function f : M → N is called a module homomorphism or a R-linear map if for any x, y ∈ M and r ∈ R,

1.f(x + y) = f(x) + f(y),

2.f(rx) = rf(x).

If M, N are right modules, then the second condition is replaced with f(xr) = f(x)r. The pre-image of the zero element under f is called the kernel of f or the null space of f. The set of all module homomorphisms from M → N is denoted by HomR(M, N). It is an abelian group with respect to addition, but is not necessarily a module unless R is commutative.

Remark: In general, if T ∈ Hom (M, N), then

1.ker(T) = {m ∈ M | T(m) = 0}.

2.im(T) = {n ∈ N | ∃ m ∈ M, T(m) = n}.

3.T is injective, or monomorphism, or one-to-one, if ker(T) = {0}.

4.T is surjective, or epimorphism, or onto, if im(T) = N.

5.T is bijective, or isomorphism, if T is both injective and surjective.

6.M and N are said to be isomorphic, M N if there exists an isomorphism T ∈ Hom(M, N).

Since a vector space is a module over a field, therefore, linear transformations of vector spaces are special cases of module homomorphisms.

EXAMPLE 2.1.2

Let R = be a ring. Let M = m, and N = n be two R-modules. Let f : M → N be a R-module homomorphism. One can check that HomR(M, N)

Definition 2.1.3

If V is a vector space over the field F, a linear operator on V is a linear transformation from V into V.

Definition 2.1.4

A linear transformation T is non-singular if T(γ) = 0 implies that γ = 0. That is, the null space of T is {0}.

Theorem 2.1.1

Let T be a linear transformation from V into W. Then T is non-singular if and only if T carries each linearly independent subset of V onto a linearly independent subset of W.

Proof: Let T : V → W be a linear transformation and non-singular, and v_1, …, vn linearly independent. To show T(v_1), …, T(vn) are linearly independent, consider

Thus, T(v_1), … T(vn) are linearly independent.

To show T is non-singular, we only need to show that T(v) = 0 implies v = 0. To do so, let v_1, … vn be a basis of V, and v = c_1v_1 + … + cnvn, then

Thus T is non-singular.

EXAMPLE 2.1.3

In 2-dimensional space 2 linear maps are described by 2 × 2 real matrices relative to the standard basis. These are some examples:

1.Rotation by 90 degrees counterclockwise:

2.Rotation by angle θ counterclockwise:

3.Reflection against the x-axis:

4.Reflection against the y-axis:

5.Scaling by k > 0 in all directions:

6.Horizontal shear mapping:

7.Vertical squeeze mapping, k > 1:

8.Projection onto the y-axis:

2.2Rank a nd Nullity of a Linear Transformation

Definition 2.2.1

Let V and W be vector spaces over the field , and let T be a linear transformation from V into W. The null space of T is the set of all vectors v ∈ V such that T(v) = 0. If V is finite-dimensional, the rank of T is the dimension of the range of T, and the nullity of T is the dimension of the null space of T.

EXAMPLE 2.2.1

Let [s] denote the ring of polynomials in a single variable s with coefficients from the field . A polynomial vector v ∈ ([s])w is a vector of size w with each entry being a polynomial. The degree n of a vector v ∈ ([s])w is the maximum amongst the degrees of its polynomial components. Alternatively we can write v as a polynomial of degree n with the coefficients being the vectors from w. Hence, ([s])w = w[s]. Similarly a polynomial matrix ∈ g×w [s] is a matrix of size g × w with the entries from [s]. The degree of a polynomial matrix is the maximum of the degrees amongst its polynomial entries. A polynomial matrix can be written as a polynomial in s with coefficients being the matrices from g×w. The null space of is {v ∈ w [s] | Rv = 0}.

Theorem 2.2.1

Let V and W be finite-dimensional vector spaces over the field , let T ∈ (V, W) be a linear transformation from V into W. Then

1.If T is injective, then dim V ≤ dim W.

2.If T is surjective, then dim V ≥ dim W.

3.If dim V = dim W, then T is an isomorphism if and only if T is injective or T is surjective.

4.rankT + nullityT = dim V.

Proof: Let = {b_1, … bn} be a basis for V.

1.Since T is injective, T(b_1), … T(bn) are a linearly vectors in W. Hence independent n ≤ dim W.

2.Since T is surjective, {T(b_1), … T(bn)} generates W, i.e., W = Span(T(b_1), … T(bn)). Hence n ≥ dim(W).

3.(⇒) If T is an isomorphism, then it is both injective and bijective. (⇐) If T is injective, then T(b_1), … T(bn) are linearly independent. Since dimV = dimW, T(b_1), … T(bn) form a basis for W. Hence T is surjective. Therefore, T is an isomorphism.

On the other hand, if T is surjective, then W = Span(T(b_1), … T(bn)), so {T(b_1), … T(bn)} contains a basis. Since dim V = dim W, T(b_1), … T(bn) in fact form a basis. Let T(v) = 0 for some Then 0 = T(v) = implies all ci = 0. Thus Thus ker T = {0}, hence T is injective. Therefore, T is an isomorphism.

4.Let k = nullityT, and let b_1, … bk be the basis for ker T, and let b_1, … bk, bk+1, … bn is a basis for V. We will show that rank T = n − k, that means we need to show that T(bk+1), … T(bn) form a basis for imT. To do so, we let w ∈ imT, so there exists v ∈ V such that T(v) = w. Thus,

where the last equality holds since bi for i = 1, … k are the basis for ker T. Thus imT ⊆ Span(T(bk+1), … T(bn)). Moreover, T(bk+1), … T(bn) must be linearly independent, otherwise, there would be ci for i = k + 1, … n, not all zero, such that which implies that But this is impossible, since b1, … bk form a basis for ker T, which in turn would imply b_1, … bn are linearly dependent, contradicting the fact they form a basis for V. Therefore, T(bk+1), … T(bn) are linearly independent and span imT, hence rankT = dim(imT) = n − k. Thus, dim V = n = k + (n − k) = nullityT + rankT.

Theorem 2.2.2

(Sylvester’s theorem) Let V, W and Y be finitely generated vector space over a field , and a ∈ (V, W), β ∈ (W, Y) are linear transformations. Then

1.nullity(βα) ≤ nullity(α) +nullity(β).

2.rank(α) + rank(β) − dim W ≤ rank(βα) ≤ min{rank(α), rank(β)}.

Proof: To prove the first claim, we let β′ = β|im(α) the restriction of to im(α). Then ker(β′) ⊆ ker(β), therefore nullity (β′) ≤ nullity(β). Hence,

To show the second claim, we note that im(βα) ⊆ im(β), so

Furthermore, since im(βα) = im(β′), and rank of any linear transformation is not greater than the dimension of its domain, we must have rank(βα) ≤ rank(α). Thus,

rank(α) + rank(β) − dim(W)

= [dim(V) − nullity(α)] + [dim(W) − nullity(β)] − dim(W)

= dim(V) − [nullity(α) + nullity(β)]          by claim 1

≤ dim(V) − nullity(βα)

= rank(βα).

Hence, we proved the claim.

Remark

Let P ∈ (V, W), A ∈ (W, Y), and Q ∈ (Y, Z), where V, W, Y, Z are finitely generated vector spaces. Then

1.If P is surjective, then rankA = rank(AP).

2.If Q is injective, then rankA = rank(QA).

3.If P, Q are isomorphisms, then rankA = rank(QAP).

Definition 2.2.2

The column rank of an m × n matrix A is the dimension of the subspace of m spanned by the columns of A. Similarly, the row rank is the dimension of the subspace of the space n of row vectors spanned by the rows of A.

Theorem 2.2.2

If A is an m × n matrix with entries in the field , then

Proof: To show this, we need to observe that there exist an invertible m × n matrix Q and an invertible n × n matrix P such that A_1 = QAP has the block form where I is an r × r identity matrix for some r, and the rest of the matrix is zero. The matrices P, Q in fact are the products of elementary matrices, i.e., the row or column operations on A. (Note that P and Q are invertible matrices, hence they are isomorphisms, and preserve rank.) For this matrix, it is obvious that row rank = column rank = r. The strategy is to reduce an arbitrary matrix to this form.

Remark: Another proof for the claim rankT + nullityT = dim V:

Let A be an m × n matrix with r linearly independent columns, that is rank(A) = r. We will produce an n × (n − r) matrix X whose columns form a basis of the null space of A. Thus the nullity of A is equal to the rank of X.

Without loss of generality, assume that the first r columns of A are linearly independent. So, we can write A = [A_1 A_2], where A_1 is m × r with r linearly independent column vectors and A_2 is m × (n − r), each of whose n − r columns are linear combinations of the columns of A_1, that is, A_2 = A_1B for some r × (n − r) matrix B. Hence, A = [A_1 A_1 B]. Let

where In−r is the (n − r) × (n − r) identity matrix, so X is an n × (n − r) matrix such that

Therefore, each of the n − r columns of X is a particular solution of Ax = 0. Furthermore, the n − r columns of X are linearly independent because Xu = 0 will imply u = 0:

Therefore, the column vectors of X form a set of n − r linearly independent solutions for Ax = 0.

Definition 2.2.3

Short exact sequences are exact sequences of the form

where f is an injective map and g is a surjective map, and the image of f is equal to the kernel of g.

The short exact sequence is called split if there exists a homomorphism h : C → B such that the composition g ° h is the identity map of C. It follows that B A ⊕ C.

If is a short exact sequence of vector spaces, then dim A + dim C = dim B. In addition, A ker(g) and C = im(g).

To generalize this, we have if

is an exact sequence of finite-dimensional vector spaces, then

2.3Representation of Linear Transformations by Matrices

Usually, a linear operator can be represented by a matrix. Let V be a finite dimensional vector space over the field , and let = {b1, … bn} be an ordered basis for V. This linear transformation can be represented by a matrix P, where the columns of P are given by

This matrix P is called a matrix representation of the linear transformation T.

EXAMPLE 2.3.1

Let T : 3 → 3 be defined by T(a_1, a_2, a_3) = (3a_1 + a_2, a_1 + a_3, a_1 − a_3). Consider the standard ordered basis ε = {e_1, e_2, e_3}. With respect to this basis the coordinate vector of an element a = (a_1, a_2, a_3) is [a]ε = [a_1, a_2, a_3]T. The matrix representation of T is

On the other hand, if we choose a basis = {b_1 = (1, 0, 0), b_2 = (1, 1, 0), b_3 = (1, 1, 1)}. Then the coordinate vectors of a and T(a) are [a] = [a_1 − a_2, a_2 − a_3, a_3]T, and [T(a)] = [2a_1 + a_2 − a_3, 2a_3, a_1 − a_3]T. The columns of matrix P are the coordinate vectors of T(b_1), T(b_2), T(b_3) relative to the basis .

The matrix representation of T with respect to this basis is

Definition 2.3.1

Let = {α_1, … αn} be an ordered basis for V, and β′ = {β_1, … βm} be an ordered basis for W. If T is any linear transformation from V into W, then T is determined by its action on the vectors αj:

Then the matrix A = (Aij) of size m × n is called the matrix of T relative to the pair of ordered basis and ′.

Theorem 2.3.1

Let V and W be finite-dimensional vector spaces over of dimension n and m respectively. Let and ′ be the basis for V and W. Then the map ϕ : (V, W) → Mm×n() defined by the matrix ϕ(T) = [T]→′ ∈ Mm×n(). Then the following diagram commutates

where the isomorphisms are the coordinate mappings.

In this setting, the following result follows directly.

Theorem 2.3.2

Let V be a finite-dimensional vector space over the field , and let

be the ordered bases for V. Suppose T is a linear operator on V. If P = [P_1, … Pn] is the n × n matrix with columns then

Alternatively, if U is the invertible operator on V defined by j = 1, … n, then

Proof: The proof follows from the diagram below:

Definition 2.3.2

Let A, B be n × n matrices over the field . We say that B is similar to A over if there is an invertible n × n matrix P over such that B = P−1AP.

Furthermore, from the above definition, we can see that if we let V be an n-dimensional vector space over the field and W an m-dimensional vector space over . Let be an ordered basis for V and ′ be an ordered basis for W. For each linear transformation T from V into W, there is an m × n matrix A with entries in such that

Moreover, for fixed bases and ′, T → A is a one-one correspondence between the set of all linear transformations from V into W and the set of all m × n matrices over the field .

This matrix A is called the matrix of T relative to the ordered bases and ′. In case V = W and = ′, we call A matrix of T relative to the ordered basis .

From the above definition, we can show that

Theorem 2.3.3

Let V be an m-dimensional vector space over the field and W an m-dimensional vector space over . Let be an ordered basis for V and ′ be an ordered basis for W. For each pair of ordered basis and ′ for V, W respectively, the function which assigns to a linear transformation T its matrix relative to and ′ is a bijection between (V, W) and the space of all m × n matrices over the field .

Proof: Let ϕ : (V, W) → Mm×n(), where ϕ(T) = [T]→′. We need to show this map is one-to-one and onto.

To show ϕ is one-to-one, note that, since every linear transformation is uniquely defined by its evaluation on the basis. If ϕ(T) = ϕ(S) for some T, S ∈ (V, W), then [T]→′ = [S]→′, which means every column [T(bi)]′ = [S(bi)]′ for i = 1, …, n. Thus T(bi) = S(bi) for every bi ∈ . Therefore, T = S.

To see ϕ is onto, let A = {aji} ∈ Mm×n(). Define a linear transformation T : V → W by hence [T(bi)]′ = [a_11, …, ami]T. Thus ϕ(T) = A, therefore, ϕ is onto.

In the next section, we will show that (V, W) is a vector space, and ϕ : (V, W) → Mm×n() is a linear transformation. Hence, Theorem 2.4.1 implies (V, W) @ Mm×n(), and the following results follow directly.

Theorem 2.3.4

Let V be an n-dimensional vector space over the field , and let W be an m-dimensional vector space over . Then the space (V, W) is finite-dimensional and has dimension mn.

Theorem 2.3.5

Let V, W, Z be finite-dimensional vector spaces over the field . Let T be a linear transformation from V into W, and U be a linear transformation from W into Z. If , ′ and ² for V, W, Z respectively, if A is the matrix of T relative to the pair , ², and B is the matrix of U relative to the pair ′, ², then the matrix of the composition UT relative to the pair , ² is the product matrix C = BA.

2.4The Algebra of Linear Transformation

Let V be a finite-dimensional vector space over the field , let T and U be a linear transformation from V into W. For any v ∈ V, the function (T + U) defined by

is a linear transformation from V into W. If c ∈ , the function cT defined by

is a linear transformation from V into W. The set of all linear transformation from V into W, together with the addition and scalar multiplication defined above, is a vector space over the field .

Theorem 2.4.1

For each pair of ordered basis and ′ for V, W respectively, the function which assigns to a linear transformation T its matrix relative to and ′ is a bijection between (V, W) and the space of all m × n matrices over the field .

Lemma Let V be an n-dimensional vector space over the field and W an m-dimensional vector space over . Let be an ordered basis for V and ′ be an ordered basis for W. Let ϕ : (V, W) → Mm×n() be defined by ϕ(T) = [T]→′. Then ϕ is a linear transformation.

Proof: Let T, S ∈ (V, W). For every bi ∈ , (cT + S)(bi) = cT(bi) + S(bi), therefore,

Thus,

hence ϕ is a linear transformation.

Definition 2.4.1

A vector space A over a field is said to be an associative algebra over if in addition to the vector space operations, there is a function ϕ : A × A → A named multiplication such that ϕ(a, b) = ab satisfies:

1.(ab)c = a(bc) for all a, b, c ∈ A, (multiplication associative);

2.(a + b)c = ac + bc and a(b + c) = ab + ac for all a, b, c ∈ A, (right and left distribution);

3.(ka)b = a(kb) = k(ab) for all a, b ∈ A and k ∈ F.

If there exists an element 1 ∈ A such that 1a = a1 = a for all a ∈ A, then A is an algebra with multiplicative identity.

Since the set of all linear transformation from V into V is a vector space over the field , we have that (V, V) is an algebra with identity over . We note that the multiplication of two linear transformation is in fact the composition of these transformations. The multiplicative identity is the identity transformation.

Definition 2.4.2

Let A and B be algebra over . An algebra homomorphism from A to B is a linear transformation ϕ : A → B such that ϕ(ab) = ϕ(a)ϕ(b) for all a, b ∈ A. An algebra isomorphism from A to B is a homomorphism which is bijective. Moreover, if ϕ : A → B is an isomorphism, then A and B are isomorphic algebras.

Definition 2.4.3

The function T from V into W is called invertible if there exists a function U from W into V such that UT is identity function on V and TU is identity function on W. If T is invertible, the function U is unique and is denoted by T−1. T is invertible if and only if

1.T is 1−1, that is T(α) = T(β) implies α = β, and

2.T is onto, that is, the range of T is all of W.

By the Definition of invertible linear transformation, we have that

Theorem 2.4.2

Let V and W be vector spaces over the field and let T be a linear transformation from V into W. If T is invertible, then the inverse function T−1

is a linear transformation from W onto V.

Moreover, let V and W be finite-dimensional vector spaces over the field such that dim V = dim W. If T is a linear transformation from V into W, then the following are equivalent:

1.T is invertible;

2.T is non-singular;

3.T is onto, that is, the range of T is W;

4.If {α_1, … αn} is a basis for V, then {T(α_1), … T(αn)} is a basis for W;

5.For any basis {β_1, … βn} for W, there exists some basis {α_1, … αn} for V such that T(αi) = βi for i = 1, … n.

Definition 2.4.4

If V and W are vector spaces over the field , any invertible linear transformation T : V → W is called an isomorphism of V onto W. If there exists an isomorphism of V onto W, we say that V is isomorphic to W.

Definition 2.4.5

A group consists of the following:

1.A set G;

2.A rule or operation which associates with each pair of elements x, y ∈ G an element xy ∈ G in such a way that

a.x(yz) = (xy)z, for all x, y, z ∈ G (associativity);

b.there is an element e ∈ G such that ex = xe = x for every x ∈ G;

c.to each element x ∈ G there corresponds an element x−1 ∈ G such that xx−1 = x−1 x = e.

A group is called commutative if it satisfies the condition xy = yx for each x, y ∈ G.

We see that the collection of invertible linear transformations in (V, V), denoted as GL(V) forms a group, called general linear group on V. Moreover, since any element of (V, V), is isomorphic to a square matrix, the invertible linear transformation corresponds an invertible square matrix. The general linear group is a non-commutative group.

2.5Applications of Linear Transformation

All linear transformations are formed by combining simple geometric processes such as rotation, stretching, shrinking, shearing, and projection. As a consequence linear transformations are important in computer graphics. For instance, to represent a 3-dimensional object on a 2-dimensional computer screen, or to look at the object from various angles, projections and rotations come into play. In addition, motion effects can be achieved by simply shrinking an object to make it appear to move away from the viewer. Linear transformations and matrices are also an important tool if we want to control the motion of a robot.

This geometric point of view is obviously useful when we want to model the motion or changes in shape of an object moving in the plane or in 3-space. However, this can be extended to higher dimensions as well. The idea that any matrix can be thought of as the product of simpler matrices that correspond to higher-dimensional versions of rotation, reflection, projection, shearing, dilation, and contraction is of enormous importance to both pure and applied mathematicians.

2.5.1 Affine Transformations

In mathematics, affine geometry is Euclidean geometry without the metric notions of distance and angle. Playfair’s axiom (i.e., given a line L and a point P not on L, there is exactly one line parallel to L that passes through P) is fundamental in affine geometry. Affine geometry is developed on the basis of linear algebra. An affine space is a set of points equipped with a set of transformations called affine transformations, functions between affine spaces that preserve points, straight lines, and parallelism of lines.

Definition 2.5.1

Let X and Y be two affine spaces, then every affine transformation T : X → Y is of the form T(x) = Mx + b, where M is a linear transformation on X and b is a vector in Y.

An affine transformation does not necessarily preserve angles between lines or distances between points, though it does preserve ratios of distances between points lying on a straight line. Examples of affine transformations include translation, scaling, similarity transformation, reflection, rotation, shear mapping, and compositions of them in any combination and sequence. Unlike a linear transformation, an affine transformation need not preserve the zero point in a linear space. Thus, every linear transformation is affine, but not every affine transformation is linear.

In affine 3-space, a rigid motion, a transformation consisting of rotations and translations, is a transformation that when acting on any point p, generates a transformed point T(p) = Rp + t, where R is a 3 × 3 orthogonal matrix (i.e., the columns of the matrix are pairwise orthogonal, and each column is of unit length) representing the rotation with det(R) = 1, and t ∈ 3 a 3-dimensional translation vector.

For any rotation matrix R acting on n, RT = R−1, the rotation is an orthogonal matrix, and thus det R = ±1. Since the inverse of a rotation matrix is its transpose, also a rotation matrix. The product of two rotation matrices is a rotation matrix. Multiplication of n × n rotation matrices is not commutative for n > 2. Moreover, any identity matrix is a rotation matrix, and that matrix multiplication is associative. Thus, the rotation matrices for n > 2 form a special non-commutative orthogonal group, and denoted by SO(n), the group of n × n rotation matrices. Multiplication of rotation matrices corresponds to composition of rotations, applied in left-to-right order of their corresponding matrices.

Convert all points in 3-space to homogeneous coordinates:

The following matrices constitute the basic affine transformations in 3-space, expressed in homogeneous form:

1.Translate:

2.Scale:

3.Shear:

4.Three basic rotations in 3-space:

Rotation about the x-axis:

Rotation about the y-axis:

Rotation about the z-axis:

The rotations determine an amount of rotation about each of the individual axes of the coordinate system. The angles θx, θy and θz of rotation about the three axes are called the Euler angles. An off axis rotation can be achieved by combining combining Euler angle rotations via matrix multiplication. Since affine translformations are not commutative, the order of rotation affects the end result.

2.5.2Projective Transformations

The idea of a projective space relates to perspective, that is, the way a camera projects a 3D scene to a 2D image. All points that lie on a projection line through the entrance pupil of the camera are projected onto a common image point. Hence, the vector space is 3 with the origin being the camera entrance pupil, and the projective space corresponds to the image points.

The real n-dimensional projective space or projective n-space, is the set of the lines in passing through the origin, or

where (x_0, … xn) ~ (y_0, … yn) if (x_0, … xn) = λ(y_0, … yn) for some λ ≠ 0.

The elements of the projective space are commonly called points. The projective coordinates of a point x = [x_0 : … : xn] where (x_0, … xn) is any element of the corresponding equivalence class. The colons and the brackets emphasizing that the right-hand side is an equivalence class, which is defined up to the multiplication by a non-zero constant.

Geometric objects, such as points, lines, or planes, can be given a representation as elements in projective spaces based on homogeneous coordinates. Transformations within and between projective spaces are called projectivities and are the fundamental concern of projective geometry. Certain properties such as collinearity, concurrency, tangency, and incidence remain invariant under the action of a projectivity, and they are referred to as projective invariants.

A projective transformation from to is an invertible (n + 1) × (n + 1) matrix P. P acts on the projective n-space as the following:

where P is an invertible (n + 1) × (n + 1) matrix.

x and y are homogeneous coordinates for a point in a projective n-space.

Lemma Let P be a real projective transformation represented by a nonsingular (n + 1) × (n + 1) matrix Then the following assertions are equivalent:

1.The restriction of P to n = {[x_0 : … : xn−1 : 1] ∈ } is an affine transformation;

2.P0,n … P(n−1),n = 0;

3.P fixes the hyper-plane xn = 0 at infinity.

Proof: 1 ⇔ 2: If

If P induces an affine transformation, then we must have yn ≠ 0 for all xi ∈ , and this implies P_0,n = … = P(n−1),n = 0. Since det P ≠ 0, we must have Pn,n ≠ 0. Thus, by rescaling, Pn,n = 1.

Conversely, if P_0,n = … = P(n−1),n = 0 and Pn, n = 1, then

and this is an affine transformation.

2 ⇔ 3: If P0,n = … =P(n−1),n = 0, then

hence the hyper-plane xn = 0 is preserved.

Conversely, if

then P0,n = … = P(n−1),n = 0.

Proposition Let Pi = [xi : yi : Zi], for i = 1, 2, 3, 4 be four points in the projective plane, no three of which are collinear. Then there is a unique projective transformation sending the standard frame, namely [1 : 0 : 0], [0 : 1 : 0], [0 : 0 : 1] and [1 : 1 : 1] to P_1, P_2, P_3 and P_4.

Proof: Since Pi for i = 1, 2, 3 are non-collinear, we must have that

In projective space

[1 : 0 : 0] = [a_1 : 0 : 0], [0 : 1 : 0] = [0 : a_2 : 0], [0 : 0 : 1] = [0 : 0 : a_3], ai ≠ 0. Hence, there exists a 3 × 3 matrix P such that

Hence P is an invertible matrix. Hence this is a projective transformation.

Now P_4 will be the image of [1 : 1 : 1] if and only if P_4 = P[1, 1, 1]T.

Hence, One can check P_4 is linearly independent from any two of P_1, P_2, P_3.

Corollary: Let Pi and Qi for i = 1, 2, 3, 4 be two sets of four points in the projective plane such that no three Pi and no three Qi are collinear. Then there is a projective transformation sending Pi to Qi for i = 1, 2, 3, 4.

Proof. Let P denote the projective transformation that sends the standard frame to the Pi, and let Q denote the transformation that does the same with the Qi. Then QP−1 is the projective transformation sending Pi to Qi.

Proposition An invertible projective transformation preserves the degree of curves in projective space.

Proof: An invertible projective transformation maps a monomial xiyjzk of degree m = i + j + k either to 0 or to another homogeneous polynomial of degree m. We claim the case that the image being zero is not possible. Let P be a projective transformation, and f(x, y, z) is a curve of degree m. If T(f(x, y, z)) = 0, then f(x, y, z) = T−1(0) = 0 since T is invertible. It is not possible. Hence, the projective transformations preserve the degree of curves.

2.6Exerc ises

1.Let V be a vector space and f : V → R be a linear map. If z ∈ V is not in the null space of f, show that every x ∈ V can be decomposed uniquely as x = v + cz, where v is in the null space of f and c is a scalar.

2.Let V = 2 and W = 3. Define L : V → W by L(x, y) = (x − y, x, y).Let F = {(1, 1), (−1, 1)}, G = {(1, 0, 1), (0, 1, 1), (1, 1, 0)}. (a) Find the matrix representation of L using the standard bases in both V and W. (b) Find the matrix representation of L using the standard basis in V and the basis G in W. (c) Find the matrix representation of L using the basis F in 2 and the standard basis in 3. (d) Find the matrix representation of L using the bases F and G.

Remark Here we include a solution provided by Andrew Crutcher, a student of this class. We can utilize the following code to find the matrix representation of an arbitrary T from B_1 to B_2 or With this code we can take care of parts a, b, c, and d easily.

[style=pyStyle]

def matrix_rep(T,B1,B2):

A = matrix.zero(QQ,T.nrows(),T.ncols())

areBasis = B1.is_invertible() and B2.is_invertible()

if areBasis and T.ncols() == B1.ncols() and

T.nrows() == B2.nrows():

B2inv = B2.inverse()

for colNum in xrange(0,T.ncols()):

A.set_column(colNum,B2inv*T*B1.column(colNum))

return A

L=matrix(QQ,3,2, [1,-1,1,0,0,1])

F=matrix(QQ,2,2, [1,1,-1,1])

G=matrix(QQ,3,3, [1,0,1,0,1,1,1,1,0])

E22=matrix.identity(2)

E33=matrix.identity(3)

print("a) L from standard to standard")

matrix_rep(L,E22,E33)

print("b) L from standard to G")

matrix_rep(L,E22,G)

print("c) L from F to standard")

matrix_rep(L,F,E33)

print("d) L from F to G")

matrix_rep(L,F,G)

This results in the following output.

[style=pyStyle]

(a) L from standard to standard

[ 1 -1]

[ 1  0]

[ 0 1]

(b) L from standard to G

[ 0  0]

[ 0  1]

[ 1 -1]

(c) L from F to standard

[ 2 0]

[ 1 1]

[-1 1]

(d) L from F to G

[ 0 0]

[-1 1]

[ 2 0]

3.Let B = {b_1, …, bn} be a basis for n and let T : n → n be defined as follows.

First show that T is a linear transformation. Next show that the matrix of T with respect to this basis, [T]B is

If E = {e_1, … en} be the standard basis for n. Show that

4.If V be the vector space of 2 × 2 matrices and KM = If T: V → V be a linear transformation defined by T(A) = AM − MA for every A ∈ V. Then what is the dimension of kernel of T?

5.Let P be the vector space of all polynomial functions on with real coefficients. Define linear transformations T, D : P → P by (Dp)(x) = p′(x) and (Tp)(x) = x^2p(x) for all x ∈ . Find matrix representations for the linear transformations D + T, DT, and TD (with respect to the usual basis {1; x; x^2} for the space of polynomials of degree two or less).

6.Let A is an n × n matrix over of rank k. Define

and

Show that L and R are linear spaces and compute their dimensions.

7.Find the null space of the matrix

8.Let p_1 = x^3 + x + 1, p_2 = 2x^3 − x^2, p_3 = x^2 + x + 1, q_1 = x^3 − 1, q_2 = x^3 − x^2 + 1, q_3 = x^3 + x be polynomials. Is it true that Span {p_1, p_2, p_3} = Span{q_1, q_2, q_3}?

9.Find the kernel of the linear transformation from 4 → 2 with the following matrix: Is the range of the transformation the same as 2?

10.What is the dimension of the subspace of 4 spanned by the column vectors

Also find the kernel of the linear transformation from 4 → 4 with the matrix formed by the above column vectors.

11.Is the function T : M2×2 → P_2 defined by

a linear transformation?

12.Compute the dimension of the range of T where T : 3 → P_2 is the linear transformation

13.Let S = {e_1, e_2} denote the standard ordered basis for 2 and let B = {x − 1; x + 2} be a basis for P_1. Let T : 2 → P_1 be the linear a transformation = ax + 2(a + b). Find [T]S→B.

14.Is the linear transformation T : P_2 → 3 given by T(ax^2 + bx + c) = an isomorphism of P_2 onto 3?

15.Let A be a linear transformation from 6 → 4 find the dimensions of the kernel and range of A, where

Also identify a basis for the column space and a basis for the null space.

16.Let f : → be defined by f(x) = 2x − 3. Show f is one-to-one and onto; find an inverse map f−1.

17.Suppose a linear mapping F : V → U is one-to-one and onto. Show that the inverse mapping F^1 : U → V is also linear.

18.Consider the linear operator T on 3 defined by

Show T is invertible, find formulas for T−1, T^2, and T−2.

Remark Below, we include a solution provided by Andrew Crutcher via computer software. Note to show T is invertible all we have to do is show ker(T) = {0}.

Let

⇒ ker(T) = {0}

∴ T is invertible.

Knowing the matrix for T is allows us to utilize SAGE to calculate T−1, T^2, T−2

[style=pyStyle]

T = matrix(QQ,3,3,[2,0,0,4,-1,0,2,3,-1])

print("T"); T

print("T^-1"); T.inverse()

print("T^2"); (T)^2

print("T^-2"); (T.inverse())^2

This results in the following output.

[style=pyStyle]

T

[ 2 0  0]

[ 4 -1 0]

[ 2 3 -1]

T^-1

[1/2 0  0]

[ 2 -1  0]

[ 7 -3 -1]

T^2

[ 4  0 0]

[ 4  1 0]

[14 -6 1]

T^-2

[ 1/4  0 0]

[ -1   1 0]

[-19/2 6 1]

19.The set S = {e3t, te3t, t^2e3t} is a basis of a vector space V of functions f : → . Let D be the differential operator on V; that is, Df = df/dt. Find the matrix representation of D relative to the basis S.

20.Suppose that the x-axis and y-axis in the plane 2 are rotated counterclockwise 30° to yield new X-axis and Y-axis for the plane. Find (a) The unit vectors in the direction of the new X-axis and Y-axis. (b) The change-of-basis matrix P for the new coordinate system. (c) The new coordinates of the points A = (1, 3), B = (2, 5), and C = (a, b).

21.Let T : 3 → 2 be defined by T(x, y, z) = (2x + y − z, 3x − 2y + 4z). (a) Find the matrix A representing T relative to the bases S = {(1, 1, 1), (1, 1, 0), (1, 0, 0)}, and S′ = {(1, 3), (1, 4)}. (b) Verify that, for any v ∈ 3, A[v]S = [Tv]S′.

22.Determine whether or not each of the following linear maps is nonsingular. If not, find a non-zero vector v whose image is 0. (a) F : 2 → 2 defined by F(x, y) = (x − y, x + 2y). (b) G : 2 → 2 defined by G(x, y) = (2x + 4y, 3x + 6y).

C H A P T E R 3

LINEAR OPERATORS

3.1 Characteristic and Minimal Polynomials

Definition 3.1.1

Let T be a linear transformation represented by a matrix A. If there is a vector x in V ≠ 0 such that

then λ is called the eigenvalue of A with corresponding eigenvector x.

If A is a k × k square matrix A = (aij) with an eigenvalue λ, then the corresponding eigenvectors satisfy

As shown in Cramer’s rule, a linear system of homogenous equations has non-trivial solutions if and only if the determinant vanishes, so the condition for existence of the solutions is given by

This equation is known as the characteristic equation of A, and the left-hand side is known as the characteristic polynomial.

Therefore, we have the following theorem:

Theorem 3.1.1

Let T be a linear operator on a finite-dimensional space V and let c be a scalar. The following are equivalent:

(a)c is an eigenvalue of T;

(b)The operator (T − c) is singular;

(c)det(T − c) = 0.

Proof: The proof directly follows the definition. The scalar c is an eigenvalue of T if and only if Tv = cv for some non-zero vector v if and only if (T − c)v = 0 if and only if det(T − c) = 0, i.e., (T − c) is singular.

Lemma: Suppose T(v) = cv. If f is any polynomial, then (f(T))(v) = (f(c))(v).

Proof: Let f(x) = anxn + an−1xn−1 + … + a_1x + a_0. Then

Theorem 3.1.2

Every operator on a finite-dimensional, non-zero, complex vector space has an eigenvalue.

Proof: Suppose V is a complex vector space with dimension n > 0 and T a linear operator. Let 0 ≠ v ∈ V. Then

is not linearly independent, because dim V = n and we have n + 1 vectors. Thus there exist complex numbers ao, …, an, not all 0. Assume an ≠ 0, such that

In case an = 0, then go to the next highest non-zero ak, note that k ≥ 1. Make the ai’s the coefficients of a polynomial, which by the fundamental theorem of algebra has a factorization

where c is a non-zero complex number, each λi ∈ , and the equation holds for all x ∈ . We then have

Thus λ_1, …, λn are eigenvalues of T.

Moreover, we see that two matrices A, B are similar, then A = P−1BP for some invertible matrix P, then

Hence we conclude that similar matrices have the same characteristic polynomial.

The algebraic multiplicity μA(λi) of the eigenvalue is its multiplicity as a root of the characteristic polynomial, that is, the largest integer ki such that (λ − λi)ki divides evenly that polynomial.

Suppose a k × k matrix A has d, d ≤ k, distinct eigenvalues. Hence the characteristic polynomial of A factors into the product of k linear terms over with some terms potentially repeating, the characteristic polynomial can instead be written as the product d terms each corresponding to a distinct eigenvalue and raised to the power of the algebraic multiplicity,

The subspace generated by the eigenvectors corresponding to an eigenvalue λ is called an eigen-subspace associated with λ. The dimension of an eigen-subspace associated with an eigenvalue λ is called the geometric multiplicity of the eigenvalue λ, i.e. dim ker(λ − λ). It is a proven result that the geometric multiplicity is at most equal to the algebraic multiplicity of a particular eigenvalue.

Definition 3.1.2

Let T be a linear operator on the finite-dimensional space V. We say that T is diagonalizable if there is a basis for V each vector of which is a eigenvector of T.

The following corollary is an easy observation from the above definition.

Corollary: Let be a basis for a finite-dimensional vector space V such that diagonalize T. Then [T] has all eigenvalues on the main diagonal. Moreover, the number of repetition of an eigenvalue is the algebraic multiplicity of that eigenvalue.

Definition 3.1.3

The companion matrix of the monic polynomial

is the square matrix defined as

With this convention, with standard basis = {e_1, …, en}, one has

and e_1 generates the vector space V as a [CT]-module over a field , and we call ei are CT cycles basis vectors.

A Vandermonde matrix is a m × n matrix

or

The determinant of a square Vandermonde matrix can be expressed as

This is called the Vandermonde determinant or Vandermonde polynomial. If all the numbers ai are distinct, then it is non-zero.

As it turns out, the roots of the characteristic polynomial of a companion matrix C, i.e., det(C − x) = 0 are precisely the roots of the polynomial p(x). The eigenvector corresponding to the eigenvalue λj is Vandermonde vector Then, if αj is a root of p(x), and v is a Vandermonde vector such that then

Definition 3.1.4

Let T : V → V be a linear operator on a finite-dimensional vector space over the field . We shall denote by Tk the composition of T with itself k times, and for any polynomial

we set

and say that p is monic if ak = 1. A minimal polynomial μT of the linear operator T is a monic polynomial of minimal degree such that μT(T) = 0.

Let us recall that a polynomial ring [x] is the subspace ∞ spanned by the vectors 1, x, x^2, …. An element of [x] is called a polynomial over . Let be a field. An ideal in [x] is a subspace M ⊆ [x] such that fg ∈ M when-ever f ∈ [x], and g ∈ M. The set M = d[x], all multiples df of d by arbitrary f ∈ [x] is an ideal. The ideal M is called the principal ideal generated by d. But if then M is generated by d_1, …, dn.

If T is a linear operator on a finite-dimensional vector space V over the field . Then the minimal polynomial for T is in fact the unique monic generator of the ideal of polynomials over which annihilate T. Moreover, the characteristic and minimal polynomial for T have the same roots, except possibly for multiplicity. Hence we can summarize as below remark:

Remark: Let T : V → V be a linear operator on a finite-dimensional vector space V over the field . Then:

(a)the minimal polynomial μT of T exists, has degree at most n = dim V, and is unique;

(b)if p ∈ [t] is such that p(T) = 0, then there is some q ∈ [t] such that p = qμT.

The minimal polynomial can be explicitly computed. Take v ∈ V, and let d be the minimal non-negative integer such that the elements in {v, T(v), …, Td(v)} are linearly dependent. Clearly d ≤ n; d = 0 if and only if v = 0, and d = 1 if and only if v is an eigenvector of T. Since elements in {v, T(v), …, Td(v)} are linearly dependent, there exist a_0, …, ad−1 ∈ such that

Note that we can assume the coefficient of Td(v) is 1 because of the minimality of d, and then set

By definition, v ∈ ker μT,v(T); more precisely, μT,v(T) is the monic polynomial p(T) of least degree such that v ∈ ker p(T). Now, if p ∈ [t] is any common multiple of μT,v1 and μT,v2 for any two vectors v_1 and v_2, then both v_1 and v_2 belong to ker p(T). More generally, if = {v_1, …, vn} is a basis of V, and p is any common multiple of μT,v1, … ,μT,vn, then ⊂ ker p(T), and p(T) = 0. We have the following result:

Theorem 3.1.3

Let T : V → V be a linear operator on a finite-dimensional vector space V over the field . Let = {v_1, …, vn} be a basis for V. Then μT is the least common multiple of μT,v1, … ,μT,vn.

Proof: Let p ∈ [t] be the least common multiple of μT,v1, … ,μT,vn. Since p(T) = 0, and so μT | p. Conversely, for j = 1, …, n, let

Then

and the minimality of the degree of μt,vj forces rj = 0. Since every μt,vj | μT, their least common multiple p | μT, and hence p = μT.

In linear algebra, the Cayley-Hamilton theorem states that every square matrix over a commutative ring satisfies its own characteristic equation. When the ring is a field, the Cayley-Hamilton theorem is equivalent to the statement that the minimal polynomial of a square matrix divides its characteristic polynomial. Below we only state the theorem:

Theorem 3.1.4

(Cayley-Hamilton). Let T be a linear operator on a finite-dimensional vector space V. If f is the characteristic polynomial for T, then f(T) = 0; i.e., the minimal polynomial divides the characteristic polynomial. (Note, if the characteristic polynomial is ci distinct, di ≥ 1, then the minimal polynomial

3.2 Eigenspaces and Diagonalizability

For a given linear operator T : V → V, a non-zero vector v and a constant scalar c are called an eigenvector and its eigenvalue, respectively, when Tv = cv. For a given eigenvalue c, the set of all v such that Tv = cv is called the c-eigenspace. The set of all eigenvalues for an operator is called its spectrum. When the operator T is described by a matrix A, then we’ll associate the eigenvectors, eigenvalues, eigenspaces, and spectrum to A as well.

Theorem 3.2.1

Each c-eigenspace is a subspace of V.

Proof: Suppose that x and y are c-eigenvectors and k is a scalar. Then

Therefore x + ky is also a c-eigenvector. Thus, the set of c-eigenvectors forms a subspace.

Definition 3.2.1

Let V be a vector space and T a linear operator on V. If W is a subspace of V, we say that W is invariant under T if for each vector w ∈ W, the vector T(w) ∈ W. That is T(W) ⊆ W.

Lemma: Let c_1 and c_2 be two distinct eigenvalues of a linear operator T : V → V. Let Wi be the space of eigenvectors associated with the eigenvalue ci. Then

(a)Wi is a subspace of V and it is invariant under T;

(b)W_1 ∩ W_2 = {0}.

Proof: First we note that Wi = ker(T − ci), hence it is a subspace. To prove this is invariant, let v, w ∈ Wi, then T(av + bw) = aT(v) + bT(w) = ac_1v + bc_1w = c_1(av + bw). Hence this is invariant under T.

To show the second claim, let v ∈ W_1 ∩ W_2, then

T(v) = c_1v, and T(v) = c_2v, ⇒ c_1v = c_2v ⇒ (c_1 − c_2)v = 0, Þ v = 0, since c_1 = c_2.

The above result shows that several eigenvectors correspond to a single eigenvalue, and an eigenvector cannot correspond to two (or more) distinct eigenvalues.

Hence, we have the following result:

Lemma 3.2.1: Let T : V → V be a linear operator on a finite-dimensional vector space V over the field . If T has distinct eigenvalues, then any eigenvectors corresponding to these eigenvalues respectively are linearly independent.

Proof: Assume the opposite, that is for some ai ≠ 0, where vi is the eigenvector corresponding to eigenvalue ci. Without loss of generality, let us assume that v_1, …, vn−1 are linearly independent, and

Applying the linear operator T, we have

and hence

Since vi are linearly independent, we must have ai(ci − cn) = 0 for i = 1, …, n − 1. Since not all ai’s are zero, ci − cn for some i, a contradiction since eigenvalues are distinct.

Corollary: Suppose V is finite-dimensional. Then each operator on V has at most dim V distinct eigenvalues.

Proof: Let T be a linear operator on V. Suppose c_1, …, cn are distinct eigenvalues of T. Let v_1, …,vn be corresponding eigenvectors. Then Lemma 3.2.1 implies that the list v_1, …, vn is linearly independent. Thus n ≤ dim V as desired.

Recall that the matrix of a linear map from one vector space to another vector space dependeds on a choice of a basis of each of the two vector spaces. Now that we are studying operators, which map a vector space to itself, the emphasis is on using only one basis. In this section, we consider the matrices of operators are square arrays, rather than the more general rectangular arrays that we considered earlier for linear maps.

A central goal of linear algebra is to show that given a linear operator T, there exists a basis of V with respect to which T has a reasonably simple matrix. To make this vague formulation a bit more precise, we might try to choose a basis of V such that the matrix representation of the linear operator has many zeros as possible.

Recall a matrix is called upper triangular if all the entries below the diagonal equal 0. Typically we represent an upper-triangular matrix in the form

Upper triangular matrices can be considered reasonably simple for n 0; almost half of its entries in an n × n upper triangular matrix are 0.

Theorem 3.2.2

Suppose T is a linear operator, and v_1, …, vn is a basis for V. Then the following are equivalent:

1.The matrix of T with respect to v_1, …, vn is upper triangular;

2.Tvj ∈ Span(v_1, …, vj) for each j ∈ {1, …, n};

3.Span(v_1, …, vj) is invariant under T for each j ∈ {1, …, n}.

Proof: The equivalence of the first two statements follows easily from the definitions.

Obviously (3) implies (2). Hence to complete the proof, we need only prove that (2) implies (3).

Thus suppose (2) holds. Fix j ∈ {1, …, n}. From (2), we know that

Thus if v is a linear combination of v_1, …, vj, then Tv ∈ Span(v_1, …, vj). Hence Span(v_1, …, vj) is invariant under T, completing the proof.

It is easy to see that the matrix of an operator in any basis for V is

If we now look for the coordinates of an eigenvector corresponding to the eigenvalue λ in basis , then

Theorem 3.2.3

Suppose V is a finite-dimensional complex vector space and T is a linear operator on V. Then T has an upper-triangular matrix with respect to some basis of V.

Proof: We will use induction on the dimension of V. Clearly the desired result holds if dim V = 1.

Suppose now that dim V > 1 and the desired result holds for all complex vector spaces whose dimension is less than dim V. Let c be any eigenvalue of T. Let

Because (T − c) is not surjective dim W < dim V. Furthermore, W is invariant under T, since for any v ∈ W,

Thus T is an operator on W. By our induction hypothesis, there is a basis v_1, …, vm of W with respect to which T has an upper-triangular matrix. Thus for each j we have

Then, we can extend v_1, …, vm to a basis v_1, …, vn of V. For k = m + 1, we have

Since the basis for range of T − c is {v_1, …,vm}, we must have that Tvm+1 ∈ Span(v_1, …,vm,vm+1). Repeating this process, the equation above shows that Tvk ∈ Span(v_1, …, vk) for all k = m + 1, …, n. Hence T has an upper triangular matrix with respect to the basis v_1, …, vn of V.

Theorem 3.2.4

Suppose T is a linear operator has an upper-triangular matrix with respect to some basis of V. Then the eigenvalues of T are precisely the entries on the diagonal of that upper-triangular matrix.

Proof: Suppose = {v_1, …, vn} is a basis for V with respect to which T has an upper-triangular matrix

Then

Hence [T − λ] is not invertible if and only if λ equals one of the numbers λi for i = 1, …, n. Thus [T − λ] is not invertible if and only if the kernel of (T − λ) is non-trivial. Therefore, there exists a non-zero vector v such that (T − λ)v = 0, that is, Tv = λv. Thus A is an eigenvalue of T if and only if it equals one of the numbers λi for i = 1, …, n.

We will see the relationship between the eigenvalues and the invariant subspaces. First, we will introduce the concept of vector space decomposition.

Definition 3.2.2

Let W_1, …, Wk be subspaces of the vector space V. We say that W_1, …, Wk are independent if

w_1 + … + wk = 0, wi ∈ Wi ⇒ wi = 0, ∀i.

Remark: Note this says that the

1.

2. Wj ∩ (W1 + … + Wr) = {0} for all r < j, and for all j;

3. Each w = w_1 + … + wk with wi ∈ Wi;

4. The expression w = w1 + … + wk with wi ∈ Wi is unique.

Suppose W_1, …, Wk are independent subspaces of V where and i is an ordered basis for Wi for 1 ≤ i ≤ k. Then = (1, …, k) is an ordered basis for V. Let T be a linear operator on V, and Ti = T|Wi. Then Ti is a linear operator on Wi. If A = [T] and Ai = [Ti]i, then A has the block form

Thus, A is a direct sum of the matrices A_1, …, Ak.

The following lemma is a direct consequence from the definition of independent vector subspaces.

Lemma 3.2.2: Let V be a finite-dimensional vector space. Let W_1, …, Wk be subspaces of V, and W = W_1 + … + Wk. The following are equivalent:

1.Wi are independent;

2.For each j, 2 ≤ j ≤ k, we have Wj ∩ (W1 + … + Wj−1) = {0}.

3.If i is an ordered basis for Wi, 1 ≤ i ≤ k, then the sequence = (1, …, k) is an ordered basis for W.

Definition 3.2.3

If any of the conditions of the above lemma holds, then the sum W = W_1+…+Wk is direct or W is the direct sum of W_1, …, Wk, and we write

Lemma 3.2.3: Let T be a linear operator on a finite-dimensional space V. Let c_1, …, ck be the distinct eigenvalues of T, and let Wj be the space of eigenvectors associated with the eigenvalue cj. If W = W_1 + … + Wk, then

In fact, if Bi is an ordered basis for Wi, then = (1, …, k) is an ordered basis for W.

Proof: Since Wi ∩ Wj = {0} for i ≠ j, W_1, …, Wk are independent subspaces. Hence by definition, W is the direct sum of W_1, …, Wk. Therefore,

W = W_1 ⊕ W_2 ⊕ … ⊕ Wk, ⇒ dim W = dim W_1 + … + dim Wk.

We can summarize that:

Theorem 3.2.5

Let T be a linear operator on a finite-dimensional space V. Let c_1, …, ck be distinct eigenvalues of T and let Wj be the null space of (T − cj). The following are equivalent:

1.T is diagonalizable;

2.The characteristic polynomial for T is f = (x − c_1)dl … (x − ck)dk, and dim Wi = dj, for i = 1, …, k.

3.W_1 +…+ Wk = W_1 ⊕ …⊕ Wk = V, and dim W = dim W_1 +…+dim Wk.

Proof: (1 ⇒ 3) Assume that T is diagonalizable. Then we can find a basis for V consisting of eigenvectors for T. Each of these vectors is associated with a particular eigenvalue, so write c_1, … ,ck for the distinct ones. We can then group together the elements of associated with cj, span them, and call the resulting subspace Wj. It follows then that

(3 ⇒ 2) Now assume that 3 holds. Then build a basis i of size ni of each Wi. Since the ci’s are eigenvalues, the i’s consist of eigenvectors for eigenvalue ci and ni > 1 for all i. Now, set = (1, …, k) is a basis for V and [T] is a diagonal matrix with distinct entries c_1, …, ck, with each ci repeated ni times. By computing the characteristic polynomial of the matrix [T], we find that item 2 holds.

(2 ⇒ 1) Now if 2 holds, then d_1 + … + dk = dim V, because the characteristic polynomial of [T] equals dim V. Therefore,

Because each ci is a root of the characteristic polynomial, it is an eigenvalue and therefore has an eigenvector. This means each dim Wi ≥ 1. Let i be a basis for Wi. As the ci’s are distinct, the Wi’s are independent subspaces, and so

This means = (1, …, k) is a basis for W_1 ⊕ … ⊕ Wk. Since it has size of dim V, it is in fact a basis for V. But each vector of is an eigenvector for T so T is diagonalizable.

Now, let us recall the minimal polynomial μT(x) of T, and factor it com-pletely into irreducible factors, to get We then consider the linear transformations (pi(T))ri, and their null spaces Vi. Each Vi is T-invariant, since if v ∈ Vi, then T(v) ∈ Vi. To see this, we note that (pi(T))ri(v) = 0 since v ∈ Vi where Vi is the null space of (pi(T))ri. Now we check (pi(T))ri(Tv) = T((pi(T))ri(v)) = T(0) = 0. Thus Tv ∈ Vi.

Theorem 3.2.6

Let the minimal polynomial of T be where pi(x) is irreducible for i = 1, …, k, and Vi is the null space of linear transformations (pi(T))ri. Then V = V_1 ⊕ … ⊕ Vk, is a direct sum of T-invariant subspaces.

Proof: Let qi(x) = μT(x)/pi(x)ri, so that qi(x) contains all but one of the irreducible factors of μT(x). Note that if i ≠ j, then μT(x) |qi(x)qj(x). Since q_1(x), …,qk(x) are relatively prime, there must exist polynomials a_1(x), …, ak(x) such that

Let Ei = αi(T)qi(T). Then For i ≠ j, EiEj = μT(T)q(T) = , i.e., zero operator, for some polynomial q(x). Thus

We only need to show that EiV = Vi for all i. First show EiV ⊆ Vi. Let v ∈ EiV. Then v = (ai(T)qi(T))(w), for some w ∈ V, so

Thus, EiV ⊆ Vi.

Now we show Vi ⊆ EiV. Let v ∈ V. Then (pi(T)ri)(v) = 0, and so for all i, j ≠ i, (qj(T))(v) = 0, since qj(T) has pi(T)ri as a factor. Thus Ejv = 0 for all i, j ≠ i. But

so

Thus Vi ⊆ EiV. Therefore, Vi = EiV, and V = V_1 + … + Vk.

Now, we will show that Vi ∩ Vj = {0}. Without loss of generality, we will show the case for i = 1, j ≠ 1. For this, we will show that E_1 : V_1 → V_1 is a bijection. Let v_1 ∈ V_1. Thus, there exists a v ∈ V such that E_1v = v_1. Since v = u_1 + w for some u_1 ∈ V_1 and w ∈ V_2 + … + Vk. So v_1 = E_1v = E_1(u_1 + w) = E_1u_1 + E_1w = E_1u_1 + 0 = E1u_1. Therefore, E_1 : V_1 → V_1 is onto. Since dim V_1 is finite, E_1 is a bijection. Therefore, each Ei is a bijection.

Now, let 0 ≠ v ∈ Vi ⊆ Vj for i ≠ j. EjEiv = 0. However, Ei is a bijection, u = Eiv ≠ 0. Since Ej is a bijection, 0 ≠ Eju = EjEiv = 0, a contradiction. Thus, Vi ∩ Vj = {0}. Thus,

Theorem 3.2.7

Let T : V → V be a linear operator on a finite-dimensional vector space V over the field . Then T is diagonalizable if and only if μT is of the form

where c_1, …, ck be the distinct eigenvalues of T.

Proof: If T is diagonalizable, it has a basis formed by eigenvectors. Let b be an eigenvector corresponding to an eigenvalue ci. Then Tb − cib = 0. So x − ci is a factor of the minimal polynomial, which can be computed just one linear factor for each of the distinct eigenvalue on the diagonal of T.

Conversely, let the minimal polynomial of T be Then V is a direct sum of the null spaces of (T − ci), which shows that there exists a basis for V consisting of eigenvectors, and so T is diagonalizable.

Let A be a square n × n matrix with n linearly independent eigenvectors, v_1, …, vn. Then A can be factorized, or has an eigen-decomposition as

where Q is the square n × n matrix whose i-th column is the eigenvector vi of A and A is the diagonal matrix whose diagonal elements are the corresponding eigenvalues, i.e., An = λi. Note that only diagonalizable matrices can be factorized in this way. Essentially, A is a linear operator on n with respect to the standard basis, and Q is a change of bases matrix from basis formed by eigenvectors to standard basis.

3.3 Jordan Canonical Form

We recall that a subspace W of V is called T-invariant if T(v) ⊆ W for all v ∈ W. A special case occurs with eigenvectors: the vector v is an eigenvector of T if and only if the 1-dimensional subspace it determines is a T-invariant subspace. Lets use these ideas in talking about diagonalization. Instead of saying that T can be diagonalized if and only if there is a basis for V consisting of eigenvectors of T, we can now say that T can be diagonalized if and only if V can be written as a direct sum of 1-dimensional T-invariant subspaces. It is this statement that can be generalized.

For a diagonalizable transformation, we have a very nice form. However it is not always true that a transformation is diagonalizable. For example, it may be that the roots of the characteristic polynomial are not in the field. Sometimes, even if the roots are in the field, they may not have multiplicities equal to the dimensions of the eigenspaces. So we look for a more general form. Instead of looking for a diagonal form, we look for a block diagonal form.

When the subspace W is invariant under the operator T, then T induces a linear operator TW on the space W. The linear operator TW is defined by TW(α) = T(α) for α ∈ W. Note TW ≠ T since the domain and T and Tw are different. When V is finite-dimensional, the invariance of W under T has a simple matrix interpretation. Suppose we choose an ordered basis ′ = {α_1, …, αn} for V such that ′ = {α_1, …, αr} is an ordered basis for W(r = dim W ≤ n). Let A = [T] so that

Since W is invariant under T, the vector Tαj, ∈ W for all j ≤ r. This means

This means that

Thus A is a block matrix

B is r × r matrix, C is r × (n − r) matrix and D is (n − r) × (n − r) matrix. B is the matrix of the induced operator TW in the ordered basis ′.

Definition 3.3.1

A Jordan normal form or Jordan canonical form of a linear operator J on a finite-dimensional vector space is an upper triangular matrix of block diagonal matrices Ji

where each block Ji, namely Jordan block of A, is a square matrix of the form

In general, Jordan canonical form must be in block diagonal form, where each block has a fixed scalar on the main diagonal, and 1’s or 0’s on the superdiagonal. These blocks are called the primary blocks. The scalars for different primary blocks must be distinct. Each primary block must be made up of secondary blocks with a scalar on the main diagonal and only 1’s on the superdiagonal (if a secondary block is of size 1 × 1, then it contains the scalar only). These blocks must be in order of decreasing size (moving down the main diagonal).

Definition 3.3.2

Let W_1 ⊆ W_2 be subspaces of V. Let be a basis for W_1. Any set ′ of vectors such that ∪ ′ is a basis for W_2 is called a complementary basis to W_1 in W_2.

Lemma 3.3.1: Let T : V → V be a linear transformation. Let {v_1, …, vk} be a complementary basis to N(Tm) in N(Tm+1), i.e., the null space of Tm in the null space of Tm+1. Then {T(v_1), …, T(vk)} is part of a complementary basis to N(Tm−1) in N(Tm).

Proof: Since vi ∈ N(Tm+1), we have Tm+1(vi) = 0, so Tm(T(vi)) = 0, and therefore T(vi) ∈ N(Tm). Also, since vi is in the complementary basis to N(Tm) in N(Tm+1), Tm(vi) ≠ 0.

We want to show that for each i = 1, …, k, T(vi) ∈ N(Tm−1). Assume the opposite, i.e., Tm−1(T(vi)) = 0 for some i. But then Tm(vi) = Tm−1(T(vi)) = 0 which is a contradiction.

Now, we will show that {T(v_1), …,T(vk)} are linearly independent. Suppose the

then

Hence c_1v_1 + … + ckvk ∈ N(Tm). Since {v_1, …, vk} form a complementary basis to N(Tm) in N(Tm+1), csv_1 + … + ckvk = 0. But this implies that ci = 0 for all i since {v_1, …, vk} is a part of basis for N(Tm+1), thus linearly independent. This shows that {T(v_1), …, T(vk)} are linearly independent, and also linearly independent of any vectors in N(Tm−1), so they are part of a complementary basis to N(Tm−1) in N(Tm).

Theorem 3.3.1

(Jordan canonical form) If the characteristic polynomial of T is a product of linear factors, then it is possible to find a matrix representation for T which has Jordan canonical form.

In particular, suppose that f(x) = (x − c_1)d1 … (x − ck)dk is the characteristic polynomial of T and suppose that μT(x) = (x − c_1)r1 … (x − ck)rk is the minimal polynomial of T. Then the matrix for T has primary blocks of size di × di corresponding to each eigenvalue ci, and in each primary block the largest secondary block has size ri × ri.

Proof: By the primary decomposition Theorem 3.2.6, we can obtain a block diagonal matrix, and then we can deal with each primary block separately. This reduces the proof to the case in which the characteristic polynomial is (x − c)d and the minimal polynomial is (x − c)r where 0 < r ≤ d.

Choose a complementary basis v_1, …, vk to N((T − c)r−1) in N((T − c)r). By the previous lemma, we have

are linearly independent.

Starting with we find additional vectors w_1, …, wt to complete a complementary basis to N(T − c)r−2 in N(T − c)r−i. Then continue this procedure until we have found a basis for N((T − c)r) (note, this is the eigenspace corresponding to the eigenvalue c). Then consider the ordered basis:

Note (T − c)r−1(v_1), (T − c)r−1(v_2), …, (T − c)r−1(vk) are eigenvectors for T corresponding to the eigenvalue c. But there may be more eigenvectors corresponding to the eigenvalue c, which we denoted by u_1, …, um. Finally, we write T = c + (T = c). Then,

Hence the matrix representation of T relative to the basis has the Jordan block form.

The following corollary follows directly from the proof of the above theorem.

Corollary 3.3.1: If a square matrix A has Jordan canonical form J, then A is similar to its Jordan canonical form, i.e., A = PJP−1 for some invertible matrix P. Note that the columns of P are the basis vectors we constructed, in the proof above.

Theorem 3.3.2

Let A and B be n × n matrices over the field of complex numbers. Then A and B are similar if and only if they have the same Jordan canonical form, up to the order of the eigenvalues.

Proof: The assumption that the matrices have complex entries guarantees that their characteristic polynomials can be factored completely, and so they can be put into Jordan canonical form.

If A and B are similar, then they represent the same linear transformation T. Therefore, A and B have the same characteristic polynomial, and the same minimal polynomial. Since the Jordan canonical form is constructed from the zeros of the characteristic polynomial of T, and the dimensions of the corresponding generalized eigenspaces, which are given by the minimal polynomial, therefore, the primary Jordan blocks are the same. However, we have no way to specify the order of the eigenvalues. Thus A and B have the same Jordan canonical form, except for the order of the eigenvalues.

Conversely, if A and B have the same Jordan canonical form JA and JB respectively, except for the order of the eigenvalues, then the matrices in Jordan canonical form are easily seen to be similar, i.e., JA ~ JB. By the previous corollary, A ~ JA ~ JB ~ B. Since similarity is an equivalence relation, it follows that A and B are similar.

Hence, in summary, suppose that T is a linear operator on V and that the characteristic polynomial for T can be factored as

where ci are distinct elements in , di ≥ 1.

Then the minimal polynomial of T is

If Wi is the null space of (T − ci)ri, then the primary decomposition says

and that the operator Ti = T|Wi has minimal polynomial (x − ci)ri. Let Ni be the linear operator on Wi defined by Ni = Ti − ci. Then Ni has minimal polynomial xri. On Wi, T acts like Ni + ci. Suppose, we choose a basis for the subspace Wi such that the matrix of Ti in this ordered basis will be the direct sum of matrices

The size of the matrices will decrease as one reads from left to write. A matrix of the form is called an elementary Jordan matrix with characteristic value c.

Let A = of matrices A_1, …, Ak, where each Ai is of the form

Where is an elementary Jordan matrix with characteristic value ci. The sizes of the matrices decrease as j increases. An n × n matrix A that satisfies the conditions above is said to be in Jordan form.

If B is an n × n matrix over the field , and if the characteristic polynomial of B factors completely over , then B is similar over to an n × n matrix A in Jordan form, and A is unique up to a rearrangement of the order of its characteristic values. We call A the Jordan form of B.

If A is a real matrix, its Jordan form can still be non-real since the eigenvalues may be complex numbers. We here give a real Jordan form for a matrix. Note that the complex roots always come as a pair of conjugate complex numbers. Let λk = αk + iβk and αk − iβk be a pair of complex conjugate eigenvalues. Let v = a + ib be an eigenvector of αk + iβk, then

Comparing the real part and imagery part of the two sides of this equation, Aa = αka − βkb and Ab = βka + αkb. We may represent the complex vector v = a + ib as a matrix [a b] where the first column represents the real part of v, and the second column the imaginary part of v. Thus, each complex vector v can be represented by a pair of two real vectors a and b. Writing this in matrix form, we have

For each pair of conjugate eigenvalues, we find a such pair of vectors. For the eigenvalue that has multiplicity greater than one, we can find the vectors using a process similar to the process used in Theorem 3.3.1. Note that all the vectors are real and the Jordan block for a complex eigenvalue α + iβ with multiplicity m is

3.4 Trace

Definition 3.4.1

If A ∈ Mn×n() is an n × n matrix over ,

then the trace of A is the sum of the diagonal entries of A, that is, trace(A) = a_11 + a_22 +…+ ann.

We have the following properties of the trace.

Theorem 3.4.1

Let A, B ∈ Mn×n(), and c ∈ . Then trace(cA) = ctrace(A), trace(A + B) = trace(A )+ trace(B), trace(AB) = trace(BA).

Proof: Let A = (aij, and B = (bij). Then

And

Corollary 3.4.1: If A is similar to B, then trace(A) = trace(B).

Proof: By definition, A is similar to B, then A = P−1BP, and

It is known that a square matrix A is always similar to its Jordan form, that is A = PJP−1 for some invertible matrix P. Given an eigenvalue λi, its geometric multiplicity is dim(ker(A − λi)), and it is the number of Jordan blocks corresponding to λi. The sum of the sizes of all Jordan blocks corresponding to the eigenvalue λi is its algebraic multiplicity. A is diagonalizable if and only if, for every eigenvalue λ of A, its geometric and algebraic multiplicities coincide.

With these properties,

3.5 Determinants

Recall definition of a rin g (Definition 1.1.1), we can see that Mn×n() is a non-commutative ring with identity over .

Definition 3.5.1

Let K be a commutative ring with identity, n a positive integer, and let D be a function which assigns to each n × n matrix A over K a scalar D(A) ∈ K. We say that D is n-linear if for each i, 1 ≤ i ≤ n, D is a linear function of the ith row when the other (n - 1) rows are held fixed. That is

Lemma 3.5.1: A linear combination of n-linear function is n-linear.

Definition 3.5.2

Let D be an n-linear function. We say D is alternating or alternate if A′ is a matrix obtained from A by interchanging two rows of A, then D(A′) = − D(A).

Note if D is alternate, then D(A) = 0 whenever two rows of A are equal.

Definition 3.5.3

Let K be a commutative ring with identity, and let n be a positive integer. Suppose D is a function from n × n matrices over K into K. We say that D is determinant function if D is n-linear, alternating, and D() = 1.

Recall, a permutation is a function that reorders the set of integers {1, …, n}. The value in the i-th position after the reordering σ is denoted by σi. The set of all such permutations (also known as the symmetric group on n elements) is denoted by Sn. For each permutation σ, sgn(σ) denotes the signature or sign of σ, a value that is +1 whenever the reordering given by a can be achieved by successively interchanging two entries an even number of times, and −1 whenever it can be achieved by an odd number of such interchanges. Below, we give the formal definition.

Definition 3.5.4

A sequence (k_1, …, kn) of positive integers not exceeding n, with the property that no two of the ki are equal, is called a permutation of degree n. The permutation is called even/odd if the number of transpositions (i.e., the interchange of two elements) used is either even or odd. The sign or signature of a permutation is

Under the operation of composition, the set of permutations of degree n is a group. This group is usually called the symmetric group of degree n.

Definition 3.5.5

Let K be a commutative ring with identity and let n be a positive integer. There is precisely one determinant function on the set of n × n matrices over K and it is the function det defined by

where the sum is computed over all permutations a of the set {1, 2, …, n}

Remark: Below are some properties of determinant.

1.det(n) = 1 where n is the n × n identity matrix.

2.det(AT) = det(A).

3.det(A−1) = = det(A−1) if A−1 exists.

4.For square matrices A, B of equal size,

5.det(cA) = cn det(A) for an n × n matrix and c ∈ K.

6.If A is a triangular matrix, i.e. aij = 0 for i > j (or, i < j), then

7.Consider an n × n matrix as n columns, the determinant is an n-linear function. Hence, the elementary column operation—replacing column Ci by Ci + αCj where α ∈ K, and all other columns are left unchanged, then the determinant of A is unchanged. (A similar result holds for rows.)

8.If in a matrix, any row or column is 0, then the determinant of that particular matrix is 0. (A similar result holds for rows.)

9.If some column can be expressed as a linear combination of the other columns, its determinant is 0. (A similar result holds for rows.)

10.Suppose that A is a matrix of size n × n over a field , then the following are equivalent.

—A is non-singular.

—A row-reduces to the identity matrix.

—The null space of A contains only the zero vector.

—The linear system Ax = b has a unique solution for every possible choice of b.

—The columns of A are a linearly independent set.

—A is invertible.

—The column space of A is n.

—The columns of A are a basis for n

—The rank of A is n.

—The nullity of A is zero.

—det(A) ≠ 0.

Definition 3.5.6

The i,j cofactor of a cofactor matrix C = (Cij), is a signed version of a minor Mij defined by

where Mij is the determinant of a submatrix of original matrix A deleting the i-th row and j-th column. We can use this in the computation of the determinant of a matrix A by expansion of the j-column

The n × n matrix adjA is the transpose of the matrix of cofactors of A, is called the classical adjoint of A.

One can write down the inverse of an invertible matrix by computing its cofactors by using Cramer’s rule.

Then the inverse of A is the transpose of the cofactor matrix times the reciprocal of the determinant of A:

Hence, we have the following theorem:

Theorem 3.5.1

Let A be an n × n matrix over K where K is a commutative ring with identity. Then A is invertible over K if and only if det A is invertible in K. When A is invertible, the unique inverse for A is

In particular, an n × n matrix over a field is invertible if and only if the determinant is different from zero.

3.6 Generalized Companion Matrix

Let p(t) be a m × n matrix with polynomial entries,

Use the concept companion matrix, we define n × n matrices A, B over the field .

Then it is straightforward to compute

The matrix pencil (A, B) is called the companion pencil of p(t) and can be used to compute the roots of p(t) as the roots of p(t) coincide with the eigenvalues of the pencil (A,B).

We can generalize this concept to polynomial matrices.

Definition 3.6.1

Let P(t) be a m × n matrix with polynomial entries,

Define the generalized companion matrix ((d − 1)m + n) × dm matrices A, B:

Proposition 3.6.1: For all t ∈ and all v ∈ m,

Proof: The straightforward computation will give the above property.

Without loss of generality, assume m ≤ n. Since rankP(t) = rankPT(t), we say that t_0 ∈ drops rankP(t) if and only if rankP(t_0) < m. Hence we have

Theorem 3.6.1

rankP(t) < m ⇔ rank(A − tB) < dm.

Proof: Suppose there exists a t_0 that drops rankP(t), i.e., P(t_0) < m. Then there exists v ≠ 0 such that P(t)v = 0. Hence, this is equivalent to say that (A − tB)x = 0 has a non-trivial solution. Hence rank(A − tB) < dm. Similarly, we have the other direction.

3.7 Solu tion of Linear System of Equations

Review the system of equations consists of linear equations:

The system can be written in the form of matrix Ax = b where

If A is a square matrix and nonsingular, then the linear system Ax = b has a unique solution x = A−1b for every possible choice of b.

Theorem 3.7.1

(Cramer’s rule). Let A be a nonsingular n × n matrix, the Ax = b has a unique solution x = [c_1, …, cn]T with

where the numerator is the determinant of the matrix A in which the k-th column is replaced by b.

Proof: A is a non-singular, the unique solution of Ax = b is x = A−1b. Let [c_1, …, cn]T be the solution. Then, substitute bk = ak_1c_1 + … + akncn, and we have

since determinant is n-linear and alternating.

Hence, the formula in this theorem gives another presentation of the solution.

Let b = 0, then Ax = 0 is a linear system of homogenous equations. The solutions of Ax = 0 form a linear space, we leave this proof to the interested readers.

The solutions of Ax = b and the solutions of Ax = 0 are closely related. Let x_0 be a solution of Ax = b and xh be a solution of Ax = 0, then x_0 + xh is a solutions of Ax = b. Suppose x_1 ≠ x_2 are solutions of Ax = b, then x_1 − x_2 is a solution of Ax = 0.

Theorem 3.7.2

Let A be an m × n matrix and S be the solution space of the homogenous linear system Ax = 0, then

Proof: Let dim S = s and v_1, …, vs form a basis of S. We extend v_1, …, vs to a basis v_1, …, vs, vs+1, …, vn of n. A induces a linear transformation from n to n, v → Av, and the image space is spanned by Avs+1, …, Avn, so rankA = dim Span{Avs+1, …, Avn}.

Notice that the dimension of Span{Avs+1, …, Avn} is n − s, otherwise, there exist αs+1, …, αn, not zero simultaneously, such that

This means that αs+1vs+1 +…+ αnvn ∈ S, which is impossible since v_1, …, vs, vs+1, …, vn is a basis for n.

Therefore, rankA = dimSpan{Avs+1, …, Avn} = n − s, equivalently, dim S + rankA = n.

3.8 Some Applicatio ns of Matrices

We give some examples to illustrate the applications of matrices in different areas.

3.8.1 Linear Program ming

Linear programming is an optimization method that is applied to a mathematical model with linear constraints. One of the most basic properties of linear program is the characterization of the program. In [Tiw04], the author shows the termination is related to eigenvalues of the corresponding matrix. We here review the results as an application of the eigenvalues and Jordan canonical form.

Consider a linear program (algorithm) of the form

where Bx > 0 represents a conjunction of linear inequalities over the state variables x and x : = Ax represents the linear assignments to each of the variables. The program P1 will terminate on a state x = c if a Bc 0. The Program P1 is said to terminate if it terminates on all initial values in for the variables in x.

Proposition 3.8.1 [Tiw04] If the linear loop program P1, defined by matrices A and B is non-terminating, then there exists a real eigenvector v of A, corresponding to positive eigenvalue, such that Bv ≥ 0.

EXAMPLE 3.8.1

Let the linear program be

The matrix A has two eigenvalues −1 and 1. The eigenvector associated to the positive eigenvalue 1 is Then [1 −1]x = [1 −1] and this program is terminating.

In the iteration computation induced by x : = Ax, we need to compute Ak for the k-th iteratiom. Jordan canonical form can help to reduce the computation.

Let P be an invertible matrix such that P−1AP = J where J = Diag(J_1, J_2, …, JK) is the real Jordan form of A and each Jordan block Ji is either of the two forms:

where D = and is the 2 × 2 identity matrix. Then P1 can be rewritten to an equivalent form

where y = P−1x.

Suppose the Ji = is of size mi × mi, then the k-the power of this block can be given explicitly as

Note that λi can be replaced by Di if Ji =

3.8.2 Geometric Transformation

In computer graphics and computer-aided design, the transformations, such as translations, rotations, and scaling, are basic operations for geometric objects. These transformations can be easily implemented by multiplication of certain matrices- Let (x, y, z) be a point in 3, its homogeneous form in 3 is (x, y, z, 1). Given a point in homogeneous form (x, y, z, w), w ≠ 0, its affine form is (x/w, y/w, z/w) ∈ 3.

Translation

For a given point, a translation means to move the point to a new position This can be mathematically achieved by adding a vector to a point; for instance, move (x, y, z, 1) to (x + x_0,y + y_0, z + z_0,1). The translation of an arbitrary point (x, y, z, 1) by a vector (x_0, y_0, z_0) can be implemented by multiplying (x, y, z, 1)T by the following matrix

and we have

Scaling

Scaling is used to change the length of a vector. A scaling in homogeneous coordinate is to transform (x, y, z, 1) to (sxx, syy, szz, 1). A geometric object is enlarged if its scaled parameters sx,sy, sz are greater than one. A scaling transformation can be implemented by multiplying (x, y, z, 1)T by the following matrix

and we have

Rotations

Another transformation of geometric objects is rotation with respect to a coordinate axis. A rotation about the x-axis by angle a counter- clockwise with right-hand rule is represented by a rotation matrix:

and we have

The matrix Rx,α is called the basic (or elemental) rotation matrix about the x-axis. Similarly, the basic rotation matrices about y axis and z axis are the following:

The above transformations can be easily combined. A rigid transformation of a vector space preserves distances between every pair of points. A rigid transformation is obtained by combining only translations and rotations.

3.8.3 Matrices in Graph Theory

A graph G consists of a set of vertices V(G) = {v_1, v_2, …, vm} and edges E(G) = e_1, e_2, …, en. We generally represent a finite graph by its adjacency matrix A(G) = (aij)m×m which is a square matrix with the entries 0 or 1, precisely,

For example, a given graph is shown in Fig. 3.1;, its adjacency matrix is

Figure 3.1 A simple graph

A commonly used property of the adjacency matrix is: the number of the paths from vi to vj with length n is exactly where A(G)n =

For this example,

Check the paths from v_1 to v_2: there is one path with length one, one path path with length two and five pathes with length three. Note that we can use the same edge more than one time.

Another important matrix of the graph is Laplacian matrix L(G). Let D(G) be the degree matrix of a graph G, it is a diagonal matrix whose (i, i) entry is the degree of i-th vertex. Continue the example,

The Laplacian matrix of G is defined by L(G) = D(G) − A(G) and

There are many properties of a Laplacian matrix such as

1.L(G) is symmetric and positive-semidefinite;

2.The number of times 0 appears as an eigenvalue of L(G) is the number of connected components in the graph;

3.The second smallest eigenvalue of L(G) is the algebraic connectivity (or Fiedler value) of G.

For this simple example, the eigenvalues of L(G) are 0, 2, 4 and 4. The number of connected components is obvious one and the algebraic connectivity of G is two according to the property of the Laplacian matrix.

3.8.4 Positional Relationship of Two Ellipsoids

Ellipsoids have a small number of geometric parameters and are excellent for approximating a wide class of convex objects in simulations of physical systems. Detecting a collision or overlap of two ellipsoids has practical applications in computer graphics, computer animation, virtual reality, robotics, CAD/CAM, etc. An algebraic equation of an ellipsoid can be written in a quadric form XTAX = 0 with respect to a symmetric matrix A where X = (x, y, z, w)T. Based on discussion on the associated matrices, one can give an algebraic condition for the separation of ellipsoids in 3-dimensional Euclidean space, [WWK01].

Consider two ellipsoids : XTAX = 0 and : XTBX = 0 in homogeneous coordinates. Their characteristic polynomial is defined as

and f(λ) = 0 is called the characteristic equation. Assuming that the interior of is defined by XTAX < 0, and the interior of is defined by XTBX < 0 the algebraic conditions for the position relationships are:

The two ellipsoids are separated by a plane if and only if f(λ) = 0 has two distinct positive roots.

The two ellipsoids touch each other externally if and only if f(λ) = 0 has a positive double root.

Note that the characteristic equation f(λ) = 0 always has at least two negative roots. As soon as two distinct positive roots are detected, not necessary to compute the exact roots, one may conclude that the two ellipsoids are separated.

EXAMPLE 3.8.2

[WWK01] Consider the sphere A : x^2 + y^2 + z^2 − 25 = 0 and the ellipsoid : (x − 9)2/9 + y^2/4 + z^2/16 − 1 = 0. Their associated symmetric matrices are

The four roots of the characteristic equation are −6.25, −1.5625, 0.60111 and 4.6211. Since there are two distinct positive roots, and are separated.

3.9 Exercises

1.Let A = Find th e sums of the principal minors of A of orders 1, 2, and 3, respectively.

2.Let B = Find: det B, adjB, and find B−1 using adjB.

3.Let A = Find: adj A. Show that adj(adj A) = A. When does A = adjA?

4.Find the characteristic polynomial of A =

5.Consider the quadratic form f(x, y) = 2x^2 − 4xy + 5y^2 = (x, y)A(x, y)T. Find matrix A. Can you diagonalize matrix A. Identify the change of variables so that f(x, y) can be written as AX^2 + BY^2.

Remark: Below is a solution provided by Andrew Crutcher via SAGE.

A = matrix(QQ,2,2,[2,-2,-2,5])

eigens = A.eigenvectors_right(); eigens

for eigen in eigens:

print "Eigenvalue: ",eigen[0]

print "Eigenvector: ",eigen[1][0]

print "Multiplicity: ", eigen[2]

P = matrix.zero(QQ,A.nrows())

D = matrix.zero(QQ,A.nrows())

for coln in range(0,len(eigens)):

v = (QQ"A.nrows()).zero_vector()

v.set(coln,eigens[coln][0])

D.set_column(coln,v)

ev = eigens[coln][1][0]

P.set_column(coln,ev)

P.inverse()*A*P

print "P"; P

print "D"; D

This would result in the following output.

[(6, [(1, -2)], 1), (1, [(1, 1/2)], 1)]

Eigenvalue: 6

Eigenvector: (1, -2)

Multiplicity: 1

Eigenvalue: 1

Eigenvector: (1, 1/2)

Multiplicity: 1

[6 0]

[0 1]

P

[ 1 1]

[ -2 1/2]

D

[6 0]

[0 1]

6.Find the minimal polynomial and characteristic polynomial of the matrix A =

Remark: Here we include the following solutions provided by Andrew Crutcher via SAGE.

A = matrix(QQ,3,3,[2,2,-5,3,7,-15,1,2,-4])

print "Eigenvalues:", A.eigenvalues()

print "Characteristic:", A.characteristic_polynomial()

print "Minimal:", A.minimal_polynomial()

This would result in the following output.

Eigenvalues: [3, 1, 1]

Characteristic: x^3 - 5*x^2 + 7*x - 3

Minimal: x^2 - 4*x + 3

7.Let A = (a) Find all eigenvalues and corresponding eigenvectors. (b) Find matrices P and D is non-singular and D = P−1AP is diagonal.

Remark: We include a solution computed by SAGE provided by Andrew Crutcher.

A = matrix(QQ,2,2,[3,-4,2,-6])

eigens = A.eigenvectors_right(); eigens

for eigen in eigens:

print "Eigenvalue: ",eigen[0]

print "Eigenvector: ",eigen[1][0]

print "Multiplicity: ", eigen[2]

P = matrix.zero(QQ,A.nrows())

D = matrix.zero(QQ,A.nrows())

for coln in range(0,len(eigens)):

v = (QQ"A.nrows()).zero_vector()

v.set(coln,eigens[coln][0])

D.set_column(coln,v)

ev = eigens[coln][1][0]

P.set_column(coln,ev)

P.inverse()*A*P

print "P";

P print "D"; D

This would result in the following output.

[(2, [ (1, 1/4) ], 1), (-5, [ (1, 2) ], 1)]

Eigenvalue: 2

Eigenvector: (1, 1/4)

Multiplicity: 1

Eigenvalue: -5

Eigenvector: (1, 2)

Multiplicity: 1

[ 2  0]

[ 0 -5]

P

[  1 1]

[1/4 2]

D

[ 2  0]

[ 0 -5]

8.Let A = (a) Find all eigenvalues and corresponding eigenvectors. (b) Find matrices P and D such that P is non-singular and D = P−1AP is diagonal. (c) Find A^6 and f(A), where f(t) = t^4 − 3t^3 − 6t^2 + 7t + 3. (d) Find a matrix such that 3 = A and B has real eigenvalues.

Remark: Again, we include a solution by SAGE provided by Andrew Crutcher.

A = matrix(QQ,2,2,[2,2,1,3])

print "a)"

eigens = A.eigenvectors_right(); eigens

for eigen in eigens:

print "Eigenvalue: ",eigen[0]

print "Eigenvector: ",eigen[1][0]

print "Multiplicity: ", eigen[2]

P = matrix.zero(QQ,A.nrows())

D = matrix.zero(QQ,A.nrows())

for coln in range(0,len(eigens)):

v = (QQ"A.nrows()).zero_vector()

v.set(coln,eigens[coln][0])

D.set_column(coln,v)

ev = eigens[coln][1][0]’

P.set_column(coln,ev)

print "b)"

P.inverse()*A*P

print "P"; P

print "D"; D

print "c)"

print "A"6"; A"6

def f(x):

return x"4-3*x"3-6*x"2+7*x+3

print "f(A)";f(A)

This would result in the following output.

a)

[(4, [(1, 1)], 1), (1, [(1, -1/2)], 1)]

Eigenvalue: 4

Eigenvector: (1, 1)

Multiplicity: 1

Eigenvalue: 1

Eigenvector: (1, -1/2)

Multiplicity: 1

b)

[4 0]

[0 1]

P

[ 1 1]

[ 1 -1/2]

D

[4 0]

[0 1]

c)

A"6

[1366 2730]

[1365 2731]

f(A)

[ 1 -2]

[-1 0]

For part d), let B = PCP−1, and remember A = PDP−1. Also note that if we take a diagonal matrix E and raise it to power (E^3 = F), realize that Fij = (E^3)ij = (Eij)3 since when we do matrix multplication the only non-zero elements are on the diagonal and they will be only multiplied by themselves.

Note B^3 = PCP−1PCP−1PCP−1 = PCCCP−1 = PC^3P−1 = PDP−1 = A, so B^3 = A.

9.Let A = and B = Find characteristic polynomial of each matrix, and find the minimal polynomial of each matrix.

Remark:

A = matrix([[4, -2, 2],[6, -3, 4], [3, -2, 3]])

B = matrix([[3, -2, 2],[4, -4, 6], [2, -3, 5]])

Print "A: characteristic:", A.characteristic_polynomial()

Print "A: minimal poly: ", A.minimal_polynomial()

Print "B: characteristic:", B.characteristic_polynomial()

Print "B: minimal poly: ", B.minimal_polynomial()

This would result in the following output.

A:    characteristic: x^3 - 4*x^2 + 5*x - 2

A:    minimal poly: x^2 - 3*x + 2

B:    characteristic: x^3 - 4*x^2 + 5*x - 2

B:    minimal poly: x^3 - 4*x^2 + 5*x - 2

10.Find a matrix A whose minimal polynomial is t^3 − 8t^2 + 5t + 7.

Remark: The minimal polynomial of the companion matrix is the polynomial.

def f(x):

return x^3-8*x^2+5*x+7

C = matrix([[0,1,0],[0,0,1],[-7,-5,8]]); C.transpose()

C.minimal_polynomial()

f(C)

This would result in the following output.

[0 0 -7]

[1 0 -5]

[0 1  8]

x^3 - 8*x^2 + 5*x + 7

[0 0 0]

[0 0 0]

[0 0 0]

11.Use the trace and the determinant of the matrix A = to find the eigenvalues, and then deduce that it is diagonalizable. Find the eigenvalues of A^2 and A−1 if it exits.

12.Determine the Jordan normal form of A = and B =

Remark The following is a solution using Sage provided by Andrew Crutcher.

A = matrix([[4, -2, 2],[6, -3, 4], [3, -2, 3]])

B = matrix([[3, -2, 2],[4, -4, 6], [2, -3, 5]])

print "A Jordan form:"; A.jordan_form()

print "A Jordan form (no subdivides):";

A.jordan_form(subdivide=false)

print "B Jordan form:"; B.jordan_form()

print "B Jordan form (no subdivides):";

B.jordan_form(subdivide=false)

This would result in the following output.

A Jordan form:

[2|0|0]

[-+-+-]

[0|1|0]

[-+-+-]

[0|0|1]

A Jordan form (no subdivides):

[2 0 0]

[0 1 0]

[0 0 1]

B Jordan form:

[2|0 0]

[-+ ]

[0|1 1]

[0|0 1]

B Jordan form (no subdivides):

[2 0 0]

[0 1 1]

[0 0 1]

13.Find the eigenvectors and a basis of each eigenspace of the matrices over

Are these matrices diagonalizable over . Find a Jordan normal form of them over , and a Jordan basis.

Remark: Solution provided by Andrew Crutcher via Sage is included below:

Eigenvalues[{{4, -5}, {2, -2}}]

Eigenvalues[{{1, -1, 1}, {3, 3, -1}, {-6, -2, 4}}]

Eigenvectors[{{1, -1, 1}, {3, 3, -1}, {-6, -2, 4}}]

This would result in the following output. Note I is for Wolfram

{1+1, 1-1}

{3 + 1 Sqrt[5], 3-1 Sqrt[5], 2}

{{-(1/6) I (2 I + Sqrt[5]), -(1/2),

1}, {1/6 I (-2 I + Sqrt[5]), -(1/2), 1}, {0, 1, 1}}

Since B has a real eigenvalue, this eigenvalue has a corresponding eigenvector which would be basis for the eigenspace of that eigenvalue v = [0, 1, 1]. Note since A, B have complex eigenvalues this means we cannot diagonalize them over or find their Jordan form over . Going back to SAGE, we can compute the rest of the eigenvalues and eigenvectors.

C = matrix(QQ,[[1,1,0],[-2,4,0],[1,-1,2]])

D = matrix(QQ,[[5,-1,-1],[3,1,-1],[6,-2,0]])

E = matrix(QQ,[[3,2,-2,0],[2,3,-2,0],[2,2,-1,0],[-2,-4,6,-1]])

mats = [C,D,E]

for matlndex in range(0,len(mats)):

print "Matrix",chr(ord(’C’)+matIndex)

print "Eigenvalues: ", mats[matIndex].eigenvalues()

for eigenInfo in mats[matIndex].eigenvectors_right():

print "Eigenvalue: ",eigenInfo[0]

print "Eigenvectors (basis of eigenspace for this

eigenvalue):"

print eigenInfo[1]

#print eigen

print "Diagonalizable: ", mats[matIndex].is_diagonalizable()

print "Jordan Form"

mats[matIndex].jordan_form()

This would result in the following output.

Matrix C

Eigenvalues: [3, 2, 2]

Eigenvalue: 3

Eigenvectors (basis of eigenspace for this eigenvalue):

[

(1, 2, -1)

]

Eigenvalue: 2

Eigenvectors (basis of eigenspace for this eigenvalue):

[

(1, 1, 0),

(0, 0, 1)

]

Diagonalizable: True

Jordan Form

[3|0|0]

[-+-+-]

[0|2|0]

[-+-+-]

[0|0|2]

Matrix D

Eigenvalues: [2, 2, 2]

Eigenvalue: 2

Eigenvectors (basis of eigenspace for this eigenvalue):

[

(1, 0, 3),

(0, 1, -1)

]

Diagonalizable: False Jordan Form [2 1|0]

[0 2|0]

[ +-]

[0 0|2]

Matrix E

Eigenvalues: [3, -1, 1, 1]

Eigenvalue: 3

Eigenvectors (basis of eigenspace for this eigenvalue):

[

(1, 1, 1, 0)

]

Eigenvalue: -1

Eigenvectors (basis of eigenspace for this eigenvalue):

[

(0, 0, 0, 1)

]

Eigenvalue: 1

Eigenvectors (basis of eigenspace for this eigenvalue):

[

(1, 0, 1, 2),

(0, 1, 1, 1)

]

Diagonalizable: True Jordan Form [ 3| 0| 0| 0]

[--+--+--+--]

[ 0|-1| 0| 0]

[--+--+--+--]

[ 0| 0| 1| 0]

[--+--+--+--]

[ 0| 0| 0| 1]

14.Find the eigenvectors and a basis of each eigenspace of the matrices over C

Are these matrices diagonalizable over ? Find a Jordan normal form of them over , and a Jordan basis.

Remark: A solution provided by Andrew Cruther is included below via Sage.

A = matrix([[4, -5],[2,-2]])

B = matrix([[2,1,0,0],[1,2,0,0],[1,1,1,0],[0,-2,2,-1]])

mats = [A,B]

for matIndex in range(0,len(mats)):

print "Matrix",chr(ord(’AC’)+matIndex)

print "Eigenvalues: ", mats[matIndex].eigenvalues()

for eigenInfo in mats[matIndex].eigenvectors_right():

print "Eigenvalue: ",eigenInfo[0]

print "Eigenvectors (basis of eigenspace for this

eigenvalue):"

print eigenInfo[1]

print "Multiplicty: ", eigenInfo[2]

This would result in the following output.

Matrix A

Eigenvalues: [1 - 1*I, 1 + 1*I]

Eigenvalue: 1 - 1*I

Eigenvectors (basis of eigenspace for this eigenvalue):

[(1, 0.6000000000000000? + 0.2000000000000000?*I)]

Multiplicty: 1

Eigenvalue: 1 + 1*I

Eigenvectors (basis of eigenspace for this eigenvalue):

[(1, 0.6000000000000000? - 0.2000000000000000?*I)]

Multiplicty: 1

Matrix B

Eigenvalues: [3, -1, 1, 1]

Eigenvalue: 3

Eigenvectors (basis of eigenspace for this eigenvalue):

[

(1, 1, 1, 0)

]

Multiplicty: 1

Eigenvalue: -1

Eigenvectors (basis of eigenspace for this eigenvalue):

[

(0, 0, 0, 1)

]

Multiplicty: 1

Eigenvalue: 1

Eigenvectors (basis of eigenspace for this eigenvalue):

[

(1, -1, 0, 1),

(0, 0, 1, 1)

]

Multiplicty: 2

Since for both matrices, the multiplicty of each eigenvalue is the same as the dimension of the eigenspace for that eigenvalue, this would mean that each matrix is diagonalizable over and the diagonalization of each matrix is also the Jordan normal form. JA will denote the Jordan form of matrix A.

C H A P T E R 4

ORTHOGONAL BASES

4.1 Inner Product Spaces

Definition 4.1.1

An inner product space is a vector space V along with a function 〈,〉 called an inner product:

which is

1.positive definite, i.e., 〈u, u〉 > 0 with equality if and only if u = 0,

2.symmetric, i.e., 〈u, v〉 = 〈v, u〉,

3.bilinear, i.e., for any a, b ∈ ,

Thus an inner product is a positive definite, symmetric bilinear form on the vector space V.

There are a few definitions that arise from the inner product definition. First, the norm of x ∈ V is defined as

It is well defined by the non-negativity axiom of the Definition of the inner product space. The norm can be considered as the length of the vector x. One can prove the Cauchy-Schwarz inequality, that is:

with equality if and only if x and y are linearly dependent. An immediate consequence of the Cauchy-Schwarz inequality is that it justifies defining the angle between two non-zero vectors x and y in the case = by the identity

We will say that non-zero vectors x, y ∈ V are orthogonal if and only if their inner product is zero, i.e., 〈x, y 〉 = 0.

Definition 4.1.2

Let W be a subspace of the inner product space V and let {w_1, …, wn} be a basis for W such that (wi, wj) = 0 if i ≠ j, then this basis is called an orthogonal basis. Furthermore, if (wi, wi) = 1 then this basis is called an orthonormal basis.

Lemma 4.1.1 If v_1, …, vk ∈ V are non-zero, pairwise orthogonal vectors, i.e., vi ≠ 0 and (vi, vj) = 0 for all i ≠ j, then they are linearly independent.

Proof: Suppose

Let us take the inner product of this equation with any vi. Using linearity of the inner product and orthogonality, we compute

Therefore, if vi ≠ 0, then ci = 0. Since this holds for all i = 1, …, k, the linear independence of v_1, …, vk follows.

As a direct consequence, any collection of non-zero orthogonal vectors forms a basis for its span.

Theorem 4.1.1

Suppose v_1, …, vk ∈ V are non-zero, pairwise orthogonal vectors of an inner product space V. Then v_1, …, vk form an orthogonal basis for their span W = Span{v_1, …, vk} ⊆ V, which is therefore a subspace of dimension k = dim W. In particular, if dim V = k, then v_1, …, vk form a orthogonal basis for V.

There are a few advantages of orthogonal and orthonormal bases. For instance, one of the key issues one encounters is to express other vectors as linear combinations of the basis vectors that is, to find their coordinates in the prescribed basis. In general, this is not an easy task, since this requires solving a system of linear equations. Computing a set of solutions may require a considerable effort in case of high-dimensional situations. However, this problem can be eliminated if the basis is orthogonal, or, even better, orthonormal. This is the crucial insight underlying the efficiency in computational problems.

Theorem 4.1.2

Let v_1, …, vn ∈ V be an orthonormal basis for an inner product space V. Then one can write any vector v ∈ V as a linear combination

in which its coordinates

are explicitly given as inner products. Moreover, its norm

Proof: Let us compute the inner product of

with one of the basis vectors. Using the orthonormality conditions

Hence

To prove the norm formula, we use the property

Since moving from an orthogonal basis to its orthonormal version is elementary, simply by dividing each basis vector by its norm, it is e nough to use an orthogonal basis.

4.2 Gram-Schmidt Process to Produce Orthonormal Basis

We understand that it is more convenient to use orthogonal or orthonormal bases, a natural question arises: how can we construct them? A practical algorithm known as the Gram-Schmidt process is one of the premier algorithms of applied and computational linear algebra.

In mathematics, particularly linear algebra and numerical analysis, the Gram-Schmidt process is a method for orthonormalizing a set of vectors in an inner product space, most commonly the Euclidean space n, equipped with the standard inner product. The Gram-Schmidt process takes a finite, linearly independent set S = {v_1, …, vk} for k ≤ n and generates an orthogonal set S′ = {u_1, …, uk} that spans the same k-dimensional subspace of n as S.

We define the projection operator by the vector projection of v onto u:

This operator projects the vector v orthogonally onto the line spanned by the vector u. If u = 0, we define proju(v) = 0, i.e., the projection map is the zero map, sending every vector onto the zero vector. The Gram-Schmidt process then works as follows:

The vectors u_1, …, uk are orthogonal vectors, and the normalized vectors w_1, …, wk form an orthonormal set. The calculation of the sequence u_1, …, uk is known as the Gram-Schmidt orthogonalization, while the calculation of the sequence w_1, …, wk is known as the Gram-Schmidt ortho-normalization as the vectors are normalized. One can check that this set of vectors indeed contains pairwise orthogonal unit vectors. The general proof proceeds by mathematical induction.

EXAMPLE 4.2.1

Consider 3 with the dot product as the inner product space. Let P be the plane spanned by vectors x_1 = (1, 2, 2) and x_2 = (1, 0, 2). Find an ortho-normal basis for P, and extend it to an orthonormal basis for 3.

Proof: We note that x_1, x_2 is a basis for the plane P, since the two vectors are linearly independent over , and we can extend it to a basis for 3 by adding one vector from the standard basis. For instance, vectors x_1, x_2, x_3 = (0, 0, 1) form a basis for 3 because the determinant of the matrix formed by x_1, x_2, x_3 is non-zero.

Now, using the Gram-Schmidt process, we orthogonalize the basis xi as the following:

So {v_1, v_2, v_3} is an orthogonal basis for 3 while {v_1, v_2} is an orthogonal basis for P. We only need to normalize the vectors,

Therefore, {w_1, w_2} is an orthonormal basis for P, and {w_1, w_2, w_3} is an orthonormal basis for 3.

Remark 4.2.1: Let W be a subspace of an inner product finite-dimensional vector space V. Let S = {v_1, …, vk} be a basis for W, we can extend S to a basis B = {v_1, …, vk, vk+1, …, vn} for V. By the Gram-Schmidt process, we obtain an orthogonal basis B’ = {u_1, …, uk, uk+1, …, un} for V. Note that S′ = {u_1, …, uk} is an orthogonal basis for W. Moreover, for any a ∈ Span(uk+1, …, un), a is orthogonal to any b ∈ W. In the next section, we will see that {uk+1, …, un} form a basis for the orthogonal complement of W in V.

4.3 Orthogonal Complements and Projections

In this section, we first introduce a concept of an orthogonal complement.

Definition 4.3.1

Let W be a subspace of the inner product space V. The orthogonal complement of W is the set

Furthermore, let the projection of x onto y be

Theorem 4.3.1

Suppose that p is the orthogonal projection of x onto the space spanned by y. Then p and x − p are orthogonal.

Proof: Since two vectors are orthogonal if and only if their inner product is zero, we check

so p and x − p are orthogonal.

Definition 4.3.2

Let W be a finite dimension subspace of the inner product space V and let {w_1, …, wn} be an orthogonal basis for W. If v is any vector in V then the orthogonal projection of v onto W is the vector:

If {w_1, …, wn} is an orthonormal basis for W, then the orthogonal projection of v onto W is the vector:

We can prove the following theorem.

Theorem 4.3.2

Let V be an n-dimensional inner product space and W a subspace of V. The following hold:

1.W⊥ is a subspace of V;

2.W ∩ W⊥ = {0};

3.dim W + dim W⊥ = n;

4.W ⊕ W⊥ = V.

Proof: (1) First note that 0 ∈ W⊥. Now suppose that w_1, w_2 ∈ W⊥. Then 〈wi, v〉 = 0 for all v ∈ W for i = 1, 2. Moreover, for some a, b ∈ , 〈aw_1 + bw_2, v〉 = a〈w_1, v〉 + b〈w_2, v〉 = 0, so aw_1 + cw_2 ∈ W⊥. Thus W⊥ is a subspace of V.

(2) Let v ∈ W ∩ W⊥, then

(3) From Remark 4.2.1, V = W + W⊥. By the second claim, and the dimension of subspaces

(4) From Remark 4.2.1 and the Definition of W⊥, for every vector v ∈ V, there are vectors w ∈ W and u ∈ W⊥ such that v = w + u. If v = w′ + u′, then w − w′ = u′ − u = 0 ∈ W ∩ W⊥. Thus, w = w′ and u = u′. By the Definition of direct sum, for every vector v ∈ V, there are unique vectors W ∈ W and u ∈ W⊥ such that v = w + u.

Now we will consider the following problem: Given an inner product vector space V, a subspace W, and a vector v ∈ V, find the set of vectors w ∈ W which are the closest to v, that is the norm |v − w| is the smallest, i.e.,

Theorem 4.3.3

Let V be a vector space with inner product 〈,〉. Let W ⊆ V be a subspace and v ∈ V. If (v − w) ⊥ W, then |v − w| < |v − u| for all u ∈ W and |v − w| = |v − u| if and only if w = u. Thus w ∈ W is closest to v.

Proof: First we note that |v − w| ≤ |v − u| if and only if |v − w|2 ≤ |v − u|2. Note that the square of the norm, |·|2 = 〈,〉, and calculate

since v − w ∈ W⊥, w − u ∈ W, and (v − w, w − u) = 0. Thus,

The equality in the above expression holds if and only if |w − u|2 = 0 if and only if w = u.

Theorem 4.3.4

Let V be a vector space with inner product 〈,〉. Let W ⊆ V be a subspace and v ∈ V. If w ∈ W is the closest to v, then v − w ⊥ W.

Proof: Since w ∈ W is the closest to v, we know that |v − w| ≤ |v − u| for all u ∈ W. Therefore the function f : → such that

has a minimum value at t = 0. We have

Thus, f′(t) = 2(v − w, x) + 2t|x|2 and since 0 is a critical number, f′(0) = 2(v − w, x) = 0. As x ∈ W is arbitrary, it follows that v − w ⊥ W.

The idea behind the construction of the vector w such that v − w ± W is the Gram-Schmidt orthogonalization process.

Theorem 4.3.5

Let V be a vector space with inner product 〈,〉. Let W ⊆ V be a subspace and assume that {v_1, …, vn} is an orthogonal basis for W. For v ∈ V let

Then v − w ⊥ W (or equivalently, w is the vector in W closest to v).

Proof:

Hence v − w ⊥ vj. Since {v_1, …, vn} is a basis for W, this implies that v − w ⊥ W.

One of the application problems related to orthogonal projection is the numerical approach to understand the least squares problem. When we try to fit one line on more than two points, we tend to face a problem that the linear equation Ax = b has no solution because there are more equations than the number of variables. In other words, the linear system is inconsistent and b is not in the column space of A. To handle this situation, we can regard Ax as an approximation of b, the optimal solution is to obtain x such that |b − Ax| is the smallest. Hence, instead of solving Ax = b, our goal is to find a vector x such that |b − Ax| is the smallest. Therefore, if A is a m × n matrix and b ∈ m, a least squares solution of Ax = b is a vector x∗ ∈ n such that |Ax∗ − b| ≤ |Ay − b| for all y ∈ n.

To do this, we recall that the column space C of A coincides with the image (= range) of A, since if A_1, …, An are the columns of A and e_1, …, en are the standard unit coordinate vectors in n, then Aei = Ai. Moreover if we assume that rankA = n, then ker(A) = {0}.

Theorem 4.3.6

For any m × n matrix A,

Proof: Let V = imA ∈ m, where the columns of A are denoted by A_1, …, An, then

Theorem 4.3.7

(The approximation theorem). The orthogonal projection pW(x) is closer to x than any other vector of W.

Proof: For any y ∈ W,

and (x − pW (x)) ± W, and pW(x) − y ∈ W. The Pythagorean theorem (for general Euclidean spaces) now shows that

with equality if and only if y = pW(x).

Theorem 4.3.8

Let A be an m × n matrix with rank n, and let P denote an orthogonal projection onto the image of A. Then for every y ∈ m, the equation Ax = Py has a unique solution a ∈ n. Moreover, a is the best approximate solution to the equation Ax = y, in the sense that for any x ∈ n, |Aa − y| ≤ |Ax − y| with equality if and only if x = a.

Proof: By definition, the orthogonal projection Py belongs to the image of A. Therefore Aa = Py for some a ∈ n. Moreover, a is uniquely determined, since if Ax_1 = Ax_2, then A(x_1 − x_2) = 0 and x_1 − x_2 ∈ ker(A), and x_1 = x_2 since ker(A) = {0}. By the approximation theorem, we know that |Py − y| ≤ |Ax − y| for every x ∈ n, with equality if and only if Ax = Py. Substituting Aa = Py, we obtain that |Aa − y| ≤ |Ax − y|.

Theorem 4.3.9

If the null space of A is {0}, then the solution of the normal system of equations AT Ax = ATy exists and equals the least squares solution of Ax = y.

Proof: Let A be a matrix of size m × n. Note since (ATA)T = ATA, so ATA is a symmetric matrix. Thus, for an eigenvector v of ATA, then ATAv = λv for some λ, and

Thus λ ≥ 0. Suppose ATA is singular, then there exists v ≠ 0 such that ATAv = 0, hence 0 = vTATAv = (Av) · (Av). This implies that Av = 0, i.e., the null space of A is not {0} contradicting to the condition. Thus, ATA must be non-singular.

Then, the system ATAx = ATy has a unique solution of the form a = (ATA)−1ATy. Thus AT(y − Aa) = ATy −ATAa = 0, hence y − Aa ∈ ker AT = (imA)⊥. Thus, y − Aa = y − Py for an orthogonal projection P of y onto the imA. Thus Aa = Py, and a is the least square solution for the system Ax = y. Therefore, the solution of the normal system of equations ATAx = ATy exists and equals the least squares solution of Ax = y.

From the proof of the above theorem, we have that the solution for the system ATAx = ATy is a = (ATA)−1ATy, so Aa = A(ATA)−1ATy. We have shown that a is the least square solution, then A(ATA)−1AT can be considered as the orthogonal projection matrix onto imA. Thus, we conclude as the following.

Corollary 4.3.1: Let A be an m × n matrix, then the matrix of the orthogonal projection onto the image of A is A(ATA)−1AT.

Now, as an application of orthogonal projection, let us see the least squares approximation problem: given n data (x_1, y_1), …, (xn, yn) ∈ 2, we would like to find a line L of the form y = mx + b which is the “closest fit” for the given data points, in the sense that the “least squares error” term

is as small as possible. To find a formula for the “least squares regression line” L, we note that the system of n equations in the two unknowns m, b

is over-determined. Assume that at least two of the the xi’s are distinct, then the matrix

has rank 2, and the system we are trying to solve can be written as

In general, y may not lie in the image of A, so this system typically has no solution. However, let P denote orthogonal projection onto the column space of A. Then Theorem 4.3.8 states that there is a unique solution v = (m_0, b_0) to the equation Av = Py, and this solution minimizes the quantity |Av − y|2. Since |Av − y|2 = S(m, b), it follows that the line L is given by the equation y = m0x + b_0.

Theorem 4.3.10

The least squares regression line L is given by the equation y = m0x + b_0, where

Where

Proof: Theorem 4.3.9 states that the least squares solution v satisfies the equation ATAv = ATy where A = and v = Compute

Therefore

Now, note that and Thus

From the equations above it follows that

Therefore the solution is

EXAMPLE 4.3.1

Suppose the three data points are (1, 2), (2, 5), (3, 7).

Then Therefore, the least squares regression line is given by the equation

4.4 Orthogonal Projections and Reflections

Matrices whose columns form an orthonormal basis of n relative to the standard Euclidean dot product play a distinguished role, they are called orthogonal matrices. Such matrices appear in a wide range of applications in geometry, physics, mechanics, and special functions. In particular, calculations involving spatial rotations are described in terms of orthogonal matrices, and orthogonal matrices are an essential ingredient in the QR algorithm for computing eigenvalues of matrices. In this section, we will study the orthogonal matrices.

Definition 4.4.1

A square matrix Q is called an orthogonal matrix if it satisfies

The orthogonality condition implies that one can easily invert an orthogonal matrix:

In fact, a matrix is orthogonal if and only if its inverse is equal to its transpose.

Theorem 4.4.1

A matrix Q is orthogonal if and only if its columns form an orthonormal basis with respect to the Euclidean dot product on n.

Proof: Let u_1, …, un be the columns of Q. Then are the rows of the transposed matrix QT. The (i, j)-th entry of the product QTQ is given as the product of the i-th row of QT times the j-th column of Q. Thus, the orthogonality requirement implies

which are precisely the conditions for u_1, …, un to form an orthonormal basis.

Corollary 4.4.1: An orthogonal matrix has determinant det Q = ±1.

Proof: We observe that

Corollary 4.4.2: The product of two orthogonal matrices is also orthogonal.

Proof: Let Q_1,Q_2 be two orthogonal matrices, then

and so the product matrix is also orthogonal.

This property says that the set of all orthogonal matrices forms a group. The orthogonal group lies at the foundation of Euclidean geometry, as well as rigid body rotation, computer graphics and animation, and many other areas.

4.4.1 Orthogonal Projection Matrix

Let a_1, …, ak linearly independent vectors in n and W = Span(a_1, …, ak). We will study how to construct projections and reflections matrices, and use these matrices to find an orthogonal projection of a given vector onto W, and reflection of a given vector x ∈ n through W.

To do so, we will note that the orthogonal projection of x onto W is in fact another vector x′ ∈ W such that (x − x′)⊥ y for all y ∈ W. Since W = Span(a1, …, ak), we must have

Now let A be an n × k matrix, k ≤ n, with columns a_1, …, ak that are linearly independent vectors in n. Then the above relation means

since x′ ∈ W, there exist C = [c_1, …, ck]T such that x′ = A[c_1, …, ck]T = AC. Therefore,

Thus, by the proof of Theorem 4.3.9, we know that if the A has linearly independent columns, then ATA is invertible. By the relation ATx = (ATA)C, we obtain C = (ATA)−1(ATx), and

The matrix

is called the orthogonal projection matrix onto the subspace W. We check that Q has the following two properties:

EXAMPLE 4.4.1

Compute the projection matrix Q for the 2-dimensional subspace W of 4 spanned by the vectors (1, 1, 0, 2) and (−1, 0, 0, 1). What is the o rthogonal projection of the vector x = (0, 2, 5, −1) onto W?

To answer the question, we let A = Then

Hence, the image of orthogonal projection is Qx = (7/11, 1/11, 0, −4/11)T

4.4.2 Reflection Matrix

Now, let us use the result of orthogonal projection matrix to analyze what is the reflection of x across W, where W is a (hyper-)plane through the origin, We note that W⊥ = c = (c_1, …, cn)T, is the normal vector of the (hyper-)plane W. Then the orthogonal projection of a vector x ∈ n onto W⊥ is given by the orthogonal projection matrix Q, which is

Now, if we scale c so that c is a unit vector, then we have

Now, let x∗ be the image of the reflection of x across W, then the distance between x and x∗ is twice as much as the distance between x and x′. Hence, we have

where Q is the matrix representation of orthogonal projection onto W. The matrix

HW = − 2ccT, where c is a unit normal vector for the plane W is called the reflection matrix for the plane W and sometimes is also called the Householder matrix.

EXAMPLE 4.4.2

Compute t he reflection of the vector x = (−1, 3, −4) across the plane 2x − y + 7z = 0.

To answer the question, we let then

Hence, the image of reflection is HWx = (39/27,48/27,123/27)T.

4.5 Properties of Symmetric Matrices

Definition 4.5.1

Let 〈,〉 = · be the standard inner product on n. The real n × n matrix A is symmetric if and only if

Since this Definition is independent of the choice of basis, symmetry is a property that depends only on the linear operator A and a choice of inner product.

The above Definition suggests that a symmetric matrix is a square matrix that is equal to its transpose. Formally, matrix A is symmetric if

Because if A = AT, then

On the other hand, if 〈Ax, y〉 = 〈x, Ay〉, then let x = ei and y = ej, then

thus,

Symmetric matrices play an important role in a broad range of applications. Not only are the eigenvalues of a symmetric matrix necessarily real, the eigenvectors always form an orthogonal basis. Hence it is the most common topic to study in terms of orthogonal bases.

To introduce the next theorem, we first define a Hermitian matrix.

Definition 4.5.2

A Hermitian matrix or self-adjoint matrix is a complex square matrix that is equal to its own conjugate transpose, that is, the element in the i-th row and j-th column is equal to the complex conjugate of the element in the j-th row and i-th column, for all indices i and j:

Hermitian matrices can be understood as the complex extension of real symmetric matrices. If the conjugate transpose of a matrix A is denoted by A∗, then the Hermitian property can be written concisely as

Lemma 4.5.1 If A is a symmetric matrix, x is an eigenvector of A, and y is orthogonal to x, then

Proof: To show y ⊥ Ax, note that x · y = 0, and

To show Ay ⊥ x,

Finally,

Theorem 4.5.1

Let A = AT be a real symmetric n × n matrix. Then

1.All the eigenvalues of A are real.

2.Eigenvectors corresponding to distinct eigenvalues are orthogonal.

3.There is an orthonormal basis of n consisting of n eigenvectors of A.

Proof: First, if A = AT is real, symmetric, then

Note in n, · is the regular dot product, and in n we have

To prove property (1), we note that if λ ∈ then

On the other hand,

Hence

Thus λ ∈ .

To prove (2), suppose

Then

This in turn implies (a − b)(v · w) = 0. Since a ≠ b, we must have that

Thus distinct eigenvalues correspond to orthogonal eigenvectors.

To prove the final statement, if all the eigenvalues of A are distinct, then the corresponding eigenvectors are orthogonal and they form a basis. By normalization, we obtain an orthonormal basis.

To prove the general case, we proceed by induction on the size n of the matrix A. Let T : n → n be the linear transformation defined by Tx = Ax.

To start, the case of a 1 × 1 matrix is trivial. Suppose A has size n × n. We know that A has at least one real eigenvalue, λ_1, and v_1 is the associated eigenvector. Let V = Span(v_1), and

denote the orthogonal complement to V.

We note that A defines a linear transformation on V⊥ since for any w ∈ V⊥, then by Lemma 4.5.1, v_1 · Aw = Av_1 · w = λ_1v_1 · w = 0. Thus, A restricted to V⊥ is a linear transformation from V⊥ to V⊥. Let y_1, …, yn−1 be an orthonormal basis for V⊥, then = {v_1/|v_1|,y_1, …,yn−1} is an orthonormal basis for n. The matrix representation of T relative to the basis is a block matrix, The first column is [T(v_1)], the coordinate vector of the image of the linear transformation T on v_1. By Lemma 4.5.3, for any yj ∈ V⊥, T(yj) = Ayj ⊥ v_1, hence the first row must be [λ, 0, …, 0]. Moreover, is symmetric, since

Thus, A′ is an (n − 1) × (n − 1) symmetric matrix, and by induction hypothesis, the eigenvectors of A′ form an orthonormal basis u_2, …, un for V⊥. Then appending the unit eigenvector u_1 = v_1/|v_1|, we obtain the orthonormal basis for n consisting of n eigenvectors of A.

The orthonormal eigenvector basis serves to diagonalize the symmetric matrix, resulting in the following spectral factorization formula.

Theorem 4.5.2

(Spectral decomposition) Let A be a real, symmetric matrix. Then there exists an orthogonal matrix Q such that

where A = diag(λ_1, …, λn) is a real diagonal matrix. The eigenvalues of A appear on the diagonal of A, while the columns of Q are the corresponding orthonormal eigenvectors.

Proof: From the proof of the previous theorem, we can construct a basis for n consisting of n orthonormal eigenvectors of A. Let Q be a matrix whose columns are the basis elements of . Let T : n → n be the linear transformation defined by Tx = Ax. Then the matrix representation of T relative to is a diagonal matrix A with eigenvalues being the diagonal entries. Q is a change of basis matrix such that A = [T]ε = QAQ−1 where ε denotes the standard basis.

Definition 4.5.3

An n × n symmetric matrix A is called positive definite if it satisfies xTAx > 0 ∀0 ≠ x ∈ n.

More generally, an n × n Hermitian matrix A is said to be positive definite if 0 < x∗Ax ∈ , ∀0 ≠ x ∈ n, x∗ denotes the conjugate transpose of x.

The negative definite, positive semi-definite, and negative semi-definite matrices are defined in the same way, i.e., the expression x∗Ax is required to be always n egative, non-negative, and non-positive, respectively.

Theorem 4.5.3

A symmetric matrix A = AT is positive definite if and only if all of its eigenvalues are strictly positive.

Proof: (⇒) Let λ be an eigenvalue with correspon ding eigenvector v, then

Hence we must have that λ > 0.

(⇐) On the other hand, if λi > 0 for all the eigenvalues, then let v_1, …, vn be a orthonormal basis in n consisting of the eigenvectors of A, then

4.6 QR Factorization

In linear algebra, a QR decomposition, or QR factorization of a square matrix is a decomposition of a matrix A into a product A = QR of an orthogonal matrix Q and an upper triangular matrix R. If A is a real matrix, then Q is an orthogonal matrix, i.e., QTQ = , and if A is a complex matrix, then Q is a unitary matrix, i.e., Q∗Q = ).

In general, when A is an m × n matrix, with m ≥ n, as the product of an m × m unitary matrix Q and an m x n upper triangular matrix R,

where R_1 is an n × n upper triangular matrix, is an (m − n) × n zero matrix.

The QR factorization can be obtained by the Gram-Schmidt process applied to the columns of the full column rank matrix A = [a_1, … , an].

Let inner product 〈v, w〉= v[H11477]w in the real case, or 〈v, w〉 = v∗w for the complex case.

Recall the projection:

then:

Express the columns ai, i = 1, … , n, over our newly computed orthonormal basis:

where

Write this in a matrix form A = QR where:

EXAMPLE 4.6.1

Consider the matrix A = Let

Performing the Gram-Schmidt procedure, we obtain

Hence, A = QR where

Two alternative technique can be applied for QR decomposition.

Givens rotation: For 2-dimensional vector v = (v_1, v_2)T, one can find a rotation matrix G_2 = such that G_2 = (v_1, v_2)T =

where cos(θ) = and sin(θ) = For a m-dimensional vector v = (v_1, …, vi, …, vm)T, a rotation matrix

Will rotate v to a vector whose j-th element is zero, i.e.,

Notice that Gm(i, j) is an orthogonal matrix. Rotate each column of the m × n matrix A such that

where R_1 is an n × n upper triangular matrix, is an (mn) × n zero matrix.

Let

and R = then QR is a QR decomposition of A.

Householder transformation: Householder transformation is a linear transformation that describes a reflection about a plane or hyperplane containing the origin. For any two vectors v, w with same length, v, w are reflections of each other with respect to a hyperplane which passes through the origin and is orthogonal to the unit vector In fact, the matrix P = − 2uu∗ will define a linear transformation such that w = Pv and P is called a Householder matrix having the following properties:

1.P∗ = P;

2.P∗P = ;

3.P2 = ;

4.diag(, P) is also a household matrix;

5.det(P) = −1.

To find a QR decomposition of A, we construct a Householder matrix P_1 where v is the first column of A, and w = Pv is a column such that

Construct a Householder matrix for the first column of such that

Let P_2 = we have

Repeat the constructions for Householder matrices and get Pn … P_1A = = R. Then Q = (Pn …P_1)−1 = P_1 … Pn and R form a QR decomposition of A.

4.7 Sing ular Value Decomposition

In linear algebra, the singular value decomposition (SVD) is a factorization of a real or complex matrix. It is a generalization of the spectral factorization. It has many useful applications.

Definition 4.7.1

A non-negative real number a is a singular value for an m × n matrix M if and only if there exist unit-length vectors u in m and v ∈ n such that

The vectors u and v are called left-singular and right-singular vectors for σ, respectively.

Definition 4.7.2

The singular value decomposition (SVD) of an m × n real or complex matrix M is a factorization of the form

where U is an m × m real or complex unitary matrix, Σ = diag(σ_1, …, σk) where σ_1 ≥ …≥ σk ≥ 0, k = min(m, n), is an m × n rectangular diagonal matrix with non-negative real numbers on the diagonal, and V is an n × n real or complex unitary matrix. The diagonal entries σi of Σ are known as the singular values of M. The columns of U and the columns of V are called the left-singular vectors and right-singular vectors of M.

Remark 4.7.1 Let M be a real m × n matrix. Let U = [u_1, …, um] and V = [v_1, …, vn]. From the relations

it follows that

Hence, the squares of the singular values are the eigenvalues of MTM, which is a symmetric matrix.

Remark 4.7.2 If M ∈ m×n, then MTM is symmetric positive semi-definite matrix, and the singular values of M are defined to be the square roots of the eigenvalues of MTM. The singular values of M will be denoted by σ_1, …, σn. It is customary to list the singular values in decreasing order so it will be assumed that σ_1 ≥ … ≥ σn.

The singular value decomposition (SVD) can also be written as

You should see a similarity between the singular value decomposition and the spectral decomposition stated in Theorem 4.5.2. In fact, if M is symmetric, then SVD and spectral decomposition are the same. In general, singular value decomposition of a matrix is not unique. The right singular vectors are orthonormal eigenvectors of MTM. If an eigenspace of this matrix is 1-dimensional there are two choices for the corresponding singular vector, these choices are negatives of each other. If an eigenspace has dimension greater than one then there are infinitely many choices for the orthonormal eigenvectors, but any of these choices would be an orthonormal basis of the same eigenspace.

EXAMPLE 4.7.5

Find the SVD of M, where M =

Proof: First, we compute the singular values by finding the eigenvalues of MMT.

Second, we will find the right singular vectors by finding an orthonormal set of eigenvectors of MTM.

The eigenvalues of MTM are 25, 9, and 0. Moreover, MTM is symmetric, so the eigenvectors are orthogonal. Now to compute the eigenvectors of MTM corresponding to the eigenvalues 25, 9, 0 are

Hence so far we have

To find U, we realize that Mvi = σiui, thus

Thus, we have the final SVD of M:

Mathematica [Wol15], Maple [Map16], MATLAB [TM], Sage [SJ05], and many other computer software programs can compute matrix decompositions. Maple [Map16] is a symbolic and numeric computing environment, and is also a multi-paradigm programming language developed by Maple-soft. Below, we will provide an example to illustrate how to use Maple to perform SVD. We first create a matrix A, and then perform singular value decomposition via Maple.

>A:=Matrix(3,4,(i,j)->i+j-1);

>SingularValues(A,output=['S','U′,'Vt']);

4.8 Applications of SVD and QR Decompositions

We give two applications of SVD and QR decompositions.

4.8.1 Image Processing

In image processing, we can represent digital images as matrices. Consider a gray scale image having m × n pixels:, it can be represented as an m × n matrix. For color images, we need three numbers per pixel, for each color: red, green, and blue (RGB). Then the image processing turns to matrix analysis. For instance, we can easily rotate an image and add two images. Here we give a classic image compression method based on singular value decomposition (SVD).

Let M be an m × n matrix of an image; there is a factorization of the form

where U is an m × m real or complex unitary matrix, Σ = diag(σ_1, …, σk) where σ_1 ≥…≥ σk ≥ 0, k = min(m, n), is an m × n rectangular diagonal matrix with non-negative real numbers on the diagonal, and V is an n × n real or complex unitary matrix. Let U = [u_1, …, um] and V = [v_1, …, vn]. The singular value decomposition (SVD) of M can also be written as

Following the fact σ_1 ≥ … ≥ σk ≥ 0, most of the information of the image is included in terms which have greater singular values. This motives people to compress the image by dropping the terms with smaller singular values. For instance, we only need to store l(m + n + 1) numbers if we use

instead of storing mn numbers by using matrix M. We compare the results for different l with an example. The image with 512 × 512-pixels shown at the left in Fig. 4.1 is a photo of one of the authors and the right image in Fig. 4.1 is the compressed one with l = 1. The left image in Fig. 4.2 is the compressed one with l = 50 and the right one is with l = 100.

Note, in terms of storage, the original image requires mn = 512 · 512 = 262144 numbers. If l = 100, then the storage for compressed image is l(m + n + 1) = 100(512 + 512 + 1) = 102500, which is about 39% of the original storage. This saves 60% of storage space, without compromising the quality of the image.

Figure 4.1 Image compression

Figure 4.2 Image com pression (cont.)

4.8.2 QR Decomposition and GCD

The matrix can used in some algebraic computations, as a benefit of this situation, we can generalize the computation to numerical way. Let two polynomials f(x) and g(x) as

The Sylvester matrix of f and g is an (m + n) × (m + n) matrix consist of the coeffic ients of f and g.

The Sylvester matrix has the following property [Lai69]:

Theorem 4.8.1

(Suppose the Sylvester matrix has the QR decomposition as S(f, g) = QR where Q is orthogonal and R is upper triangular. Then the last non-zero row of R gives the coefficients of the GCD of f and g. Precisely, let Rd be the last non-zero line of R, then the GCD of f and g can be written as

We can check the property with a simple example. Suppose that

then the Sylvester matrix is

Compute the QR decomposition matrices as

The last line non-zero line of R is by the above theorem, the GCD of f(x) and g(x) should be

One can find GCD(f, g) = x + 1 which is exactly equal to up to a non-zero constant scalar.

When small perturbations are applied to the coefficients of the polynomials, the GCD obtained after the perturbation may be different from the original GCD. But for the engineering purposes, the new GCD should be close to the original GCD since only small perturbations are introduced. It is difficult to use the Euclidean algorithm numerically. The QR decomposition focuses on matrix computations and gives a way to compute a numerical approximation. Add perturbations to the two polynomials f and g, we have

Using the numerical GCD method based on QR factoring [CWZ04], one can find an approximate GCD as

Thus, the approximate GCD is x + 0.99952 1892859819.

4.9 Exercises

1.Consider the vectors a = (1, 5) and b = (3, 4) in 2. Find the inner product of these two vectors and find the angle between them.

2.Find k so that (1, 2, k, 3) and (3, k, 7, 5) are orthogonal vectors in 4.

3.Let W be the subspace of 4 spanned by (1, 2, 3, −1) and (2, 4, 7, 2). Find a basis of the orthogonal complement W⊥ of W.

4.Let S consist of the following vectors in 4:

(1, 1, 0, −1), (1, 2, 1, 3), (1, 1, −9, 2), (16, −13, 1, 3).

Is S orthogonal and a basis of 4? If so, find the coordinate of vector (a, b, c, d) in 4 relative to the basis S.

5.Find an orthogonal basis, and an orthonormal basis for the subspace spanned by the following vectors:

(1, 1, 1, 1), (1, 1, 2, 4), (1, 2, −4, −3).

6.Project the vector orthogonally onto the line

7.In 4, project v = onto the line

8.Compute the orthogonal projection matrix Q for the subspace W ⊂ 4 spanned by (1, 2, 0, 0) and (1, 0, 1, 1). Then find the image of the orthogonal projection of the vector (3, 2, 1, 5) onto W.

9.Compute the reflection matrix for reflection across the plane x + y –

z = 0. Then find the image of the reflection of the vector (1, 2, 3).

10.Compute the QR decomposition of matrix A =

11.Compute the QR decomposition of matrix A =

12.Compute the SVD decomposition of matrix A =

13.Compute the SVD decomposition of matrix A =

14.Compute the SVD decomposition of matrix A =

C H A P T E R 5

MATRIX DECOMPOSITION

5.1 Decomposition over ℝ or ℂ

In linear algebra, a matrix decomposition or matrix factorization is a factorization of a matrix into a product of matrices. There are many different matrix decompositions; each finds use among a particular class of problems. Below, we provide a list of common decompositions based on their applications.

5.1.1 Decompositions to Solve Linear Systems

In general, the following decompositions are commonly used to solve systems of linear equations.

1.LU decomposition: applicable to square matrix A

where L is lower triangular and U is upper triangular.

2.Rank factorization: applicable to m × n matrix A of rank r

where C is an m × r full column rank matrix and F is an r × n full row rank matrix.

3.Cholesky decomposition: applicable to square, symmetric, positive definite matrix A

where L is a lower triangular matrix with positive diagonal entries. The Cholesky decomposition is unique, it is also applicable for complex Hermitian positive definite matrices.

4.QR decomposition: applicable to m × n matrix A

where Q is an orthogonal matrix of size m × m, and R is an upper triangular matrix of size m × n. For details of QR decomposition, please refer to Section 4.6.

5.1.2 Decompositions Based on Eigenvalues

1.Eigen-decomposition, also called spectral decomposition: applicable to square matrix A with distinct eigenvectors (not necessarily distinct eigenvalues).

where Λ is a diagonal matrix formed from the eigenvalues of A, and the columns of Q are the corresponding eigenvectors of A. For details, see Section 3.2.

2.Jordan decomposition, also called Jordan normal form, or Jordan canonical form, applicable to a square matrix A. Jordan normal form generalizes the eigen-decomposition to cases where there are repeated eigenvalues and cannot be diagonalized. For details, see Section 3.3.

3.Spectral decomposition for a real, symmetric matrix A.

where Λ is a diagonal matrix formed from the eigenvalues of A, and Q is an orthogonal matrix, whose columns are the corresponding orthonormal eigenvectors of A. For details, see Section 4.5.

4.Singular value decomposition: applicable to m × n matrix A.

where ∑ is an m × n matrix where the only non-zero entries are the nonnegative diagonal entries in non-increasing order, U and V are unitary matrices, and V∗ denotes the conjugate transpose of V (or simply the transpose, if V contains real numbers only). The diagonal elements of ∑ are called the singular values of A. For details of SVD, please refer to Section 4.7.

5.1.3 Examples

LU Decomposition

In many applications involving solving systems of linear equations, one needs to solve Ax = b for many different vectors b with a fixed nonsingular matrix A. Gaussian elimination with pivoting is the most efficient and accurate way to solve a linear system. The key component of this method is to decompose A itself.

We observe if a system is in the following form

then the system has a unique solution that is easy to obtain

On the other hand, if the system is given as a lower triangular matrix as

then the system can be solved via forward substitution and has a unique solution

Also, if the matrix is given in an upper triangular form

then the system can be solved via backward substitution and has a unique solution

LU decomposition, or LU factorization, stands for “lower upper,” which factors a matrix as the product of a lower triangular matrix and an upper triangular matrix. The LU decomposition can be viewed as the matrix form of Gaussian elimination. Let A be an n × n nonsingular square matrix. One can perform row operation on A via a sequence of elementary matrices E_1, …, Ek to obtain an upper triangular matrix

Hence,

Since each Ei is a lower triangular matrix, the product of the inverse of elementary matrices is a lower triangular matrix. Thus A can be factored as

Furthermore, if A is a nonsingular matrix, then for each L, the upper triangular matrix U is unique but an LU decomposition is not unique. There can be more than one such LU decomposition for a matrix A. For example

This is because when we compute LU decomposition by elementary transformations, the matrix U depends on the matrix L. To find out the unique LU decomposition, it is necessary to put some restriction on L and U matrices. For example, we can require all the entries of its main diagonal to be ones.

Therefore, given a system of linear equations in a matrix form

to solve the equation for x given A and b, we can decompose A = LU , then the solution is done in two logical steps: first, solve the equation Ly = b for y via forward substitution; then solve the equation Ux = y for x via backward substitution.

Remark 5.1.1: Not all non-singular matrices have an LU factorization. It is a proven result [HJ85] that: A matrix A = (aij)1 ≤ i, j ≤ n has an LU factorization if and only if the leading principal submatrices Ak of A are nonsingular for k = 1, …, n.

The leading principal submatrix Ak = (aij)1 ≤ i, j ≤ k consists of the entries from the first k rows and k columns of A.

Rank Decomposition

Given an m × n matrix A of rank r, a rank decomposition or rank factorization of A is a product A = CF , where C is an m × r matrix and F is an r × n matrix.

Every finite-dimensional matrix has a rank decomposition. Since the rankA = r, there are r linearly independent columns in A; equivalently, the dimension of the column space of A is r. Thus, let c_1, …, cr be any basis for the column space of A and let C = [c_1, …, cr]. Therefore, every column vector of A is a linear combination of the columns of C. That is, if

then the j-th column of A can be expressed as

where fij are the scalar coefficients of aj in terms of the basis c_1, …, cr. This implies that A = CF, where is an r × n matrix. For example,

Then C is obtained by removing the third column of A, and F is formed by removing the last row of zeroes in the reduced echelon form. Thus

We note that the rank decomposition is not unique. If A = C_1F_1 is a rank factorization, then C_2 = C_1R and F_2 = R−1F_1 gives another rank factorization for any invertible r × r matrix R.

Cholesky Decomposition

In linear algebra, the Cholesky decomposition or Cholesky factorization is a decomposition of a Hermitian, positive-definite matrix A into the product A = LL∗ of a lower triangular matrix L with real and positive diagonal entries and its conjugate transpose L∗. If A has real entries, L has real entries as well, and A = LLT.

Every Hermitian positive-definite matrix (and thus also every real-valued symmetric positive-definite matrix) has a unique Cholesky decomposition, that is, there is only one lower triangular matrix L with strictly positive diagonal entries such that A = LL∗. If the matrix A is Hermitian and positive semi-definite, then it still has a decomposition of the form A = LL∗ where the diagonal entries of L are allowed to be zero. However, the decomposition need not be unique when A is positive semi-definite.

The algorithm to calculate the matrix L for the decomposition is a modified version of Gaussian elimination. The recursive algorithm starts with i := 1 and

At step i, after performing Gaussian elimination to matrix A_1, the matrix Ai has the following form:

where i−1 denotes the identity matrix of dimension i − 1. Define the matrix Li by

then

where

Repeat this for i = 1, …, n, and An+1 = . Hence, the lower triangular matrix

Mathematica [Wol15], Maple [Map16], MATLAB [TM], Sage [SJ05], and many other computer software packages can compute matrix decompositions. MATLAB is a popular multi-paradigm numerical computing environment developed by Math Works. MATLAB allows matrix manipulations, plotting of functions and data, implementation of algorithms, creation of user interfaces, and interfacing with programs written in other languages, including C, C++, C#, Java, Fortran, and Python. MATLAB is a power tool for both students and engineers. Below, we use MATLAB to create a Pascal’s matrix, then perform LU decomposition, QR decomposition, and Cholesky decomposition for this Pascal’s matrix.

>>X=pascal(4) %generate a Pascal’s matrix

X =

1   1   1   1

1   2   3   4

1   3   6  10

1   4  10  20

>> [L,U]=lu(X) %LU decomposition

L =

1.0000         0         0         0

1.0000    0.3333    1.0000         0

1.0000    0.6667    1.0000    1.0000

1.0000    1.0000         0         0

U =

1.0000    1.0000    1.0000     1.0000

0    3.0000    9.0000    19.0000

0         0   -1.0000    -3.3333

>> [Q,R]=qr(X) %QR decomposition

Q =

-0.5000     0.6708     0.5000     0.2236

-0.5000     0.2236    -0.5000    -0.6708

-0.5000    -0.2236    -0.5000     0.6708

-0.5000    -0.6708     0.5000    -0.2236

R =

-2.0000    -5.0000    -10.0000    -17.5000

0    -2.2361     -6.7082    -14.0872

0          0      1.0000      3.5000

0          0           0     -0.2236

>> R=chol(X) %Cholesky decomposition, where R=L^*

R =

1   1   1   1

0   1   2   3

0   0   1   3

0   0   0   1

Since we investigated decomposition associated with the eigenvalues in previous chapters, below we only provide a few examples.

Eigen-decomposition

EXAMPLE 5.1.1

Taking a matrix A = Since

There are two eigenvalues λ_1 = 1 and λ_2 = 3.

If λ = 1, then Av = 1v gives v =

If λ = 3, then Av = 3v gives v =

Thus the eigen-decomposition is

Jordan Canonical Decomposition

EXAMPLE 5.1.2

Suppose an n × n matrix A is of the form

Check that

We check that the dimension of the eigenspace corresponding to the eigenvalue 4 is 1, so A is not diagonalizable. However, there is an invertible matrix P such that A = P−1J P,

where where J is the Jordan normal form of A.

Of course, we can hand compute matrices J and P for Example 5.1.2, but many computer software packages have built in code to complete this task. The following is a Sage [SJ05] code for the computation of Jordan canonical form in Example 5.1.2.

A=matrix(QQ, [[5, 4, 2, 1],[0,1,-1,-1], [-1,-1,3,0],[1,1,-1,2]])

A.jordan_form(transformation=True)

([2|0|0 0]

[-+-+---]

[0|1|0 0]

[-+-+---]

[0|0|4 1]

[0|0|0 4],

[ 1  1  1  1]

[-1 -1  0  0]

[ 0  0 -1  0]

[ 1  0  1  0])

Spectral Decomposition

EXAMPLE 5.1.3

Let A = We continue with Sage code to obtain the minimal polynomial, eigenvalues, and eigenvectors.

B=matrix(QQ, [[3, 2],[2,3]])

B.minpoly()

x^2 - 6*x + 5

B.eigenvalues()

[5, 1]

B.eigenmatrix_left()

([5 0],[0 1], [ 1 1],[ 1 -1])

Hence the eigen-decomposition is

Since A is a symmetric matrix, we can compute an orthonormal basis to obtain a spectral decomposition

5.2 Iterative Methods to Solve Linear Systems Numerically

Solving linear systems or matrix equations is a classical problem in matrix computations. In general, there are four methods to solve a linear system.

1.Use Cramer’s rule to solve the system, if the matrix is a full-rank square matrix.

2.Compute the inverse or pseudoinverse of the system matrix.

3.Use matrix decomposition methods.

4.Use iterative methods.

Note that computing and applying the inverse matrix is much more expensive and often numerically less stable than applying one of the other algorithms. Hence the first two options are not used in matrix computations, especially for high-dimensional matrices.

The inverse of nonsingular square matrix A can be computed by the methods like Gauss-Jordan or LU decomposition. If A is not square, then ATA and AAT become square. Hence, it may be possible to apply Gauss-Jordan or LU decomposition to compute the inverse of ATA or AAT. Otherwise, a pseudoinverse (an inverse-like matrix) can be computed by singular value decomposition (SVD). Please see Section 5.1.1 for details of using ma- trix decompositions to solve linear systems.

In this section, we will focus on iterative methods to solve Ax = b. A method of this type is a mathematical procedure that begins with an approximation to the solution, x_0, then generates a sequence of improved approximations x_1, …, xn that converge to the exact solution. This approach is appealing in engineering because it can be stopped as soon as the n-th approximation has an acceptable precision. Iterative methods are often useful for large and sparse system, but iterative methods can be unreliable; since for some problems they may have slow convergence, or they may not converge at all. There are two fundamental iterative methods: the Jacobi method and the GaussSeidel method.

5.2.1 Jacobi Iiterative Method

First, the Jacobi iterative method is an algorithm for determining the solutions of a diagonally dominant system of linear equations. A square matrix A = (aij) where aij denotes the entry in the i-th row and j-th column is said to be diagonally dominant if

Let Ax = b be a square system of n linear equations, where:

Then A can be decomposed into a diagonal component D, and the remainder R:

We note that R = L + U where L and U are the strictly lower and upper parts of A.

Then the solution is then obtained iteratively via

where x(k) is the k-th iteration of x and x(k+1) is the (k + 1)-th iteration of x. The the solution for the system is

We will use the following example to illustrate the method.

EXAMPLE 5.2.1

Let

where x(0) is the initial approximation. Then, the above procedure yields

The iteration gives

5.2.2 Gauss-Seidel iterative method

The Gauss-Seidel iterative method is very similar to the Jacobi method. But unlike the Jacobi method, the Gauss-Seidel method includes successive displacement. That is, the computation of x(k+1) uses only the elements of that have already been computed, and only the elements of x(k) that have not yet to be advanced to the (k + 1)-th iteration.

Let Ax = b be a square system of n linear equations, where:

Then A can be decomposed into its lower triangular component and its strictly upper triangular component given by:

The system of linear equations Ax = b can be rewritten as:

The Gauss-Seidel method now solves the left-hand side of the above expression for x, using previous value for x on the right hand side:

where and

Using the lower triangular matrix L∗, the elements of x(k+1) can be computed sequentially using forward substitution:

The procedure terminates when an acceptable precision is achieved.

We will use the following example to illustrate this method.

EXAMPLE 5.2.1

Let Ax = b be the following:

where x(0) is the initial approximation. Then

The iteration formula gives:

The algorithm converges to the exact solution, and we check that:

5.3 Matrix over Principle Ideal Domain

5.3.1 Matrix Decomposition over PID

In abstract algebra, a principal ideal domain, or PID, is an integral domain in which every ideal is principal, i.e., can be generated by a single element. More generally, a principal ideal ring is a non-zero commutative ring whose ideals are principal. The distinction is that a principal ideal ring may have zero divisors whereas a principal ideal domain cannot.

Principal ideal domains behave somewhat like the integers, with respect to divisibility: any element of a PID has a unique decomposition into prime elements; any two elements of a PID have a greatest common divisor. If gcd(x, y) = 1 for x and y in a PID, then every element of the PID can be written in the form ax + by for some a, b in this PID.

Furthermore, one of the important properties of a PID is that if (a_1) ⊆ … ⊆ (a_2) ⊆ …is an increasing sequence of ideals, then there is an n such that (an) = (an+1) = …. To see this, we note that ∪(ai) is also an ideal, and must be generated by an element b in a PID. Therefore, ∪(ai) = (b), and this forces (an) = (an+1) = … = (b).

In this section, we will discuss the structure theorem for finitely generated modules over a principal ideal domain from the point of view of matrices.

Let R be a principal ideal domain and let M be a finitely generated R-module. If {m_1, …, mn} is a set of generators of M, then we have a surjective R-module homomorphism

Let K = ker ϕ = then M > Rn/K. It is known that K is finitely generated. Suppose that {a_1, …, am} ⊆ Rn is a generating set for K, where ai = (ai_1, ai_2, …, ain), then we will refer to the matrix (aij) over R as the relation matrix for M relative to the generating set {m_1, …, mn} of M and the generating set {a_1, …, am} ⊆ Rn of K. In the language of commutative algebra, K is call the syzygy module of the generating set {m_1, …, mn} of M.

Lemma 5.3.1 Let M be a finitely generated R-module, with ordered generating set {m_1, …, mn}. Suppose that the submodule K is generated by {a_1, …, am}. Let A be the m × n relation matrix relative to these generators.

1.Let P ∈ Mm×m(R) be an invertible matrix. If [l_1, …, lm] are the rows of PA, then they generate K, and so PA is the relation matrix relative to [m_1, …, mn] and [l_1, …, lm].

2.Let Q ∈ Mn×n(R) be an invertible matrix and write Q−1 = (qij) If

then [t_1, …, tn] is a generating set for M and the rows of AQ generate the corresponding relation submodule. Therefore, AQ is a relation matrix relative to [t_1, …, tn].

3.Let P and Q be m × m and n × n invertible matrices, respectively. If B = PAQ, then B is the relation matrix relative to an appropriate ordered set of generators of M and of the corresponding relation submodule.

Proof:

1.Notice the matrix multiplication gives

In addition that P is an invertible matrix, A = P−1[l_1, …, Im]T. Hence, the rows of the matrix A can be expressed in terms of {l_1, …, lm}. Matrix A can be considered as a relation matrix relative to the generating set {m_1, …, m} ⊂ M and {l_1, …, lm} ⊂ Rn.

2.Notice the matrix multiplication gives

Thus, {t_1, …, tn} is a generating set for M. In addition,

yields that the rows of AQ generate the corresponding relation submodule. Therefore, AQ is a relation matrix relative to {t_1, …, tn}.

3.The claim follows directly from (1) and (2).

Proposition 5.3.1 Suppose that A is a relation matrix for an R-module M. If there are invertible matrices P and Q for which

is a diagonal matrix, then

Proof: The matrix PAQ above is the relation matrix for an ordered generating set [m_1, …, mn] relative to a relation submodule generated by the rows of PAQ. If f : Rn → M is a homomorphism such that then K = ker(f). Thus, Since K is also the kernel of the surjective R-module homomorphism such that g(r_1, …, rn) = (r_1 + (a_1), …, rn + (an)). Thus,

Definition 5.3.1

Let R be a principal ideal domain and let A be a p × n matrix with entries in R. We say that A is in Smith normal form if there are non-zero a_1, …, am ∈ R such that ai | ai+1 for each i < m, and

Theorem 5.3.1

If A is a matrix with entries in a principal ideal domain R, then there are invertible matrices P and Q over R such that PAQ is in Smith normal form.

Proof: We will only illustrate the argument for the case of 2 × 2 matrix. Consider and let e_0 = gcd(a, c), and hence e_0 = ax + cy for some x, y ∈ R. Thus

since

and

An similar treatment applied to the first row via multiplying on the right by an invertible matrix and obtain a matrix to the form where e_1 = gcd(e_0, u).

Continuing this process, alternating between the first row and the first column, will produce a sequence of elements e_0, e_1, …such that ei+1 | ei, i ≥ 0. As ideals, this says (e_0) ⊆ (e_1) ⊆ … ⊆ (en) = …= (e), since increasing sequence of principal ideals stabilizes in PID. Thus, in finitely many steps multiplying by invertible matrices Pi and Qi, we derive

Thus, one more row or column operation, we have a diagonal matrix

Now, let g = gcd(e, D), then e = ge′ and D = gD′ and there exists m, n ∈ R such that g = em + Dn, hence,

Thus,

and we conclude that there are invertible matrices P and Q over R such that PAQ is in Smith normal form.

A consequence of the existence of a Smith normal form is the following structure theorem of finitely generated modules over PID.

Corollary 5.3.1: Suppose M is a finitely generated module over a PID R, then there are elements a_1, …, am ∈ R such that ai | ai+1, i = 1, …, m − 1, and t ∈ ≥ 0 such that M ≅ R/(a_1)⊕ … ⊕ R/(am) ⊕ Rt.

Proof: Let A be a relation matrix for M, and let B be its Smith normal form, i.e., for some invertible matrices P, Q,

Proposition 5.3.1 implies

Hence, we proved our claim.

It is known that a polynomial ring in x over the field , [x] is a PID, and in the remainder of this section, we will focus on the case when R = [x]. Let A ∈ Mn() be an n × n matrix, then we can consider n as a finitely generated [x]-module via

Let e_1, …, en be the standard basis for n. Now, we consider a [x]-module homomorphism:

Note, if A = (aij), then

thus

Hence, x − A is a relation matrix relative to [e_1, …, en].

From now on, let v_1, …, vn be the rows of x − AT , and let E_1, …, En be the standard basis vectors of [x]n.

Lemma 5.3.2: Let Then there are gi(x) ∈ [x] and bi ∈ such that

Proof: We will prove the claim by induction on

If m = 0, then fi(x) are constant, hence let bi = fi(x), and the claim is true.

Assume that for m > 0, and the claim is true for polynomial vectors [f_1(x), …, fn(x)] whose maximal degree is no more than m. Hence, for i = 1, …, n. by division algorithm, fi(x) = qi(x)(x − aii) + ri, where deg(qi(x)) ≤ deg(fi(x)) − 1, ri ∈ . Consider

Notice, that the entries of the second polynomial vector has degree strictly less than deg(f_1(x)). Repeating this process for each fi(x), we have

Thus, the claim is true by induction.

Proposition 5.3.2. If ϕ is a [x]-module homomorphism defined by

then ker(ϕ) is generated by the rows of x − AT.

Proof: Let M be the submodule of [x]n generated by v_1, …, vn, the rows of x − AT. To show M = ker(ϕ), we first note that vi ∈ ker(ϕ), thus M ⊆ ker(ϕ). Thus, we only need to show that ker(ϕ) ⊆ M .

Let Ei ∈ ker(ϕ), and by Lemma 5.3.2,

Since vi ∈ ker(ϕ), we must have that Moreover,

Thus,

Thus, ker(ϕ) ⊆ M.

Therefore, we conclude ker(ϕ) = M.

Since [x]/(1) is the zero module, with the above notation, we can conclude that

Corollary 5.3.2: If

is the Smith normal form of A, then as a [x]-module,

The invariant factors of n are f_1(x), …, fm(x).

It is difficult to hand compute Smith normal form. Many computer algebra systems have build-in code to compute Smith normal form. Below, we present one simple example via Maple. In this example, we first create a matrix Ax over the ring ℝ[x], then, we compute the Smith normal form of matrix Ax.

>Ax:= Matrix([[1,2*x,2*x^22*x],[1,6*x,6*x^26*x],[1,3,x]]);

>S := SmithForm(Ax);

5.4 Exercises

1.Find LU decompositions for the matrices

2.Verify the following Cholesky decomposition

3.Verify the following Cholesky decomposition

4.Verify the following QR decomposition

5.Find LU, Cholesky, QR decomposition for the matrix A =

6.Find eigenvalue decompositions of the following matrices if possible:

7.Find a SVD of the matrix

8.Consider matrix A = Determine a SVD. This decomposition is not unique, and find another SVD.

9.Suppose A is an n × n matrix over the complex numbers, and A = S∑V∗ is a SVD. Find an eigenvalue decomposition of the Hermitian

10.Find a Jordan decomposition of the matrix A =

11.Write the matrix A = in Jordan canonical form.

12.Apply Jacobi iterative method to solve

13.Apply Jacobi iterative method to solve

Continue iterations until two successive approximations are identical when rounded to three significant digits.

14.Apply the Gauss-Seidel iterative method to solve

Continue iterations until two successive approximations are identical when rounded to three significant digits.

15.Apply other methods to solve

BIBLIOGRAPHY

[CWZ04]

R. M. Corless, S. M. Watt, and Lihong Zhi, Qr factoring to compute the gcd of univariate approximate polynomials, IEEE Transactions on Signal Processing 52 (2004), no. 12, 3394–3402.

[HJ85]

Roger A. Horn and Charles R. Johnson, Matrix analysis, Cambridge University Press, Boston, United States, 1985.

[Lai69]

M. A. Laidacker, Another theorem relating sylvester’s matrix and the greatest common divisor, Mathematics Magazine 42 (1969), no. 3, 126–128.

[Map16]

Maplesoft, Maple, a division of Waterloo Maple Inc., Waterloo, Ontario, 2016.

[R C13]

R Core Team, R: A language and environment for statistical computing, R Foundation for Statistical Computing, Vienna, Austria, 2013.

[SJ05]

William Stein and David Joyner, SAGE: System for algebra and geometry experimentation, Communications in Computer Algebra (SIGSAM Bulletin) (July 2005), http://www.sagemath.org.

[Tiw04]

Ashish Tiwari, Termination of linear programs, Computer Aided Verification: 16th International Conference, CAV 2004, Boston, MA, USA, July 13–17, 2004. Proceedings (Rajeev Alur and Doron A. Peled, eds.), Springer-Verlag, Berlin Heidelberg, 2004, pp. 70–82.

[TM]

The MathWorks, Inc. Matlab 8.0 and statistics toolbox 8.1, Natick, Massachusetts, United States.

[Wol15]

Wolfram, Mathematica, 10.3 ed., Wolfram Research, Inc., Champaign, Illinois, 2015, https://www.wolfram.com.

[WWK01]

Wenping Wang, Jiaye Wang, and Myung-Soo Kim, An alge-braic condition for the separation of two ellipsoids, Comput. Aided Geom. Des. 18 (2001), no. 6, 531–539.

INDEX

R-linear map, 36

q-ary code, 24

A

affine geometry, 50

affine transformation, 50

algebra homomorphism, 48

algebra isomorphism, 48

algebraic multiplicity, 63

associative algebra, 47

B

basis, 11

bijective, 36

bilinear, 107

binary code, 24–25, 27

C

characteristic equation, 61

characteristic polynomial, 61

check vector, 24

Cholesky decomposition, 145–150

code vector, 25

code vectors, 24

codewords, 24

column rank, 41

companion matrix, 63

coordinate of v relative to the ordered basis, 14

coordinate vector of v relative to the ordered basis, 14

D

decoding, 24

determinant, 19–20

dimension, 13

direct product, 6

direct sum, 6, 71

E

eigen-decomposition, 74

eigenvalue, 61

encoding, 24

epimorphism, 36

error-correcting, 26

Euler angles, 52

extended binary Golay code, 29

F

field, 2

finitely generated, 8

G

general linear group, 49

generalized companion matrix, 85–87

generator matrix, 25, 27

geometric multiplicity of the eigenvalue, 63

Golay codes, 29

group, 49

H

Hamel basis, 12

Hamming codes, 26

Hermitian, 4

Hermitian matrix, 123

I

independent, 71

injective, 32

inner product, 107

inner product space, 107–109

invariant under a linear operator, 69

invertible, 48

isomorphic, 36

isomorphic algebras, 48

isomorphism, 36

J

Jordan block, 76

Jordan canonical form, 76

Jordan normal form, 76

K

kernel, 36

L

left R-module, 5

left-singular vector, 131

linear code, 24

linear combination, 8

linear operator, 35

linear space, 3

linear transformation, 35–38

linearly dependent, 10

linearly independent, 10

LU Decomposition, 142–145

M

matrix, 4

matrix relative to the ordered bases, 45

matrix representation, 43, 55

module homomorphism, 35–36

monic, 63

monomorphism, 36

N

non-singular linear transformation, 37

null space, 30, 36–37

nullity, 38–43

O

one-to-one, 36

ordered basis, 14

orthogonal, 107–139

orthogonal basis, 108

orthogonal complement, 111

orthogonal matrix, 119

orthogonal projection, 119–122

orthonormal basis, 108

P

parity check code, 24

parity check matrix, 25

PID, 154

positive definite, 107, 125

principal ideal domain, 154

principal ideal ring, 154

projective space, 52

projectivities, 52

Q

QR decomposition, 126

QR factorization, 126

R

rank, 38–43

rank decomposition, 145

right-singular vector, 131

rigid motion, 50

ring, 2

rotation, 92–93

row rank, 41

S

scaling, 91–92

self-adjoint, 4

self-adjoint matrix, 123

set, 1

short exact sequence, 43

singular value, 130

singular value decomposition, 130–133

Smith normal form, 157

span, 8–11

spanning sequence, 8

Spectral decomposition, 125

spectrum, 66

split, 43

standard generator matrix, 27

standard parity check matrix, 27

subset, 1

subspace, 4

sum, 5

superset, 1

surjective, 36

SVD, 130–133

SVD, singular value decomposition, 130–133

symmetric, 107, 122–126

syzygy module, 155

T

ternary code, 24

trace, 81–82

translation, 91

U

union of the two sequences, 9

unitary matrix, 126

V

Vandermonde determinant, 64

Vandermonde matrix, 64

Vanderm onde polynomial, 64

vector space, 3