Linear Algebra, First Part

Blackboard Notes

Bernd Gärtner

October 31, 2023

Contents

0 Preface 3

1 Vectors and Matrices 4

1.1 Vectors and Linear Combinations . . . . . . . . . . . . . . . . . . . . . . . . . 4
1.1.1 Vector addition: v + w . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
1.1.2 Scalar multiplication: cv . . . . . . . . . . . . . . . . . . . . . . . . . . 5
1.1.3 (Linear) combination: cv + dw . . . . . . . . . . . . . . . . . . . . . . 5
1.1.4 Combining more vectors, matrix notation . . . . . . . . . . . . . . . . 6
1.1.5 Three vectors v1 , v2 , v3 in R3 . . . . . . . . . . . . . . . . . . . . . . . 6
1.2 Lengths and Angles from Dot Products . . . . . . . . . . . . . . . . . . . . . 7
1.2.1 Scalar product (or dot product,
√ inner product): v · w . . . . . . . . . 7
1.2.2 Length of a vector: kvk = v · v . . . . . . . . . . . . . . . . . . . . . 7
1.2.3 Perpendicular (or orthogonal) vectors: v · w = 0 . . . . . . . . . . . . 7
1.3 Matrices and Their Column Spaces . . . . . . . . . . . . . . . . . . . . . . . . 8
1.3.1 Matrix-vector multiplication . . . . . . . . . . . . . . . . . . . . . . . 9
1.3.2 Column space: C(A) . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
1.3.3 (Linear) independence of vectors . . . . . . . . . . . . . . . . . . . . . 10
1.3.4 Rank: rank(A) = number of independent columns . . . . . . . . . . 11
1.4 Matrix Multiplication AB and CR . . . . . . . . . . . . . . . . . . . . . . . . 11
1.4.1 Distributivity and associativity . . . . . . . . . . . . . . . . . . . . . . 12
1.4.2 A = CR . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12

2 Solving Linear Equations Ax = b 13

2.1 Elimination and back substitution . . . . . . . . . . . . . . . . . . . . . . . . 13
2.1.1 Back substitution . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
2.1.2 Elimination . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
2.1.3 Elimination succeeds ⇔ the columns of A are independent . . . . . . 15
2.2 Elimination Matrices and Inverse Matrices . . . . . . . . . . . . . . . . . . . 16
2.2.1 The Inverse Theorem . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
2.2.2 The inverse of a product AB . . . . . . . . . . . . . . . . . . . . . . . 17
2.3 Matrix Computations and A = LU . . . . . . . . . . . . . . . . . . . . . . . . 17
2.3.1 The cost of elimination . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
2.3.2 The great factorization A = LU . . . . . . . . . . . . . . . . . . . . . . 19

1
 2.4 Permutations and Transposes . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
2.4.1 The P A = LU factorization . . . . . . . . . . . . . . . . . . . . . . . . 20
2.4.2 The transpose of A . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
2.4.3 Symmetric matrices . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
2.4.4 Symmetric LU-factorization . . . . . . . . . . . . . . . . . . . . . . . . 22

3 The Four Fundamental Subspaces 23

3.1 Vector Spaces and Subspaces . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
3.1.1 Examples of vector spaces . . . . . . . . . . . . . . . . . . . . . . . . . 23
3.1.2 Subspaces of vector spaces . . . . . . . . . . . . . . . . . . . . . . . . 23
3.1.3 The column space of A . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
3.1.4 The columns of A span the vector space C(A) . . . . . . . . . . . . . 24
3.2 Computing the Nullspace by Elimination: A = CR . . . . . . . . . . . . . . . 25
3.2.1 Elimination column by column: the steps from A to R0 . . . . . . . . 26
3.2.2 The matrix factorization A = CR and the nullspace . . . . . . . . . . 27
3.3 The Complete Solution to Ax = b . . . . . . . . . . . . . . . . . . . . . . . . . 27
3.3.1 Number of solutions of Ax = b . . . . . . . . . . . . . . . . . . . . . . 28
3.4 Independence, Basis, and Dimension . . . . . . . . . . . . . . . . . . . . . . . 28
3.4.1 Bases (for Matrix Spaces) . . . . . . . . . . . . . . . . . . . . . . . . . 29
3.5 Dimensions of the Four Subspaces . . . . . . . . . . . . . . . . . . . . . . . . 30

4 Orthogonality 31
4.1 Orthogonality of vectors and subspaces . . . . . . . . . . . . . . . . . . . . . 31
4.1.1 Orthogonal complement V ⊥ . . . . . . . . . . . . . . . . . . . . . . . 32
4.1.2 The big picture . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33

2
Chapter 0

Preface

These are the blackboard notes for the first half of the course

Lineare Algebra (401-0131-00L)

held at the Department of Computer Science at ETH Zürich in HS23. The notes roughly
correspond to what I plan to write on the tablet during my lectures (in German for the
first half of the course). The actual tablet notes will be made available after each lecture.
In structure and content, the notes are based on the book

Introduction to Linear Algebra (Sixth Edition) by Gilbert Strang, Wellesley -

Cambridge Press, 2023.

The notes are rather dense and not meant to replace full lecture notes or a book. Mainly,
they should free students from the need to copy material from the blackboard. Many
additional explanations (and answers to questions) will be given in the lectures. Exercises
to practice the material will be published in the course Moodle and are discussed during
the exercise classes.
To summarize, these notes do not represent a complete and standalone Linear Algebra
course; rather, they are meant to support the lectures and exercise classes.
I also want to point out that Strang’s book is not part of the course’s official material,
and there is no need for students to buy the book. With the blackboard notes, exercises,
lectures, and exercises classes, the course is self-contained. Strang’s book serves as rec-
ommended but optional literature.

Bernd Gärtner, Zürich, September 5, 2023

3
Chapter 1

Vectors and Matrices

1.1 Vectors and Linear Combinations

A vector is (for now) an element of Rn vector = sequence (tuple) of n real numbers
y  
−2 y      
 
−2 u1 v1 w1
2
  
  −2
2 4 u
 
v
 
w 
 
 2 0 u =  ..2  , v =  ..2  , w =  .. 2  , . . .
   
1 . .  . 
3
x x un vn wn
0 0  
 
0 0
0= z 0 = 0
0
0
R2 : xy-plane R3 : xyz-space Rn
  y
4
R: real numbers Vector = “movement” : go 1
 
4
n ∈ N (natural numbers) 4 steps right and 1 step up! 1
0: zero vector.
x
0

1.1.1 Vector addition: v + w

Combine the movements!
y  
2
3  
      5
v1 w1 v1 + w1 2
       v   w2   v2 + w2 
2 2 3 5 n  2
R : + = R :  ..  +  ..  =   x
   
3 −1 2 .. 
.  .   .  
3
vn wn vn + wn −1
“Parallelogram”

4
1.1.2 Scalar multiplication: cv
Move c times as far! (c: the scalar)
y  
6
   
v1 cv1
     v2   cv2    3
2 2 6 2
R :3 = Rn : c  ..  =  .. 
   
1 3 .  .  1
vn cvn x
 
1
1.1.3 (Linear) combination: cv + dw 18  
          2
2 3 10 9 1 5
5 −3 = − = 3
3 −1 15 −3 18
 
3
  2
−3 3
Here: c = 5, d = −3. −1  
3
−1
     
b1 2 3
Every vector b = is a combination of and ! Proof: we want c and d such that
b2 3 −1
     
2 3 b
c +d = 1 .
3 −1 b2
 
