The Art of Linear Algebra: Foreword
The Art of Linear Algebra: Foreword
The Art of Linear Algebra: Foreword
Kenji Hiranabe ∗
†
with the kindest help of Gilbert Strang
Abstract
I tried intuitive visualizations of important concepts introduced in “Linear Algebra for Everyone”. 1
This is aimed at promoting understanding of vector/matrix calculations and algorithms from the
perspectives of matrix factorizations. They include Column-Row (CR), Gaussian Elimination (LU ),
Gram-Schmidt Orthogonalization (QR), Eigenvalues and Diagonalization (QΛQT ), and Singular Value
Decomposition (U ΣV T ).
Foreword
I am happy to see Kenji Hiranabe’s pictures of matrix operations in linear algebra ! The pictures are an
excellent way to show the algebra. We can think of matrix multiplications by row · column dot products,
but that is not all – it is “linear combinations” and “rank 1 matrices” that complete the algebra and the art.
I am very grateful to see the books in Japanese translation and the ideas in Kenji’s pictures.
– Gilbert Strang
Professor of Mathematics at MIT
Contents
1 Viewing a Matrix – 4 Ways 1
5 Practical Patterns 6
1
1 Viewing a Matrix – 4 Ways
A matrix (m × n) can be seen as 1 matrix, mn numbers, n columns and m rows.
! ! !
# $ # $ # $
" ! % & ! % & ! % &
' ( ' ( ' (
∗
a11 a12 | | −a1 −
A = a21 a22 = a1 a2 = −a∗2 −
a31 a32 | | −a∗3 −
Here, the column vectors are in bold as a1 . Row vectors include ∗ as in a∗1 . Transposed vectors and
matrices are indicated by T as in aT and AT .
!" ! ! !"#$%&"'()#$$*+(,-.&/ !#
! ! 01+2$3$41#&56
$! ! $! $ %
!
! " # $" & " ' $" & $! ( "$" ( #$# " $ % & "$ "%
$# # $# #$ #%
#
2
3 Matrix times Vector – 2 Ways
A matrix times a vector creates a vector of three dot products (Mv1) as well as a linear combination (Mv2)
of the column vectors of A.
• Sec. 1.1 (p.3) Linear combinations
• Sec. 1.3 (p.21) Matrices and Column Spaces
!"#
! !"$ ! "
$ % * +*! ,%*" - $ % * $ %
! !
!" # & ' * # +&*! , '*" -
!" # & ' * # *! & , *" '
" "
( ) +(*! , )*" - ( ) ( )
At first, you learn (Mv1). But when you get used to viewing it as (Mv2), you can understand Ax as a
linear combination of the columns of A. Those products fill the column space of A denoted as C(A). The
solution space of Ax = 0 is the nullspace of A denoted as N(A).
Also, (vM1) and (vM2) shows the same patterns for a column vector times a matrix.
!"# !
The products fill the row space of A denoted as C(AT ). The solution space of yA = 0 is the left-nullspace
of A denoted as N(AT ).
The four subspaces consists of N(A) + C(AT ) (which are perpendicular to each other) in Rn and N(AT )
+ C(A) in Rm (which are perpendicular to each other).
3
• Sec. 3.5 (p.124) Dimensions of the Four Subspaces
" / !"$!
!! !"
+ "# +,"-
!"# % ' !"# % '
,"-'()*!+ !"#$%&'()*!+
!""#$" !""#"#
!! !"
&$##()*!+
#+./'&$##()*!+
.,"- "# % & .,"# - $" % &
!"# % ( ) ' !"# % * ) '
4
4 Matrix times Matrix – 4 Ways
“Matrix times Vector” naturally extends to “Matrix times Matrix”.
!! ! !! ! !
" #
!!
!!
%
! "
$
! !
FB9?:G9:;3?:<46-H :@6>7<I8465<J46?<636@B=6<A6734I6!6=3?7:;8@D
! " 0 0 2%
KL86G7<5B;8567<J@637869:48376;<=>:43?:<4@6<A67<J@D # $ 0!! 0!" ) 1# 1$ #% ) 1#2%# + 1$2%$
2$
% & "! ""
1%# 1%#E ! " 0!! 0!" "0"! "0""
! " ' ( 0!! 0!" + $ 0"! 0"" ) #0!! #0!" + $0"! $0""
! ! ) #
# $ ' ( ) 1$ E ) 1%$E
%
" " % & %0!! %0!" &0"! &0""
% & 1%& 1%&E
5
5 Practical Patterns
Here, I show some practical patterns which allow you to capture the coming factorizations more intuitively.
!"# ! !$# !
!""#$%&'()(*%)'+&)#(,)-.%/(0.+,(-12(.%'1- !""#$%&'()(*%)'+&)#(,)-.%/(0.+,(-12(#20-
34)#23(2)41(4+#5,&6 34)#23(2)41(.+76
%$ %$ '$' %$ '$'
!" # $! $" $# %% # %$ $! %% $" %& $# "& # %% '% # %% ''%
'
Pattern 1 is a combination of (MM2) and (Mv2). Pattern 2 is an extention of (MM3). Note that Pattern
1 is a column operation (multiplying a matrix from right), whereas Pattern 2 is a row operation (multiplying
a matrix from left).
(P1′ ) multipies the diagonal numbers to the columns of the matrix, whereas (P2 ′ ) multipies the diagonal
numbers to the row of the matrx. Both are variants of (P1) and (P2).
6
!" ! " "
!"#$%&'(()*+%,'-)$%'+.(")*%/.,0#+'(#.+%.1%%/.23,+$4
5.3%6#22%)+/.3+()*%("#$%#+%7#11)*)+(#'28*)/3**)+/)%)93'(#.+$4
&$ '$
!"# $ %! %" %# &% '% $ '$ &$ %! ( '% &% %" ! '& && %#
&& '&
Figure 9: Pattern 3 - (P3)
This pattern appears when you solve differential equations and recurrence equations:
du(t)
= Au(t), u(0) = u0
dt
un+1 = Aun , u0 = u0
[ ]
In both cases, the solutions are expressed with eigenvalues (λ1 , λ2 , λ3 ), eigenvectors X = x1 x2 x3
[ ]T
of A, and the coefficients c = c1 c2 c3 which are the coordinates of the initial condition u(0) = u0 in
terms of the eigenvectors X.
u0 = c1 x1 + c2 x2 + c3 x3
c1
c = c2 = X −1 u0
c3
and the general solution of the two equations are:
7
!" ! " "
!"#$%&'("')"*&+,-."/+0."%+"$")1#"+2"&$.,"3"#$%&'4-)5
$)"'.")'.617$&"8$71-9-'6-.8$71-"/-4+#:+)'%'+.;
&% '%!
!"# ! $ %" %# %$ && '!& $ &% %% '%! ( && %& '!& ! &' %' '!'
&' '!'
Figure 10: Pattern 4 - (P4)
This pattern (P4) works in both eigenvalue decomposition and singular value decomposition. Both de-
compositions are expressed as a product of three matrices with a diagonal matrix in the middle, and also a
sum of rank 1 matrices with the eigenvalue/singular value coefficients.
More details are discussed in the next section.
8
6 The Five Factorizations of a Matrix
• Preface p.vii, The Plan for the Book.
!"#$%$"#$"&'()*+,"-'."'/
! " #$ 0)1'$(2$*)"'3)4,'."'0
5$6#-'&)'()*+,"'46"7'8'4)1'46"7
59 #$(),%)-.&.)"'34),
>0 #$(),%)-.&.)"'6-
C.<$"D6*+$'#$(),%)-.&.)"
(" ')' ! )3'6'-E,,$&4.(',6&4.F'@
C.<$"D$(&)4-'."'>G'$.<$"D6*+$-'." !
@."<+*64'D6*+$'#$(),%)-.&.)"
9
6.1 A = CR
• Sec.1.4 Matrix Multiplication and A = CR (p.29)
All general rectangular matrices A have the same row rank as the column rank. This factorization is the
most intuitive way to understand this theorem. C consists of independent columns of A, and R is the row
reduced echelon form of A. A = CR reduces to r independent columns in C times r independent rows in R.
A = CR
[ ] [ ][ ]
1 2 3 1 2 1 0 1
=
2 3 5 2 3 0 1 1
Procedure: Look at the columns of A from left to right. Keep independent ones, discard dependent ones
which can be created by the former columns. The column 1 and the column 2 survive, and the column 3
is discarded because it is expressed as a sum of the former two columns. To rebuild A by the independent
columns 1, 2, you find a row echelon form R appearing in the right.
! " #
#$%&'
! " ! ! "" ! "" ! "" ! !"
Now you see the column rank is two because there are only two independent columns in C and all the
columns of A are linear combinations of the two columns of C.
! " #
!"#$%
! & ! & " ' !"
' & " '
And you see the row rank is two because there are only two independent rows in R and all the rows of A
are linear combinations of the two rows of R.
10
6.2 A = LU
Solving Ax = b via Gaussian elimination can be expressed as a LU factorization. Usually, you apply
elementary row operation matrices (E) from left of A to make upper trianglar U .
EA = U
A = E −1 U
let L = E −1 , A = LU
# ! "
! " " !
To find L and U , peel off the rank 1 matrix made of the first row and the first column of A. This leaves
A2 . Do this recursively and decompose A into the sum of rank 1 matrices.
! "
" !"#$%
! " !!
"
11
6.3 A = QR
A = QR changes the columns of A into perpendicular columns of Q, keeping C(A) = C(Q).
q1 = a1 /|a1 |
q2 = a2 − (q1T a2 )q1 , q2 = q2 /|q2 |
q3 = a 3 − (q1T a3 )q1 − (q2T a3 )q2 , q3 = q3 /|q3 |
a1 = r11 q1
a2 = r12 q1 + r22 q2
a3 = r13 q1 + r23 q2 + r33 q3
| | | r11 r12 r13
A = q1 q2 q3 r22 r23 = QR
| | | r33
QQT = QT Q = I
# ! " $! $" $#
! ! " " " !"#$%
#!" # # ! # ! " !"
Figure 16: A = QR
The column vectors of A can be adjusted into an orthonormal set: the column vectors of Q. Each column
vector of A can be rebuilt from Q and the upper triangular matrix R .
See Pattern 1 (P1) again for the graphic interpretation.
12
6.4 S = QΛQT
All symmetric matrices S must have real eigenvalues and orthogonal eigenvectors. The eigenvalues are the
diagonal elements of Λ and the eigenvectors are in Q.
| | | λ1 −q1T −
S = QΛQT = q1 q2 q3 λ2 −q2T −
| | | λ3 −q3T −
| [ ] | [ ] | [ ]
= λ1 q1 −q1T − + λ2 q2 −q2T − + λ3 q3 −q3T −
| | |
= λ 1 P 1 + λ 2 P2 + λ 3 P3
A symmetric matrix S is diagonalized into Λ by an orthogonal matrix Q and its transpose. And it is
broken down into a combination of rank 1 projection matrices P = qq T . This is the spectral theorem.
Note that Pattern 4 (P4) is working for the decomposition.
S = S T = λ 1 P1 + λ 2 P2 + λ 3 P3
QQT = P1 + P2 + P3 = I
P1 P2 = P2 P3 = P3 P1 = O
P12 = P1 = P1T , P22 = P2 = P2T , P32 = P3 = P3T
13
6.5 A = U ΣV T
All matrices including rectangular ones have a singular value decomposition (SVD).
A = U ΣV T has the singular vectors of A in U and V . And its singular values in Λ.
• Sec.7.1 (p.259) Singular Values and Singular Vecrtors
Figure 18: A = U ΣV T
You can find V as an orthonormal basis of Rn (eigenvectors of AT A), and U as an orthonormal basis of
R (eigenvectors of AAT ). Together they diagonalize A into Σ. This is also expressed as a combination of
m
rank 1 matrices.
| | | σ1 [ ] | [ | [
−v T
− ] ]
A = U ΣV T = u1 u2 u3 σ2 1
= σ1 u1 −v1T − + σ2 u2 −v2T −
−v2 −
T
| | | | |
= σ1 u1 v1T + σ2 u2 v2T
Note that:
U U T = Im
V V T = In
See Pattern 4 (P4) for the graphic notation.
14