ADVANCED
LINEAR ALGEBRA

www.pdfgrip.com


TEXTBOOKS in MATHEMATICS
Series Editor: Ken Rosen
PUBLISHED TITLES
ABSTRACT ALGEBRA: AN INQUIRY-BASED APPROACH
Jonathan K. Hodge, Steven Schlicker, and Ted Sundstrom
ABSTRACT ALGEBRA: AN INTERACTIVE APPROACH
William Paulsen
ADVANCED CALCULUS: THEORY AND PRACTICE
John Srdjan Petrovic
ADVANCED LINEAR ALGEBRA
Nicholas Loehr
COLLEGE GEOMETRY: A UNIFIED DEVELOPMENT
David C. Kay
COMPLEX VARIABLES: A PHYSICAL APPROACH WITH APPLICATIONS AND MATLAB®
Steven G. Krantz
ESSENTIALS OF TOPOLOGY WITH APPLICATIONS
Steven G. Krantz
INTRODUCTION TO ABSTRACT ALGEBRA
Jonathan D. H. Smith
INTRODUCTION TO MATHEMATICAL PROOFS: A TRANSITION
Charles E. Roberts, Jr.
INTRODUCTION TO PROBABILITY WITH MATHEMATICA®, SECOND EDITION
Kevin J. Hastings
LINEAR ALBEBRA: A FIRST COURSE WITH APPLICATIONS

Larry E. Knop
LINEAR AND NONLINEAR PROGRAMMING WITH MAPLE™: AN INTERACTIVE, APPLICATIONS-BASED
APPROACH
Paul E. Fishback
MATHEMATICAL AND EXPERIMENTAL MODELING OF PHYSICAL AND BIOLOGICAL PROCESSES
H. T. Banks and H. T. Tran
ORDINARY DIFFERENTIAL EQUATIONS: APPLICATIONS, MODELS, AND COMPUTING
Charles E. Roberts, Jr.
REAL ANALYSIS AND FOUNDATIONS, THIRD EDITION
Steven G. Krantz
www.pdfgrip.com


TEXTBOOKS in MATHEMATICS

ADVANCED
LINEAR ALGEBRA

NICHOLAS LOEHR
Virginia Polytechnic Institute and State University
Blacksburg, USA

www.pdfgrip.com


CRC Press
Taylor & Francis Group
6000 Broken Sound Parkway NW, Suite 300
Boca Raton, FL 33487-2742
© 2014 by Taylor & Francis Group, LLC

CRC Press is an imprint of Taylor & Francis Group, an Informa business
No claim to original U.S. Government works
Version Date: 20140306
International Standard Book Number-13: 978-1-4665-5902-8 (eBook - PDF)
This book contains information obtained from authentic and highly regarded sources. Reasonable efforts have been
made to publish reliable data and information, but the author and publisher cannot assume responsibility for the validity of all materials or the consequences of their use. The authors and publishers have attempted to trace the copyright
holders of all material reproduced in this publication and apologize to copyright holders if permission to publish in this
form has not been obtained. If any copyright material has not been acknowledged please write and let us know so we may
rectify in any future reprint.
Except as permitted under U.S. Copyright Law, no part of this book may be reprinted, reproduced, transmitted, or utilized in any form by any electronic, mechanical, or other means, now known or hereafter invented, including photocopying, microfilming, and recording, or in any information storage or retrieval system, without written permission from the
publishers.
For permission to photocopy or use material electronically from this work, please access www.copyright.com (http://
www.copyright.com/) or contact the Copyright Clearance Center, Inc. (CCC), 222 Rosewood Drive, Danvers, MA 01923,
978-750-8400. CCC is a not-for-profit organization that provides licenses and registration for a variety of users. For
organizations that have been granted a photocopy license by the CCC, a separate system of payment has been arranged.
Trademark Notice: Product or corporate names may be trademarks or registered trademarks, and are used only for
identification and explanation without intent to infringe.
Visit the Taylor & Francis Web site at

and the CRC Press Web site at


www.pdfgrip.com


Dedication
This book is dedicated

to Nanette
and Olivia

and Heather
and Linda
and Zoe.

www.pdfgrip.com


This page intentionally left blank

www.pdfgrip.com


Contents

Preface

I

xvii

Background on Algebraic Structures

1 Overview of Algebraic Systems
1.1 Groups . . . . . . . . . . . . .
1.2 Rings and Fields . . . . . . . .
1.3 Vector Spaces . . . . . . . . .
1.4 Subsystems . . . . . . . . . . .
1.5 Product Systems . . . . . . . .
1.6 Quotient Systems . . . . . . .
1.7 Homomorphisms . . . . . . . .

1.8 Spanning, Linear Independence,
1.9 Summary . . . . . . . . . . . .
1.10 Exercises . . . . . . . . . . . .

1

. . . . . . . . . . . . .
. . . . . . . . . . . . .
. . . . . . . . . . . . .
. . . . . . . . . . . . .
. . . . . . . . . . . . .
. . . . . . . . . . . . .
. . . . . . . . . . . . .
Basis, and Dimension
. . . . . . . . . . . . .
. . . . . . . . . . . . .

2 Permutations
2.1 Symmetric Groups . . . . . . . . . . . . . .
2.2 Representing Functions as Directed Graphs
2.3 Cycle Decompositions of Permutations . .
2.4 Composition of Cycles . . . . . . . . . . . .
2.5 Factorizations of Permutations . . . . . . .
2.6 Inversions and Sorting . . . . . . . . . . . .
2.7 Signs of Permutations . . . . . . . . . . . .
2.8 Summary . . . . . . . . . . . . . . . . . . .
2.9 Exercises . . . . . . . . . . . . . . . . . . .

.
.

.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.


.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.

.
.
.

.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.

.
.
.
.

.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.

.

.
.
.
.
.
.
.
.
.

3
3
4
6
7
8
9
11
13
15
17

.
.
.
.
.
.
.
.

.

.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.

.

.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.

.

.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.

.

.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.

.

.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.

.

.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.

23
23
24
24
26
27
28
29

30
30

3 Polynomials
3.1 Intuitive Definition of Polynomials . . . . . .
3.2 Algebraic Operations on Polynomials . . . .
3.3 Formal Power Series and Polynomials . . . .
3.4 Properties of Degree . . . . . . . . . . . . . .
3.5 Evaluating Polynomials . . . . . . . . . . . .
3.6 Polynomial Division with Remainder . . . .
3.7 Divisibility and Associates . . . . . . . . . .
3.8 Greatest Common Divisors of Polynomials .
3.9 GCDs of Lists of Polynomials . . . . . . . .
3.10 Matrix Reduction Algorithm for GCDs . . .
3.11 Roots of Polynomials . . . . . . . . . . . . .
3.12 Irreducible Polynomials . . . . . . . . . . . .
3.13 Factorization of Polynomials into Irreducibles
3.14 Prime Factorizations and Divisibility . . . .

