Lecture plan

▶ Function of matrices
▶ Matrix power
▶ Inverse matrix
▶ Inverse matrix
▶ Definition and properties
▶ Simple examples
▶ Gauss-Jordan elimination to find A−1
▶ Transposition of matrices
▶ Definition and properties
▶ Examples
▶ A = LU factorization
Classification of functions

▶ Scalar functions
▶ y(x) scalar function of scalar argument
▶ y(x) scalar function of vector argument
▶ y(X) scalar function of matrix argument
▶ Example: determinant of a matrix, det X
▶ Vector functions
▶ y(x) vector function of scalar argument
▶ Example: position of a particle in R2 as a function of time
▶ y(x) vector function of vector argument
▶ Example: transformation from cartesian to polar coordinates
▶ y(X) vector function of matrix argument
▶ Matrix functions
▶ Y (x) matrix function of scalar argument
▶ Y (x) matrix function of vector argument
▶ Y (X) matrix function of matrix argument
Matrix functions of matrices

▶ Elementary functions eA , ln A, sin A, cos A, . . . (advance

topic)
▶ Matrix powers
An = AA | {z . . . A}
n times

▶ A0 = I by definition
▶ A−1 (inverse matrix) — the main issue of our study
Inverse matrix

Definition
A square matrix A is invertible (non-singular) if there exists a
matrix A−1 such that AA−1 = I and A−1 A = I

Properties and features

▶ The matrix A cannot have two different inverses
▶ if BA = I (B is a left inverse) and AC = I (C is a right
inverse)
▶ BAC = B(AC) = BI = B
▶ BAC = (BA)C = IC = C =⇒ B = C
▶ If A is invertible then solution to Ax = b is x = A−1 b
▶ if Ax = b =⇒ A−1 Ax = A−1 b =⇒ x = A−1 b
▶ when solving Ax = b for different b’s, it is more convenient to
compute x = A−1 b (not doing elimination for every b)
▶ Not all matrices have inverses
Inverse matrix
Properties and features
▶ A−1 exists if and only if elimination produces n pivots
▶ Elimination solves Ax = b without explicitly using A−1
▶ If there is x ̸= 0 such that Ax = 0 =⇒ A−1 does not exist
▶ Proof: A−1 Ax = 0 =⇒ x = 0 =⇒ contradiction
▶ No inverse if we can find x ̸= 0 such that Ax = 0
▶ Example
    
1 3 3 0
=
2 6 −1 0
| {z } | {z } | {z }
A x 0

▶ observation: columns of A are linearly dependent

     
1 3 0
3+ (−1) =
2 6 0
▶ observation: rows of A are linearly dependent

(1, 3) 2 + (2, 6) (−1) = (0, 0)

example: why A−1 does not exist (row picture)

▶ by definition (and using the 3rd way of matrix multiplication)

      
α β 1 3 (1, 3) α + (2, 6) β 1 0
= =
γ δ 2 6 (1, 3) γ + (2, 6) δ 0 1
| {z } | {z } | {z }
A−1 A I

▶ no linear combination of rows of A can produce (1, 0)

(1, 3) α + (2, 6) β = (1, 3) (α + 2β) ̸= (1, 0)

example: why A−1 does not exist (column picture)

▶ by definition (and using the 2nd way of matrix multiplication)

             
1 3 α β 1 3 .. 1 3 1 0
= α+ γ . β+ δ =
2 6 γ δ 2 6 2 6 0 1
| {z } | {z } | {z }
A A−1 I
 
1
▶ no linear combination of columns of A can produce
0
       
1 3 1 1
α+ γ= (α + 3γ) ̸=
2 6 2 0
example: solvability with singular A (column picture)

▶ Ax = b with singular A (not existing A−1 ) is solvable iff b is

a linear combination of columns of A
▶ In our example, solvable iff b2 − 2b1 = 0
    
1 3 x1 b1
=
2 6 x2 b2
| {z } | {z } | {z }
A x b

▶ Solution is not-unique (multiplicity of solutions)

           
1 3 b1 1 1 1
x1+ x2 = =⇒ x1+ 3x2 = b =⇒ x1 +3x2 = b1
2 6 2b1 2 2 2 1
Inverse matrix
Properties and features
▶ If A−1 exists the only one solution to Ax = b is x = A−1 b
▶ Proof: if y ̸= x is another solution, that is Ay = b then
Ax − Ay = A(x − y) = 0 and since x − y ̸= 0 it implies
that A is not invertible, which contradicts to our assumption.
▶ If A is invertible its rows/columns are linearly independent

