Matrix Algebra Linear Sys. Sol. Elimination Inverse and det Eigendecomposition Digonalization SVD Quad.

Forms

Day 2: Linear Algebra

PUN Chi Seng

SPMS MSc Preparatory Module

1/ 40 Day 2: Linear Algebra SPMS MSc Preparatory Module PUN Chi Seng
Matrix Algebra Linear Sys. Sol. Elimination Inverse and det Eigendecomposition Digonalization SVD Quad. Forms

Matrix Algebra

Matrices
In this session, we will review some matrix operations and their properties.

We usually use capital (and bold) letters A, B, X, etc to denote matrices:

a12 · · · a1M
 
a11
 a21 a22 · · · a2M 
A= . ..  = [aij ]N×M ,
 
.. ..
 .. . . . 
aN1 aN2 ··· aNM
where aij =elements of A and N, M =row, column dimension, respectively.

I, the identity matrix with  diagonal  elements all equal to 1 and off-diagonal elements
1 0 0
all equal to 0, e.g. I = 0 1 0.
0 0 1
 
a11
 a21 
[a11 , a12 , · · · , a1M ] is called a row vector;  .  is called a column vector;
 
 .. 
aN1
By default, “vector” means “column vector”.
2/ 40 Day 2: Linear Algebra SPMS MSc Preparatory Module PUN Chi Seng
Matrix Algebra Linear Sys. Sol. Elimination Inverse and det Eigendecomposition Digonalization SVD Quad. Forms

Matrix Algebra

Matrix Operations: Transpose and Trace

• Transpose
If A = [aij ]N×M , then the transpose of A is:
 
a11 a21 ··· aN1
>
 a12 a22 ··· aN2 
A = [aji ]M×N =  
··· ··· ··· ··· 
a1M a2M ··· aNM

i.e. By interchanging the rows and columns.

• Let A be a N × N square matrix, if A> = A, then A is called symmetric.

• Trace
If A = [aij ]N×N is a square matrix, then the trace of A is
N
X
tr (A) = aii ,
i=1

the sum of the values on the main diagonal of A.

3/ 40 Day 2: Linear Algebra SPMS MSc Preparatory Module PUN Chi Seng
Matrix Algebra Linear Sys. Sol. Elimination Inverse and det Eigendecomposition Digonalization SVD Quad. Forms

Matrix Algebra

Matrix Operations: Addition, Subtraction, and Multiplication

• Matrix Addition and Subtraction

Let matrices A and B have the same dimension: A = [aij ]N×M , B = [bij ]N×M , then
A + B = [aij + bij ]N×M , A − B = [aij − bij ]N×M .

• Matrix Multiplication

Let A = [aij ]N×M , B = [bij ]M×K , and p, q are positive integers, then
(1) Scalar product:
αA = [αaij ]N×M is a scalar product of scalar α and matrix A.

(2) Matrix multiplication:

(Defined only if column dimension of A =row dimension of B)
" M #
X
AB = aim bmj .
m=1 N×K

(3) Powers of a matrix:

Ap = A · A · · · A; Ap Aq = Ap+q ; (Ap )q = Apq .

| {z }
p times

4/ 40 Day 2: Linear Algebra SPMS MSc Preparatory Module PUN Chi Seng
Matrix Algebra Linear Sys. Sol. Elimination Inverse and det Eigendecomposition Digonalization SVD Quad. Forms

Matrix Algebra

Two Important Differences between the Algebra of Matrices and Numbers

1 Matrix multiplication is, in general, not commutative. AB 6= BA.

   
• e.g. A = 4 −1 2 1
and B = , then
0 1 −3 4
   
11 0 8 −1
AB = , BA = .
−3 4 −12 7

2 Let 0 denote the zero matrix (with zero for every element).
In the algebra of real numbers, ab = 0 ⇒ a = 0 or b = 0.
In the algebra of matrices, AB = 0 ; A = 0 or B = 0. The reverse is true.
 
  4
• e.g. A = 3 1 3
, B =  3 , AB = 0.
1 2 2
−5

5/ 40 Day 2: Linear Algebra SPMS MSc Preparatory Module PUN Chi Seng
Matrix Algebra Linear Sys. Sol. Elimination Inverse and det Eigendecomposition Digonalization SVD Quad. Forms

Matrix Algebra

Properties of Matrix Operations

Let A, B, C be matrices with appropriate dimensions.

1 (A + B)> = A> + B>
2 (AB)> = B> A>

3 tr (A + B) = tr (A) + tr (B)
4 tr (AB) = tr (BA)

5 A + B = B + A (commutative law for addition)

6 A + (B + C) = (A + B) + C (associative law for addition)