.
.
.
.
.
.
.
.
.
.
.

.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.

.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.

.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.

.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.

.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.

.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.

.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.

.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.

.
.
.

35
35
36
37
39
40
41
43
44
45
46
48
49
51
52
vii

www.pdfgrip.com


viii

Contents
3.15
3.16
3.17

3.18
3.19
3.20
3.21
3.22

II

Irreducible Polynomials in Q[x] . . . . . . . .
Irreducibility in Q[x] via Reduction Mod p .
Eisenstein’s Irreducibility Criterion for Q[x] .
Kronecker’s Algorithm for Factoring in Q[x]
Algebraic Elements and Minimal Polynomials
Multivariable Polynomials . . . . . . . . . .
Summary . . . . . . . . . . . . . . . . . . . .
Exercises . . . . . . . . . . . . . . . . . . . .

.
.
.
.

.
.
.
.
.
. .
. .
. .


.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.

.
.

.
.
.
.
.
.

.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.

.
.
.
.
.

.
.
.

.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.


.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.

.
.

.
.
.
.
.
.

.
.
.
.
.
.
.
.

Matrices

53
54
54
55
56
58
60
62

71

4 Basic Matrix Operations

4.1 Formal Definition of Matrices and Vectors . . .
4.2 Vector Spaces of Functions . . . . . . . . . . . .
4.3 Matrix Operations via Entries . . . . . . . . . .
4.4 Properties of Matrix Multiplication . . . . . . .
4.5 Generalized Associativity . . . . . . . . . . . . .
4.6 Invertible Matrices . . . . . . . . . . . . . . . . .
4.7 Matrix Operations via Columns . . . . . . . . .
4.8 Matrix Operations via Rows . . . . . . . . . . .
4.9 Elementary Operations and Elementary Matrices
4.10 Elementary Matrices and Gaussian Elimination
4.11 Elementary Matrices and Invertibility . . . . . .
4.12 Row Rank and Column Rank . . . . . . . . . . .
4.13 Conditions for Invertibility of a Matrix . . . . .
4.14 Summary . . . . . . . . . . . . . . . . . . . . . .
4.15 Exercises . . . . . . . . . . . . . . . . . . . . . .
5 Determinants via Calculations
5.1 Matrices with Entries in a Ring . . . . . . . .
5.2 Explicit Definition of the Determinant . . . . .
5.3 Diagonal and Triangular Matrices . . . . . . .
5.4 Changing Variables . . . . . . . . . . . . . . .
5.5 Transposes and Determinants . . . . . . . . .
5.6 Multilinearity and the Alternating Property .
5.7 Elementary Row Operations and Determinants
5.8 Determinant Properties Involving Columns . .
5.9 Product Formula via Elementary Matrices . .
5.10 Laplace Expansions . . . . . . . . . . . . . . .
5.11 Classical Adjoints and Inverses . . . . . . . . .
5.12 Cramer’s Rule . . . . . . . . . . . . . . . . . .
5.13 Product Formula for Determinants . . . . . . .
5.14 Cauchy–Binet Formula . . . . . . . . . . . . .

5.15 Cayley–Hamilton Theorem . . . . . . . . . . .
5.16 Permanents . . . . . . . . . . . . . . . . . . . .
5.17 Summary . . . . . . . . . . . . . . . . . . . . .
5.18 Exercises . . . . . . . . . . . . . . . . . . . . .

www.pdfgrip.com

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.

.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.

.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.

.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.

.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.

.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.

.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.

.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.


.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

73
73
74
75
77
78
79
81
83
84
86
87
87

89
90
92

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.


.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.


.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

101
101
102
103
103
104
106
107
109
109
111

113
114
115
116
118
120
121
123

.
.
.
.
.
.
.
.


Contents

ix

6 Concrete vs. Abstract Linear Algebra
6.1 Concrete Column Vectors vs. Abstract Vectors . . . .
6.2 Examples of Computing Coordinates . . . . . . . . .
6.3 Concrete vs. Abstract Vector Space Operations . . . .
6.4 Matrices vs. Linear Maps . . . . . . . . . . . . . . . .
6.5 Examples of Matrices Associated with Linear Maps .
6.6 Vector Operations on Matrices and Linear Maps . . .

6.7 Matrix Transpose vs. Dual Maps . . . . . . . . . . . .
6.8 Matrix/Vector Multiplication vs. Evaluation of Maps
6.9 Matrix Multiplication vs. Composition of Linear Maps
6.10 Transition Matrices and Changing Coordinates . . . .
6.11 Changing Bases . . . . . . . . . . . . . . . . . . . . .
6.12 Algebras of Matrices and Linear Operators . . . . . .
6.13 Similarity of Matrices and Linear Maps . . . . . . . .
6.14 Diagonalizability and Triangulability . . . . . . . . .
6.15 Block-Triangular Matrices and Invariant Subspaces .
6.16 Block-Diagonal Matrices and Reducing Subspaces . .
6.17 Idempotent Matrices and Projections . . . . . . . . .
6.18 Bilinear Maps and Matrices . . . . . . . . . . . . . . .
6.19 Congruence of Matrices . . . . . . . . . . . . . . . . .
6.20 Real Inner Product Spaces and Orthogonal Matrices .
6.21 Complex Inner Product Spaces and Unitary Matrices
6.22 Summary . . . . . . . . . . . . . . . . . . . . . . . . .
6.23 Exercises . . . . . . . . . . . . . . . . . . . . . . . . .

.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.

III Matrices with Special Structure

131
131
133
135
136
138
140
141
142
142
143
144
145
147
147
149
150
151
152
153
154
155
156

161

167

7 Hermitian, Positive Definite, Unitary, and Normal
7.1 Conjugate-Transpose of a Matrix . . . . . . . . . . .
7.2 Hermitian Matrices . . . . . . . . . . . . . . . . . .
7.3 Hermitian Decomposition of a Matrix . . . . . . . .
7.4 Positive Definite Matrices . . . . . . . . . . . . . . .
7.5 Unitary Matrices . . . . . . . . . . . . . . . . . . . .
7.6 Unitary Similarity . . . . . . . . . . . . . . . . . . .
7.7 Unitary Triangularization . . . . . . . . . . . . . . .
7.8 Simultaneous Triangularization . . . . . . . . . . . .
7.9 Normal Matrices and Unitary Diagonalization . . .
7.10 Polynomials and Commuting Matrices . . . . . . . .
7.11 Simultaneous Unitary Diagonalization . . . . . . . .
7.12 Polar Decomposition: Invertible Case . . . . . . . .
7.13 Polar Decomposition: General Case . . . . . . . . .
7.14 Interlacing Eigenvalues for Hermitian Matrices . . .
7.15 Determinant Criterion for Positive Definite Matrices
7.16 Summary . . . . . . . . . . . . . . . . . . . . . . . .
7.17 Exercises . . . . . . . . . . . . . . . . . . . . . . . .