▶ The inverse of a product (AB)−1 = B −1 A−1

▶ Proof:
−1 −1 −1
(AB)(AB)−1 = A |BB
{z } A = AA = I
I

▶ Extension to multiple factors:

(AB . . . Y Z)−1 = Z −1 Y −1 . . . B −1 A−1

▶ (A−1 )−1 = A
Inverse Matrix
Easy examples
▶ Diagonal matrix
   
d1 . . . 0 1/d1 . . . 0
 .. . . .. 
A= . =⇒ A−1 =  ... .. .. 

. .  . . 
0 ... dn 0 . . . 1/dn

▶ Elimination matrix: E −1
ij (l) = E ij (−l)
   
1 0 0 1 0 0
E 31 (2) =  0 1 0  , E −1
31 (2) =
 0 1 0  = E 31 (−2)
2 0 1 −2 0 1

▶ A formula to remember (2 × 2 matrix)

 −1  
a b 1 d −b
=
c d ad − bc −c a
| {z }
determinant
Computing A−1 by the Gauss-Jordan elimination

Preliminaries
▶ Fact1 if B ≜ [b1 b2 . . . bn ] then
AB = A [b1 b2 . . . bn ] = [Ab1 Ab2 . . . Abn ]
▶ Fact2 for Ax = b the solution x = A−1 b.
Let A−1 ≜ [α1 α2 . . . αn ] and b = (b1 , b2 , . . . , bn ) then

x = A−1 b = α1 b1 + α2 b2 + . . . + αn bn

▶ If b = (1, 0, . . . , 0) ≜ e1 =⇒ x = α1
▶ If b = (0, 1, . . . , 0) ≜ e2 =⇒ x = α2
▶ If b = (0, 0, . . . , 1) ≜ en =⇒ x = αn

By solving Ax = b for b = e1 , b = e2 , . . . , b = en , one can

find all the columns α1 , α2 , . . . , αn of the inverse matrix A−1 .
Computing A−1 by the Gauss-Jordan elimination
Key idea
▶ To solve Ax = b for b = e1 , b = e2 , . . . , b = en at once
▶ Write
 down the augmented
 matrix

A |e1 |e2 | . . . |en  = [A | I]

| {z }
I
▶ For the augmented block matrix [A | I] we have

A−1 [A | I] = I | A−1
 

▶ Main idea transform [A | I] =⇒ I | A−1 by elementary

 

(forward and backward) transformations

▶ Gaussian elimination implies forward processing only.
Gauss-Jordan elimination combines both the forward
elimination and the backward substitution
Example 1: find A−1
 
1 3
A=
2 7

▶ By definition
    
1 3 a c 1 0
=
2 7 b d 0 1
| {z } | {z } | {z }
A A−1 I

▶ The problem is reduced to solving two systems

           
1 3 a 1 1 3 c 0
= and =
2 7 b 0 2 7 d 1
| {z } | {z } | {z } | {z }
A Col1 (A−1 ) A Col2 (A−1 )

▶ Can be solved “at once” by transforming [A|I] =⇒ I | A−1

 
Example 1: transforming [A|I] =⇒ I | A−1
 

   
1 3 1 3 1 0
A= , [A|I] =
2 7 2 7 0 1

▶ Step1 (Gauss): −2 row1 + row2 → row2

    
1 0 1 3 1 0 1 3 1 0
=
−2 1 2 7 0 1 0 1 −2 1
| {z } | {z } | {z }
E 21 (−2) [A|I] E 21 [A|I]

▶ Step2 (Jordan): −3 row2 + row1 → row1

    
1 −3 1 3 1 0 1 0 7 −3
=
0 1 0 1 −2 1 0 1 −2 1
| {z } | {z } | {z }
E 12 (−3) [A|I] E 12 E 21 [A|I]

The left block is I, and the right one is A−1 .

Example 1: [A|I] =⇒ I | A−1 continued
 
We found
    
−1 7 −2 1 −3 1 0
A = =
−3 1 0 1 −2 1
| {z } | {z }
E 12 (−3) E 21 (−2)

Check that
    
1 3 7 −3 1 0
=
2 7 −2 1 0 1
| {z } | {z } | {z }
A A−1 I