7 (AB)C = A(BC) (associative law for multiplication)

8 A(B + C) = AB + AC (left distributive law for multiplication)
9 (A + B)C = AC + BC (right distributive law for multiplication)

10 Let A, B ∈ RN×N . If AB = I, then BA = I.

6/ 40 Day 2: Linear Algebra SPMS MSc Preparatory Module PUN Chi Seng
Matrix Algebra Linear Sys. Sol. Elimination Inverse and det Eigendecomposition Digonalization SVD Quad. Forms

Types of Solutions of a Linear System

Types of Solutions of a Linear System

A system of N linear equations in M variables, Ax = b, can have:

No solution if and only if rank(A)<rank([A|b])

This happens frequently for over-determined systems, i.e. N > M,
but can also happen when N ≤ M (e.g. equations are contradictory).

Unique solution if and only if rank(A)=rank([A|b])= M

Infinitely many solutions if and only if rank(A)=rank([A|b])< M

Definition
A linear system is called
consistent if there is at least one solution;
inconsistent if it has no solution;
overdetermined if it has more equations than unknowns;
underdetermined if it has fewer equations than unknowns;
exactly determined if it has the same number of equations and unknowns.

7/ 40 Day 2: Linear Algebra SPMS MSc Preparatory Module PUN Chi Seng
Matrix Algebra Linear Sys. Sol. Elimination Inverse and det Eigendecomposition Digonalization SVD Quad. Forms

Types of Solutions of a Linear System

Example (No solution)

The overdetermined system of linear equations
   
6 1 4   1
5 2 9 x  2
   
7 6 9 y  = 6 ,
   
1 9 1 z  9
6 2 2 8

where we have 5 equations for 3 variables. The system is inconsistent, and hence has
no solution. (Return to this page later ) If we write the system as Ax = b, what is the
rank of A? What is the rank of [A|b]?

8/ 40 Day 2: Linear Algebra SPMS MSc Preparatory Module PUN Chi Seng
Matrix Algebra Linear Sys. Sol. Elimination Inverse and det Eigendecomposition Digonalization SVD Quad. Forms

Types of Solutions of a Linear System

Example (No solution)

The system of linear equations
    
1 2 −3 x 1
1 2 −3 y  = 2 ,
1 −1 1 z 0

is inconsistent, even though we have the same number of equations and variables
(N = M).

In this case, it is obvious the system is inconsistent because we are trying to make
x + 2y − 3z equals to 1 and 2 simultaneously. Sometimes, such inconsistencies are not
immediately apparent. For instance, the linear system
    
1 2 −3 x 1
2 1 −2 y  = 2 ,
1 −1 1 z 0

is also inconsistent. The second equation of this linear system is obtained by adding
the second and third equations of the previous linear system.

9/ 40 Day 2: Linear Algebra SPMS MSc Preparatory Module PUN Chi Seng
Matrix Algebra Linear Sys. Sol. Elimination Inverse and det Eigendecomposition Digonalization SVD Quad. Forms

Types of Solutions of a Linear System

Example (Unique solution)

The system of linear equations
    
1 2 −3 x 1
1 2 0  y  = 2
1 −1 1 z 0

has unique solution    

x 4/9
y  = 7/9 .
z 3/9

10/ 40 Day 2: Linear Algebra SPMS MSc Preparatory Module PUN Chi Seng
Matrix Algebra Linear Sys. Sol. Elimination Inverse and det Eigendecomposition Digonalization SVD Quad. Forms

Types of Solutions of a Linear System

Example (Infinitely many solutions)

The system of equations  
  x  
1 2 −3   1
y =
1 −1 1 0
z
has infinitely many solutions.

We can choose to write these solutions either in terms of x, y , or z. Suppose we want

to write the solutions in terms of z, the above system of equations can be written as
    
1 2 x 1 + 3z
= ,
1 −1 y −z

whose solution can be expressed as

z +1 4z + 1
x= , y= .
3 3

11/ 40 Day 2: Linear Algebra SPMS MSc Preparatory Module PUN Chi Seng
Matrix Algebra Linear Sys. Sol. Elimination Inverse and det Eigendecomposition Digonalization SVD Quad. Forms

Gauss-Jordan Elimination

The Method of Elimination

The method of elimination consists of repeatedly performing the following (elementary

row) operations:
• Interchange two equations (rows).
• Multiply an equation (row) by a non-zero constant.
• Add a multiple of one equation (row) to another.

Formally, we introduce the following two ways to solve for linear systems:
Gaussian elimination
• row echelon method
• elementary row operations
• backward substitution

Gauss-Jordon elimination
• reduced row echelon method
• elementary row operations