b1
b2 y
“Column Picture:”
 
2
 
Draw a parallelogramwith  opposite
  corners 0 and b 3 c
d  3
2 3 −1
and sides parallel to and . The other two 2
3  −1
  3
2 3 x
corners are c and d . 0
3 −1 
3
−1

d
“Row picture:”
Two equations in two unknowns c and d: b1
3
2c + 3d = b1 2c + 3d = b1 b1
2
3c − d = b2 b2 c
3

Draw them as lines in the cd-plane. The intersection point −b2

solves both equations. 3c − d = b2

5
 y
 
     
2 4
2 4 6
Doesn’t always work: All combinations of and are on a 3
3 6
line! (Exercise: What goes wrong in column and row pictures?)
x

1.1.4 Combining more vectors, matrix notation

 
          3    
1 −1 0 1 1 −1 0   1·3−1·2−0·4 1
3 +2 −4 = 2 = =
2 3 1 8 2 3 1 2·3+3·2−1·4 8
| {z } | {z } −4
combination of 3 vectors matrix
| {z }
matrix-vector multiplication

m × n matrix
 
z }| c1 {
 
|

| | |  c2 
v1 v2 · · · vn  .. = b
   
m rows  
c1 v 1 + c2 v 2 + · · · + cn v n = b  .
| {z } | | | |
combination of n vectors in Rm
n columns
c n

↑
Matrix: “container for vectors” m × 1 matrix: a single vector in Rm

1.1.5 Three vectors v1 , v2 , v3 in R3

The combinations c1 v1 + c2 v2 + c3 v3 form a line (vectors are collinear), a plane (vectors are
coplanar), or the whole space (vectors are independent).
 
−3  
   
  −2 −2

2

 3 −2 y  −3   y
2  2 y
 2 −1  3  3
3  1 0 0 −1
2 3
1

x x   x
−1
 
−1
 1 z  1
z z
3 3

6
1.2 Lengths and Angles from Dot Products
1.2.1 Scalar product (or dot product, inner product): v · w
   
v1 w1
     v2   w2 
2 1 4
R : · = 1 · 4 + 2 · 6 = 16 Rn :  .. ·  .. = v1 w1 + v2 w2 + · · · + vn wn .
   
2 6  .  .
vn wn

√
1.2.2 Length of a vector: kvk = v·v
 
v1
√  v2 
 
−4 p q
2 n
R : = (−4)2 + 22 = 20 R :  .. = v12 + v22 + · · · + vn2
 
2  .
vn
Why? Pythagoras!
 
−4
 2
  0
 
−4 −4 √
900
2
 2 3 42 + 2 2
4
3
900

√
q
2
√ 2 42 + 2 2 + 3 2
42 + 2 2 √ 0
= 42 + 2 2 + 3 2

Unit vector: kuk = 1. Standard unit vectors: y  

0 0
 
For every v 6= 0, u v e2 =
 ..  1
1 v
.
v kvk
ei = 1 ← position i
 
0
kvk . x 1
 ..  e1 =
is a unit vector. 0 0

1.2.3 Perpendicular (or orthogonal) vectors: v · w = 0

  y
−1  
   
2 4
4 −1
· = −4 · 1 + 2 · 2 = 0. 2
2 2 900
x

7
Cosine Formula: v
v·w w
cos(α) = for v, w 6= 0. α
kvkkwk
Because | cos(α)| ≤ 1:
Cauchy-Schwarz inequality: |v · w| ≤ kvkkwk.
| {z }
| cos(α)|kvkkwk
v
Triangle inequality: kvk kwk
kv + wk ≤ kvk + kwk. 0 v+w
kv + wk
“From 0 directly to v + w is shorter than via v or w.” kwk kvk
w
 
  −2
−3   y
Hyperplanes.  3 2  
3
y 0 d = 3
   
−3 1 3
If d ∈ Rn , d 6= 0, the set d= 0
1 3

{v ∈ Rn : v · d = 0} x x
0
 
−1
 1 z v·d=0
is a hyperplane: all vectors
3
perpendicular to d.

R2 : a line R3 : a plane

1.3 Matrices and Their Column Spaces

Matrix with m rows, n columns: m × n matrix (A, B, . . .) A + B, cA:
     
1 2 5 6 6 8
+ =
 

a11 a12 · · · a1n
 3 4 7 8 10 12
1 2  a21 a22 · · · a2n     
3×2 matrix : 3 4 m×n matrix :  .. 1 2 2 4
 
.. .. ..  2 =
5 6
 . . . .  3 4 6 8
am1 am2 · · · amn
0 : zero matrix, aij = 0 for all i, j
Square matrix: m = n.
         
1 0 0 2 0 0 2 1 −3 2 0 0 2 1 −3
0 1 0 0 4 0 0 4 7  1 4 0  1 4 7
0 0 1 0 0 5 0 0 5 −3 7 5 −3 7 5
identity (symbol: I) diagonal upper triangular lower triangular symmetric
aii = 1, aij = 0 if i 6= j aij = 0 if i 6= j aij = 0 if i > j aij = 0 if i < j aij = aji

8
1.3.1 Matrix-vector multiplication
       
1 2 1 2   1·7+2·8
7 3 + 8 4
   = 3 4 7 = 3 · 7 + 4 · 8
8
5 6 5 6 5·7+6·8
| {z } | {z }
combination scalar products
    
a11 a12 ··· a1n x1 a11 x1 + a12 x2 + · · · + a1n xn
 a21 a22 ··· a2n   x2   a21 x1 + a22 x2 + · · · + a2n xn

Ax = =
    
 .. .. .. ..   ..   .. 
 . . . .  .   . 
am1 am2 · · · amn xn am1 x1 + am2 x2 + · · · + amn xn
| {z } | {z }
A x

      
 x1 u1 x1 u1 · x

| |

| |

| | | x   u2   x2   u2 · x 
 2 
x1 v1 + x2 v2 + · · · + xn vn = v1 v2 · · · vn   ..  =    ..  =
   
..  .. 
.  .  .   . 
| | |
| {z }
combination
} xn um xn um · x

