Chapter 4

Review of Linear Algebra and Matrices

Computational Methods
(SECE)

Yonas Y.
Computational Methods (SECE) Chapter 4 Yonas Y. 1 / 27
 Outline

1 Review of basic algebra

Basics of linear system solution
Range space and null space

2 Basics of eigenvalue problems

Diagonalizability and spectral decomposition

3 Vector and matrix norms

Vector norms
Matrix norms

4 Special classes of matrices

Symmetric positive definite matrices
Orthogonal vectors and matrices

5 Singular values

Computational Methods (SECE) Chapter 4 Yonas Y. 2 / 27

 Review of basic algebra Basics of linear system solution

Basics of linear system solution

Example 4.1: Consider the simple example of finding the point of intersection of
two straight lines in a plane.

Find  
x1
x=
x2
which satisfies
a11 x1 + a12 x2 = b1
a21 x1 + a22 x2 = b2
or
Ax = b
with  
a11 a12
A=
a21 a22

Computational Methods (SECE) Chapter 4 Yonas Y. 3 / 27

 Review of basic algebra Basics of linear system solution

Geometrically, unique solution exists if and only if lines are not parallel.

Figure: 4.1 Intersection of two straight lines: a11 x1 + a12 x2 = b1 and a21 x1 + a22 x2 = b2 .
When are the lines parallel?
When their slopes are equal, expressed algebraically by the condition
− aa11
12
= − aa21
22
, or
det(A) = a11 a22 − a12 a21 = 0.
When the determinant of a square matrix A equals 0 we say that A is singular.
Equivalently, A is nonsingular if and only if its columns (or rows) are linearly
independent.
Computational Methods (SECE) Chapter 4 Yonas Y. 4 / 27
 Review of basic algebra Range space and null space

Range space and null space

We can write Ax = b as

a1 x1 + a2 x2 + · · · + an xn = b

where aj is the j-th column of A.

If A is nonsingular, then the columns aj are linearly independent.

Then there is a unique way of writing any vector b as a linear combination of
these columns.
Hence, if A is nonsingular, then there is a unique solution for the system
Ax = b.

Computational Methods (SECE) Chapter 4 Yonas Y. 5 / 27

 Review of basic algebra Range space and null space

In general, for a square n × n system there is a unique solution if one of the

following equivalent statements hold:

A is nonsingular;
det(A) 6= 0;
A has linearly independent columns or rows;
there exists an inverse A−1 satisfying AA−1 = I = A−1 A;
range(A) = Rn ;
null(A) = {0}.

range(A) ≡ all vectors that can be written as linear combination of columns of A,

i.e., all vectors y that can be written as y = Ax, for some vector x.
null(A) ≡ nullspace of A ≡ all vectors z for which Az = 0.

Computational Methods (SECE) Chapter 4 Yonas Y. 6 / 27

 Review of basic algebra Range space and null space

Example 4.2: The matrix  

1 1
A=
3 3
is singular, as noted earlier.

To find the nullspace (Ax = 0) the elements of x are characterized by the

relation x1 + x2 = 0
   
1
null(A) = α ∀α in R
−1

Next, observe that if b ∈ range(A), then it can be written as a linear

combination of the columns of A; hence
   
1
range(A) = β ∀β in R
3

Computational Methods (SECE) Chapter 4 Yonas Y. 7 / 27

 Review of basic algebra Range space and null space

Almost singularity

Let’s look at linear system of equations, slightly perturbed to read

    
1+ 1 x1 2+
=
3 3 x2 6

where  is a small but positive number, 0 <   1.

The matrix in this example is nonsingular, so there is a unique solution,

 
1
x= .
1
b

System matrix above is ’almost singular’, i.e., a small perturbation (removing )

makes it singular and there are many solutions.
The close-by problem has many solutions, some are far apart from b
x:
ill-conditioned problem.

Computational Methods (SECE) Chapter 4 Yonas Y. 8 / 27

 Basics of eigenvalue problems

Basics of eigenvalue problems

The algebraic eigenvalue problem
Ax = λx
is fundamental.
Here the product of A and the eigenvector x equals the product of the
scalar eigenvalue λ and the same vector.
Together, (λ, x) is an eigenpair, and the set of eigenvalues forms the
spectrum of A.
If there are n eigenpairs (λj ,xj ) and if the eigenvectors are linearly
independent,
Any other vector y ∈ Rn can be written as their linear combination, i.e., there
are coefficients αj such that
Xn
y= αj xj ,
j=1
Then
n
X n
X
Ay = αj Axj = αj λj xj .
j=1 j=1
Computational Methods (SECE) Chapter 4 Yonas Y. 9 / 27
 Basics of eigenvalue problems

The n eigenvalues of an n × n matrix

Does every real n × n matrix have n eigenvalues?

(λI − A)x = 0.

Since we want a nontrivial x, this means that λI − A must be singular.

Therefore we can find λ by forming the characteristic polynomial and
finding its roots.
det(λI − A) = 0.

A polynomial of degree n has n generally complex and not necessarily distinct