12/ 40 Day 2: Linear Algebra SPMS MSc Preparatory Module PUN Chi Seng
Matrix Algebra Linear Sys. Sol. Elimination Inverse and det Eigendecomposition Digonalization SVD Quad. Forms

Gauss-Jordan Elimination

(Reduced) Row Echelon Form

Definition
A matrix is said to be in reduced row echelon form if it satisfies the properties:
(a) All zero rows, if there are any, appear at the bottom of the matrix.
(b) The first nonzero entry from the left of a nonzero row is a 1. This entry is called
a leading one of its row.
(c) For each nonzero row, the leading one appears to the right and below any leading
one’s in preceding rows.
(d) If a column contains a leading one, then all other entries in that column are zero.

An N × M-matrix satisfying properties (a), (b), & (c) is said to be in row echelon form.

Example
Left: reduced row echelon form Right: row echelon form
   
1 2 0 0 1 1 2 3 6 10
0 0 1 2 3 0 0 1 2 3
0 0 0 0 0 0 0 0 0 0

13/ 40 Day 2: Linear Algebra SPMS MSc Preparatory Module PUN Chi Seng
Matrix Algebra Linear Sys. Sol. Elimination Inverse and det Eigendecomposition Digonalization SVD Quad. Forms

Gauss-Jordan Elimination

Rank

Definition (Rank)
The rank of a N × M-matrix A, rank(A), is the maximum number of linearly
independent columns of A. This is also the number of linearly independent rows of A.

Clearly, rank(A) ≤ min(N, M).

Because
• Row operations do not change the row space, hence do not change the row rank;
and
• each matrix has a unique corresponding reduced row echelon form matrix (a
theorem),
rank(A) =the number of nonzero rows in the unique reduced row echelon form of A.

14/ 40 Day 2: Linear Algebra SPMS MSc Preparatory Module PUN Chi Seng
Matrix Algebra Linear Sys. Sol. Elimination Inverse and det Eigendecomposition Digonalization SVD Quad. Forms

Gauss-Jordan Elimination

Solving a Linear System using the Method of Elimination

To solve a system of linear equations Ax = b using the method of elimination, we need

to first form the augmented matrix [A|b] (Step 1), and then perform elementary row
operations on this object.
Gaussian elimination
Step 2. Obtain a row echelon form [C∗ |d∗ ].
Step 3. Solve the linear system corresponding to [C∗ |d∗ ] by
backward substitution

Gauss-Jordan elimination
Step 2. Obtain a reduced row echelon form [C|d].
• If A is invertible, then C = I.
Step 3. For each nonzero row of the matrix [C|d], solve the
corresponding equation for the unknown associated
with the leading one in that row.
In Step 3, The rows consisting entirely of zeros can be ignored, because the
corresponding equation will be satisfied for any values of the unknowns.

15/ 40 Day 2: Linear Algebra SPMS MSc Preparatory Module PUN Chi Seng
Matrix Algebra Linear Sys. Sol. Elimination Inverse and det Eigendecomposition Digonalization SVD Quad. Forms

Gauss-Jordan Elimination

Solving a Linear System using Elimination

Example (Gauss-Jordan elimination)
Solve the linear system

x + y + 2z − 5w = 3
2x + 5y − z − 9w = −3
2x + y − z + 3w = −11
x − 3y + 2z + 7w = −5

by the Gauss-Jordan elimination.

16/ 40 Day 2: Linear Algebra SPMS MSc Preparatory Module PUN Chi Seng
Matrix Algebra Linear Sys. Sol. Elimination Inverse and det Eigendecomposition Digonalization SVD Quad. Forms

Matrix Inverse and Matrix Solutions

Matrix Inverse
Definition (Matrix inverse)
A−1 is the matrix inverse of the N × N square matrix A if it satisfies the conditions

AA−1 = A−1 A = I,

where I is the N × N identity matrix.

Remark: For a non-singular 2 × 2 matrix,
 −1  
a b 1 d −b
= ,
c d ad − bc −c a
where ad − bc is the determinant of the matrix.

Find the matrix inverse (if exists): [A|I] → · · · Gauss–Jordan Elimination · · · → [I|A−1 ]

Properties:
• (A−1 )> = (A> )−1
• (AB)−1 = B−1 A−1
• Woodbury formula (A + UCV)−1 = A−1 − A−1 U(C−1 + VA−1 U)−1 VA−1
17/ 40 Day 2: Linear Algebra SPMS MSc Preparatory Module PUN Chi Seng
Matrix Algebra Linear Sys. Sol. Elimination Inverse and det Eigendecomposition Digonalization SVD Quad. Forms

Matrix Inverse and Matrix Solutions

Matrix Solution