Matrices
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .

. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.


.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.


.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

169
169
171
172
173
174
176
177
178
180
181
182

183
184
185
187
188
189

8 Jordan Canonical Forms
8.1 Examples of Nilpotent Maps . . . . . . . . . . .
8.2 Partition Diagrams . . . . . . . . . . . . . . . .
8.3 Partition Diagrams and Nilpotent Maps . . . . .
8.4 Computing Images via Partition Diagrams . . .

.
.
.
.

.
.
.
.

.
.
.
.

.
.

.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

195
196
197
198
199

www.pdfgrip.com


.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.


.
.
.
.


x

Contents
8.5
8.6
8.7
8.8
8.9
8.10
8.11
8.12
8.13
8.14
8.15
8.16
8.17

Computing Null Spaces via Partition Diagrams . . . .
Classification of Nilpotent Maps (Stage 1) . . . . . .
Classification of Nilpotent Maps (Stage 2) . . . . . .
Classification of Nilpotent Maps (Stage 3) . . . . . .
Fitting’s Lemma . . . . . . . . . . . . . . . . . . . . .
Existence of Jordan Canonical Forms . . . . . . . . .

Uniqueness of Jordan Canonical Forms . . . . . . . .
Computing Jordan Canonical Forms . . . . . . . . . .
Application to Differential Equations . . . . . . . . .
Minimal Polynomials . . . . . . . . . . . . . . . . . .
Jordan–Chevalley Decomposition of a Linear Operator
Summary . . . . . . . . . . . . . . . . . . . . . . . . .
Exercises . . . . . . . . . . . . . . . . . . . . . . . . .

9 Matrix Factorizations
9.1 Approximation by Orthonormal Vectors . . .
9.2 Gram–Schmidt Orthonormalization . . . . .
9.3 Gram–Schmidt QR Factorization . . . . . . .
9.4 Householder Reflections . . . . . . . . . . . .
9.5 Householder QR Factorization . . . . . . . .
9.6 LU Factorization . . . . . . . . . . . . . . . .
9.7 Example of the LU Factorization . . . . . . .
9.8 LU Factorizations and Gaussian Elimination
9.9 Permuted LU Factorizations . . . . . . . . .
9.10 Cholesky Factorization . . . . . . . . . . . .
9.11 Least Squares Approximation . . . . . . . . .
9.12 Singular Value Decomposition . . . . . . . .
9.13 Summary . . . . . . . . . . . . . . . . . . . .
9.14 Exercises . . . . . . . . . . . . . . . . . . . .

.
.
.
.
.
.

.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
. .
. .

.
.
.
.
.
.
.
.
.
.
.

.
.

.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.


.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.

.

.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.

.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.

.
.
.
.
.
.
.
.

200
201
202
203
204
205
206
207
209
210
211
212
213

.
.
.
.
.
.
.

.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.

.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.

.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.

.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.

.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.

.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.

.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.

219
220
221
222
224
226
227

229
230
232
234
235
236
237
239

10 Iterative Algorithms in Numerical Linear Algebra
10.1 Richardson’s Algorithm . . . . . . . . . . . . . . . .
10.2 Jacobi’s Algorithm . . . . . . . . . . . . . . . . . . .
10.3 Gauss–Seidel Algorithm . . . . . . . . . . . . . . . .
10.4 Vector Norms . . . . . . . . . . . . . . . . . . . . .
10.5 Metric Spaces . . . . . . . . . . . . . . . . . . . . .
10.6 Convergence of Sequences . . . . . . . . . . . . . . .
10.7 Comparable Norms . . . . . . . . . . . . . . . . . .
10.8 Matrix Norms . . . . . . . . . . . . . . . . . . . . .
10.9 Formulas for Matrix Norms . . . . . . . . . . . . . .
10.10 Matrix Inversion via Geometric Series . . . . . . .
10.11 Affine Iteration and Richardson’s Algorithm . . . .
10.12 Splitting Matrices and Jacobi’s Algorithm . . . . .
10.13 Induced Matrix Norms and the Spectral Radius . .
10.14 Analysis of the Gauss–Seidel Algorithm . . . . . .
10.15 Power Method for Finding Eigenvalues . . . . . . .
10.16 Shifted and Inverse Power Method . . . . . . . . .
10.17 Deflation . . . . . . . . . . . . . . . . . . . . . . . .
10.18 Summary . . . . . . . . . . . . . . . . . . . . . . .
10.19 Exercises . . . . . . . . . . . . . . . . . . . . . . . .


.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.


.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.


.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.


.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.


.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

245
245
246
247
248
250
250
251
252
254

255
256
257
257
259
259
261
262
262
264

.
.
.
.
.
.
.
.
.
.
.
.
.
.

www.pdfgrip.com

.
.

.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.


Contents


xi

IV The Interplay of Geometry and Linear Algebra
11 Affine Geometry and Convexity
11.1 Linear Subspaces . . . . . . . . . . . . . .
11.2 Examples of Linear Subspaces . . . . . .
11.3 Characterizations of Linear Subspaces . .
11.4 Affine Combinations and Affine Sets . . .
11.5 Affine Sets and Linear Subspaces . . . . .
11.6 Affine Span of a Set . . . . . . . . . . . .
11.7 Affine Independence . . . . . . . . . . . .
11.8 Affine Bases and Barycentric Coordinates
11.9 Characterizations of Affine Sets . . . . .
11.10 Affine Maps . . . . . . . . . . . . . . . .
11.11 Convex Sets . . . . . . . . . . . . . . . .
11.12 Convex Hulls . . . . . . . . . . . . . . .
11.13 Carath´eodory’s Theorem . . . . . . . . .
11.14 Hyperplanes and Half-Spaces in Rn . . .
11.15 Closed Convex Sets . . . . . . . . . . . .
11.16 Cones and Convex Cones . . . . . . . . .
11.17 Intersection Lemma for V-Cones . . . .
11.18 All H-Cones Are V-Cones . . . . . . . .
11.19 Projection Lemma for H-Cones . . . . .
11.20 All V-Cones Are H-Cones . . . . . . . .
11.21 Finite Intersections of Closed Half-Spaces
11.22 Convex Functions . . . . . . . . . . . . .
11.23 Derivative Tests for Convex Functions .
11.24 Summary . . . . . . . . . . . . . . . . .
11.25 Exercises . . . . . . . . . . . . . . . . . .


271

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.


.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.

273
273
274
275
276
277
278
279
280
281
282
283
284
284
286
287
289
290
291
292
293
294
296
297
298
301


