Introduction to Computational Linear Algebra

Algorithms for the Eigenvalue Problem 125

section, we consider methods that only use the matrix A as an operator: the

only available operation is the matrix-vector multiplication v −→ Av.

5.4.1 Rayleigh-Ritz Projection

Let us assume that the columns of V = [v

1

, ··· , v

k

] ∈ R

n×k

form an orthonor-

mal basis of a k-dimensional invariant subspace X of the matrix A ∈ R

n×n

.

Therefore

V

∗

V = I

k

, and

∀i = 1, ··· , k, ∃y

i

∈ R

k

, such that Av

i

= V y

i

.

An orthonormal basis U of the entire space R

n×n

is obtained by adjoining a

set of vectors W ∈ R

n×(n−k)

to V to get the orthogonal matrix U = [V, W ].

By expressing the operator defined by A into the basis U, the new matrix is:

U

T

AU =



V

T

AV V

T

AW

O W

T

AW



. (5.25)

We notice that the block W

T

AV is null since the columns of AV b