Theorem
Let A be a square N × N matrix. The following statements are equivalent:
• A is invertible (or nonsingular or nondegenerate), that is A has an inverse.
• I can be obtained by applying a finite sequence of elementary row operations to A.
• det(A) 6= 0.
• rank(A) = N.

Formally, if A is a square matrix and its inverse exists, the previous Gauss-Jordan
elimination method

[A|b] → · · · Gauss–Jordan Elimination · · · → [I|x]

is equivalent to computing the matrix inverse, so that the linear system Ax = b can be
solved as
x = A−1 b.

18/ 40 Day 2: Linear Algebra SPMS MSc Preparatory Module PUN Chi Seng
Matrix Algebra Linear Sys. Sol. Elimination Inverse and det Eigendecomposition Digonalization SVD Quad. Forms

Matrix Inverse and Matrix Solutions

Solving a Linear System using Cramer’s Rule

The matrix inverse of a 2 × 2 matrix is easy to compute, because its determinant and
cofactors are easy to compute. There is a method to solve linear equations involving
N × N matrices, called Cramer’s rule, that involved the computation of determinants
and cofactors. This method is described in greater details in
[Link]

To use this method, we need to learn how to compute the determinant of an N × N

square matrix. Suppose the matrix is

···
 
a11 a12 a1N
 a21 a22 ··· a2N 
A= . ..  .
 
.. ..
 .. . . . 
aN1 aN2 ··· aNN

The Cramer’s rule is only applicable for the linear systems with square matrix A having
non-zero determinant (or equivalently invertible or nonsingular).

19/ 40 Day 2: Linear Algebra SPMS MSc Preparatory Module PUN Chi Seng
Matrix Algebra Linear Sys. Sol. Elimination Inverse and det Eigendecomposition Digonalization SVD Quad. Forms

Matrix Inverse and Matrix Solutions

Determinant Computation
The determinant of A can be written as a Laplace expansion (formula):

a11 a12 ··· a1N

a21 a22 ··· a2N XN XN
i+j
det(A)= |A| = . .. .. .. = (−1 ) a i,j M i,j = (−1 )i+j ai,j Mi,j
.. . . . j=1 i=1
aN1 aN2 ··· aNN
a22 ··· a2N a21 a23 ··· a2N a21 ··· a2,N−1
. . . . . N+1 . .
= a11 .
.
.
.
.
.
.
− a12 .
.
.
.
.
.
.
.
.
+ · · · + (−1) a1N .
.
.
.
.
.
.
aN2 ··· aNN aN1 aN3 ··· aNN aN1 ··· aN,N−1
 
a33 a34 ··· a3N a32 a33 ··· a3,N−1

= a11 a22 .
.
.
.
.
.
.
.
.
.
.
.
+ · · · + (−1)N+2 a2N .
.
.
.
.
.
.
.
.
.
.
.

aN3 aN4 ··· aNN aN2 aN3 ··· aN,N−1

−a12 [· · · ] + · · · + (−1)N+1 a1N [· · · ]

= ···
where Mi,j the determinant of the (N − 1) × (N − 1)-matrix that results from A by
removing the i-th row and the j-th column. The expression (−1)i+j Mi,j is known as a
cofactor.
20/ 40 Day 2: Linear Algebra SPMS MSc Preparatory Module PUN Chi Seng
Matrix Algebra Linear Sys. Sol. Elimination Inverse and det Eigendecomposition Digonalization SVD Quad. Forms

Matrix Inverse and Matrix Solutions

Properties of the Determinant

We will state the following properties of the determinant without proof:
1 If A is upper (lower) triangular, then det(A) = a11 a22 · · · aNN .

2 The det(A) = 0 if
• all elements of one row (or one column) are zero; or
• two rows (or two columns) are identical; or
• two rows (or two columns) are proportional.

3 If we interchange two rows (or two columns) of matrix A to get matrix A0 , then
det(A0 )=-det(A).
4 If we multiply each element in one row (or one column) of a matrix A by a
constant k to get a matrix A0 , then det(A0 )=k det(A).
5 If we add to each element of i-th row, k times the corresponding element of j-th
row, to obtain a matrix A0 , then det(A0 )=det(A).

6 det(A> )=det(A).
7 det(A−1 )=1/det(A) if A is non-singular.
8 det(AB) =det(A)det(B). (but, det(A + B) 6=det(A)+det(B) in general)
9 det(A1 · · · An ) =det(Ai1 · · · Ain ) =det(A1 ) · · · det(An ).
21/ 40 Day 2: Linear Algebra SPMS MSc Preparatory Module PUN Chi Seng
Matrix Algebra Linear Sys. Sol. Elimination Inverse and det Eigendecomposition Digonalization SVD Quad. Forms