12 Ruler and Compass Constructions
12.1 Geometric Constructibility . . . . . . . . . . . . .
12.2 Arithmetic Constructibility . . . . . . . . . . . . .
12.3 Preliminaries on Field Extensions . . . . . . . . .
12.4 Field-Theoretic Constructibility . . . . . . . . . .
12.5 Proof that GC ⊆ AC . . . . . . . . . . . . . . . .
12.6 Proof that AC ⊆ GC . . . . . . . . . . . . . . . .
12.7 Algebraic Elements and Minimal Polynomials . .
12.8 Proof that AC = SQC . . . . . . . . . . . . . . . .
12.9 Impossibility of Geometric Construction Problems
12.10 Constructibility of the 17-Gon . . . . . . . . . . .
12.11 Overview of Solvability by Radicals . . . . . . . .
12.12 Summary . . . . . . . . . . . . . . . . . . . . . .
12.13 Exercises . . . . . . . . . . . . . . . . . . . . . . .

.
.
.
.
.
.
.
.
.
.
.
.
.

.

.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.

.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.

.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.

.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.

.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.

.
.

.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.


309
310
311
312
314
314
316
320
322
323
324
326
327
328

13 Dual Spaces and Bilinear Forms
13.1 Vector Spaces of Linear Maps . .
13.2 Dual Bases . . . . . . . . . . . . .
13.3 Zero Sets . . . . . . . . . . . . . .
13.4 Annihilators . . . . . . . . . . . .
13.5 Double Dual V ∗∗ . . . . . . . . .
13.6 Correspondence between Subspaces

.
.
.
.
.
.


.
.
.
.
.
.

.
.
.
.
.
.

.
.
.
.
.
.

.
.
.
.
.
.

.

.
.
.
.
.

.
.
.
.
.
.

.
.
.
.
.
.

.
.
.
.
.
.

.
.
.

.
.
.

.
.
.
.
.
.

.
.
.
.
.
.

.
.
.
.
.
.

.
.
.
.
.

.

335
335
336
337
338
339
341

. . .
. . .
. . .
. . .
. . .
of V

.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.


. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
and V ∗

www.pdfgrip.com

.
.
.
.
.
.


xii

Contents
13.7 Dual Maps . . . . . . . . . . . . .
13.8 Nondegenerate Bilinear Forms . .
13.9 Real Inner Product Spaces . . . .
13.10 Complex Inner Product Spaces .
13.11 Comments on Infinite-Dimensional
13.12 Affine Algebraic Geometry . . . .
13.13 Summary . . . . . . . . . . . . .
13.14 Exercises . . . . . . . . . . . . . .

. . . . .

. . . . .
. . . . .
. . . . .
Spaces
. . . . .
. . . . .
. . . . .

14 Metric Spaces and Hilbert Spaces
14.1 Metric Spaces . . . . . . . . . . . . .
14.2 Convergent Sequences . . . . . . . . .
14.3 Closed Sets . . . . . . . . . . . . . . .
14.4 Open Sets . . . . . . . . . . . . . . .
14.5 Continuous Functions . . . . . . . . .
14.6 Compact Sets . . . . . . . . . . . . .
14.7 Completeness . . . . . . . . . . . . . .
14.8 Definition of a Hilbert Space . . . . .
14.9 Examples of Hilbert Spaces . . . . . .
14.10 Proof of the Hilbert Space Axioms for
14.11 Basic Properties of Hilbert Spaces . .
14.12 Closed Convex Sets in Hilbert Spaces
14.13 Orthogonal Complements . . . . . .
14.14 Orthonormal Sets . . . . . . . . . . .
14.15 Maximal Orthonormal Sets . . . . .
14.16 Isomorphism of H and ℓ2 (X) . . . .
14.17 Continuous Linear Maps . . . . . . .
14.18 Dual Space of a Hilbert Space . . . .
14.19 Adjoints . . . . . . . . . . . . . . . .
14.20 Summary . . . . . . . . . . . . . . .
14.21 Exercises . . . . . . . . . . . . . . . .


V

.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.


.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.

.
.
.

.
.
.
.
.

.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.

.
.
.
.
.
.

.
.

.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.


.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.

.
.
.

.
.
.
.
.

.
.
.
.
.
.
.
.

342
344
345
346
348
349
350
352

. . . .
. . . .
. . . .
. . . .
. . . .
. . . .

. . . .
. . . .
. . . .
ℓ2 (X)
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .

.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.


.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.


359
360
361
362
363
364
365
366
368
369
371
373
374
375
377
378
379
381
382
383
384
387

Modules, Independence, and Classification Theorems

15 Finitely Generated Commutative Groups
15.1 Commutative Groups . . . . . . . . . . . . . . . . . .
15.2 Generating Sets . . . . . . . . . . . . . . . . . . . . .
15.3 Z-Independence and Z-Bases . . . . . . . . . . . . . .
15.4 Elementary Operations on Z-Bases . . . . . . . . . .

15.5 Coordinates and Z-Linear Maps . . . . . . . . . . . .
15.6 UMP for Free Commutative Groups . . . . . . . . . .
15.7 Quotient Groups of Free Commutative Groups . . . .
15.8 Subgroups of Free Commutative Groups . . . . . . .
15.9 Z-Linear Maps and Integer Matrices . . . . . . . . . .
15.10 Elementary Operations and Change of Basis . . . . .
15.11 Reduction Theorem for Integer Matrices . . . . . . .
15.12 Structure of Z-Linear Maps between Free Groups . .
15.13 Structure of Finitely Generated Commutative Groups
15.14 Example of the Reduction Algorithm . . . . . . . . .
15.15 Some Special Subgroups . . . . . . . . . . . . . . . .
15.16 Uniqueness Proof: Free Case . . . . . . . . . . . . . .

www.pdfgrip.com

.
.
.
.
.
.
.
.
.
.
.
.

.
.

.
.
.
.
.
.
.
.
.
.
.
. .
. .
. .

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

395
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.

397
397
399
400
401
402
403
404
405
406
408
411
413
414
415
417
418


Contents
15.17
15.18
15.19
15.20

15.21
15.22

xiii
Uniqueness Proof: Prime Power Case
Uniqueness of Elementary Divisors .
Uniqueness of Invariant Factors . . .
Uniqueness Proof: General Case . . .
Summary . . . . . . . . . . . . . . .
Exercises . . . . . . . . . . . . . . . .

.
.
.
.
.
.

.
.
.
.
.
.

.
.
.
.
.

.

.
.
.
.
.
.

.
.
.
.
.
.

.
.
.
.
.
.

.
.
.
.
.
.


.
.
.
.
.
.

.
.
.
.
.
.

.
.
.
.
.
.

.
.
.
.
.
.

.
.

.
.
.
.

419
422
423
424
424
426