|
| {z
A, column picture | {z } | {z } | {z }
A, row picture x scalar products

1.3.2 Column space: C(A)

All combinations (“span”) of the columns. If A is m × n,
C(A) = {Ax : x ∈ Rn } ⊆ Rm . Always: 0 ∈ C(A).
y y
         
2 4  
2 2 4 2  
2 4
C = R2 C = c :c∈R 6
3 1 3  
3 6 3 3
4
(plane, 2-dim.) 1 (a line, 1-dim.)
x x

How many columns are needed to span C(A)?

  Check v1 , v2 , . . . , vn ! If vi is a combination of v1 , . . . , vi−1 ,
| | |
then vi is dependent (not needed): Every combination of
A = v1 v2 · · · vn 
v1 , . . . , vi is already a combination of v1 , . . . , vi−1 . Proof:
| | |
y
 
c1 v 1 + · · · + ci v i = c1 v1 + · · · + ci−1 vi−1 + ci (d1 v1 + · · · + di−1 vi−1 )
 
2 4
| {z } | {z } 3 6
combination of v1 , · · · , vi vi not needed
= (c1 + ci d1 )v1 + · · · + (ci−1 + ci di−1 )vi−1
| {z }
combination of v1 , . . . , vi−1 x

9
Otherwise, vi is independent (needed: “adds a dimension.”) y 
2
3 needed
Checking order doesn’t matter: we always find the same num-  
4
ber of independent columns (3.4).
1
For v1 (i = 1): v1 , . . . , vi−1 contains no vectors. 0 is the only x
combination of no vectors. (“The sum of nothing is 0”.)

1.3.3 (Linear) independence of vectors

Definition: Vectors w1 , w2 , . . . , wk are. . .
. . . (linearly) independent if. . . . . . (linearly) dependent if. . .

(i) no vector is a combination of the (i’) some vector is a combination of the

previous ones. Or previous ones. Or

(ii) no vector is a combination of the (ii’) some vector is a combination of the

other ones. Or other ones. Or

(iii) there are no c1 , c2 , . . . , ck besides (iii’) there are some c1 , c2 , . . . , ck besides

0, 0, . . . , 0 such that 0, 0, . . . , 0 such that

c1 w1 + c2 w2 + · · · + ck wk = 0. c1 w1 + c2 w2 + · · · + ck wk = 0.
All say the same (are equivalent): (i) ⇔ (ii) ⇔ (iii). The opposites also: (i’) ⇔ (ii’) ⇔ (iii’).

Proof: (i’)⇒(ii’) (if (i’) is true, then (ii’) is true): clear (“previous ones” are “other ones”).
(ii’)⇒(iii’): If

wi = c1 w1 + · · · + ci−1 wi−1 + ci+1 wi+1 + · · · + ck wk , ← (ii’)

then
c1 w1 + · · · + ci−1 wi−1 − 1wi + ci+1 wi+1 + ck wk = 0. ← (iii’)
(iii’)⇒(i’): If there are some c1 , c2 , . . . , ck besides 0, 0, . . . , 0 such that

c1 w1 + c2 w2 + · · · + ck wk = 0 ← (iii’)

take the largest i such that ci 6= 0. Then c1 w1 + c2 w2 + · · · + ci wi = 0 and hence

c1 ci−1
wi = − w1 − · · · − wi−1 . ← (i’)
ci ci
The columns of a matrix A are. . .
. . . independent if . . . . . . dependent if . . .

(iii) there is no x besides 0 such that (iii’) there is some x besides 0 such that
Ax = 0. Ax = 0.

10
1.3.4 Rank: rank(A) = number of independent columns
     
2 4 2 4 0 0
rank = 2, rank = 1, rank = 0.
3 1 3 6 0 0

Row space: R(A). All combinations of the rows

y y  
    3 6
2 4   2 4   
R = R2 2 4 R = c 2 4 :c∈R
3 1 3 6  
2 4
 
3 1
(plane, 2-dim.) (a line, 1-dim.)
x x

In the examples, number of independent columns = number of independent rows. Coin-

cidence? No (3.5)! Easy case: rank 1.

Matrices of rank 1. One independent column.

   
v1 c1 v1 c2 v1 · · · cn v1
All columns  v  ⇒  c1 v2 c2 v2 · · · cn v2  ⇒ All rows
 2
of A are A =  .. of A are [c1 , c2 , . . . , cn ]
 
 ..  .. . . .. 
multiples of
 . 
⇐
 . . . .  ⇐ multiples of
| {z }
6=0
vm c1 vm c2 vm · · · cn vm
| {z } | {z }
6=0 rank 1: some cj vi 6= 0

1.4 Matrix Multiplication AB and CR

A : m × k matrix; B : k × n matrix; AB : m × n matrix.
   
u1 u1 · v1 u1 · v2 ··· u1 · vn
| |

| |

 
| | |
u2  u2 · v1 u2 · v2 ··· u2 · vn 
  
AB =   v1 v2 · · · vn  =  ..
  
.. .. .. .. 
 . 
| | |
 . . . . 
um um · v1 um · v2 ··· um · vn
|

| {z }
| {z } B, column picture | {z }
A, row picture mn scalar products

     
01 2 1 1·0+2·1 1·1+2·0 2 1
AB = = = ”column exchange”
13 4 0 3·0+4·1 3·1+4·0 4 3
      
0 1 1 2 0·1+1·3 0·2+1·4 3 4
BA = = = ”row exchange”
1 0 3 4 1·1+0·3 1·2+0·4 1 2

Square matrices: usually, BA 6= AB (matrix multiplication is not commutative).

General matrices: BA can be undefined (if m 6= n), or of different size than AB.

11
Everything is matrix multiplication!

Vector-vector
      
1 2 1 3   3  
Matrix-vector: = Scalar (inner) product: 1 2 = 11
3 4 1 7 | {z } 4 |{z}
| {z } |{z} |{z} 1×2 |{z} 1×1
2×2 2×1  2×1    2×1
  1 2   3   3 6
Vector-matrix: 1 1 = 4 6 Outer product: 1 2 = ← rank 1
| {z } 3 4 | {z } 4 | {z } 4 8
1×2 | {z } 1×2 |{z} 1×2 | {z }
2×2 2×1 2×2
   
u1 B u1
| |

| |

| |

| |
   
 u2 B   u2  | | | | | |
=  v1 v2 · · · vn  = Av1 Av2 · · · Avn 
   
 .. ..
 .   . 
| | | | | |
um B um
|

| {z } | {z }
| {z } | {z } B, column picture AB, column picture
AB, row picture A, row picture

1.4.1 Distributivity and associativity

A(B + C) = AB + AC and (B + C)D = BD + CD (AB)C = A(BC) = ABC.
More matrices: brackets don’t matter: (AB)(CD) = A((BC)D) = · · · = ABCD .
Distributivity: easy
Associativity: boring calculations with sums and products involving matrix entries
More matrices: needs proof!

1.4.2 A = CR
Finding the independent columns, revisited:
 
1 0  
1 2 0 3
A = 2 1
0 0 1 −2
    columns
   of A  3 2 |
1 2 0 3 1 2 0 3
{z }
| {z } R
C
A= 2 4 1 4
  2  4  1 4
3 6 2 5 3 6 2 5 C: the independent columns
R: how to combine them to get all
=

v1 1v1 2v1 3v1 columns

v2 Rank factorization: if A has r indepen-
v3 1v3 −2v3 dent columns, then |{z}
A = |{z}
C |{z}
R .
v4 m×n m×r r×n
independent? yes no yes no Efficient computation: (3.2)
R is unique: if A = CR = CR0 , then C(R − R0 ) = 0 ⇒ Cw = 0 for every column w of
R − R0 ⇒ w = 0, since the columns of C are independent (1.3.3).

12
Chapter 2

Solving Linear Equations Ax = b

2.1 Elimination and back substitution

System of m linear equations in n unknowns x1 , x2 , . . . , xn :
     
a11 x1 + a12 x2 + · · · + a1n xn = b1 
 a11 a12 · · · a1n x1 b1
a21 x1 + a22 x2 + · · · + a2n xn = b2  a21 a22 · · · a2n   x2   b2 

     
Ax = b :  .. ..   ..  =  .. 

.. .. ..
. 
  . . . .  .   . 

am1 x1 + am2 x2 + · · · + amn xn = bm  am1 am2 · · · amn xn bm
| {z } | {z } | {z }
A, m×n x∈Rn b∈Rm

Given A and b, find x! For now: m = n, A is square matrix.

2.1.1 Back substitution

If A upper triangular:

     equation substitution solution

2 3 4 x1 19
0 5 6 x2  = 17 row 3 7x3 = 14 x3 = 2
row 2 5x2 + 6x3 = 17 5x2 + 12 = 17 x2 = 1
0 0 7 x3 14
row 1 2x1 + 3x2 + 4x3 = 19 2x1 + 11 = 19 x1 = 4

2.1.2 Elimination
General case: Transform Ax = b to U x = c with same solution but upper triangular U
(Gauss elimination). Then back substitution!

13
Row Operations
   
2 3 4 19
fat number: the pivot A = 4 11 14 b = 55

2 8 17 50
subtract 2·(Row
 1) from
 (Row 2):   ↓  
1 0 0 2 3 4 19
E21 = −2 1 0 E21 A = 0 5 6 E21 b = 17
0 0 1 2 8 17 50
subtract 1·(Row
 1) from
 (Row 3):   ↓  
1 0 0 2 3 4 19
E31 =  0 1 0  E31 E21 A = 0 5 6 E31 E21 b = 17

−1 0 1 0 5 13 31
subtract 1·(Row
 2) from
 (Row 3):   ↓  
1 0 0 2 3 4 19
E32 = 0 1 0  E32 E31 E21 A = 0
 5 6 E32 E31 E21 b = 17

0 −1 1 0 0 7 14
| {z } | {z }
U c
↑ elimination matrices done!

Less nice case:

 
2 3 4
A = 4 6 14 b = ···
2 8 17
elimination in first column:   ↓
2 3 4
E31 E21 A = 0 0 6
 E31 E21 b = · · ·
0 5 13
can’t go
 on with
 pivot 0: exchange rows 2 and  3:  ↓
1 0 0 2 3 4
P23 = 0 0 1 P23 E31 E21 A = 0 5 13 P23 E31 E21 b = · · ·
0 1 0 0 0 6
| {z } | {z }
U c
↑ permutation matrix done!

Ugly case:
 
2 3 4
A = 4 6 14 b = ···  
2 3 4
2 3 17 0 5 6
elimination in first column:   ↓ 0 0 0
2 3 4
also
E31 E21 A = 0 0 6 E31 E21 b = · · ·
ugly!
0 0 13
no row exchange helps, give up for now!

14
Solving U x = c also solves Ax = b
Same solutions before and after each row operation!

x is a subtract c·(Row i) from (Row j) T : matrix of the

solution or exchange rows i and j row operation
before: Ax = b =⇒
|{z} T A x = |{z}
|{z} Tb
0
~ do! A w b0
w 
A b
z}|{ z}|{ undo!
T 0 A0 x = T 0 b0 ⇐= A0 x = b0 : x is a
z}|{
T 0 : matrix of the add c·(Row i) to (Row j) solution
row operation or exchange rows i and j after

Also holds if A is non-square.

Special case: b = 0 (⇒ b0 = T b = 0): Ax = 0 ⇔ A0 x = 0

(In)dependence of columns is preserved

The columns of 1.3.3 There is x 6= 0 There is x 6= 0 1.3.3 The columns of
⇐⇒ ⇔ 0 ⇐⇒ 0
A are dependent such that Ax = 0 such that A x = 0 A are dependent

Ugly case in step j ⇒ the first j columns are dependent

  find  
1 23 0 equation substitution solution
0 anything goes!
45 x1 0
    
j = 3 : 0
 row 3 0x3 = 0 x3 = 4
00  x2  = 0
 

 .. ..
..  ..  row 2 4x2 + 5x3 = 0 4x2 + 20 = 0 x2 = −5
.  x3

. . . row 1 x1 + 2x2 + 3x3 = 0 x1 + 2 = 0 x1 = −2
0 0 0 0
| {z }
6=0

Also true in the original matrix A, because (in)dependence of columns is preserved.

2.1.3 Elimination succeeds ⇔ the columns of A are independent

Elimination (allowing row exchanges) succeeds: Elimination fails:

⇒ U has nonzero diagonal elements (pivots). ⇒ The columns of some

⇒ Every column of U is independent from the intermediate matrix
previous ones. are dependent (ugly
case)
⇒ The columns of U are independent (1.3.3).
⇒ The columns of A are
⇒ The columns of A are independent (2.1.2). dependent. (2.1.2).

15
2.2 Elimination Matrices and Inverse Matrices
Elimination:
  do!  
2 3 4 −→ 2 3 4
A = 4 11 14 U = 0 5 6
2 8 17 ←− 0 0 7
undo!

E −1 E −1
z }| { z }| {
1 1 1 −1 −1 −1 −1
Ex32 Ex31 Ex
21 A = U Eij : do! Eij : undo! A = E21x E31
x E32
xU
     
   
  subtract 2·(Row 1) from (Row 2) add 2·(Row 1) to (Row 2)  
 
 subtract 1·(Row 1) from (Row 3) add 1·(Row 1) to (Row 3) 
subtract 1·(Row 2) from (Row 3) add 1·(Row 2) to (Row 3)
An n × n matrix M is invertible if there is an n × n matrix M −1 (the inverse of M ) such
that
  
1 0 ··· 0
 0 1 · · · 0 M · . . . : do something!
−1 −1
M M = M M = I I =  .. .. . . .. . M −1 · . . . : undo it !
  
 . . . .
0 0 ··· 1 I · . . . : do nothing!

There can only be one inverse: If M X = Y M = I, then X = Y , because

X = IX = (Y M )X = Y (M X) = Y I = Y.
↑
associativity (1.4.1)
Case 1 × 1: M = x , M −1 = x1 (if x 6= 0).
   

Case 2 × 2:
   
a b −1 1 d −b
M= , M = (if ad − bc 6= 0)
c d ad − bc −c a

2.2.1 The Inverse Theorem

Case n × n:
A is invertible (i)
⇔
For every b ∈ Rn , Ax = b has a unique solution x (ii)
⇔
the colunns of A are independent (iii)

16
Proof:
(i) ⇒ (ii): if A is invertible, then

• A−1 b solves Ax = b: A(A−1 b) = (AA−1 )b = Ib = b.

• Uniqueness: If Ax = b, then x = A−1 b: A−1 b = A−1 (Ax) = (A−1 A)x = Ix = x.

(ii) ⇒ (iii): if Ax = 0 has a unique solution (0), the columns of A are independent (1.3.3).
(iii) ⇒ (ii): If the columns of A are independent, elimination succeeds (2.1.3): Ax = b ⇔
U x = c (and U has nonzero diagonal elements). Back substitution: unique solution x.
(ii) ⇒ (i): If Ax = b has a unique solution for all b, we find v1 , v2 , . . . , vn such that
       
1 0 0   1 0 ··· 0
0 1 0 | | | 0 1 · · · 0
Av1 =  .. , Av2 =  .. , . . . , Avn =  ..  ⇒ A v1 v2 · · · vn =  .. .. . . .. .
         
. . .
| | |
. . . .
0 0 1 | {z } 0 0 ··· 1
|{z} |{z} |{z} B | {z }
e1 e2 en I

So AB = I. Still need BA = I to conclude that B = A−1 :

• AI = IA = (AB)A = A(BA), hence A(I − BA) = 0 by distributivity (1.4.1).

• Columns of I − BA: w1 , w2 , . . . , wn . Then Awi = 0 for all i.

• The columns of A are independent by (ii) ⇒ (iii). Hence wi = 0 for all i. So I − BA =

0, meaning BA = I.

For any two n × n matrices A, B: If AB = I, then BA = I (Exercise).

2.2.2 The inverse of a product AB

If A and B are n × n and invertible, then AB is also invertible, and

(AB)−1 = B −1 A−1 . (”undo” works in reverse order of ”do”)

Proof: (AB)(B −1 A−1 ) = A(BB −1 )A−1 = AIA−1 = AA−1 = I.

Works for more matrices: (ABC)−1 = C −1 B −1 A−1 .

2.3 Matrix Computations and A = LU

2.3.1 The cost of elimination
How many operations (·, /, +, −) are needed to solve Ax = b?

17
Elimination in step j. Subtract `ij · (Row j) from (Row i):
matrix number of entries right-hand side
u11 ··· c1
0 u22 · · · c2
..
0 0 . c3
row j 0 0 ··· ujj · · · ujn ← n − j + 1 1 → cj
..
.
row i 0 0 ··· ?ij · · · ?in ← n − j + 1 1 → ?i
for one i for i = j + 1, . . . , n
op. where? A→U b→c A→U b→c
/ `ij = ?ij /ujj 1 (n − j)
· r = `ij · (Row j) (n − j + 1) 1 (n − j)(n − j + 1) (n − j)
− (Row i) −r (n − j + 1) 1 (n − j)(n − j + 1) (n − j)

Elimination in all steps j = 1, . . . , n − 1. Apply known formulas (sum of the first inte-
gers, sum of the first square numbers):
A → U:
Pn−1
• Divisions: j=1 (n − j) = 21 (n2 − n)
Pn−1
• Multiplications / Subtractions: j=1 (n − j)(n − j + 1) = 13 (n3 − n)
b → c:
Pn−1
• Multiplications / Subtractions: j=1 (n − j) = 21 (n2 − n)
2
Roughly n3 operations for A → U and n2 for b → c.
3

Back substitution. In row j of U x = c, substitute the already known values of xj+1 , . . . , xn

into
ujj xj + uj,j+1 xj+1 + · · · + ujn xn = cj
and solve for xj :
1
xj = (cj − uj,j+1 xj+1 − · · · − ujn xn ) .
ujj
op. for one j for j = n, n − 1, . . . , 1
/ 1 Pn n
· (n − j) (n − j) = 21 (n2 − n)
Pj=1
n 1 2
− (n − j) j=1 (n − j) = 2 (n − n)

Roughly n2 operations.
2 3
Solving Ax = b (for one or more b0 s) takes roughly n operations for A → U , and
3
roughly 2n2 operations per b (b → c, back substitution).

18
2.3.2 The great factorization A = LU
Elimination: A → U (upper triangular). Assumption for now: no row exchanges!

Elimination in row i. Subtract `ij · (Row j of U ) from (Row i):

u11 · · · ← finalized (in U )

0 u22 · · · ← finalized (in U )
.. ..
0 0 . .
row j 0 0 ··· ujj · · · ujn ← finalized (in U )
..
.
row i 0 0 ··· ?ij · · · ?in

Happens in steps j = 1, . . . , i − 1. How does (Row i) change in each step?

(Row i) of A initially
− `i1 · (Row 1) of U step 1
− `i2 · (Row 2) of U step 2
..
.
− `i,i−1 · (Row i − 1) of U step i − 1
= (Row i) of U in the end

(Row i) of A is a combination of the first i rows of U . Matrix notation:

 
(Row i) of A = `i1 `i2 · · · `i,i−1 1 0 · · · 0 U.
| {z }
row vector
  
1 u11 u12 · · · u1n
 `21 1  u22 · · · u2n 
A =  ..
  
..  .. .. 
 . .  . . 
`n1 · · · `n,n−1 1 unn
| {z }| {z }
L, lower triangular U , upper triangular

In this notation, we omit 0’s above/below the diagonal.

2.4 Permutations and Transposes

A = LU fails if there are row exchanges. Is there a fix?
Fact: Reordering the rows of a matrix S reorders the rows of SA in the same way:

19
       
w1 w1 A Example: w2 w2 A
| |

| |

| |

| |

| |

| |

| |

| |
 w2   w2 A 
exchange
 w1   w1 A 
A =  A = 
       
 .. .. 
rows 1, 2
 .. .. 
 .   .   .   . 
wm wm A of S → S 0 wm wm A
|

|
| {z } | {z } | {z } | {z }
S SA S0 S0A

Permutation matrix P : reordering (permutation) of the rows of I. 1 0 0 

0 1 0

P A: permutation of the rows of IA = A. 0 1 0 0 0 1
P x: permutation of the the entries of x. 0 0 1 1 0 0
If P, P 0 are permutation matrices, then also P P 0 : reordering twice is another reordering.
There are n! = 1 · 2 · · · n permutation matrices (n × n), since n things can be ordered in n!
ways:
n n! orderings
1 1 1
2 2 12, 21
3 6 123, 132, 213, 231, 312, 321
4 24 1234, 1243, . . .

2.4.1 The P A = LU factorization

Idea: move all row exchanges to the beginning (A → P A), then we can eliminate without
row exchanges (P A = LU ).
Ej : do all elimination steps in column j
Notation:
P k, ` : exchange rows k and `
   
ujj ujj
| | |

| | |

| | |

| | |
Example (↑ : move row exchange up!): 
 ? 


 ? 

 P k, ` 
A→U P A = LU ? ?
 
   
 ...   ... 
E1 P 2,5
P 2,5 P 2,5 exchange rows 2 and 5    
P 2,5↑ E1
E1 P 3,4 and then rows 3 and 4 ? ?
|

E2 E2
P 3,4↑ E 1
P 3,4 P 3,4↑
E2 E2 Ej Ej
   
1 23 ← move ujj ujj
| | |

| | |

| | |

| | |

Why it works:

 0 


 0 

 P k, ` 
0 0
 
Ej P k, `    
has the same effect as if k, ` > j.  ...   ... 
P k, ` Ej    
0 0
|

20
2.4.2 The transpose of A
 
 1 4
1 2 3
A= ← reflection along ” ” → A> = 2 5
4 5 6
3 6
↑
↑
A23 >
(A )32
row i of A = column i of A> Aij = (A> )ji Scalar product:
column j of A = row j of A> (A> )> = A v> |{z}
v · w = |{z} w
1×n n×1
> > >
Transpose of a product: (AB) = B A
AB ← reflection along ” ” → B > A> :

(AB)ij  (B > A> )ji 

 
   
u1 v1

| |

| |

| |

| |
     
 | | |   | | | 
 
u2 v2
 
 
 v1 v 2 · · · vn  =   u1 u2 · · · um 
   
 ..  ..

 . 
| | | 
  . 
| | | 

um  vn }
|

