Linear Algebra, Theory And Applications
Kenneth Kuttler
November 5, 2012
,2
,Contents
1 Preliminaries 11
1.1 Sets And Set Notation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
1.2 Functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
1.3 The Number Line And Algebra Of The Real Numbers . . . . . . . . . . . . . 12
1.4 Ordered fields . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
1.5 The Complex Numbers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
1.6 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
1.7 Completeness of R . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
1.8 Well Ordering And Archimedean Property . . . . . . . . . . . . . . . . . . . . 21
1.9 Division And Numbers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
1.10 Systems Of Equations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
1.11 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31
1.12 Fn . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32
1.13 Algebra in Fn . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32
1.14 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33
1.15 The Inner Product In Fn . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33
1.16 What Is Linear Algebra? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36
1.17 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36
2 Linear Transformations 37
2.1 Matrices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37
2.1.1 The ij th Entry Of A Product . . . . . . . . . . . . . . . . . . . . . . . 41
2.1.2 Digraphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43
2.1.3 Properties Of Matrix Multiplication . . . . . . . . . . . . . . . . . . . 45
2.1.4 Finding The Inverse Of A Matrix . . . . . . . . . . . . . . . . . . . . . 48
2.2 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51
2.3 Linear Transformations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53
2.4 Subspaces And Spans . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56
2.5 An Application To Matrices . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61
2.6 Matrices And Calculus . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62
2.6.1 The Coriolis Acceleration . . . . . . . . . . . . . . . . . . . . . . . . . 63
2.6.2 The Coriolis Acceleration On The Rotating Earth . . . . . . . . . . . 66
2.7 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71
3 Determinants 77
3.1 Basic Techniques And Properties . . . . . . . . . . . . . . . . . . . . . . . . . 77
3.2 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 81
3.3 The Mathematical Theory Of Determinants . . . . . . . . . . . . . . . . . . . 83
3.3.1 The Function sgn . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 84
3
, 4 CONTENTS
3.3.2 The Definition Of The Determinant . . . . . . . . . . . . . . . . . . . 86
3.3.3 A Symmetric Definition . . . . . . . . . . . . . . . . . . . . . . . . . . 87
3.3.4 Basic Properties Of The Determinant . . . . . . . . . . . . . . . . . . 88
3.3.5 Expansion Using Cofactors . . . . . . . . . . . . . . . . . . . . . . . . 90
3.3.6 A Formula For The Inverse . . . . . . . . . . . . . . . . . . . . . . . . 92
3.3.7 Rank Of A Matrix . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 94
3.3.8 Summary Of Determinants . . . . . . . . . . . . . . . . . . . . . . . . 96
3.4 The Cayley Hamilton Theorem . . . . . . . . . . . . . . . . . . . . . . . . . . 97
3.5 Block Multiplication Of Matrices . . . . . . . . . . . . . . . . . . . . . . . . . 98
3.6 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 102
4 Row Operations 105
4.1 Elementary Matrices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 105
4.2 The Rank Of A Matrix . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 110
4.3 The Row Reduced Echelon Form . . . . . . . . . . . . . . . . . . . . . . . . . 112
4.4 Rank And Existence Of Solutions To Linear Systems . . . . . . . . . . . . . . 116
4.5 Fredholm Alternative . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 117
4.6 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 118
5 Some Factorizations 123
5.1 LU Factorization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 123
5.2 Finding An LU Factorization . . . . . . . . . . . . . . . . . . . . . . . . . . . 123
5.3 Solving Linear Systems Using An LU Factorization . . . . . . . . . . . . . . . 125
5.4 The P LU Factorization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 126
5.5 Justification For The Multiplier Method . . . . . . . . . . . . . . . . . . . . . 127
5.6 Existence For The P LU Factorization . . . . . . . . . . . . . . . . . . . . . . 128
5.7 The QR Factorization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 130
5.8 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 133
6 Linear Programming 135
6.1 Simple Geometric Considerations . . . . . . . . . . . . . . . . . . . . . . . . . 135
6.2 The Simplex Tableau . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 136
6.3 The Simplex Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 140
6.3.1 Maximums . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 140
6.3.2 Minimums . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 143
6.4 Finding A Basic Feasible Solution . . . . . . . . . . . . . . . . . . . . . . . . . 150
6.5 Duality . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 152
6.6 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 156
7 Spectral Theory 157
7.1 Eigenvalues And Eigenvectors Of A Matrix . . . . . . . . . . . . . . . . . . . 157
7.2 Some Applications Of Eigenvalues And Eigenvectors . . . . . . . . . . . . . . 164
7.3 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 167
7.4 Schur’s Theorem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 173
7.5 Trace And Determinant . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 180
7.6 Quadratic Forms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 181
7.7 Second Derivative Test . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 182
7.8 The Estimation Of Eigenvalues . . . . . . . . . . . . . . . . . . . . . . . . . . 186
7.9 Advanced Theorems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 187
7.10 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 190
Kenneth Kuttler
November 5, 2012
,2
,Contents
1 Preliminaries 11
1.1 Sets And Set Notation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
1.2 Functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
1.3 The Number Line And Algebra Of The Real Numbers . . . . . . . . . . . . . 12
1.4 Ordered fields . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
1.5 The Complex Numbers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
1.6 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
1.7 Completeness of R . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
1.8 Well Ordering And Archimedean Property . . . . . . . . . . . . . . . . . . . . 21
1.9 Division And Numbers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
1.10 Systems Of Equations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
1.11 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31
1.12 Fn . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32
1.13 Algebra in Fn . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32
1.14 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33
1.15 The Inner Product In Fn . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33
1.16 What Is Linear Algebra? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36
1.17 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36
2 Linear Transformations 37
2.1 Matrices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37
2.1.1 The ij th Entry Of A Product . . . . . . . . . . . . . . . . . . . . . . . 41
2.1.2 Digraphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43
2.1.3 Properties Of Matrix Multiplication . . . . . . . . . . . . . . . . . . . 45
2.1.4 Finding The Inverse Of A Matrix . . . . . . . . . . . . . . . . . . . . . 48
2.2 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51
2.3 Linear Transformations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53
2.4 Subspaces And Spans . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56
2.5 An Application To Matrices . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61
2.6 Matrices And Calculus . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62
2.6.1 The Coriolis Acceleration . . . . . . . . . . . . . . . . . . . . . . . . . 63
2.6.2 The Coriolis Acceleration On The Rotating Earth . . . . . . . . . . . 66
2.7 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71
3 Determinants 77
3.1 Basic Techniques And Properties . . . . . . . . . . . . . . . . . . . . . . . . . 77
3.2 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 81
3.3 The Mathematical Theory Of Determinants . . . . . . . . . . . . . . . . . . . 83
3.3.1 The Function sgn . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 84
3
, 4 CONTENTS
3.3.2 The Definition Of The Determinant . . . . . . . . . . . . . . . . . . . 86
3.3.3 A Symmetric Definition . . . . . . . . . . . . . . . . . . . . . . . . . . 87
3.3.4 Basic Properties Of The Determinant . . . . . . . . . . . . . . . . . . 88
3.3.5 Expansion Using Cofactors . . . . . . . . . . . . . . . . . . . . . . . . 90
3.3.6 A Formula For The Inverse . . . . . . . . . . . . . . . . . . . . . . . . 92
3.3.7 Rank Of A Matrix . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 94
3.3.8 Summary Of Determinants . . . . . . . . . . . . . . . . . . . . . . . . 96
3.4 The Cayley Hamilton Theorem . . . . . . . . . . . . . . . . . . . . . . . . . . 97
3.5 Block Multiplication Of Matrices . . . . . . . . . . . . . . . . . . . . . . . . . 98
3.6 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 102
4 Row Operations 105
4.1 Elementary Matrices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 105
4.2 The Rank Of A Matrix . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 110
4.3 The Row Reduced Echelon Form . . . . . . . . . . . . . . . . . . . . . . . . . 112
4.4 Rank And Existence Of Solutions To Linear Systems . . . . . . . . . . . . . . 116
4.5 Fredholm Alternative . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 117
4.6 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 118
5 Some Factorizations 123
5.1 LU Factorization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 123
5.2 Finding An LU Factorization . . . . . . . . . . . . . . . . . . . . . . . . . . . 123
5.3 Solving Linear Systems Using An LU Factorization . . . . . . . . . . . . . . . 125
5.4 The P LU Factorization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 126
5.5 Justification For The Multiplier Method . . . . . . . . . . . . . . . . . . . . . 127
5.6 Existence For The P LU Factorization . . . . . . . . . . . . . . . . . . . . . . 128
5.7 The QR Factorization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 130
5.8 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 133
6 Linear Programming 135
6.1 Simple Geometric Considerations . . . . . . . . . . . . . . . . . . . . . . . . . 135
6.2 The Simplex Tableau . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 136
6.3 The Simplex Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 140
6.3.1 Maximums . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 140
6.3.2 Minimums . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 143
6.4 Finding A Basic Feasible Solution . . . . . . . . . . . . . . . . . . . . . . . . . 150
6.5 Duality . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 152
6.6 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 156
7 Spectral Theory 157
7.1 Eigenvalues And Eigenvectors Of A Matrix . . . . . . . . . . . . . . . . . . . 157
7.2 Some Applications Of Eigenvalues And Eigenvectors . . . . . . . . . . . . . . 164
7.3 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 167
7.4 Schur’s Theorem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 173
7.5 Trace And Determinant . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 180
7.6 Quadratic Forms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 181
7.7 Second Derivative Test . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 182
7.8 The Estimation Of Eigenvalues . . . . . . . . . . . . . . . . . . . . . . . . . . 186
7.9 Advanced Theorems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 187
7.10 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 190