Matrix Inverse and Matrix Solutions

Cramer’s Rule

Consider a linear system Ax = b, where A is a N × N-matrix with non-zero

determinant, x = (x1 , . . . , xN )> is column vector of variables, and b = (b1 , . . . , bN )> is
a N-dimensional constant vector. Then the theorem states that in this case the system
has a unique solution, whose individual values for the unknowns are given by:
det(Ai )
xi = , i = 1, . . . , N,
det(A)
where Ai is the matrix formed by replacing the i-th column of A by the vector b:

a11 · · · a1,i−1 b1 a1,i+1 · · · a1N

 
 a21 · · · a2,i−1 b2 a2,i+1 · · · a2N 
Ai =  .
 
.. .. .. .. 
 .. ··· . . . ··· . 
aN1 · · · aN,i−1 bN aN,i+1 · · · aNN

Remark: This method is rarely used nowadays, because for large matrices, it is
computationally less efficient compared to Gauss-Jordan elimination.

22/ 40 Day 2: Linear Algebra SPMS MSc Preparatory Module PUN Chi Seng
Matrix Algebra Linear Sys. Sol. Elimination Inverse and det Eigendecomposition Digonalization SVD Quad. Forms

Matrix Inverse and Matrix Solutions

Block Matrices: Let A, B, C , D be the matrices with suitable dimensions.

• Transpose and Trace
>
A> C>
    
A B A B
= , tr = tr(A) + tr(D)
C D B> D > C D
• Addition and Subtraction
     
A1 B1 A2 B2 A1 ± A2 B1 ± B2
± =
C1 D1 C2 D2 C1 ± C2 D1 ± D2
• Multiplication
        
A B αA αB A1 B1 A2 B2 A1 A2 + B1 C2 A1 B2 + B1 D2
α = , =
C D αC αD C1 D1 C2 D2 C1 A2 + D1 C2 C1 B2 + D1 D2
• Inverse (if A and D are invertible (sufficient condition),)
−1  −1
A + A−1 B(D − CA−1 B)−1 CA−1 −A−1 B(D − CA−1 B)−1
 
A B
=
C D −(D − CA−1 B)−1 CA−1 (D − CA−1 B)−1
• Determinant    
A 0 A B
det = det(A)det(D) =
C D 0 D

   det(A)det(D − CA−1 B), if A is invertible,
A B
det = det(AD − BC ), if they are square matrices of
C D  the same size and CD = DC .
23/ 40 Day 2: Linear Algebra SPMS MSc Preparatory Module PUN Chi Seng
Matrix Algebra Linear Sys. Sol. Elimination Inverse and det Eigendecomposition Digonalization SVD Quad. Forms

Eigenvalues and Eigenvectors

Eigenvalue Problem

Definition
A matrix eigenvalue problem has the structure

Ax = λx

where A is a N × N square matrix, x is a N × 1 nonzero vector, and λ is a scalar.

Remark: The solution is not unique.

If x is a solution so will be cx (c is a non-zero scalar). This is because

Ax = λx =⇒ A(cx) = λ(cx).

In practice, to regulate the solution, we consider only the solutions that have unit
length, i.e.
√ q
kxk = xT x = x12 + x22 + · · · + xN2 = 1.
The solution of unit length is unique up to a change of sign, since if x is a solution of
unit length then so is −x.

24/ 40 Day 2: Linear Algebra SPMS MSc Preparatory Module PUN Chi Seng
Matrix Algebra Linear Sys. Sol. Elimination Inverse and det Eigendecomposition Digonalization SVD Quad. Forms

Eigenvalues and Eigenvectors

Eigenvalues and Eigenvectors

The eigenvalue problem

Ax = λx
can only be satisfied by a special set {λi } of scalars, and a corresponding special set
{xi } of normalized nonzero vectors. In fact, for a N × N matrix A, we can find at most
N pairs (λi , xi ) that satisfies the above equation.

Definition
We call λi an eigenvalue of A. The set of eigenvalues {λi } is frequently referred to as
the spectrum of A. We call xi an eigenvector of A, corresponding to the eigenvalue λi .

Remark: When A is non-singular, its eigenvectors {xi } forms a basis for RN . In

general, this basis is not orthogonal.
• This basis of eigenvectors is orthogonal when A is symmetric, i.e. A = A> .

25/ 40 Day 2: Linear Algebra SPMS MSc Preparatory Module PUN Chi Seng
Matrix Algebra Linear Sys. Sol. Elimination Inverse and det Eigendecomposition Digonalization SVD Quad. Forms

Eigenvalues and Eigenvectors

Characteristic Polynomial and Equation

Definition
Let A = [aij ] be an N × N matrix. The determinant