roots, and we can write

det(λI − A) = (λ − λ1 )(λ − λ2 ) · . . . · (λ − λn ) = 0.

where the roots λ1 , λ2 , . . ., λn are the eigenvalues of A.

Computational Methods (SECE) Chapter 4 Yonas Y. 10 / 27

 Basics of eigenvalue problems

Example 4.3: For a 2 × 2 matrix we have

 
λ − a11 −a12
det(λI − A) = det = (λ − a11 )(λ − a22 ) − a12 a21
−a21 λ − a22
= λ2 − (a11 + a22 )λ + (a11 a22 − a12 a21 )

We have to solve a quadratic equation of form

λ2 − bλ + c = 0

If discriminant (∆) > 0, then there are two real solutions given by

1 √
λ1,2 = (b ± ∆)
2
if ∆ = 0, then there is the double root 12 (b).
if ∆ < 0, then there are no real solutions.
1 √
λ1,2 = (b ± i −∆)
2

Computational Methods (SECE) Chapter 4 Yonas Y. 11 / 27

 Basics of eigenvalue problems Diagonalizability and spectral decomposition

Diagonalizability and spectral decomposition

Few basic properties of eigenvalues:

1. If Ax = λx, then for any complex scalar α

(A + αI )x = (λ + α)x

2. For any positive integer k

Ak x = λk x
3. If B = S −1 AS and Ax = λx, then By = λy, where x = Sy.
B has the same eigenvalues as A.
B is similar to A and call the transformation A → S −1 AS a similarity
transformation of A.

Computational Methods (SECE) Chapter 4 Yonas Y. 12 / 27

 Basics of eigenvalue problems Diagonalizability and spectral decomposition

4. Spectral decomposition: Let X be the matrix whose columns are eigenvectors

of A, and suppose that X is square and nonsingular. Then

AX = A[x1 , x2 , . . . , xn ]
= [λ1 x1 , λ2 x2 , . . . , λn xn ]
= X Λ,

where Λ is a diagonal matrix with the eigenvalues on its diagonal,

Λ = diag (λ1 , λ2 , . . . , λn ). Therefore, we can write

A = X ΛX −1 .

This decomposition is the spectral decomposition of A, and any matrix A

that can be decomposed in this fashion is diagonalizable.

Computational Methods (SECE) Chapter 4 Yonas Y. 13 / 27

 Vector and matrix norms Vector norms

Vector norms

What exactly is a norm?

It is a function with a range of scalar values, denoted k · k: Rn → R+ such

that
1 k x k ≥ 0, for all x ∈ R and k x k = 0 ⇔ x = 0.
2 k αx k = |α| k x k for all α ∈ R.
3 k x + y k ≤ k x k + k y k for all x, y ∈ Rn . (triangle inequality)

This generalizes absolute value or magnitude of a scalar.

Computational Methods (SECE) Chapter 4 Yonas Y. 14 / 27

 Vector and matrix norms Vector norms

Frequently used norms are

The spectral norm or Euclidean norm or 2-norm or `2 norm:
It measures the Euclidean length of a vector and is defined by
√
k x k2 = xT x
= (x12 + x22 + · · · + xn2 )1/2
n
!1/2
X
2
= |xi | .
i=0

The ∞-norm or maximum norm:

It measures the largest element in modulus and is defined by
k x k∞ := max |xi |.
1≤i≤n

The 1-norm or `1 norm:

It measures the sum of all the elements in modulus and is defined by
n
X
k x k1 := |xi |.
i=1

Computational Methods (SECE) Chapter 4 Yonas Y. 15 / 27

 Vector and matrix norms Vector norms