Also check that

     
1 3 −1 1 0 1 −3
A= = {E 12 (−3)E 21 (−2)} =
2 7 2 1 0 1
| {z } | {z }
E −1 −1
21 (−2)=E 21 (2) E 12 (−3)=E 12 (3)

is the product of lower and upper triangular matrices

Example 2: find A−1  
2 −1 0
A =  −1 2 −1 
0 −1 2

▶ By definition
    
2 −1 0 a d g 1 0 0
 −1 2 −1   b e h  =  0 1 0 
0 −1 2 c f k 0 0 1
| {z }| {z } | {z }
A A−1 I

▶ The problem is reduced to solving three systems

           
a 1 d 0 g 0
A  b  = 0 , A
   e  = 1 , A
   h  = 0 

c 0 f 0 k 1
| {z } | {z } | {z }
Col1 (A−1 ) Col2 (A−1 ) Col3 (A−1 )

▶ Can be solved “at once” by transforming [A|I] =⇒ I | A−1

 
Example 2: transforming [A|I] =⇒ I | A−1
 

   
2 −1 0 2 −1 0 1 0 0
A =  −1 2 −1  , [A|I] =  −1 2 −1 0 1 0 
0 −1 2 0 −1 2 0 0 1

▶ Step1 (Gauss): 1
2 row1 + row2 → row2
  
1 0 0 2 −1 0 1 0 0
 1 1 0   −1 2 −1 0 1 0 =
2
0 0 1 0 −1 2 0 0 1
| {z }| {z }
E 21 ( 12 ) [A|I]
 
2 −1 0 1 0 0
3 1
 0
2 −1 2 1 0

0 −1 2 0 0 1
| {z }
E 21 [A|I]
Example 2: [A|I] =⇒ I | A−1 continued
 

 
2 −1 0 1 0 0
3 1
E 21 [A|I] = 0 2 −1 2 1 0
 
0 −1 2 0 0 1

▶ Step2 (Gauss): 2
3 row2 + row3 → row3
  
1 0 0 2 −1 0 1 0 0
3 1
 0 1 0  0
2 −1 2 1 0
=
0 23 1 0 −1 2 0 0 1
| {z }| {z }
E 32 ( 23 ) E 21 [A|I]
 
2 −1 0 1 0 0
3 1
2 −1
 0 1 0 
2
4 1 2
0 0 3 3 3 1
| {z }
E 32 E 21 [A|I]
The left block is upper triangular, but we need to make it I.
Example 2: [A|I] =⇒ I | A−1 continued
 

 
2 −1 0 1 0 0
3 1
E 32 E 21 [A|I] = 0 2 −1 1 0 

2
4 1 2
0 0 3 3 3 1

▶ Step3 (Jordan): 3
4 row3 + row2 → row2
  
1 0 0 2 −1 0 1 0 0
 0 1 3  0 3
−1 1
1 0 =
4 2 2
4 1 2
0 0 1 0 0 3 3 3 1
| {z }| {z }
E 23 ( 34 ) E 32 E 21 [A|I]
 
2 −1 0 1 0 0
 0 3 3 3 3
2 0 4 2 4

4 1 2
0 0 3 3 3 1
| {z }
E 23 E 32 E 21 [A|I]
Example 2: [A|I] =⇒ I | A−1 continued
 

 
2 −1 0 1 0 0
3 3 3 3
E 23 E 32 E 21 [A|I] =  0 2 0 4 2 4

4 1 2
0 0 3 3 3 1

▶ Step4 (Jordan): 23 row2 + row1 → row1

1 23 0
  
2 −1 0 1 0 0
 0 1 0  3 3 3 3
0 2 0 4 2 4
=
4 1 2
0 0 1 0 0 3 3 3 1
| {z }| {z }
E 12 ( 23 ) E 23 E 32 E 21 [A|I]
3 1
 
2 0 0 2 1 2
 0 3 3 3 3
2 0 4 2 4

4 1 2
0 0 3 3 3 1
| {z }
E 12 E 23 E 32 E 21 [A|I]
The left block is already diagonal, but we need to make it I.
Example 2: [A|I] =⇒ I | A−1 continued
 

3 1
 
2 0 0 2 1 2
3 3 3 3
E 12 E 23 E 32 E 21 [A|I] =  0 2 0 4 2 4

4 1 2
0 0 3 3 3 1

▶ Step5 (Jordan): 12 row1 → row1; 2

3 row2 → row2; 3
4 row3 →
row3.
 1  3 1

2 0 0 2 0 0 2 1 2
 0 2 0  0 3