16 Axiomatic Approach to Independence, Bases, and Dimension
16.1 Axioms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
16.2 Definitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
16.3 Initial Theorems . . . . . . . . . . . . . . . . . . . . . . . . . . .
16.4 Consequences of the Exchange Axiom . . . . . . . . . . . . . . .
16.5 Main Theorems: Finite-Dimensional Case . . . . . . . . . . . . .
16.6 Zorn’s Lemma . . . . . . . . . . . . . . . . . . . . . . . . . . . .
16.7 Main Theorems: General Case . . . . . . . . . . . . . . . . . . .
16.8 Bases of Subspaces . . . . . . . . . . . . . . . . . . . . . . . . .
16.9 Linear Independence and Linear Bases . . . . . . . . . . . . . .
16.10 Field Extensions . . . . . . . . . . . . . . . . . . . . . . . . . .
16.11 Algebraic Independence and Transcendence Bases . . . . . . . .
16.12 Independence in Graphs . . . . . . . . . . . . . . . . . . . . . .
16.13 Hereditary Systems . . . . . . . . . . . . . . . . . . . . . . . . .
16.14 Matroids . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
16.15 Equivalence of Matroid Axioms . . . . . . . . . . . . . . . . . .
16.16 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
16.17 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .


.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.


.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

437
437
438
438
439
440
442
443
446
446
448

449
452
453
454
455
456
457

17 Elements of Module Theory
17.1 Module Axioms . . . . . . . . . . . . . . . . . . . .
17.2 Examples of Modules . . . . . . . . . . . . . . . . .
17.3 Submodules . . . . . . . . . . . . . . . . . . . . . .
17.4 Submodule Generated by a Subset . . . . . . . . . .
17.5 Direct Products, Direct Sums, and Hom Modules .
17.6 Quotient Modules . . . . . . . . . . . . . . . . . . .
17.7 Changing the Ring of Scalars . . . . . . . . . . . . .
17.8 Fundamental Homomorphism Theorem for Modules
17.9 More Module Homomorphism Theorems . . . . . .
17.10 Chains of Submodules . . . . . . . . . . . . . . . .
17.11 Modules of Finite Length . . . . . . . . . . . . . .
17.12 Free Modules . . . . . . . . . . . . . . . . . . . . .
17.13 Size of a Basis of a Free Module . . . . . . . . . . .
17.14 Summary . . . . . . . . . . . . . . . . . . . . . . .
17.15 Exercises . . . . . . . . . . . . . . . . . . . . . . . .

.
.
.
.
.

.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.

.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.

.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.


463
463
465
466
467
468
470
472
472
474
476
478
479
481
483
486

18 Principal Ideal Domains, Modules over PIDs, and Canonical Forms
18.1 Principal Ideal Domains . . . . . . . . . . . . . . . . . . . . . . . . . . .
18.2 Divisibility in Commutative Rings . . . . . . . . . . . . . . . . . . . . .
18.3 Divisibility and Ideals . . . . . . . . . . . . . . . . . . . . . . . . . . . .
18.4 Prime and Irreducible Elements . . . . . . . . . . . . . . . . . . . . . .
18.5 Irreducible Factorizations in PIDs . . . . . . . . . . . . . . . . . . . . .
18.6 Free Modules over a PID . . . . . . . . . . . . . . . . . . . . . . . . . .
18.7 Operations on Bases . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

.
.
.

.
.
.
.

.
.
.
.
.
.
.

493
494
494
495
496
497
498
499

www.pdfgrip.com

.
.
.
.
.
.


.
.
.
.
.
.

.
.
.
.
.
.

.
.
.
.
.
.

.
.
.
.
.
.
.
.

.
.
.
.
.
.
.

.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.


.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.


.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.

.
.
.
.
.
.

.
.
.
.
.
.
.
.
.

.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.

.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.


xiv

Contents
18.8 Matrices of Linear Maps between Free Modules .
18.9 Reduction Theorem for Matrices over a PID . . .
18.10 Structure Theorems for Linear Maps and Modules
18.11 Minors and Matrix Invariants . . . . . . . . . . .
18.12 Uniqueness of Smith Normal Form . . . . . . . .
18.13 Torsion Submodules . . . . . . . . . . . . . . . .
18.14 Uniqueness of Invariant Factors . . . . . . . . . .

18.15 Uniqueness of Elementary Divisors . . . . . . . .
18.16 F [x]-Module Defined by a Linear Operator . . . .
18.17 Rational Canonical Form of a Linear Map . . . .
18.18 Jordan Canonical Form of a Linear Map . . . . .
18.19 Canonical Forms of Matrices . . . . . . . . . . . .
18.20 Summary . . . . . . . . . . . . . . . . . . . . . .
18.21 Exercises . . . . . . . . . . . . . . . . . . . . . . .

. . .
. . .
. .
. . .
. . .
. . .
. . .
. . .
. . .
. . .
. . .
. . .
. . .
. . .

.
.
.
.
.
.
.

.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.

.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.

.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.

.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.

.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.

.
.
.
.
.
.
.

VI Universal Mapping Properties and Multilinear Algebra
19 Introduction to Universal Mapping Properties
19.1 Bases of Free R-Modules . . . . . . . . . . . . . . .
19.2 Homomorphisms out of Quotient Modules . . . . .
19.3 Direct Product of Two Modules . . . . . . . . . . .
19.4 Direct Sum of Two Modules . . . . . . . . . . . . .
19.5 Direct Products of Arbitrary Families of R-Modules
19.6 Direct Sums of Arbitrary Families of R-Modules . .
19.7 Solving Universal Mapping Problems . . . . . . . .
19.8 Summary . . . . . . . . . . . . . . . . . . . . . . . .
19.9 Exercises . . . . . . . . . . . . . . . . . . . . . . . .

500
502
504
505
506
507
508
509
510
512

513
514
516
518

525

.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.

.
.
.

.
.
.
.
.
.

.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.

.
.
.

.
.
.
.
.
.

.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.

.
.
.

.
.
.
.
.
.

.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.

.
.
.

.
.
.
.
.
.

.
.
.
.
.
.
.
.
.

527
529
529
531
532
533
534
537
539
541

20 Universal Mapping Problems in Multilinear Algebra
20.1 Multilinear Maps . . . . . . . . . . . . . . . . . . . .