Figure: 4.2 The ”unit circle” according to the three norms, `1 , `2 , and `∞ . Note that the
diamond is contained in the circle, which in turn is contained in the square.

Computational Methods (SECE) Chapter 4 Yonas Y. 16 / 27

 Vector and matrix norms Vector norms

Example 4.4: Suppose we want to measure the distance between the two vectors
   
11 12
x =  12  and y =  14  .
13 16

Let
 
1
z = y − x =  2 .
3
Then

k z k1 = 1 + 2 + 3 = 6,
√
k z k2 = 1 + 4 + 9 ≈ 3.7417,
k z k∞ = 3.

Although the values of the different norms are different, they have the same order
of magnitude.

Computational Methods (SECE) Chapter 4 Yonas Y. 17 / 27

 Vector and matrix norms Matrix norms

Matrix norms

It answer questions such as how far a matrix is from being singular, and to be able
to examine quantitatively the stability of our algorithms.

Matrix norms:
functions which take a matrix as an argument,
produce a scalar value, and
satisfy the above three norm conditions.

Some matrix norms are induced by vector norms. Given an m × n matrix A and a
vector norm k · k, define

k Ax k
k A k = max
kxk
x6=0

= max k Ax k .
kxk=1

Computational Methods (SECE) Chapter 4 Yonas Y. 18 / 27

 Vector and matrix norms Matrix norms

A matrix norm is a function k A k: Rm×n → R+ such that

1 k A k ≥ 0, for all A ∈ Rm×n and k A k = 0 ⇔ A = 0.

2 k αA k = |α| k A k for all α ∈ R.

3 k A + B k ≤ k A k + k B k. (triangle inequality)

Note that matrix norms are often also required to satisfy the consistency property,

k A · B k ≤ k A kk B k

Computational Methods (SECE) Chapter 4 Yonas Y. 19 / 27

 Vector and matrix norms Matrix norms

Calculating induced matrix norms

In general, for an m × n matrix

n
X
k A k∞ := max |aij |.
1≤i≤m
j=1

An expression of similar simplicity is available also for the 1-norm and is given by
m
X
k A k1 := max |aij |.
1≤i≤n
j=1

No such simple expression is available for the 2-norm, though!

Computational Methods (SECE) Chapter 4 Yonas Y. 20 / 27

 Vector and matrix norms Matrix norms

Example 4.5: Consider

 
1 3 7
A= .
−4 1.2725 −2

Then
k A k∞ = max{11, 7.2725} = 11,
k A k1 = max{5, 4.2725, 9} = 9,
q q
k A k2 = max k Ax k2 = max (Ax)T Ax = max xT (AT A)x.
xT x=1 xT x=1 xT x=1

We can calculate
 
17 −2.09 15
AT A =  −2.09 10.6193 18.455  ,
15 18.455 53

but we still need to figure out how to maximize the quadratic form xT (AT A)x.

Computational Methods (SECE) Chapter 4 Yonas Y. 21 / 27

 Vector and matrix norms Matrix norms

The 2-norm and spectral radius

To calculate the 2-norm of a matrix, we need to consider the eigenvalues of AT A.

Let B be a square, n × n real matrix. We define the spectral radius of B as

ρ(B) = max{|λ|; λ is the eigenvalue of B}.

The spectral radius is often a pretty good lower bound for a norm.
Further, it can be shown that even for rectangular (i.e., not necessarily
square) matrices, we have
q
k A k2 = ρ(AT A).

Continuing with Example 4.5 the eigenvalues of the matrix AT A, are

(approximately) 0, 16.8475, and 63.7718.
Thus p
k A k2 ≈ 63.7718) ≈ 7.9857.

Computational Methods (SECE) Chapter 4 Yonas Y. 22 / 27

 Special classes of matrices Symmetric positive definite matrices

Symmetric positive definite matrices

The square matrix A is symmetric if, AT = A.
Furthermore, a matrix A is positive definite if

xT Ax > 0 ∀x 6= 0.
Pn
Thus, for any column vector x = (x1 , . . . , xn )T we require i,j=1 ai,j xi xj > 0,
provided that at least one component xj 6= 0.
A symmetric n × n matrix has n real eigenpairs. If A is also positive definite,
For any eigenvalue λ = λj and its associated eigenvector x = xj
n
X
0 < xT Ax = λxT x = λ xi2 ,
i=1

implying that λj > 0. Hence all eigenvalues are positive,

λ1 ≥ λ2 ≥ · · · ≥ λn > 0.

Computational Methods (SECE) Chapter 4 Yonas Y. 23 / 27

 Special classes of matrices Orthogonal vectors and matrices

Orthogonal vectors and matrices

Orthogonal vectors: Two vectors u, v ∈ Rn are orthogonal if

uT v = 0.

Vectors u and v are orthonormal if k u k2 =k v k2 = 1.

In geometric terms, orthogonality of two vectors simply means that the vectors
form a right angle between them.

A square matrix Q is orthogonal if its columns are pairwise orthonormal, i.e.,

QT Q = I . Hence also Q −1 = Q T .

Important property: for any orthogonal matrix Q and vector x:

k Qx k2 =k x k2

Hence
k Q k2 =k Q −1 k2 = 1
Computational Methods (SECE) Chapter 4 Yonas Y. 24 / 27
 Singular values

Singular values
The singular value decomposition (SVD) is a basic matrix decomposition that is
particularly stable under all conditions.

rank of A satisfies rank(A) = r ≤ min(m, n).

Computational Methods (SECE) Chapter 4 Yonas Y. 25 / 27
 Singular values

Example 4.6: The SVD of the matrix

 
1 2
A= 3 4 
5 6

is given by
 
0.229847696400071 0.883461017698525 −0.408248290463864
U =  0.524744818760294 0.240782492132547 0.816496580927726  ;
0.819641941120516 −0.401896033433433 −0.408248290463863
 
9.525518091565107 0
Σ= 0 0.514300580658642  ;
0 0
 
0.619629483829340 −0.784894453267053
V = ;
0.784894453267053 0.619629483829340
The singular values of A are extracted from the diagonal of Σ and hence are
σ1 = 9.525518091565107 and σ2 = 0.514300580658642.

Computational Methods (SECE) Chapter 4 Yonas Y. 26 / 27

 Singular values

End of Chapter 3

Questions?

Computational Methods (SECE) Chapter 4 Yonas Y. 27 / 27