|
 | {z }  | {z 
| {z } B | {z } A>
A ij B> ji
| {z } | {z }
ui ·vj vj ·ui

Works for more matrices: (ABC)> = C > B > A> .

Transpose of the inverse: (A−1 )> = (A> )−1
AA−1 = I
⇓
(A−1 )> A> = (AA ) = I > =
−1 >
I
⇓
(A−1 )> is the inverse of A>
Permutation matrix: P −1 = P > . Rows of P : p1 , . . . , pn (reordering of rows of I).
Each pi has a single 1 at a different position ⇒ pi · pi = 1, pi · pj = 0 for i 6= j.
 
 
p1

| |

| |

  

p2  | | | 
P P > = I.
 
 1 2 ···
p p pn 
 = Iij ⇔

 ..

 . 
| | | 
 pn }
|

 | {z 
| {z } P T , column picture
P, row picture ij
| {z }
pi ·pj

21
2.4.3 Symmetric matrices
S is symmetric if S = S > (such S must be square).
 
2 1 −3
S= 1 4 7
−3 7 5
If S is symmetric, then also S −1 (if it exists):
(S −1 )> = (S > )−1 = S −1 .
For every matrix A, both A> A and AA> are symmetric:
(A> A)> = A> (A> )> = A> A, (AA> )> = (A> )> A> = AA> .

2.4.4 Symmetric LU-factorization

Normal elimination step: 
  
1 2 1 2 U = L−1 A A = LU
subtract 2·(Row 1) E21 =
2 6 0 2 ⇓ ⇓
from (Row 2)
|{z}
L−1 | {z } | {z }
A, symmetric U D = L−1 A(L> )−1 A = LDL>
Now add this extra step:     ⇑ ⇑
1 2 > 1 0
subtract 2·(Column 1) E21 = D = U (L−1 )> U = DL>
0 2 |{z} 0 2
from (Column 2) | {z } (L−1 )> | {z } = U (L> )−1
U D, diagonal

The general picture: product of elimination matrices

↓
       −1  
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
A= 0 0 0  0 0 0  , U= 0 0 0  A 0 0 0  = 0 0 0 
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
 L   U  L−1 (exercise)
0 0 0 0 0 0 0 0
0 0 0  0 0 0  = U (L−1 )> = L−1 A(L−1 )> ← symmetric, if A is symmetric
0 0 0 0 0 0 (exercise)
U (L−1 )>
(exercise)
=

      
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0  0 0 0  0 0 0  = 0 0 0 
0 0 0 0 0 0 0 0 0 0 0 0
D = U (L−1 )> is upper triangular and symmetric ⇒ D is diagonal.

D = L−1 A(L−1 )> → A = LDL>

22
Chapter 3

The Four Fundamental Subspaces

3.1 Vector Spaces and Subspaces

3.1.1 Examples of vector spaces
There is more than R2 , R3 , . . .
Vector space: (abstract) concept of things that we can do with vectors
R2 , R3 , . . .: examples.
concept number type vector space
things that we . . . numbers: calculations! . . . vectors: combinations!
can do with. . . a + b, a − b, a · b, a/b v + w, c · v
N (natural numbers) R2
Z (integers) R3
Q (rational numbers) C3 (complex vectors)
examples R (real numbers) R2×2 (2 × 2 matrices; A + B, cA (1.3))
C (complex numbers) RR (functions f : R → R)
{0, 1} (bits) {0, 1}n (bit vectors)
.. ..
. .
We mostly (but not only) care about R2 , R3 , . . . and their subspaces.

3.1.2 Subspaces of vector spaces

V : vector space. Subspace: nonempty U ⊆ V satisfying: if v, w ∈ U and c is a scalar, then

(i) v + w ∈ U (ii) cv ∈ U.

Every subspace U contains 0: take some u ∈ U , then 0u = 0 ∈ U by (ii).

Smallest subspace: U = {0}. Largest subspace: U = V .

23
 y y y

x x x

z z z

subspaces: line through 0 plane through 0 not a subspace: misses 0

A subspace of a vector space is itself a vector space.

Two subspaces of V = R2×2:   
a b a 0
U1 : all symmetric matrices U2 : all diagonal matrices
b d 0 d

3.1.3 The column space of A

C(A) = {Ax : x ∈ Rn }
is a subspace of Rm : If v, w ∈ C(A) and c a scalar, then Ax = v and Ay = w for some
x, y ∈ Rn . Hence,

(i) v + w = A(x + y) ∈ C(A) cx ) ∈ C(A)