20.2 Alternating Maps . . . . . . . . . . . . . . . . . . . .
20.3 Symmetric Maps . . . . . . . . . . . . . . . . . . . . .
20.4 Tensor Product of Modules . . . . . . . . . . . . . . .
20.5 Exterior Powers of a Module . . . . . . . . . . . . . .
20.6 Symmetric Powers of a Module . . . . . . . . . . . . .
20.7 Myths about Tensor Products . . . . . . . . . . . . .
20.8 Tensor Product Isomorphisms . . . . . . . . . . . . .
20.9 Associativity of Tensor Products . . . . . . . . . . . .
20.10 Tensor Product of Maps . . . . . . . . . . . . . . . .
20.11 Bases and Multilinear Maps . . . . . . . . . . . . . .
20.12 Bases for Tensor Products of Free R-Modules . . . .
20.13 Bases and Alternating Maps . . . . . . . . . . . . . .
20.14 Bases for Exterior Powers of Free Modules . . . . . .
20.15 Bases for Symmetric Powers of Free Modules . . . .
20.16 Tensor Product of Matrices . . . . . . . . . . . . . .
20.17 Determinants and Exterior Powers . . . . . . . . . .
20.18 From Modules to Algebras . . . . . . . . . . . . . . .
20.19 Summary . . . . . . . . . . . . . . . . . . . . . . . .
20.20 Exercises . . . . . . . . . . . . . . . . . . . . . . . . .

.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.

547
547
548
549
550
553
555
557
558
560
561
562
564
565
566
567
568
569
571
573
577

www.pdfgrip.com


Contents
Appendix: Basic Definitions
Sets . . . . . . . . . . . . . .

Functions . . . . . . . . . . .
Relations . . . . . . . . . . .
Partially Ordered Sets . . . .

xv
.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.


.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.


.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.


.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.


.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.


583
583
583
584
585

Further Reading

587

Bibliography

591

Index

595

www.pdfgrip.com


This page intentionally left blank

www.pdfgrip.com


Preface

What is linear algebra, and how is it used? Upon examining almost any introductory text
on linear algebra, we find a standard list of topics that seems to define the subject. On

one hand, one part of linear algebra consists of computational techniques for solving linear
equations, multiplying and inverting matrices, calculating and interpreting determinants,
finding eigenvalues and eigenvectors, and so on. On the other hand, there is a theoretical side
to linear algebra involving abstract vector spaces, subspaces, linear independence, spanning
sets, bases, dimension, and linear transformations.
But there is much more to linear algebra than just vector spaces, matrices, and linear
equations! The goal of this book is to explore a variety of advanced topics in linear algebra,
which highlight the rich interconnections linking this subject to geometry, algebra, analysis,
combinatorics, numerical computation, and many other areas of mathematics. The book
consists of twenty chapters, grouped into six main subject areas (algebraic structures,
matrices, structured matrices, geometric aspects of linear algebra, modules, and multilinear
algebra). Some chapters approach introductory material from a more sophisticated or
abstract viewpoint; other chapters provide elementary expositions of more theoretical
concepts; yet other chapters offer unusual perspectives or novel treatments of standard
results.
Unlike some advanced mathematical texts, this book has been carefully designed to
minimize the dependence of each chapter on material found in earlier chapters. Each
chapter has been conceived as a “mathematical vignette” devoted to the development of
one specific topic. If you need to learn about Jordan canonical forms, or ruler and compass
constructions, or the singular value decomposition, or Hilbert spaces, or QR factorizations,
or convexity, or normal matrices, or modules, you may turn immediately to the relevant
chapter without first wading through ten chapters of algebraic background or worrying
that you will need a theorem covered two hundred pages earlier. We do assume the reader
has already encountered the basic linear algebra concepts described earlier (solving linear
systems, computing with matrices and determinants, knowing elementary facts about vector
spaces and linear maps). These topics are all revisited in a more sophisticated setting at
various points throughout the book, but this is not the book you should read to learn the
mechanics of Gaussian elimination or matrix multiplication for the first time! Chapter 1
provides a condensed review of some pertinent definitions from abstract algebra. But the
vast majority of the book requires very little knowledge of abstract algebra beyond the

definitions of fields, vector spaces over a field, subspaces, linear transformations, linear
independence, and bases. The last three chapters build on the material on modules covered
in Chapter 17, and in a few places one needs to know about permutations (covered in
Chapter 2) and polynomials (discussed in Chapter 3).
Although this book focuses on theoretical aspects of linear algebra, giving complete
proofs of all results, we supplement and explain the general theory with many specific
examples and concrete computations. The level of abstraction gradually increases as one
proceeds through the book, as we move from matrices to vector spaces to modules. Except
in Chapter 16, we have deliberately avoided presenting the mathematical content as a dry
skeleton of itemized definitions, theorems, and proofs. Instead, the material is presented in

xvii

www.pdfgrip.com


xviii

Advanced Linear Algebra

a narrative format, providing motivation, examples, and informal discussions to help the
reader understand the significance of the theorems and the intuition behind the proofs. Each
chapter ends with a summary containing a structured list of the principal definitions and
results covered in the chapter, followed by a set of exercises. Most exercises are not used in
the main text, and consist of examples, computations, and proofs that will aid the reader
in assimilating the material from the chapter. The reader is encouraged to use a computer
algebra system to help solve computationally intensive exercises.
This text is designed for use by advanced undergraduates or beginning graduate students,
or as a reference. For a second course in linear algebra, one could cover most of the chapters
in Parts II, III, and IV, reviewing Part I as needed. For a second course in abstract algebra

focusing on the role of linear-algebraic ideas, one could cover Parts I, V, and VI along with
selections from the rest of the book (such as Chapter 12 or Chapter 13). The next section
describes the contents of each chapter; for more details on what is covered in a given chapter,
consult the summary for that chapter.

Synopsis of Topics Covered
Part I: Background on Algebraic Structures.
Chapter 1: Overview of Algebraic Systems. This chapter contains a condensed
reference for the abstract algebra background needed in some parts of the book. We review
the definitions of groups, commutative groups, rings, integral domains, fields, vector spaces,
algebras, and homomorphisms of these structures. We also quickly cover the constructions
of subgroups, product groups, quotient groups, and their analogues for other algebraic
systems. Finally, we recall some fundamental definitions and results from elementary linear
algebra involving linear independence, spanning sets, bases, and dimension. Most of the
later chapters in this book require only a small subset of the material covered here, e.g.,
the definitions of a field, vector space, linear map, subspace, linearly independent list, and
ordered basis.
Chapter 2: Permutations. This chapter provides the basic definitions and facts about
permutations that are required for the study of determinants and multilinear algebra. After
describing the symmetric groups Sn , we show how to visualize functions on a finite set using
directed graphs. This idea leads naturally to the factorization of permutations into disjoint
cycles. One can also write permutations as products of transpositions or basic transpositions.
To understand the role of basic transpositions, we introduce inversions and prove that a list
of numbers f = [f (1), f (2), . . . , f (n)] can be sorted into increasing order by interchanging
adjacent elements inv(f ) times. For permutations f , we define sgn(f ) = (−1)inv(f ) and use
this formula to establish fundamental properties of the sgn function.
Chapter 3: Polynomials. This chapter covers background on one-variable polynomials
over a field, which is used in chapters discussing canonical forms, ruler and compass
constructions, primary decompositions, commuting matrices, etc. Topics include intuitive
and formal definitions of polynomials, evaluation homomorphisms, the universal mapping