0 3 3 3 =
3 2 4 2 4
0 0 34 0 0 4
3
1
3
2
3 1
| {z }| {z }
S( 12 , 23 , 34 ) E 12 E 23 E 32 E 21 [A|I]
3 1 1
 
1 0 0 4 2 4
 0 1 0 1 1
2 1 2

1 1 3
0 0 1 4 2 4
| {z }
SE 12 E 23 E 32 E 21 [A|I]
−1
The left block is I, the right one is the inverse matrix A .
Example 2: [A|I] =⇒ I | A−1
 
We found
3 1 1
 
4 2 4
A−1 =  1
2 1 1
2
 = SE 12 E 23 E 32 E 21
3 1 3
4 2 4

Check that
3 1 1
    
2 −1 0 4 2 4 1 0 0
 −1 1 1
2 −1   2 1 2
= 0 1 0 
3 1 3
0 −1 2 4 2 4 0 0 1
| {z }| {z } | {z }
A A−1 I

Note that A can be represented as a product of two (upper and

lower) triangular matrices
−1 −1 −1 −1 −1
A = E21 E E E12 S
| {z 32} | 23 {z }
lower upper
Example 3: find A−1  
2 4 −2
A= 4 9 −3 
−2 −3 7

▶ By definition
    
2 4 −2 a d g 1 0 0
 4 9 −3   b e h  =  0 1 0 
−2 −3 7 c f k 0 0 1
| {z }| {z } | {z }
A A−1 I

▶ The problem is reduced to solving three systems

           
a 1 d 0 g 0
A  b  = 0 , A
   e  = 1 , A
   h  = 0 

c 0 f 0 k 1
| {z } | {z } | {z }
Col1 (A−1 ) Col2 (A−1 ) Col3 (A−1 )

▶ Can be solved “at once” by transforming [A|I] =⇒ I | A−1

 
Example 3: transforming [A|I] =⇒ I | A−1
 

   
2 4 −2 2 4 −2 1 0 0
A= 4 9 −3  , [A|I] =  4 9 −3 0 1 0 
−2 −3 7 −2 −3 7 0 0 1

▶ Step1 (Gauss): −2 row1 + row2 → row2

  
1 0 0 2 4 −2 1 0 0
 −2 1 0   4 9 −3 0 1 0 =
0 0 1 −2 −3 7 0 0 1
| {z }| {z }
E 21 (−2) [A|I]
 
2 4 −2 1 0 0
 0 1 1 −2 1 0 
−2 −3 7 0 0 1
| {z }
E 21 [A|I]
Example 3: [A|I] =⇒ I | A−1 continued
 

 
2 4 −2 1 0 0
E 21 [A|I] =  0 1 1 −2 1 0 
−2 −3 7 0 0 1

▶ Step2 (Gauss): 1 row1 + row3 → row3

  
1 0 0 2 4 −2 1 0 0
 0 1 0  0 1 1 −2 1 0  =
1 0 1 −2 −3 7 0 0 1
| {z }| {z }
E 31 (1) E 21 [A|I]
 
2 4 −2 1 0 0
 0 1 1 −2 1 0 
0 1 5 1 0 1
| {z }
E 31 E 21 [A|I]
Example 3: [A|I] =⇒ I | A−1 continued
 

 
2 4 −2 1 0 0
E 31 E 21 [A|I] =  0 1 1 −2 1 0 
0 1 5 1 0 1

▶ Step3 (Gauss): −1 row2 + row3 → row3

  
1 0 0 2 4 −2 1 0 0
 0 1 0  0 1 1 −2 1 0  =
0 −1 1 0 1 5 1 0 1
| {z }| {z }
E 32 (−1) E 31 E 21 [A|I]
 
2 4 −2 1 0 0
 0 1 1 −2 1 0 
0 0 4 3 −1 1
| {z }
E 32 E 31 E 21 [A|I]
The left block is upper triangular, but we need to make it I.
Example 3: [A|I] =⇒ I | A−1 continued
 

 
2 4 −2 1 0 0
E 32 E 31 E 21 [A|I] = 0 1
 1 −2 1 0 
0 0 4 3 −1 1

▶ Step4 (Jordan): − 14 row3 + row2 → row2

  
1 0 0 2 4 −2 1 0 0
 0 1 −1   0 1 1 −2 1 0 =
4
0 0 1 0 0 4 3 −1 1
| {z }| {z }
E 23 (− 14 ) E 32 E 31 E 21 [A|I]
 