a11 − λ a12 ··· a1N

a21 a22 − λ ··· a2N
f (λ) = det(A − λI) = .. .. .. ..
. . . .
aN1 aN2 ··· aNN − λ

is called the characteristic polynomial of A. The equation

f (λ) = det(A − λI) = 0

is called the characteristic equation of A.

Remark: f (λ) is a polynomial of degree N and thus it has N roots (counting repeats).

Abel’s Impossibility Theorem tells us that there are in general no closed-form solutions
for the roots of polynomial equations with degree greater or equal to 5. We can still
solve for the real roots of such characteristic equations using numerical methods.
26/ 40 Day 2: Linear Algebra SPMS MSc Preparatory Module PUN Chi Seng
Matrix Algebra Linear Sys. Sol. Elimination Inverse and det Eigendecomposition Digonalization SVD Quad. Forms

Eigenvalues and Eigenvectors

Computing Eigenvalues and Eigenvectors

Theorem
An N × N matrix A is invertible if and only if λ = 0 is not an eigenvalue of A.

Theorem
The eigenvalues of A are the roots of the characteristic polynomial of A.

The procedure for finding the eigenvalues and associated eigenvectors of a matrix is as
follows:
Step 1 Determine the roots of the characteristic polynomial
f (λ) = det(A − λI). These are eigenvalues of A.
Step 2 For each eigenvalue λ, find all the nontrivial solutions to the
homogeneous system (A − λI)x = 0. These are the eigenvectors of A
associated with the eigenvalue λ.

27/ 40 Day 2: Linear Algebra SPMS MSc Preparatory Module PUN Chi Seng
Matrix Algebra Linear Sys. Sol. Elimination Inverse and det Eigendecomposition Digonalization SVD Quad. Forms

Eigenvalues and Eigenvectors

Properties of Eigenvalues and Eigenvectors

1 If A is a real symmetric matrix then its eigenvalues are all real.

2 If A, B are both N × N and A is invertible, then eigenvalues of AB and BA are the

same.

3 Eigenvalues of A and A> are the same.

4 If AN×N is invertible and λ1 , · · · , λn are eigenvalues of A, then λ−1 −1

1 , · · · , λn are
−1
eigenvalues of A .

5 If AN×N is symmetric and λi , λj are two distinct eigenvalues of A, then the

corresponding eigenvectors xi , xj must be orthogonal, i.e. x>
i xj = 0.

Qn
6 det(A) = i=1 λi .
• If any eigenvalue λi = 0, then det(A) = 0, and so A is singular.
• If every λi 6= 0, then det(A) 6= 0, and so A is invertible.

Pn
7 tr (A) = i=1 λi .
28/ 40 Day 2: Linear Algebra SPMS MSc Preparatory Module PUN Chi Seng
Matrix Algebra Linear Sys. Sol. Elimination Inverse and det Eigendecomposition Digonalization SVD Quad. Forms

Eigenvalues and Eigenvectors

Eigenvalues and Eigenvectors

Example (Eigenvalues and Eigenvectors)

 
1 2
Suppose A = , then
−1 4
   
2 1 λ 0
det(A − λI) = det −
4 −1 0 λ
 
1−λ 2
= det
−1 4−λ
= (1 − λ)(4 − λ) + 2
= λ2 − 5λ + 6
= (λ − 2)(λ − 3)

(Polynomial of λ of degree 2)

det(A − λIn ) = (λ − 2)(λ − 3) = 0 =⇒ eigenvalues are λ1 = 2 and λ2 = 3.

29/ 40 Day 2: Linear Algebra SPMS MSc Preparatory Module PUN Chi Seng
Matrix Algebra Linear Sys. Sol. Elimination Inverse and det Eigendecomposition Digonalization SVD Quad. Forms

Eigenvalues and Eigenvectors

Example (Eigenvalues and Eigenvectors, continued)

The eigenvector associated with λ1 = 2 satisfies Av = λv, i.e.

v1 + 2v2 = 2v1
−v1 + 4v2 = 2v2

Hence v = (v1 , v2 )> satisties

  −v1 + 2v2 = 0.
1
We can take e.g. v = , and hence the eigenvector of unit length is
1/2
   √ 
v 2 1 2/√5
u= = √ = .
kvk 5 1/2 1/ 5

Try λ2 = 3 by yourself!

30/ 40 Day 2: Linear Algebra SPMS MSc Preparatory Module PUN Chi Seng
Matrix Algebra Linear Sys. Sol. Elimination Inverse and det Eigendecomposition Digonalization SVD Quad. Forms

Digonalization

Digonalization
Definition
A matrix B is said to be similar to a matrix A if there is a nonsingular (or an
invertible) matrix P such that
B = P−1 AP.