property for polynomial rings, polynomial division with remainder, greatest common
divisors, roots of polynomials, irreducible polynomials, existence and uniqueness of prime
factorizations, minimal polynomials, and ways to test polynomials for irreducibility.

www.pdfgrip.com


Preface

xix

Part II: Matrices.
Chapter 4: Basic Matrix Operations. This chapter revisits some basic material about
matrices from a somewhat more sophisticated perspective. Topics studied include formal
definitions of matrices and matrix operations, vector spaces of functions and matrices,
matrix multiplication and its properties, invertible matrices, elementary row and column
operations, elementary matrices, Smith canonical form, factorization of invertible matrices
into elementary matrices, the equality of row rank and column rank, and the theorem giving
equivalent conditions for a matrix to be invertible.
Chapter 5: Determinants via Calculations. The main properties of matrix determinants are often stated without full proofs in a first linear algebra course. This chapter
establishes these properties starting from an explicit definition of det(A) as a sum over
permutations of signed products of entries of A. Topics include multilinearity of the
determinant as a function of the rows (or columns) of A, the alternating property, the
effect of elementary row (or column) operations, the product formula, Laplace expansions,
the classical adjoint of A, the explicit formula for A−1 , Cramer’s rule, the Cauchy–Binet
formula, the Cayley–Hamilton theorem, and a quick introduction to permanents.
Chapter 6: Concrete vs. Abstract Linear Algebra. In elementary linear algebra, one
first learns to execute computations involving “concrete” objects such as column vectors
and matrices. Later, one learns about abstract vector spaces and linear transformations.
Concrete concepts defined for matrices (e.g., matrix multiplication, matrix transpose,

diagonalizability, idempotence) have abstract counterparts for linear transformations (e.g.,
composition of maps, dual maps, existence of a basis of eigenvectors, and being a projection).
The goal of this chapter is to give a thorough account of the relations between the
concrete world of column vectors and matrices on the one hand, and the abstract world
of vector spaces and linear maps on the other hand. We build a dictionary linking these
two worlds, explaining the exact connection between each abstract concept and its concrete
manifestation. In particular, we carefully describe how taking coordinates relative to an
ordered basis yields a vector space isomorphism between an abstract vector space V and a
concrete space F n of column vectors; whereas computing the matrix of a linear map relative
to an ordered basis gives an algebra isomorphism between an algebra of linear operators and
an algebra of matrices. We also discuss how congruence, orthogonal similarity, and unitary
similarity of matrices are related to bilinear maps, real inner product spaces, and complex
inner product spaces.

Part III: Matrices with Special Structure.
Chapter 7: Hermitian, Positive Definite, Unitary, and Normal Matrices. This
chapter develops the basic facts about the special types of matrices mentioned in the
title by building an analogy between properties of complex numbers (being real, being
positive, having modulus 1) and properties of matrices (being Hermitian, being positive
definite, being unitary). This analogy provides motivation for the central notion of a normal
matrix. The chapter also includes a discussion of unitary similarity, triangularization, and
diagonalization, the spectral theorem for normal matrices, simultaneous triangularization
and diagonalization of commuting families, the polar decomposition of a matrix, and the
singular value decomposition.
Chapter 8: Jordan Canonical Forms. This chapter gives a novel and elementary
derivation of the existence and uniqueness of the Jordan canonical form of a complex matrix.
The first step in the proof is to classify nilpotent linear operators (with scalars in any field)
by a visual analysis of partition diagrams. Once this classification is complete, we combine it

www.pdfgrip.com



xx

Advanced Linear Algebra

with a version of Fitting’s lemma to derive Jordan canonical forms with no explicit mention
of generalized eigenspaces. The chapter concludes with remarks on how one might compute
the Jordan form, an application to systems of differential equations, and a discussion of the
Jordan–Chevalley decomposition of a linear operator into a sum of commuting nilpotent
and diagonalizable linear maps.
Chapter 9: Matrix Factorizations. There are many ways to factor a matrix into products
of other matrices that have a special structure (e.g., triangular or unitary matrices). These
factorizations often appear as building blocks in algorithms for the numerical solution
of linear algebra problems. This chapter proves the existence and uniqueness of several
matrix factorizations and explores the algebraic and geometric ideas leading to these
factorizations. Topics covered include the Gram–Schmidt orthonormalization algorithm,
QR-factorizations, Householder reflections, LU factorizations and their relation to Gaussian
elimination, Cholesky’s factorization of positive semidefinite matrices, the normal equations
for solving least-squares problems, and the singular value decomposition.
Chapter 10: Iterative Algorithms in Numerical Linear Algebra. This chapter
studies methods for solving linear systems and computing eigenvalues that employ an
iterative process to generate successive approximations converging to the true solution.
Iterative algorithms for solving Ax = b include Richardson’s method, the Jacobi method,
and the Gauss–Seidel method. After developing some background on vector norms and
matrix norms, we establish some theoretical results ensuring the convergence of these
algorithms for certain classes of matrices. The chapter ends with an analysis of the power
method for iteratively computing the largest eigenvalue of a matrix. Techniques for finding
other eigenvalues (the shifted power method, inverse power method, and deflation) are also
discussed briefly.


Part IV: The Interplay of Geometry and Linear Algebra.
Chapter 11: Affine Geometry and Convexity. Most introductions to linear algebra
include an account of vector spaces, linear subspaces, the linear span of a subset of Rn , linear
independence, bases, dimension, and linear transformations. However, the parallel theory
of affine sets and affine transformations is seldom covered in detail. This chapter starts by
developing the basic notions of affine geometry: affine sets, the affine span of a subset of
Rn , affine combinations, characterizations of affine sets (as translates of linear subspaces, as
solution sets of linear equations, and as intersections of hyperplanes), affine independence,
barycentric coordinates, and affine transformations. We continue with an introduction to
the vast subject of convexity, discussing convex sets, convex hulls, convex combinations,
Carath´eodory’s theorem, simplexes, closed convex sets, convex cones, descriptions of convex
sets as intersections of half-spaces, convex functions, epigraphs, Jensen’s inequality, and
derivative tests for convex functions.
Chapter 12: Ruler and Compass Constructions. Why can a regular 17-gon be
constructed with ruler and compass, whereas a regular 7-gon cannot? Which angles can
be trisected with a ruler and compass? These questions and others are answered here in a
linear-algebraic way by viewing field extensions as vector spaces and looking at dimensions.
This material is often presented toward the end of an abstract algebra course, or is skipped
altogether. Our development is entirely elementary, using only basic facts about analytic
geometry, plane geometry, fields, polynomials, and dimensions of vector spaces.
Chapter 13: Dual Spaces and Bilinear Forms. A fruitful idea in mathematics is
the interplay between geometric spaces and structure-preserving functions defined on these
spaces. This chapter studies the fundamental case of a finite-dimensional vector space V

