Linear Algebra
Australian National University
1
AlphaFold2
• Protein is a chain of amino acids and has complex 3D structures.
What structural biologists do:
Working hard to find
a crystallization condition
Cryogenic electron microscopy
What AlphaFold2 does:
Iterative refinement
Widely used attention
Noise student training
Noise added to input – robust model training
Jumper et al., Highly accurate protein structure prediction with AlphaFold, Nature, 2021
Vectors
• A simple example of vector, an element of R!
13 ! 𝒚 = 12 ∈ R ” 𝒙= 2⋮ ∈R 3
−1
• Adding two vectors (component wise) 𝒂, 𝒃 ∈ R!: 𝒂+𝒃=𝒄 ∈R!
1 −2 −1 2+5=7 303
• Multiplying 𝒂 ∈ R! by 𝜆 ∈ R results in a scaled vector: 𝜆𝒂 ∈ R!
3
2.1 Systems of Linear Equations • Examples
−𝑥” + 𝑥# + 3𝑥$ = 3 1 𝑥”+𝑥# +2𝑥$=2 (2)
2𝑥# + 5𝑥$ = 1 (3) Does it have solution? No
3 unknowns
𝑥” 𝑥# 𝑥$
Adding the first two equations yields 2𝑥# + 5𝑥$ = 5 . It contradicts Equation (3)
4
2.1 Systems of Linear Equations • Examples
𝑥” + 𝑥# = 1 1 𝑥”− 𝑥# = 3 2
Does it have solution? Yes, it has a unique solution (2,-1)
𝑥” + 𝑥# + 𝑥$ = 0 1 𝑥” + 𝑥# + 2𝑥$ = 2 2
+3𝑥$ = 6 3
Does it have solution? Yes, it has infinitely many solutions
𝑥4 = 2 𝑥5 = −1
𝑥3 = 2
𝑥4 + 𝑥5 = −2
5
2.2 Matrices
• A rectangular scheme consisting of 𝑚 rows and 𝑛 columns:
𝑎33 𝑎34 ⋯ 𝑎35
𝑨= 𝑎43 𝑎44 ⋯ 𝑎45 , 𝑎 ∈R. ⋮ ⋮ ⋮ 78
𝑎63 𝑎64 ⋯ 𝑎65
•Byconvention 1,𝑛-matricesarecalledrowsand 𝑚,1- matrices are called columns. These special matrices are also called row/column vectors.
𝑖th row, 𝑗th column
6
2.2 Matrices •R-×!isthesetofallreal-valued 𝑚,𝑛-matrices.
Space
#rows, #cols
reshape image
classifier
Shanghai
feature
Perhaps the simplest feature representation
7
Matrix – example
RGB image
Gray scale image
5466x3244x3 Binary image
640×427
400×255
3×6
8
0, 255
5466
640
3244
400
0,1
3
255
6
427
2.2.1 Matrix Addition and Multiplication
• The sum of two matrices 𝑨 ∈ R-×!, 𝑩 ∈ R-×! is defined as the element-wise sum,
𝑎”” + 𝑏”” ⋯ 𝑎”! + 𝑏”! -×! 𝑨+𝑩≔ ⋮ ⋮ ∈R
𝑎-“+𝑏-” ⋯ 𝑎-!+𝑏-! 01″×$ −50″×$
• Example
For𝑨=1 2 ∈R ，𝑩= 1 1 ∈R ,weobtain
3 −2 0 −4
−51 “×$ 𝑨+𝑩=23∈R
3 −6
9
2.2.1 Matrix Multiplication
•Example −1 1 $×# 1 2 3 #×$
For𝑨= 01 23∈R ，𝑩=0 2 1∈R ,weobtain
−1×1 + 1×0
−1×3 + 1×1
−1 1 1 2 3 𝑨 𝑩 = 01 23 0 2 1
1 2 3 −1 1 𝑩𝑨 = 0 2 1 0 2
13
−1 0 $×$ = 0 4 2 ∈ R
186
2 14 #×# = 1 7 ∈ R
−2
10
2.2.1 Matrix Addition and Multiplication
• For matrices 𝑨 ∈ R-×!, 𝑩 ∈ R!×3, the element 𝑐45 of the product
𝑪 = 𝑨𝑩 ∈ R-×3 is defined as !
𝑐45 =F𝑎46𝑏65,
67″
𝑖 = 1, … , 𝑚. 𝑗 = 1, … , 𝑘
𝑐45 ≠ 𝑎45𝑏45
• To compute element 𝑐45 we multiply the elements of the 𝑖th row of 𝑨 with the 𝑗th column of 𝑩 and sum them up.
11
2.2.1 Matrix Addition and Multiplication
• One property that is unique to matrices is the dimension property. This property has two parts:
𝑨⏟ 𝑩⏟ = 𝑪⏟ !×’ ‘×) !×)
10⋯0⋯0
01⋯0⋯0
• Identity Matrix
𝑰5 =
10 01
100 𝑰3 = 0 1 0 001
𝑰!≔⋮ ⋮ ⋱ ⋮ ⋱ ⋮∈R!×! 00⋯1⋯0
⋮⋮⋱⋮⋱⋮ 00⋯0⋯1
12
2.2.1 Matrix Addition and Multiplication
• Properties of matrices
• Associativity
∀𝑨 ∈ R-×!,𝑩 ∈ R!×9,𝑪 ∈ R9×:: 𝑨𝑩 𝑪 = 𝑨(𝑩𝑪)
• Distributivity
∀𝑨,𝑩∈R-×!,𝑪,𝑫∈R!×9: 𝑨+𝑩 𝑪=𝑨𝑪+𝑩𝑪 𝑨𝑪+𝑫 =𝑨𝑪+𝑨𝑫
• Multiplication with the identity matrix:
∀𝑨∈R-×!:𝑰-𝑨=𝑨𝑰! =𝑨 𝑰- ≠ 𝑰! for 𝑚 ≠ 𝑛.
13
2.2.2 Inverse and Transpose
• Inverse: consider a square matrix 𝑨 ∈ R!×!. Let matrix 𝑩 ∈ R!×! have the property that 𝑨𝑩 = 𝑰!= 𝑩𝑨. 𝑩 is called the inverse of 𝑨 and denoted by 𝑨;𝟏.
• Example
𝑨𝑩=1 −1 1 1=1 0=𝑰5 010101
𝑨=1 −1,𝑩=1 1 0101
𝑩 = 𝑨P𝟏
The matrices are inverse to each other, because
𝑨𝑩=𝑰# =𝑩𝑨
14
2.2.2 Inverse and Transpose
• Transpose: For 𝑨 ∈ R-×! , the matrix 𝑩 ∈ R!×- with 𝑏45 = 𝑎54 is
called the transpose of 𝑨. We write 𝑩 = 𝑨? 𝑨=1 02,𝑨?=1−10
−1 −5 6 0 −5 1 013 263
• Important properties of inverses and transposes:
𝑨 + 𝑩 ;” ≠ 𝑨;” + 𝑩;” 𝑨𝑨;” = 𝑰 = 𝑨;”𝑨
𝑨? ? = 𝑨
1 ≠1+1 𝑎+𝑏𝑎𝑏
𝑨𝑩 ;” = 𝑩;”𝑨;” 𝑨 + 𝑩 ? = 𝑨? + 𝑩? 𝑨𝑩 ? = 𝑩?𝑨?
𝑨𝑩 @ 𝑩P4𝑨P4 =𝑨𝑰𝑨P4 =𝑨𝑨P4 =𝑰
15
2.2.2 Inverse and Transpose
• Symmetric: A matrix 𝑨 ∈ R!×! is symmetric if 𝑨 = 𝑨?
𝑨= 1 −2 𝑨,= 1 −2 −2 0 −2 0
• The sum of symmetric matrices 𝑨, 𝑩 ∈ R!×! is always symmetric.
?? 𝑨+𝑩= 𝑨+𝑩
1 −2 + 1 3 = 2 1 −2 0 3 −1 1 −1
𝑨 = 𝑨R
• The product of two symmetric matrics is generally not symmetric
1011=11 0011 00
2.2.3 Multiplication by a Scalar • Ascalar𝜆∈R
• Let𝑨∈R-×!.Then𝜆𝑨=𝑲,where𝑘45 =𝜆𝑎45 𝑨=10 3 𝜆=1.5
1.5 0 4.5 3 0 −1.5
2 0 −1
𝜆𝑨 =
2.2.3 Multiplication by a Scalar
• For 𝜆, 𝜑 ∈ R, there following properties hold:
• Associativity • Transpose
• Distributivity
λ𝜑 𝑪=𝜆 φ𝑪 , 𝑪∈R)×!
λ 𝑩𝑪 = 𝜆𝑩 𝑪=𝑩 𝜆𝑪 = 𝑩𝑪 λ,𝑩∈R)×!,𝑪∈R!×’
λ𝑪 , =𝑪,𝜆, =𝑪,λ=λ𝑪,, 𝑪∈R)×!
λ+𝜑 𝑪=𝜆𝑪+𝜑𝑪, 𝑪∈R)×!
λ 𝑩+𝑪 =𝜆𝑩+𝜆𝑪, 𝑩,𝑪∈R)×!
2.2.4 Compact Representations of Systems of Linear Equations
• Consider the system of linear equations,
2𝑥” + 3𝑥# + 5𝑥$ = 1 4𝑥” − 2𝑥# − 7𝑥$ = 8
9𝑥” + 5𝑥# − 3𝑥$ = 2
• Using matrix multiplication, we can write it into a compact form
2 3 5 𝑥” 1
4 −2 −7 𝑥# = 8 𝑨𝒙=𝒃 95−3𝑥$ 2
2.3 Solving Systems of Linear Equations • Now we have a general form of an equation system
⋮
𝑎””𝑥” + 𝑎”#𝑥# + ⋯ + 𝑎”!𝑥! = 𝑏” 𝑎#”𝑥” + 𝑎##𝑥# + ⋯ + 𝑎#!𝑥! = 𝑏A
, 𝑎-“𝑥” + 𝑎-#𝑥# + ⋯ + 𝑎-!𝑥! = 𝑏-
• 2.3.1 Particular and General Solution
Step 1. Find a particular solution to 𝑨𝒙 = 𝒃
Step 2. Find all solutions to 𝑨𝒙 = 𝟎
Step 3. Combine the solutions from steps 1. and 2. to the general solution We use Gaussian elimination to solve the equation system
2.3.2 Elementary Transformations
• Elementary transformations keep the solution set the same, but transform the equation system into a simpler form.
• Elementary transformations include:
• Exchange of two equations
• Multiplication of an equation (row) with a constant 𝜆 ∈ R\ 0
• Addition of two equations (rows)
×3
𝑅1 𝑅1+𝑅2
𝑅2 𝑅2
𝑅3 𝑅3
Row-echelon form (REF) and reduced row- echelon form (RREF)
• Row Echelon Form
• All rows with 0s only are at the
bottom
• A pivot is always strictly to the right
of the pivot of the row above it
From Lorenzo A. Sadun’s teaching video
• Reduced Row Echelon Form • Every pivot is 1
• The pivot is the only non-
zero entry in its column
Gaussian Elimination – example
𝑥” + 𝑥# − 𝑥$ = 9 𝑥# +3𝑥$ =3 −𝑥” − 2𝑥$ = 2
augmented matrix
1 1 −1 9
0133 −1 0 −2 2
R1+R3 -> R3
1 1 −1 9 0133 0 1 −3 11
R3-R2 -> R3
1 1 −1 9 0133 0 0 −6 8
Gaussian Elimination – example
• Seek all solutions to the following system of equations
2𝑥” + 3𝑥# − 2𝑥$ + 5𝑥C = 1 𝑥” + 2𝑥# − 𝑥$ + 3𝑥C = 2 −𝑥” − 2𝑥# + 𝑥$ − 𝑥C = 4
2 3 −2 5 1
1 2 −1 3 2 −1−2 1 −14
Swap R1 and R2
1 2 −1 3 2
2 3 −2 5 1 −1−2 1 −14
R2-2R1 -> R2 1 2 −1 3 2 0−1 0 −1−3
row-echelon form (REF)
R1+R3 -> R3
00026
How to find the general solution to 𝑨𝒙 = 𝒃
2𝑥” + 3𝑥# − 2𝑥$ + 5𝑥C = 1 𝑥” + 2𝑥# − 𝑥$ + 3𝑥C = 2 −𝑥” − 2𝑥# + 𝑥$ − 𝑥C = 4
Gaussian elimination 1 2 −1 3 2 ⇝ 0 −1 0 −1 −3
00026 𝑥” 𝑥# 𝑥$ 𝑥C 𝒃X
Step 1. Find a particular solution to
𝑨𝒙 = 𝒃
Step 2. Find all solutions to 𝑨𝒙 = 𝟎 Step 3. Combine the solutions from steps 1. and 2. to the general solution
Step 1: Finding a particular solution to 𝑨𝒙 = 𝒃
Let free variables be 0, calculate the value of basic variables
1 2 −1 3 2 0−1 0 −1−3 00026
𝑥” 𝑥# 𝑥$ 𝑥C 𝒃X
0+0+0+2𝑥C =6
𝑥$: free variable
𝑥” 𝑥# 𝑥C : basic variables
𝑥C = 3
A particular solution:
−7 0 0 3
0 − 𝑥# + 0 − 𝑥C = −3
𝑥# = 0
𝑥” + 2𝑥# − 𝑥$ + 3𝑥C = 2 𝑥” + 0 − 0 + 9 = 2
𝑥” = −7
Step 2: Find all solutions to 𝑨𝒙 = 𝟎
Let one free variables be 1, and the rest free variables be 0, calculate the
value of basic variables
1 2 −1 3 0 0−1 0 −10 00020
𝑥” 𝑥# 𝑥$ 𝑥C
1 allsolutionsto𝑨𝒙=𝟎: 𝒙∈𝑅Z:𝒙=𝜆 01 ,𝜆∈𝑅
0
Step 3: Combine the solutions from steps 1. and 2. to the general solution
−7 1 allsolutionsto𝑨𝒙=𝒃: 𝒙∈𝑅Z:𝒙= 0 +𝜆 01 ,𝜆∈𝑅
30
We first immediately get 𝑥Z = 0 from Row 3.
After setting 𝑥3 = 1, we have 0−𝑥5 +0−𝑥Z =0,
𝑥4 + 2𝑥5 − 1 + 3𝑥Z = 0
𝟎
Another example
−2𝑥” + 4𝑥# − 2𝑥$ − 𝑥C + 4𝑥K = −3 4𝑥” − 8𝑥# + 3𝑥$ − 3𝑥C + 𝑥K = 2 𝑥” − 2𝑥# + 𝑥$ − 𝑥C + 𝑥K = 0
𝑥” − 2𝑥# −2 4 −2−14−3
4 −8 3 −3 1 2 SwapR1andR3 1 −2 1 −1 1 0
1 −2 0 −3 4 𝑎
− 3𝑥C
1 −2
+ 4𝑥K = 𝑎
1 −1 1 0
4 −8
−2 4 −2−14−3
3 −3 1 2 1 −2 0 −3 4 𝑎
R2-4R1 -> R2 R3+2R1->R3
R4-R1 -> R4
R4-R3 -> R4
1 0
−3 2 R4-R2->R4 0 0
−1 1 −3 2
0 −3 6 −3 0 −3 6 𝑎−2
1 −2 1 −1 0 0 −1 1 0 0 0 −3 0 0 −1 −2
1 −2 1 −1 1 0
1 −2 1 −1 1
0 0 −1 1 −3 2
0 0 0 −3 6 −3 00000𝑎+1
6 −3 0 0
3
𝑎
0 0
0
𝑎 must equal to 1 for this equation system to have solutions
Finding a particular solution to 𝑨𝒙 = 𝒃
Let free variables be 0, calculate the value of basic variables 1−21−1 1 0
0 0 1 −1 3 −2 0 0 0 1 −2 1 000000
𝑥” 𝑥# 𝑥$ 𝑥C 𝑥K
It’s already in the REF. We let 𝑥5 and 𝑥[ be 0.
A particular solution:
2
0 −1 1 0
𝑥0 − 2𝑥1 = 1
𝑥” − 𝑥0 + 3𝑥1 = −2
𝑥2 − 2𝑥$ + 𝑥” − 𝑥0 + 𝑥1 = 0
𝑥0 = 1 𝑥” = −1
𝑥2 = 2
Find all solutions to 𝑨𝒙 = 𝟎
• Let one free variables be 1, and the rest free variables be 0, calculate the value of basic variables 2
1−21−1 1 0 0 0 1 −1 3 0 0 0 0 1 −2 0 000000
𝑥” 𝑥# 𝑥$ 𝑥C 𝑥K
Let𝑥$ be1and𝑥1 be0.Weget
1
0
0 2 0
−1 1
1
Let𝑥$ be0and𝑥1 be1.Weget
22 [10
allsolutionsto𝑨𝒙=𝟎: 𝒙∈𝑅 :𝜆4 0 +𝜆5 −1 ,𝜆4,𝜆5 ∈𝑅 02
01
How to find the general solution to 𝑨𝒙 = 𝒃
• Step 3. Combine the solutions from steps 1. and 2. to the
general solution
Step 1: 𝑥” 2 Step 2: 2 2
𝑥#0 10
𝑥$ = −1 𝒙∈𝑅1:𝒙=𝜆2 0 +𝜆$ −1 ,𝜆2,𝜆$ ∈𝑅
𝑥C 1 𝑥K 0
General solution:
0 21
222 K010
𝒙∈𝑅 :𝒙= −1 +𝜆” 0 +𝜆# −1 ,𝜆”,𝜆# ∈𝑅 102
001
𝑨𝒙 = 𝒃
𝑨𝒙 = 𝟎
Proof
• Given 𝑨 ∈ R&×( with 𝑚 < 𝑛, then 𝑨𝒙 = 𝟎 has infinitely many solutions
• Proof
• This system always has at least one solution since homogeneous • Consider𝑨𝟎=𝟎alwaysholds
• Matrix 𝑨 brought in row echelon form contains at most 𝑚 pivots. 𝟏 −2 0 0 −2
Forexample, 0 0 𝟏 0 1 ∈RZ×[ 0 0 0 𝟏 −2
00000
• There will have 𝑛 − 𝑚 ≥ 1 non-pivot columns, or free variables. It means we can find at least one solution 𝒙∗ ≠ 𝟎. Then, 𝜆𝒙∗, 𝜆 ∈ R are solutions to 𝑨𝒙 = 𝟎.
Proof
• A system of linear equations 𝑨𝒙 = 𝒃 either has no solutions, a unique solution or infinitely many solutions
• Proof
• Let’s assume the system 𝑨𝒙 = 𝒃 has two solutions 𝒑 and 𝒒.
• We have
𝑨𝒑 = 𝒃 𝑨𝒒 = 𝒃
• Consider
𝒗=𝒑+𝑡𝒒−𝒑,𝑡∈R
• We have
𝑨𝒗=𝑨 𝒑+𝑡 𝒒−𝒑 =𝑨𝒑+𝑡 𝑨𝒒−𝑨𝒑 =𝒃+𝑡 𝒃−𝒃 =𝒃
• We thus have infinitely many solutions (by varying 𝑡)
proof by contradiction
a form of proof that establishes the truth or the validity of a proposition, by showing that assuming the proposition to be false leads to a contradiction.
Calculating the Inverse with Gaussian Elimination
• To compute the inverse 𝑨;𝟏 of 𝑨 ∈ R!×! ,
• We need to find a matrix 𝑿 that satisfies 𝑨𝑿 = 𝑰𝒏.
• Then,𝑿=𝑨;𝟏 .
• We can write this down as a set of simultaneous linear equations𝑨𝑿=𝑰𝒏,wherewesolvefor𝑿= 𝒙𝟏|⋯|𝒙𝒏
• We use the augmented matrix notation and use Gaussian Elimination.
𝑰𝒏|𝑨B𝟏
𝑨|𝑰𝒏 ⇝⋯⇝
Calculating the Inverse with Gaussian Elimination
𝑨|𝑰𝒏 ⇝⋯⇝
𝑰𝒏|𝑨B𝟏
Calculating the Inverse with Gaussian Elimination • Example: determine the inverse of
1020
𝑨= 1 1 0 0 ∈𝑅C 1201
1111
• First, write down the augmented matrix
10201000 11000100 12010010 11110001
𝑨=
𝑨
𝑰𝒏
Calculating the Inverse with Gaussian Elimination
• Use Gaussian elimination to bring it into reduced row-echelon form (RREF)
1 0 2 0 1 0 0 0 1 0 0 0 −1 2 −2 2 𝑨=11000100⇝⋯⇝𝑨=01001 −1 2 −2 1 2 0 1 0 0 1 0 0 0 1 0 1 −1 1 −1
1 1 1 1 0 0 0 1 0 0 0 1 −1 0 −1 2
• The desired inverse is given as its right-hand side
REF
−1 2 −2 2 1 −1 2 −2 1 −1 1 −1
𝑨P𝟏
𝑨B2 =
−1 0 −1 2
Calculating Reduced Row-echelon form - example
2 −2 4 −2 R2-R1->R2 2 −2 4 −2 2 −2 4 −2
2 1 10 7 R3+2R1->R3 0 3 6 9 Swap 0 3 6 9 −4 4 −8 4 R4-2R1->R4 0 0 0 0 R3andR4 0 3 6 10 4 −1 14 6 0 3 6 10 0 0 0 0
2 −2 4 −2 Multiplication 1 −1 2 −1 R3-R2->R3 0369 0123
0 0 0 1 byscalar 0 0 0 1 0000 0000
R1+R3->R1 1−120R1+R2->R1 1040 0120 0120
R2-3R3->R2 0 0 01 0001
This matrix is not invertible
REF
≠ 𝑰0 0000 0000
RREF
Moore-Penrose pseudo-inverse
• We can calculate 𝑨;”only when 𝑨 is a square matrix and is invertible
• Otherwise, under mild conditions, we can use the following pseudo-inverse:
𝑨𝑥=𝒃 ⇔ 𝑨I𝑨𝑥= 𝑨I𝒃⇔𝑥= 𝑨I𝑨 J3𝑨I 𝒃 • 𝑨?𝑨 ;”𝑨? is the Moore-Penrose pseudo-inverse of 𝑨
Check your understanding
• Which of the following are correct?
(A) A vector, when multiplied by a scale, is still a vector. True
(B) For a system of linear equations with 𝑛 variables, it is possible that none of them are free variables. True
(C)For a system of linear equations with 𝑛 variables, the maximum number of pivots in the REF is 𝑛 − 1. False
(D) A matrix, when added by an identity matrix, stays as is. False (E) We can use matrix transpose in Gaussian Elimination. False (F) Two arbitrary matrices can be multiplied False
(G)Two arbitrary matrices can be added. False
(H)An image with black borders is not a matrix.
False
Check your understanding
• Let A, B, C be 2×2 matrices.
• Which of the following are equivalent to A(B+C)?
• AB+AC
• BA+CA
• A(C+B)
• (B+C)A
• Which of the following expressions are equivalent to I2(AB)?
• AB
• BA
• (AB)I2
• (BA)I2