2 4 −2 1 0 0
 0 1 0 − 11
4
5 1 
4 −4
0 0 4 3 −1 1
| {z }
E 23 E 32 E 31 E 21 [A|I]
Example 3: [A|I] =⇒ I | A−1 continued
 

 
2 4 −2 1 0 0
E 23 E 32 E 31 E 21 [A|I] =  0 1 0 − 11
4
5 1 
4 −4
0 0 4 3 −1 1

▶ Step5 (Jordan): 1
2 row3 + row1 → row1

1 0 12
  
2 4 −2 1 0 0
 0 1 0  0 1 0 − 11
4
5 1 
4 −4 =
0 0 1 0 0 4 3 −1 1
| {z }| {z }
E 13 ( 12 ) E 23 E 32 E 31 E 21 [A|I]
5
− 21 1
 
2 4 0 2 2
11 5
 0 1 0 −4 4 − 14 
0 0 4 3 −1 1
| {z }
E 13 E 23 E 32 E 31 E 21 [A|I]
Example 3: [A|I] =⇒ I | A−1 continued
 

5
− 12 1
 
2 4 0 2 2
11 5
E 13 E 23 E 32 E 31 E 21 [A|I] =  0 1 0 −4 4 − 41 
0 0 4 3 −1 1

▶ Step6 (Jordan): −4 row2 + row1 → row1

5
− 12 1
  
1 −4 0 2 4 0 2 2
11 5
 0 1 0  0 1 0 −4 4 − 14 =
0 0 1 0 0 4 3 −1 1
| {z }| {z }
E 12 (− 14 ) E 13 E 23 E 32 E 31 E 21 [A|I]
27
− 11 3
 
2 0 0 2 2 2
 0 1 0 − 11
4
5
4
1
−4 
0 0 4 3 −1 1
| {z }
E 12 E 13 E 23 E 32 E 31 E 21 [A|I]
The left block is already diagonal, but we need to make it I.
Example 3: [A|I] =⇒ I | A−1 continued
 

27
− 11 3
 
2 0 0 2 2 2
11 5
E 12 E 13 E 23 E 32 E 31 E 21 [A|I] =  0 1 0 −4 4 − 14 
0 0 4 3 −1 1

▶ Step7 (Jordan): 1 1
2 row1 → row1; 4 row3 → row3

1 27
− 11 3
  
0 0
2 2 0 0 2 2 2
 0 1 0  0 1 0 − 11
4
5
4 − 14 =
0 0 14 0 0 4 3 −1 1
| {z }| {z }
S( 12 ,1, 14 ) E 12 E 13 E 23 E 32 E 31 E 21 [A|I]
27
− 11 3
 
1 0 0 4 4 4
 0 1 0 − 11
4
5
4 − 14 
3 1 1
0 0 1 4 −4 4
| {z }
SE 12 E 13 E 23 E 32 E 31 E 21 [A|I]
−1
The left block is I, the right one is the inverse matrix A .
Example 3: [A|I] =⇒ I | A−1 continued
 
We found
27
− 11 3
 
4 4 4
A−1 =  − 11
4
5
4 − 14  = SE 12 E 13 E 23 E 32 E 31 E 21
3
4 − 14 1
4

Check that
  27
− 11 3
   
2 4 −2 4 4 4 1 0 0
 4 9 −3   − 11
4
5
4 − 41 = 0 1 0 
3
−2 −3 7 4 − 41 1
4 0 0 1
| {z }| {z } | {z }
A A−1 I

Note that A can be represented as a product of two (upper and

lower) triangular matrices
−1 −1 −1 −1 −1 −1 −1
A = E21 E31 E32 E23 E13 E12 S
| {z }| {z }
lower upper
Lecture plan

▶ Matrix transpose
▶ Examples and notation
▶ Definition and properties
▶ Useful representations:
▶ inner and outer vector products
▶ symmetric and skew-symmetric matrices
▶ Transpose of permutation matrices
▶ A = LU factorization
Transposition: definition & examples
▶ Transposition is non-algebraic operation
▶ Columns of A become rows of AT and rows of A become
columns of AT
▶ (i-th row, j-th column) element of AT is
 T
(j-th row, i-th column) element of A: A ij = [A]ji
▶ Examples

  1 4
1 2 3
A= AT =  2 5 
4 5 6
3 6

1  
A= 2  AT = 1 2 3
3

▶ If A is an m × n matrix then AT is an n × m matrix.