www.pdfgrip.com


Preface


xxi

and the dual space V ∗ of linear functions from V to the field of scalars. We show how
the notions of zero sets and annihilators set up inclusion-reversing bijections between the
subspaces of V and the subspaces of V ∗ . Once this correspondence is understood, we explore
how the choice of an inner product on V (or, more generally, a nondegenerate bilinear form)
sets up an isomorphism between V and V ∗ . We also discuss the double dual V ∗∗ and its
relation to V , along with dual maps and adjoint operators. The chapter concludes with a
few comments on Banach spaces and affine algebraic geometry.
Chapter 14: Metric Spaces and Hilbert Spaces. This chapter gives readers a taste of
some aspects of infinite-dimensional linear algebra that play a fundamental role in modern
analysis. We begin with a self-contained account of the material we need from analysis,
including metric spaces, convergent sequences, closed sets, open sets, continuous functions,
compactness, Cauchy sequences, and completeness. Next we develop the basic theory of
Hilbert spaces, exploring topics such as the Schwarz inequality, the parallelogram law,
orthogonal complements of closed subspaces, orthonormal sets, Bessel’s inequality, maximal
orthonormal sets, Parseval’s equation, abstract Fourier expansions, the role of the Hilbert
spaces ℓ2 (X), Banach spaces of continuous linear maps, the dual of a Hilbert space, and
the adjoint of an operator. A major theme is the interaction between topological properties
(especially completeness), algebraic computations, and geometric ideas such as convexity
and orthogonality. Beyond a few brief allusions to L2 spaces, this chapter does not assume
any detailed knowledge of measure theory or Lebesgue integration.

Part V: Modules, Independence, and Classification Theorems.
Chapter 15: Finitely Generated Commutative Groups. A central theorem of group
theory asserts that every finitely generated commutative group is isomorphic to a product
of cyclic groups. This theorem is frequently stated, but not always proved, in first courses
on abstract algebra. This chapter proves this fundamental result using linear-algebraic
methods. We begin by reviewing basic concepts and definitions for commutative groups,
stressing the analogy to corresponding concepts for vector spaces. The key idea in the proof

of the classification theorem is to develop the analogue of Gaussian elimination for integervalued matrices and to use this algorithm to reduce such matrices to a certain canonical
form. We also discuss elementary divisors and invariant factors and prove uniqueness results
for these objects. The uniqueness proof is facilitated by using partition diagrams to visualize
finite groups whose size is a prime power. This chapter uses the very concrete setting of
integer matrices to prepare the reader for more abstract algebraic ideas (universal mapping
properties and the classification of finitely generated modules over principal ideal domains)
covered in later chapters.
Chapter 16: Axiomatic Approach to Independence, Bases, and Dimension. This
chapter presents a general axiomatic treatment of some fundamental concepts from linear
algebra: linear independence, linear dependence, spanning sets, and bases. A major objective
is to prove that every vector space V has a basis, and the cardinality of the basis is uniquely
determined by V . One benefit of the axiomatic approach is that it sweeps away a lot of
irrelevant extra structure, isolating a few key properties that underlie the main theorems
about linear independence and bases. Even better, these axioms arise in other situations
besides classical linear algebra. Hence, all the theorems deduced from the axioms will apply
to those other situations as well. For example, we will prove properties of the transcendence
degree of field extensions by verifying the axioms of the general theory. We conclude with
a quick introduction to matroids, which arise by specializing our axiomatic framework to
finite sets. This chapter departs from the narrative style of the rest of the book by giving a
rigidly structured sequence of axioms, definitions, theorems, and proofs.

www.pdfgrip.com


xxii

Advanced Linear Algebra

Chapter 17: Elements of Module Theory. This chapter introduces the reader to
some fundamental concepts in the theory of modules over arbitrary rings. We adopt the

approach of using the analogy to vector spaces (which are modules over fields) to motivate
fundamental constructions for modules, while carefully pointing out that certain special
facts about vector spaces fail to generalize to modules. In particular, the fact that not
every module has a basis leads to a discussion of free modules and their properties.
Specific topics covered include submodules, quotient modules, direct sums, generating sets,
direct products, Hom modules, change of scalars, module homomorphisms, kernels, images,
isomorphism theorems, the JordanHăolder theorem, length of a module, free modules, bases,
and invariance of the size of a basis when the ring of scalars is commutative.
Chapter 18: Principal Ideal Domains, Modules over PIDs, and Canonical Forms.
This chapter gives a detailed proof of one of the cornerstones of abstract algebra: the
classification of all finitely generated modules over a PID. The chapter begins by proving
the necessary algebraic properties of principal ideal domains, including the fact that every
PID is a unique factorization domain. The classification proof is modeled upon the concrete
case of commutative groups (covered in Chapter 15); a central idea is to develop a matrix
reduction algorithm for matrices with entries in a PID. This algorithm changes any matrix
into a diagonal matrix called a Smith normal form, which leads to the main structural
results for modules. As special cases of the general theory, we deduce theorems on the
rational canonical form and Jordan canonical form of linear operators and matrices. We
also prove uniqueness of the elementary divisors and invariant factors of a module, as well
as uniqueness of the various canonical forms for matrices.

Part VI: Universal Mapping Properties and Multilinear Algebra.
Chapter 19: Introduction to Universal Mapping Properties. The concept of a
universal mapping property (UMP) pervades linear and abstract algebra, but is seldom
mentioned in introductory treatments of these subjects. This chapter gives a careful and
detailed introduction to this idea, starting with the UMP satisfied by a basis of a vector
space. The UMP is formulated in several equivalent ways (as a diagram completion property,
as a unique factorization property, and as a bijection between collections of functions).
The concept is further developed by describing the UMP’s characterizing free R-modules,
quotient modules, direct products, and direct sums. This chapter serves as preparation for

the next chapter on multilinear algebra.
Chapter 20: Universal Mapping Properties in Multilinear Algebra. The final
chapter uses the idea of a universal mapping property (UMP) to organize the development
of basic constructions in multilinear algebra. Topics covered include multilinear maps,
alternating maps, symmetric maps, tensor products of modules, exterior powers, symmetric
powers, and the homomorphisms of these structures induced by linear maps. We also
discuss isomorphisms between tensor product modules, bases of tensor products and
related modules, tensor products of matrices, the connection between exterior powers and
determinants, and tensor algebras.
I wish you an exciting journey through the rich landscape of linear algebra!
Nicholas A. Loehr

www.pdfgrip.com


Part I

Background on Algebraic
Structures

www.pdfgrip.com


This page intentionally left blank

www.pdfgrip.com