Definition
We shall say that the matrix A is diagonalizable if it is similar to a diagonal matrix. In
this case, we also say that A can be diagonalized. Otherwise, A is called defective.

Theorem
• Similar matrices have the same eigenvalues.
• A is diagonalizable if and only if A has N linearly independent eigenvectors.

If A is diagonalizable matrix, then P−1 AP = D is a diagonal matrix. Moreover,

• the diagonal elements of D are the eigenvalues of A.
• P is a matrix whose columns are N linearly independent eigenvectors of A.
• The order of the columns of P determines the order of the diagonal entries in D.
31/ 40 Day 2: Linear Algebra SPMS MSc Preparatory Module PUN Chi Seng
Matrix Algebra Linear Sys. Sol. Elimination Inverse and det Eigendecomposition Digonalization SVD Quad. Forms

Digonalization

Procedure for Diagonalizing a Matrix

An N × N matrix will fail to be diagonalizable only if it does not have N linearly

independent eigenvectors.

The procedure for diagonalizing a matrix A is as follows:

Step 1 Form the characteristic polynomial f (λ) = det(A − λIn ) of A.
Step 2 Find the roots of the characteristic polynomial of A.
Step 3 For each eigenvalue λj of A of multiplicity kj , find a basis for the
solution space (A − λj In )x = 0 (the eigenspace associated with λj ).
• If the dimension of the eigenspace is less than kj ,
then A is not diagonalizable / defective.
We thus determine N linearly independent eigenvectors of A.
Step 4 Let P be the matrix whose columns are the N linearly independent
eigenvectors determined in Step 3. Then P−1 AP = D, a diagonal
matrix whose diagonal elements are the eigenvalues of A that
correspond to the columns of P.

32/ 40 Day 2: Linear Algebra SPMS MSc Preparatory Module PUN Chi Seng
Matrix Algebra Linear Sys. Sol. Elimination Inverse and det Eigendecomposition Digonalization SVD Quad. Forms

Digonalization

Diagonalization of Symmetric Matrices and Eigendecomposition

Theorem
If A is symmetric N × N matrix, then there exists an orthogonal matrix P such that
P−1 AP = D, a diagonal matrix. The eigenvalues of A lie on the main diagonal of D.

Remark: Thus, not only is a symmetric matrix always diagonalizable, but it is

diagonalizable by means of an orthogonal matrix. In such a case, we say that A is
orthogonally diagonalizable.

Theorem
An N × N matrix A is orthogonally diagonalizable if and only if A is symmetric.

Theorem
If A is diagonalizable with P−1 AP = D, then for any integers k,

Ak = PDk P−1 .

A = PDP−1 is called the eigenvalue decomposition (EVD) or eigendecomposition of A.

Remark: Further, if A is invertible, then A−1 can be written as A−1 = PD−1 P−1 .
33/ 40 Day 2: Linear Algebra SPMS MSc Preparatory Module PUN Chi Seng
Matrix Algebra Linear Sys. Sol. Elimination Inverse and det Eigendecomposition Digonalization SVD Quad. Forms

Digonalization

Diagonalization

Example (Diagonalization)
Diagonalize  
1 2 0 0
2 1 0 0
A=
0
.
0 1 2
0 0 2 1

34/ 40 Day 2: Linear Algebra SPMS MSc Preparatory Module PUN Chi Seng
Matrix Algebra Linear Sys. Sol. Elimination Inverse and det Eigendecomposition Digonalization SVD Quad. Forms

Singular Value Decomposition (SVD)

Singular Value Decomposition

In this session, we investigate the decomposition/factorization of a M × N matrix A.

Definition (Singular Value Decomposition)

Let A be an M × N matrix with rank r . Then there exists an M × N matrix Σ:
σ1 0 · · · 0
 
 0 σ2 · · · 0   
 ..

.. .. .. 0 r ×(N−r ) 
Σ=. ,

 . . . 
 0 · · · σr  
0 
0 (M−r )×r
0 (M−r )×(N−r )

where σ1 ≥ σ2 ≥ · · · ≥ σr > 0 are the first r singular values of A, and there exist an
M × M orthogonal matrix U and an N × N orthogonal matrix V such that

A = UΣV> .

• The singular values of A are square roots of the eigenvalues of AA> (or A> A).
• The columns of U (resp. V) are eigenvectors of AA> (resp. A> A). They are also
called left (resp. right) singular vectors of A.
35/ 40 Day 2: Linear Algebra SPMS MSc Preparatory Module PUN Chi Seng
Matrix Algebra Linear Sys. Sol. Elimination Inverse and det Eigendecomposition Digonalization SVD Quad. Forms

Singular Value Decomposition (SVD)