Notation for inner and outer products

▶ Inner (dot/scalar) product

 
y1
n
T
  y2  X
x y= x1 x2 . . . xn  = x i yi
 
..
 . 
i=1
yn

▶ Outer (tensor/diadic) product

   
x1 x1 y1 x1 y2 . . . x1 ym
 x2     x2 y1 x2 y2 . . . x2 ym 
xy T =  .  y1 y2 . . . ym =  .
   
.. .. ..
 ..   ..

. . . 
xn xn y1 xn y2 . . . xn ym
Basic properties of transposition

▶ (AT )T = A
▶ (cA)T = cAT , where c is a scalar
▶ (A + B)T = AT + B T
▶ (AB)T = ?
(AB)T = B T AT

▶ recall that for any matrix [AT ]ij = [A]ji

▶ recall that rowi (A) = coli (AT ) and coli (A) = rowi (AT )
Proof:
▶ [AB]ij = rowi (A) · colj (B)
▶ [(AB)T ]ij = [AB]ji = rowj (A) · coli (B)
▶ [B T AT ]ij = rowi (B T ) · colj (AT )
▶ [B T AT ]ij = coli (B) · rowj (A) = [(AB)T ]ij
Basic properties of transposition

▶ (AT )T = A
▶ (cA)T = cAT , where c is a scalar
▶ (A + B)T = AT + B T
▶ (AB)T = B T AT
▶ (ABC . . . XY Z)T = Z T Y T X T . . . C T B T AT
▶ for square matrices (A−1 )T = (AT )−1 ≜ A−T
▶ proof:
▶ A−1 A = I =⇒ (A−1 A)T = I T =⇒ AT (A−1 )T = I
▶ but by definition of the inverse of AT we have AT (AT )−1 = I
▶ note
▶ Ax is the linear combination of the columns of A
▶ (Ax)T = xT AT is the linear combination of the rows of AT
Symmetric and skew-symmetric matrices
▶ Symmetric and skew-symmetric matrices are square
▶ Symmetric matrix: aij = aji or A = AT
▶ Skew-symmetric matrix aij = −aji or A = −AT
▶ Diagonal elements of skew-symmetric matrices are zeros
(aii = −aii =⇒ aii = 0)
▶ A + AT is always symmetric

T
T
▶ A + AT = AT + AT = AT + A = A + AT
▶ A − AT is always skew-symmetric

T
T
▶ A − AT = AT − AT = AT − A = −(A − AT )
▶ Any square matrix can be decomposed as

A + AT A − AT
   
A= + = Asym + Askew
2 2
| {z } | {z }
symmetric skew-symmetric
Rectangular matrices
▶ If R is a rectangular m × n matrix then RT is a rectangular
n × m matrix
▶ R RT is m × m symmetric matrix: (R RT )T = R RT
example  
  1 0  
1 2 1  6 2
2 1 =
0 1 0 2 1
| {z } 1 0 | {z }
R | {z } RRT
RT

▶ RT R is n × n symmetric matrix: (RT R)T = RT R

example
   
1 0   1 2 1
 2 1  1 2 1
= 2 5 2 
0 1 0
1 0 | {z } 1 2 1
| {z } R | {z }
RT RT R
Transpose of permutation matrices
▶ Definition: a square matrix that has exactly one entry 1 in
each row and each column and 0s elsewhere
▶ Row exchange matrices
         
0 1 0 x1 x2 0 0 1 x1 x3
 1 0 0   x2  =  x1  ,  1 0 0   x2  =  x1  .
0 0 1 x3 x3 0 1 0 x3 x2

▶ Multiple permutations

▶ Inverse is transpose
P −1 = P T

xT x = (P x)T (P x) = xT P T P x =⇒ P T P = I =⇒ P T = P −1
LU factorization

▶ is one of many other useful factorizations

▶ A = LU represents the factorization of A in terms of two
matrices
▶ L is lower triangular and U is upper triangular
▶ the factorization is useful for solving Ax = b =⇒ LU x = b.
▶ if U and L are known one can use a two-step procedure
▶ first, denote U x by c and solve Lc = b
▶ then solve U x = c
▶ U and L can be established (up to scaling) from the
Gauss-Jordan procedure
▶ multiplying a triangular matrix by a diagonal one does not
change the structure (keeps it triangular)
▶ one more (balanced) representation A = LDU
▶ when rows are exchanged P A = LU =⇒ A = P T LU