(ii) cv = A(|{z}
| {z }
∈Rn ∈Rn

3.1.4 The columns of A span the vector space C(A)

Span, Basis Example
V : vector space C(A)
S: sequence of vectors in V the columns of A
S spans V : V = all combinations of S the columns span C(A)
S basis of V : S independent, S spans V the independent columns: basis of C(A)

V S dependent S independent

S spans V ← basis

S doesn’t

24
3.2 Computing the Nullspace by Elimination: A = CR
Nullspace of (m × n) matrix A: all solutions of Ax = 0
      
1 2 1 2 x 0
N : =
3 6 3 6 y 0
N(A) = {x ∈ Rn : Ax = 0} (subspace of Rn ) y
x + 2y = 0
If all columns are independent: N(A) = {0} 3x + 6y = 0
m x
“Computing” a subspace: find a basis of it!
x = −2y
For N(A), we do this by computing A = CR (1.4.2): x = −2y
   
| | | | | | | | | |
A = v1 v2 v3 v4 v 5 v 6 v7  → C = v1 v3 v6  (the independent columns)
| | | | | | | | | |

y v 1 = 1v 1 v4 = r14 v1 + r24 v3
 ↑ ↑ 
1 r12 0 r14 r15 0 r17
R= 1 r24 r25 0 r27  (how to combine them to get all columns)
1 r37

R is in reduced row echelon form: Plan:

1 0 0 0 0
1 0 0 0 Transform A to R using (Gauss-Jordan) elim-
1 0 0 ination; we get C on the way.
0 1 0
1 Row operations don’t change solutions
e1 e2 e3 e4 e5 ··· (2.1.2): Ax = 0 ⇔ Rx = 0, N(A) = N(R).
(standard unit vectors) Read a basis of N(R) off R.

The basis of N(R)

Example: ”free variables”
           ↓ 
1 2 0 3 1 0 x1 2 3 x2 x1 −2 −3 x2
R= Rx = + =0 ⇔ =
0 0 1 −2 0 1 x3 0 −2 x4 x3 0 2 x4
| {z } | {z } | {z } | {z }
(1.4.2) I F −F
     
Two special solutions: set the free variables x2 to
1
,
0
x4 0 1
. . . is a combination of the two special
every
x independent solutions. Since they span ⇓
solution. . .
     N(R), they
   are a basis.
         
x2 x2 1 0 x1 −2 −3
x
 4 x
 4
 0   1 
x2  =
   1  0
= x2     + x4      ,  
x1 x 1 0 x3   0  2
−F 2
    
−F −F
x3 x4 0 1 x4 0 1

25
General case: R is (r × n).
general example
xI : vector of the r variables for e1 , e2 , . . . , er r×n 2 × 4
xF : vector of the n − r other variables (free variables) x2
xF
Rx = IxI + F xF = 0 ⇔ xI = −F xF x 4 
x1
xI
n − r special solutions: set the free variables xF to e1 , e2 , . . . , en−r x3

every . . . is a combination of the n − r special independent

x
solution. . .  solutions.  Since they
 span  N(R), they are a basis.
 
xF xF e1 e2 en−r
= (xF )1 + (xF )2 + · · · + (xF )n−r
xI −F xF −F e1 −F e2 −F en−r

3.2.1 Elimination column by column: the steps from A to R0

k → k + 1 (row operations)
Case 1: only 0’s in blue Case 2: some ? 6= 0 in blue
(dependent column) (independent column)
1 0 0 0 1 0 0 0
1 0 0 1 0 0
1 0 1 0
1 1
0.
.. ?
For k = 0, 1, . . . , n − 1: 0
k columns done: k + 1 columns done: exchange rows:
1 0 0 0 1 0 0 0 1 0 0 0
1 0 0 1 0 0 1 0 0
1 0 1 0 1 0
1 ? 1
0.
1
?
..
0
→ k + 1 columns done multiply row by 1/?:
1 0 0 0
1 0 0
1 0
new row operation → 1
1

n columns done: R0 eliminate in column k + 1:

1 0 0 0 0 0 1 0 0 0 0
1 0 0 0 0 1 0 0 0
1 0 0 0 1 0 0
1 0 0 also above pivot→ 1 0
1 0 1
1 0
0
remove zero rows: R k + 1 columns done:
1 0 0 0 0 0 1 0 0 0 0
1 0 0 0 0 1 0 0 0
1 0 0 0 1 0 0
1 0 0 1 0
1 0 1
1 0
0

26
3.2.2 The matrix factorization A = CR and the nullspace
A → R0 → R gives the same R as in A = CR (1.4.2):

 A = CR  elimination A → R0
 
| | | | | | | | | | | | | |
A = v1 v2 v3 v4 v 5 v 6 v7  → R0 = e1 w2 e2 w4 w5 e3 w7 
| | | | | | | | | | | | | |
(?)

y v1 = 1v1 v4 = r14 v1 + r24 v3 ⇐⇒ w4 = r14 e1 + r24 e2
↑ ↑  ↓ 
  1 r12 0 r14 r15 0 r17
1 r12 0 r14 r15 0 r17  1 r24 r25 0 r27 
R= 1 r24 r25 0 r27  ← R0 =  
 1 r37 
1 r37

 
r14
 0
 
 r24 
  (2.1.2)
−1 :
x= v4 = r14 v1 + r24 v3 ⇔ Ax = 0 ⇐⇒ R0 x = 0 ⇔ w4 = r14 e1 + r24 e2 (?)

 0
 
 0
0

3.3 The Complete Solution to Ax = b

As in (2.1.2), apply row operations also to b (A → R0 , b → c). Solutions don’t change:

Rx = d 
0 = ? 

 If some ? 6= 0, no solution!
Ax = b ⇔ R0 x = c ⇔ .. .. .. c Otherwise, solve
. . . 


0 = ? 
Rx = IxI +F xF = d ⇔ xI = d−F xF
Ax = 0 ⇔ Rx = 0
Particular solution: set the free variables xF to 0
every . . . is a particular solution of Rx = d, plus a
x
solution. . . combination
 of the n − r special
 solutions of Rx  =0 
xF xF 0 e1 e2 en−r
= + (xF )1 + (xF )2 + · · · + (xF )n−r
xI d − F xF d −F e1 −F e2 −F en−r
Ax = b
particular solution every solution
Ax = 0 combination of special solutions
0

27
3.3.1 Number of solutions of Ax = b
rank (number of independent columns) = r r≤n
↓ ⇓
Ax = b → R0 x = c → Rx = d r ≤ min(m, n) full rank: r = min(m, n)
↑ ↑ ↑ ⇑
(m × n) (m × n) (r × n) r≤m

r=n r<n
R0
(full rank) (dependent columns)
invertible underdetermined
(full rank)
r=m

← free variables

1 solution ∞ many solutions

overdetermined
(zero rows)
r<m

← free variables

0 or 1 solution 0 or ∞ many solutions

depending on c (if some ? 6= 0, then 0)

3.4 Independence, Basis, and Dimension

V : vector space

S: sequence of
vectors in V

independent basis of V spans V

e1 , e2 , . . . , en (columns of I): standard basis of Rn .
The columns of any invertible n × n matrix A are a basis of Rn . They are independent and
spanning: for every b ∈ Rn , Ax = b has a solution (2.2.1).
If v1 , v2 , . . . , vn is a basis of V , then every v ∈ V is a unique combination.

28
Proof: if v = a1 v1 + · · · + an vn = b1 v1 + · · · + bn vn , then 0 = (a1 − b1 )v1 + · · · + (an − bn )vn .
By independence, a1 − b1 = · · · = an − bn = 0.

Every basis of V has the same number of vectors.

This number is the dimension dim(V ) of V .

Proof (by contradiction):

Suppose there is a basis v1 , v2 , . . . , vm and a larger basis w1 , w2 , . . . , wn . A basis spans
V ⇒ each wj is a combination of the vi ’s:
w j = ? v1 + ? v 2 + · · · + ? vm
↓ ↓ ↓
vector xj with m numbers
Matrix notation:
 
   | | |
w1 w2 · · · wn = v1 v2 · · · v m x1 x 2 · · ·
 xn 
| {z } | {z } | | |
B A
| {z }
X, m×n

rank(X) ≤ min(m, n) = m < n, so the columns of X are dependent (3.3.1): there is c 6= 0

such that Xc = 0. Then Bc = AXc = A0 = 0 ⇔ c1 w1 + c2 w2 + · · · + cn wn = 0, so the
wj ’s are dependent and not a basis. Contradiction!
Works for all vector spaces, not only (subspaces of) Rn : consider A, B as 1 × m, 1 × n with
vector entries (column vectors, or other objects).

3.4.1 Bases (for Matrix Spaces)

vector space basis dimension
Rn e1 , e2 , . . . , en n
        
a b 1 0 0 1 0 0 0 0
all 2 × 2 matrices , , , 4
c d 0 0 0 0 1 0 0 1
     
a 0 1 0 0 0
diagonal matrices , 2
0 d 0 0 0 1
         
a b 1 0 0 1 0 0 0 0
symmetric matrices , + , 3
b d 0 0 0 0 1 0 0 1

{0} ∅ (empty set) 0

There are no independent vectors in {0}, so the basis must be empty. 0 is a combination
of ∅ (sum of nothing = 0).

29
3.5 Dimensions of the Four Subspaces
A: m × n matrix (m rows, n columns).
This section:
subspace of definition dimension
m
C(A) R combinations of the columns of A r = rank(A)
>
R(A) = C(A ) R n
combinations of the rows of A = columns of A> r
n
N(A) R solutions of Ax = 0 n−r
>
N(A ) R m
solutions of A> y = 0 m−r

Row space R(A) = C(A> )

Gauss-Jordan: A → R0 by row operations:

• subtract c·(Row i) from (Row j)

• exchange (Row i) and (Row j)

• multiply (Row i) with c 6= 0

Exercise: Row operations don’t change the row space! R(A) = R(R0 ).
1 0 0 0 0 0
1 0 0 0 0 r independent rows that span the row space:
1 0 0 0 basis of R(R0 )
R0 : 1 0 0
1 0 dim(R(A)) = dim(R(R0 )) = r
1
zero rows
e1 e2 ··· er
For every matrix: Number of independent rows = number of independent columns!
We knew this for rank-1 matrices (r = 1): (1.3.4)

Nullspace N(A)
Gauss-Jordan: A → R0 → R (remove zero rows of R0 ).
Row operations don’t change the nullspace (2.1.2):
Ax = 0 ⇔ R0 x = 0 ⇔ Rx = 0 N(A) = N(R).
Already found a basis of N(R) with n − r vectors (3.2). dim(N (A)) = n − r.

Left nullspace N(A> )

As previously shown for every matrix: dim(nullspace) = number of columns − rank.
Apply this to A> : dim N(A> ) = m − dim(C(A> )) = m − r.
Why “left”? : all solutions of A> y = 0 = all solutions of y> A = 0> .

30
Chapter 4

Orthogonality

4.1 Orthogonality of vectors and subspaces

Recall (1.2.3, 2.4.2): v, w ∈ Rn are perpendicular or orthogonal if v · w = v> w = 0.
     
4 −1   −1 w v
· = 4 2 = 0.
2 2 2 900
| {z } | {z }
v·w v> w

Two subspaces V and W of Rn are orthogonal if v · w = 0 for all v ∈ V and all w ∈ W .

y y y
W W W

x x x
V V
z z V

If A is m × n:
y
> n
• N(A) and R(A) = C(A ) are orthogonal in R .  
  1 2
1 2
• N(A> ) and R(A> ) = C(A) are orthogonal in Rm . R
3 6 x
Proof. v ∈ N(A) ⇔ Av = 0. w ∈ C(A> ) ⇔ w = A> x.
Then y
 
(1.4.1) (2.4.2) 1 2
v> w = v> (A> x) = (v> A> )x = (Av)> x = 0. N
3 6
| {z }
0>
x
(3.2)
Same for N(A> ) and C(A). x = −2y

31
Exercise: If V and W are orthogonal, V ∩ W = {0} (only the zero vector is in both).
If V and W are subspaces of Rn such that V ∩ W = {0}, y
then dim(V ) + dim(W ) ≤ n.
W
Proof. Let k = dim(V ), ` = dim(W ), v1 , . . . , vk a basis of V ,
w1 , . . . , w` a basis of W . Want to show: these k + ` vectors
are independent. x
Suppose c1 v1 + · · · + ck vk + d1 w1 + · · · d` w` = 0. Then
| {z } | {z }
v∈V w∈W (⇒−w∈W ) z V
v = −w ∈ V ∩ W , so v = w = 0. v1 , . . . , vk and w1 , . . . , w`
are independent ⇒ c1 , . . . , ck = 0 and d1 , . . . , d` = 0 ⇒
v1 , . . . , vk , w1 , . . . , w` are independent (1.3.3) ⇒ k + ` ≤ n. dim(V ) = 2, dim(W ) = 1

4.1.1 Orthogonal complement V ⊥

V subspace of Rn .
Definition: w ∈ Rn is orthogonal to V if w is orthogonal to all vectors in V .
V ⊥ : all vectors in Rn that are orthogonal to V . Exercise: V ⊥ is a subspace.
Let V, W be orthogonal subspaces of Rn . The following statements are equivalent.
V = N(A), W = R(A) = C(A> )
⊥ y
(i) W = V true W
⇑ u
(ii) dim(V ) + dim(W ) = n true: (n − r) + r = n (3.5) w
⇓
v x
n
(iii) every u ∈ R can be written true
V
as u = v + w with unique
vectors v ∈ V, w ∈ W

Proof: v1 , . . . , vk a basis of V , w1 , . . . , w` a basis of W .

(i)⇒(ii): Observation: w ∈ Rn orthogonal to V ⇔ w orthogonal to v1 , . . . , vk . Let A be
the matrix with rows v1 , . . . , vk . Then V = C(A> ) (dimension k) and W = V ⊥ = N(A)
(dimension n − k, 3.5).
(ii)⇒(iii): As previously seen, v1 , . . . , vk , w1 , . . . , w` are independent. Since k + ` = n, they
are a basis of Rn . So
u = c1 v 1 + · · · + ck v k + d 1 w 1 + · · · d ` w `
| {z } | {z }
v w
with unique scalars (3.4) ⇒ unique v, w.
(iii)⇒(i): We need that W contains all vectors orthogonal to V . Let u ∈ Rn be orthogonal
to V . We can write u = v + w with v ∈ V, w ∈ W . Multiplying with v from the left,
>
v
|{z}u = v> v + v >
| {zw} ⇒ v> v = kvk2 = 0 ⇒ v=0 ⇒ u = w ∈ W.
0 0

32
 4.1.2 The big picture
Rm
b 0
C(A)
R(A) = C(A>)
Axrow Ax Axnull N(AT )

xrow x Ax = b

xnull N(A) : Ax = 0
0
Rn

(3.3): Solutions of Ax = b = particular solution of Ax = b + solutions of Ax = 0

(4.1): N(A) and C(A> ), N(A> ) and C(A) are orthogonal subspaces. . .

(4.1.1): . . . and orthogonal complements. For x ∈ Rn : x = xrow + xnull (row space and
nullspace components). If Ax = b, then Axrow = b, Axnull = 0.

33
Index

N (natural numbers), 4 factorization

R (real numbers), 4 CR, 12
0 (zero vector), 4 LU, 19
free variables
associativity of nullspace, 25
matrix multiplication, 12 full rank matrix, 28
back substitution, 13 Gauss elimination, 13
basis Gauss-Jordan elimination, 25
of a vector space, 24
hyperplane, 8
Cauchy-Schwarz inequality, 8 normal vector, 8
collinear vectors, 6
column space identity matrix, 8
of a matrix, 9 independent vectors, 6, 10
combination inner product, 7
of two vectors, 5 intersecting lines, 5
several vectors, 6 inverse
coplanar vectors, 6 of permutation matrix, 21
cosine formula, 8 inverse matrix, 16
CR factorization, 12 of a product, 17
invertible matrix, 16
dependent vectors, 10 characterization, 16
diagonal magtrix, 8
dimension left nullspace
of a vector space, 29 of a matrix, 30
dot product, 7 length
of a vector, 7
elimination line, 8
cost, 17 linear combination, 5
failure, 15 of two vectors, 5
Gauss, 13 several vectors, 6
Gauss-Jordan, 25 linear equation system, 13
pivot, 14 back substitution, 13
success, 15 complete solution, 27
elimination matrix, 14 Gauss elimination, 13
number of solutions, 28

34
 overdetermined, 28 number-matrix, 8
row exchange, 14 number-vector, 5
row operation, 14 vector-matrix, 12
underdetermined, 28 vector-vector
linearly dependent vectors, 10 dot product, 7
linearly independent vectors, 10 inner product, 7
lower triangular matrix, 8 outer product, 12
LU-factorization, 19 scalar product, 7
symmetric, 22
with row exchanges, 20 normal vector, 8
nullspace
matrix, 8 free variables, 25
column picture, 9 of a matrix, 25
column space, 9
diagonal, 8 orthogonal complement, 32
elimination, 14 orthogonal subspaces, 31
full rank, 28 dimensions, 32
identity, 8 orthogonal vectors, 7, 31
inverse, 16 outer product, 12
invertible, 16 overdetermined linear equation system, 28
left nullspace, 30 parallelogram, 5
lower triangular, 8 permutation matrix, 14, 20
nullspace, 25 inverse, 21
free variables, 25 perpendicular vectors, 7, 31
permutation, 14, 20 pivot, 14
rank, 11 plane, 8
rank 1, 11 Pythagoras, 7
reduced row echelon form, 25
row picture, 9 rank
row space, 11 of a matrix, 11
square, 8 rank-1 matrix, 11
symmetric, 8, 22 reduced row echelon form
transpose, 21 of a matrix, 25
upper triangular, 8 row exchange, 14
zero, 8 row operation, 14
matrix multiplication, 11 row space
associativity, 12 of a matrix, 11
matrix notation, 6
matrix space, 29 scalar, 5
matrix-vector multiplication, 9 scalar multiplication, 5
multiplication scalar product, 7
matrix-matrix, 11 span, 9
matrix-vector, 9 spanning vectors

35
 of a vector space, 24 scalar product, 7
square matrix, 8 span, 9
standard unit vector, 7
subspace, 23 zero matrix, 8
subspaces zero vector, 4
orthogonal, 31
symmetric
LU-factorization, 22
symmetric matrix, 8, 22
system of linear equations, 13
transpose
of a matrix, 21
of a product, 21
of the inverse, 21
triangle inequality, 8
underdetermined linear equation system, 28
unit vector, 7
standard, 7
upper triangular matrix, 8
vector
in Rn , 4
length, 7
vector addition, 4
vector space
basis, 24
concept, 23
dimension, 29
spanning vectors, 24
subspace, 23
vector-matrix multiplication, 12
vectors
(linearly) dependent, 10
(linearly) independent, 10
collinear, 6
coplanar, 6
dot product, 7
independent, 6
inner product, 7
orthogonal, 7, 31
outer product, 12
perpendicular, 7, 31

36