A Few Remarks on SVD

• The matrices U and V are not unique, but the diagonal entries of Σ are
necessarily the singular values of A.
• Any factorization A = UΣV> , with U and V orthogonal and Σ as presented
before, is called a singular value decomposition (SVD) of A.

Applications of SVD include:

• Find the rank of a M × N matrix A.

• Solve homogeneous linear equations of the form Ax = 0.

• Solve linear least squares problems.

• Matrix approximation (principal component analysis).

36/ 40 Day 2: Linear Algebra SPMS MSc Preparatory Module PUN Chi Seng
Matrix Algebra Linear Sys. Sol. Elimination Inverse and det Eigendecomposition Digonalization SVD Quad. Forms

Singular Value Decomposition (SVD)

Procedure for Computing a Singular Value Decomposition

1 Find an orthonormal basis {v1 , . . . , vN } for RN consisting of eigenvectors of A> A,

arranged so that the associated eigenvalues satisfy λ1 ≥ · · · λr > 0 and
λr +1 = · · · = λN = 0, where r =rank(A).

2 Construct the N × N orthogonal matrix V = [v1 , . . . , vN ].

p
3 Let σj = λj (1 ≤ j ≤ r ), and construct the M × N diagonal matrix Σ, whose
(j, j)-entry is σj (1 ≤ j ≤ r ) and has zeros elsewhere.

4 The set {Av1 , . . . , Avr } is orthogonal and σj = kAvj k. Compute

uj = (1/σj )Avj (1 ≤ j ≤ r ).

5 Extend {u1 , . . . , ur } to an orthonormal basis {u1 , . . . , uM } for RM . Write the

M × M orthogonal matrix U = [u1 , . . . , ur ].

6 A = UΣV> .

37/ 40 Day 2: Linear Algebra SPMS MSc Preparatory Module PUN Chi Seng
Matrix Algebra Linear Sys. Sol. Elimination Inverse and det Eigendecomposition Digonalization SVD Quad. Forms

Quadratic Forms and Positive definiteness

Quadratic Forms and Positive-definite Matrices

• Quadratic Forms
Let AN×N be a square matrix, then x> Ax is called a quadratic form of x, where x
is N × 1 vector.
    
• e.g. A = 1 2
, x> Ax = [x1 , x2 ]
1 2 x1
= x12 + 5x1 x2 + 4x22 .
3 4 3 4 x2

• Positive-definite Matrices
Let AN×N be symmetric. If for any xN×1 6= 0, it has

x> Ax > 0,

then A is said to be a positive definite matrix.

If x> Ax ≥ 0 for all x, then A is positive semi-definite.

38/ 40 Day 2: Linear Algebra SPMS MSc Preparatory Module PUN Chi Seng
Matrix Algebra Linear Sys. Sol. Elimination Inverse and det Eigendecomposition Digonalization SVD Quad. Forms

Quadratic Forms and Positive definiteness

Properties of Positive-definite Matrices

(i) A symmetric matrix AN×N is positive-definite if and only if all eigenvalues of A are
positive.

(ii) A is positive semi-definite if and only if all eigenvalues of A are non-negative.

 
• e.g. The matrix A = 1 3
is not positive-definite.
3 4

det(A − λI) = 0 =⇒ λ2 − 5λ − 5 = 0 =⇒ λ1 = 5.85, λ2 = −0.85 < 0.

(iii) If A is positive-definite, then so is A−1 .

(iv) Suppose BN×M be any matrix, then B> B and BB> are both positive semi-definite.

39/ 40 Day 2: Linear Algebra SPMS MSc Preparatory Module PUN Chi Seng
Matrix Algebra Linear Sys. Sol. Elimination Inverse and det Eigendecomposition Digonalization SVD Quad. Forms

Quadratic Forms and Positive definiteness

Square Root Matrices

Let AN×N be symmetric positive-definite. By the EVD, we define
• Square root matrix: The square root of A is defined as
 1/2 
λ1 0
A1/2 = UΛ1/2 U> , where Λ1/2 = 
 .. 
.
 . 
1/2
0 λn

Verification: A1/2 A1/2 = (UΛ1/2 U> )(UΛ1/2 U> ) = UΛU> = A.

• Inverse square root matrix: The inverse square root of A is defined as

 −1/2 
λ1 0
A−1/2 = UΛ−1/2 U> , where Λ−1/2 = 
 .. 
.
 . 
−1/2
0 λn

Verification: A−1/2 A−1/2 = (UΛ−1/2 U> )(UΛ−1/2 U> ) = UΛ−1 U> = A−1 .

40/ 40 Day 2: Linear Algebra SPMS MSc Preparatory Module PUN Chi Seng