Section 6.

4 Spectral Radius and Convergence Theorem

6.4 Spectral Radius and Convergence Theorem

In this section, we prove a necessary and sufficient condition for convergence of any
stationary iterative method. The condition is based on the spectral radius of the
iterative matrix of the method. We start by defining stationary iterative methods.

Definition 6.4.1 [Stationary Iterative Methods].

An iterative method for a system of n linear equation is called a (one-step) station-
ary iterative method if the terms of the iterative sequence {x(k) } can be written
in the form
x(k+1) = Bx(k) + c, (6.23)
for some B ∈ Mn (R) and c ∈ Rn .

Remark 6.4.2.
Observe that Jacobi and Gauss-Seidel methods are stationary methods. In fact, we
can construct our own stationary iterative method for a linear system of the form
Ax = b through the following steps:

1. first writing the coefficient matrix A in the form A = X + Y , for some

X, Y ∈ Mn (R), with X invertible;
2. then rewriting the given system as Xx = −Y x + b; and
3. finally get the stationary method by taking B = −X −1 Y and c = X −1 b.

We now define the notion of spectral radius in the general context.

Definition 6.4.3 [Spectral Radius].

Let A ∈ Mn (C) and let λi ∈ C, i = 1, 2, . . . , n, be the eigenvalues of A. The spectral
radius of A is defined as
ρ(A) = max |λj |.
j=1,2,...,n

We now list some of the important results concerning spectral radius.

Lemma 6.4.4.
For any subordinate matrix norm # · # : Mn (C) → [0, ∞),

ρ(A) ≤ #A#, for all A ∈ Mn (C).

93
S. Baskar and S. Sivaji Ganesh Spring 2022-23
 Section 6.4 Spectral Radius and Convergence Theorem

Proof of the above lemma is left as an exercise.

The following theorem says that ρ(A) is the greatest lower bound for any subordinate
matrix norm of a given matrix A.

Theorem 6.4.5.
For each A ∈ Mn (C) and each # > 0, there exists a subordinate matrix norm # · #
such that
ρ(A) ≤ #A# < ρ(A) + #.

Proof of the above theorem is omitted for this course.

Lemma 6.4.6.
Let B ∈ Mn (C). Then ρ(B) < 1 if and only if

lim B n z = 0, for every z ∈ Cn .

n→∞

Proof is omitted for this course.

Lemma 6.4.7.
Let B ∈ Mn (C) with ρ(B) < 1. Then (I − B)−1 exists and we have

(I − B)−1 = I + B + B 2 + . . . .

Proof is omitted for this course.

We now give the main convergence theorem for any stationary iterative method.

Theorem 6.4.8 [Necessary and Sufficient Conditions].

For any x(0) ∈ Rn , the sequence {x(k) } defined by (6.23) converges to the solution of
x = Bx + c if and only if
ρ(B) < 1.

Proof.
We first assume that ρ(B) < 1 and prove that the sequence {x(k) } converges for any

94
S. Baskar and S. Sivaji Ganesh Spring 2022-23
 Section 6.5 Exercises

x(0) ∈ Rn . The proof follows from the above two lemmas.

Conversely, assume that the sequence {x(k) } converges for any x(0) ∈ Rn and prove
that ρ(B) < 1.
We give the proof only for the particular case when all the eigenvalues of B are real.
The proof for the general case is omitted for this course.
On the contrary assume that ρ(B) ≥ 1. Let I be such that ρ(B) = |λI |. Let v I be
an eigenvector corresponding to the eigenvalue λI . Choose the initial guess x(0) as
x(0) := x + v I where x satisfies x = Bx + c. Then, using (6.23), we get

x(k+1) − x = λk+1
I vI .

Since, we assumed ρ(B) ≥ 1, the above equation implies #x(k+1) −x# → ∞ as k → ∞,

which is a contradiction.

6.5 Exercises
Iterative Methods
1. Let A be a diagonally dominant matrix such that aij = 0 for every i, j ∈
{1, 2, · · · , n} such that i > j + 1. Does naive Gaussian elimination method
preserve the diagonal dominance? Justify your answer.

2. Let A be a diagonally dominant matrix. Show that all the diagonal elements of
A are non-zero (i.e., aii (= 0 for i = 1, 2, · · · , n.). As a consequence, the iterating
sequences of Jacobi and Gauss-Seidel methods are well-defined if the coefficient
matrix A in the linear system Ax = b is a diagonally dominant matrix.

3. Write the formula for the Jacobi iterative sequence of the system

7x1 − 15x2 − 21x3 = 2,

7x1 − x2 − 5x3 = −3,
7x1 + 5x2 + x3 = 1.

Without performing the iterations, show that the sequence does not converge to
the exact solution of this system. Can you make a suitable interchange of rows
so that the resulting system is diagonally dominants?
4. Find the n×n matrix B and the n-dimensional vector c such that the Gauss-Seidel
method can be written in the form

x(k+1) = Bx(k) + c, k = 0, 1, 2, · · ·

95
S. Baskar and S. Sivaji Ganesh Spring 2022-23
 Section 6.5 Exercises

Here B is called the iterative matrix for the Gauss-Seidel method.

5. Check for the convergence of the Jacobi and Gauss-Seidel methods for each of the
following systems.
i)

5x1 + 2x2 + x3 = 0.12,

1.75x1 + 7x2 + 0.5x3 = 0.1,
x1 + 0.2x2 + 4.5x3 = 0.5.

ii)

x1 − 2x2 + 2x3 = 1,
x1 + x2 − x3 = 1,
2x1 − 2x2 + x3 = 1.

iii)

x1 + x2 + 10x3 = −1,
2x1 + 3x2 + 5x3 = −6,
3x1 + 2x2 − 3x3 = 4.

96
S. Baskar and S. Sivaji Ganesh Spring 2022-23
CHAPTER 7

Eigenvalues and Eigenvectors

Let A be an n × n matrix with real entries. Eigenvalues of A are defined as the roots
of the equation
det(λI − A) = 0. (7.1)

Note that det(λI − A) is a polynomial in λ of degree n, which is known as characteristic

polynomial of the matrix A. We know that even if A has real entries, the eigenvalues
need not be real numbers. It is also a known fact that for every matrix, there are n
eigenvalues λ1 , λ2 , · · · , λn (in this list, each eigenvalue is repeated as many times as its
algebraic multiplicity, i.e., multiplicity of the eigenvalue as a root of the characteristic
polynomial).

When n = 2 the characteristic polynomial is a quadratic polynomial for which there

is a nice formula for computing roots. When n = 3, there is a formula that many of
us do not remember. When n = 4, none has a formula. But computing eigenvalues
is important for applications. Therefore, numerically approximating the eigenvalues is
the only way out.

One obvious way of approximating an eigenvalue of a matrix is to first obtain the

characteristic polynomial (7.1) explicitly in λ and then use one of the numerical methods
discussed in the next chapter (on methods for solving nonlinear equations) to compute
a root of this polynomial. But this is not an efficient way of computing eigenvalues
because of two reasons. One reason is that obtaining explicit form of (7.1) is itself a
difficult task when the dimension of the matrix is very large. Secondly, if we make any
small error (like floating-point error) in obtaining the explicit form of the polynomial
(7.1), the resulting polynomial may have a root which is entirely different from any of

97
S. Baskar and S. Sivaji Ganesh Spring 2022-23
 Section 7.1 Power Method

the eigenvalues that we are looking for. This is illustrated in the following example
by Wilkinson where we see that “the roots of polynomials are extremely sensitive to
perturbations in the coefficients”.

Example 7.0.1 [Wilkinson’s example].

Let f (x) and g(x) be two polynomials given by
f (x) = (x − 1)(x − 2) · · · (x − 10), g(x) = x10 .

The roots of the polynomial f (x) are 1, 2, · · · , 10, and all these roots are simple roots.
If we perturb this polynomial as F (x) = f (x) + 0.01g(x), then all the roots lie in the
interval [1, 3.5] (verified graphically). In fact, the largest root of the polynomial f (x)
is 10 and the largest root of the polynomial F (x) is approximately equal to 3.398067.
Thus, if the coefficient of x10 is perturbed by a small amount of 0.01, the root 10 of
f (x) could move as much a distance as approximately 6.6.

Due to the two reasons discussed above, we look for an alternate method to compute the
eigenvalues of a given matrix. One such method is the power method that can be used to
obtain the eigenvalue which is the largest in magnitude among all the other eigenvalues
and the corresponding eigen vector. In Subsection 7.1, we present the power method
and discuss the condition under which this method can be applied. In Subsection 7.2 we
prove the Gerschgorin theorem which may be used as a tool to find a class of matrices
for which power method can be applied successfully.

7.1 Power Method

There are many variations of power method in the literature. We will present the most
elementary form of power method. We always deal with matrices with real entries, all
of whose eigenvalues are real numbers.
Power method is used to obtain a specific eigenvalue called dominant eigenvalue and
a corresponding eigenvector for a given n × n matrix A. The concept of a dominant
eigenvalue plays a very important role in many applications. The power method pro-
vides an approximation to it under some conditions on the matrix. We now define the
concept of a dominant eigenvalue.

Definition 7.1.1 [Dominant Eigenvalue of a Matrix].

An eigenvalue λ of an n × n matrix A is said to be a dominant eigenvalue of A if

|λ| = max{ |z| : z is an eigenvalue of A }.

98
S. Baskar and S. Sivaji Ganesh Spring 2022-23
 Section 7.1 Power Method

Remark 7.1.2.

1. If a dominant eigenvalue of a matrix is equal to zero, then all its eigenvalues

are zero and an eigenvector can be found by solving the linear system Ax = 0.
2. If λ is a dominant eigenvalue of a matrix A, then there is no other eigenvalue
of A whose distance from zero is more than that of λ from zero.
3. Let µ1 , µ2 , · · · , µn be the eigenvalues of A (repeated according to their alge-
braic multiplicities) of an n × n matrix A. These eigenvalues can be renamed
(relabelled, reindexed) as λ1 , λ2 , · · · , λn such that they satisfy the condition:

|λ1 | ≥ |λ2 | ≥ · · · ≥ |λn |.

Note that λ1 is a dominant eigenvalue of A.

A matrix may have a unique dominant eigenvalue or more than one dominant eigen-
values. Further, even if dominant eigenvalue is unique the corresponding algebraic and
geometric multiplicities could be more than one, and also both algebraic and geometric
multiplicities may not be the same. All these possibilities are illustrated in the following
example.

Example 7.1.3.

1. The matrix  
1 0 0
A=  0 −2 1 
0 0 −1
has eigenvalues 1, −1, and −2. The matrix A has a unique dominant eigenvalue,
which is −2 as this is the largest in absolute value, of all eigenvalues. Note that
the dominant eigenvalue of A is a simple eigenvalue.
2. The matrix  
1 3 4
B=  0 2 1 
0 0 −2
has eigenvalues 1, −2, and 2. According to our definition, the matrix B has
two dominant eigenvalues. They are −2 and 2. Note that both the dominant
eigenvalues of B are simple eigenvalues.

99
S. Baskar and S. Sivaji Ganesh Spring 2022-23
 Section 7.1 Power Method

3. Consider the matrices

 
1 3 4 % & % &
2 0 2 1
C1 =  0 2 5  , C2 = , C3 = .
0 2 0 2
0 0 2

The matrix C1 has a unique dominant eigenvalue 2, which has algebraic mul-
tiplicity 2 and geometric multiplicity 1. The matrix C2 has a unique dominant
eigenvalue 2, whose algebraic and geometric multiplicities equal 2. The matrix
C3 has a unique dominant eigenvalue 2, which has algebraic multiplicity 2 and
geometric multiplicity 1.
As mentioned above the power method is used to compute the dominant eigenvalue
and the corresponding eigen vector of a given n × n matrix provided this eigenvalue is
unique. Thus, in the above examples, power method can be used for the matrices A
but not for B even though B has distinct eigenvalues. Let us now detail the power
method.

Hypotheses for which the power method can work

Assume that an n × n matrix A has real eigenvalues λ1 , λ2 , · · · , and λn (repeated

according to their algebraic multiplicities) with the following properties:
(H1) The eigenvalues are such that

|λ1 | > |λ2 | ≥ |λ3 | ≥ · · · ≥ |λn | (7.2)

That is, A has a unique dominant eigenvalue λ1 which is a simple eigenvalue.

(H2) There exists a basis of Rn consisting of eigenvectors of A. That is, there exists
v 1 , v 2 , · · · , v n satisfying Av k = λk v k for k = 1, 2, · · · , n; and such that for each
v ∈ Rn there exists unique real numbers c1 , c2 , · · · , cn such that

v = c1 v 1 + c2 v 2 + · · · + cn v n .

Equivalently, the matrix A is diagonalizable.

(H3) An initial guess x(0) ∈ Rn be chosen such that

n
'
x(0) = cj v j , (7.3)
j=1

∞
(
for some scalars c1 , c2 , · · · , cn ∈ R with c1 (= 0 and x (0)
∈
/ KerAk .
k=1

100
S. Baskar and S. Sivaji Ganesh Spring 2022-23
 Section 7.1 Power Method

Let us now discuss the key idea behind power method.

• Choose a non-zero vector x(0) ∈ Rn arbitrarily so that we can find scalars c1 , c2 ,
· · · , cn ∈ R such that

x(0) = c1 v 1 + c2 v 2 + · · · + cn v n , c1 (= 0.

• Pre-multiplying by A and substituting Av i = λi v i , i = 1, · · · , n, we get

% % & % & &
(0) λ2 λn
Ax = c1 λ1 v 1 + · · · + cn λn v n = λ1 c1 v 1 + c2 v 2 + · · · + cn vn .
λ1 λ1
Note here that we have assumed λ1 (= 0, which follows from the Assumption (1)
above.
• Pre-multiplying by A again and simplying, we get
) % &2 % &2 *
λ 2 λn
A2 x(0) = λ21 c1 v 1 + c2 v 2 + · · · + cn vn
λ1 λ1

• For each k ∈ N, applying A k-times on x(0) yields

) % &k % &k *
λ λn
(7.4)
2
Ak x(0) = λk1 c1 v 1 + c2 v 2 + · · · + cn vn
λ1 λ1

• Using the assumption (7.2), we get |λj /λ1 | < 1, for j = 2, · · · , n. Therefore, we
have
Ak x(0)
lim = c1 v 1 . (7.5)
k→∞ λk1

For c1 (= 0, the right hand side of the above equation is a scalar multiple of the
eigenvector.
• From the above expression for Ak x(0) , we also see that

(Ak+1 x(0) )i
lim = λ1 , (7.6)
k→∞ (Ak x(0) )i

where i is any index such that the fractions on the left hand side are meaningful
(which is the case when x(0) ∈
/ ∪∞k=1 KerA ).
k

The power method generates two sequences {µk } and {x(k) }, using the results (7.5) and
(7.6), that converge to the dominant eigenvalue λ1 and the corresponding eigenvectors
v 1 , respectively.
We now describe the steps involved in the power method for generating these two
sequences.

101
S. Baskar and S. Sivaji Ganesh Spring 2022-23
 Section 7.1 Power Method

Setting up the iterative sequences:

Step 1: Choose a vector x(0) arbitrarily and set y (1) := Ax(0) .
Step 2: Define µ1 := yi , where i ∈ {1, · · · , n} is the least index such that
(1)

(1)
#y (1) #∞ = |yi |

and set
y (1)
x(1) := .
µ1
Step 3: From x(1) , we can obtain µ2 and x(2) as in step 2.
Continue this procedure.
General form of the power method iterative sequences:
After choosing the initial vector x(0) arbitrarily, we generate the sequences {µ(k) } and
{x(k) } using the formulas
y (k+1)
(7.7)
(k+1)
µk+1 = yi , x(k+1) = ,
µk+1
where

y (k+1) = Ax(k) and i is such that |yi (7.8)

(k+1)
| = #y (k+1) #∞ ,

for k = 0, 1, · · · .
This iterative procedure is called the power method.

Remark 7.1.4.
The scaling factor µk introduced in (7.7) makes sure that x(k) has its maximum
norm equal to 1, i.e., #x(k) #∞ = 1. This rules out the possibilities of limk→∞ x(k)
being 0 or the vector x(k) escaping to infinity.

We now discuss the sufficient conditions under which the power method converges.

Theorem 7.1.5 [Convergence Theorem for Power method].

Hypothesis: Let A be an n × n matrix with real eigenvalues having the following
properties:
(H1) A has a unique dominant eigenvalue λ1 which is a simple eigenvalue. That is,

|λ1 | > |λ2 | ≥ · · · ≥ |λn |,

102
S. Baskar and S. Sivaji Ganesh Spring 2022-23
 Section 7.1 Power Method

where λ1 , λ2 , · · · , λn are the eigenvalues of A (repeated according to their al-

gebraic multiplicities).
(H2) A has n linearly independent real eigenvectors, v i , i = 1, · · · , n.
(H3) An initial guess x(0) ∈ Rn be chosen such that
n
'
x (0)
= cj v j , (7.9)
j=1

∞
(
for some scalars c1 , c2 , · · · , cn ∈ R with c1 (= 0 and x(0) ∈
/ KerAk .
k=1

Conclusion: Then, in the power method (7.7)-(7.8),

1. the sequence {µk } converges to the dominant eigenvalue λ1 and
2. a subsequence of the sequence {xk } converges to an eigenvector corresponding
to the eigenvalue λ1 .

Proof.
From the definition of x(k+1) , we have

x(k+1) = mk+1 Ak+1 x(0) ,

where mk+1 = 1/(µ1 µ2 · · · µk+1 ).

n
'
But, x(0) = cj v j , c1 (= 0. Therefore
j=1

) n % &k+1 *
' λj
x(k+1) = mk+1 λk+1
1 c1 v 1 + cj vj .
j=2
λ1

Taking maximum norm on both sides and noting that #x(k) #∞ = 1, we get
, % &k+1 ,
+ + , n
' λj ,
, ,
1 = +mk+1 λk+1
1
+ , c v
1 1 + c j v j, .
, λ1 ,
j=2 ∞

Since |λj /λ1 |k → 0 as k → ∞, we get

+ + 1
lim +mk+1 λk+1
1
+= < ∞.
k→∞ |c1 |#v 1 #∞

103
S. Baskar and S. Sivaji Ganesh Spring 2022-23
 Section 7.1 Power Method

Using this, we get


v1


 either +

 #v 1 #∞





 v1
lim x(k+1) k+1
= lim mk+1 λ1 c1 v 1 = or − . (7.10)
k→∞ k→∞  #v 1 #∞







 or oscillates between

 the above two vectors

This completes the proof of Conclusion (2).

Let us now prove that µk → λ1 . For this, we first note that

lim y (k+1) = Kλ1 v 1 ,

k→∞

up to a subsequence, where K = ±1/#v 1 #∞ . Since v 1 is an eigen vector, there is at

least one non-zero component of v 1 . We choose one such component of v 1 and denote
it by (v1 )j . Since (v1 )j (= 0 and yj → Kλ1 (v1 )j , as k → ∞, there exists an integer
(k+1)

N > 0 such that

(= 0, for all k ≥ N .
(k+1)
yj
Similarly, we see that
(= 0, for all k ≥ N .
(k+1)
xj
Therefore, we can write
(k+1)
yj (Ax(k) )j
µk+1 = (k+1)
= ,
xj (x(k+1) )j
where j denotes the component as given above. Taking limit, we have

lim µk+1 = λ1 .
k→∞

which gives the desired result.

Note that the above theorem does not guarantee the convergence of the sequence {xn }
to an eigenvector of the dominant eigenvalue. However, if the dominant eigenvalue has
an eigenvector with a unique dominant component, then this sequence converges as
discussed in the following theorem.

104
S. Baskar and S. Sivaji Ganesh Spring 2022-23
 Section 7.1 Power Method

Theorem 7.1.6 [Second Convergence Theorem for Power Method].

Let A be an n × n matrix satisfying the hypotheses (H1), (H2), and (H3) of
Theorem 7.1.5. In addition to these hypotheses,
(H4) let v 1 = (v11 , v12 , · · · , v1n )T be such that there exists a unique index j ∈
{1, 2, · · · , n} with the property

|v1j | = #v 1 #∞ (7.11)

This hypothesis is referred to as v 1 has a single maximal component.

Conclusion: Then, in the power method (7.7)-(7.8),
1. the sequence {µk } converges to the dominant eigenvalue λ1 and
2. The sequence of vectors x(k) converges to an eigenvector corresponding to the
dominant eigenvalue λ1 .

Proof.
Let us first set up some notation. Let the eigenvectors v 1 , v 2 , · · · , v n be given by

v j = (vj1 , vj2 , · · · , vjn )T , for j = 1, 2, · · · , n. (7.12)

Since x(0) = c1 v 1 + c2 v 2 + · · · + cn v n , we have

Ax(0) = c1 λ1 v 1 + c2 λ2 v 2 + · · · + cn λn v n .

In coordinate form, we have

Ax(0) = (λ1 c1 v11 + λ2 c2 v21 + · · · + λn cn vn1 , · · · , λ1 c1 v1n + λ2 c2 v2n + · · · + λn cn vnn )T

(7.13)
In fact, for each k ∈ N, we have

Ak x(0) = (λk1 c1 v11 + λk2 c2 v21 + · · · + λkn cn vn1 , · · · , λk1 c1 v1n + λk2 c2 v2n + · · · + λkn cn vnn )T
(7.14)
Maximum norm of the vector A x is going to be the modulus of one of its compo-
k (0)

nents. From (H4), we have

|v1i |
≤1 for i = 1, 2, · · · , n. (7.15)
|v1j |

105
S. Baskar and S. Sivaji Ganesh Spring 2022-23
 Section 7.1 Power Method

Observe that
(Ak x(0) )i λk1 c1 v1i + λk2 c2 v2i + · · · + λkn cn vni
= .
(Ak x(0) )j λk1 c1 v1j + λk2 c2 v2j + · · · + λkn cn vnj

The last equation can be written in the form

λk2 c2 λkn cn
v1i + v 2i + · · · + vni
(Ak x(0) )i λk1 c1 λk1 c1
= (7.16)
(Ak x(0) )j λk c 2 λk c n
v1j + 2k v2j + · · · + nk vnj
λ1 c 1 λ1 c 1
v1i
Note that the RHS in the equation (7.16) converges to as k → ∞. Since,
v1j
+ +
+ v1i +
+ + < 1,
+ v1j + for i (= j, (7.17)

we can conclude that there exists a K ∈ N such that for k ≥ K,

+ k (0) +
+ (A x )i +
+ +
+ (Ak x(0) )j + < 1. (7.18)

As a consequence, the maximum norm of Ak x(0) is equal to |(Ak x(0) )j | where j is as

given in (H4).

For k ≥ K, the sequence µk is given by

λk2 c2 λkn cn
v2j + · · · +
v1j + vnj
(Ak x(0) )j λk1 c1 λk1 c1
µk = k−1 (0) = λ1 . (7.19)
(A x )j λk−1 c2 λk−1
n cn
v1j + 2k−1 v2j + · · · + vnj
λ1 c 1 λk−1
1 c 1

Thus,
lim µk = λ1 . (7.20)
k→∞

For k ≥ K, the sequence x(k) is given by

Ak x(0)
x(k) =
(Ak x(0) )j
% k (0) &T
(A x )1 (Ak x(0) )j−1 (Ak x(0) )j+1 (Ak x(0) )n
= ,··· , , 1, , · · · , k (0) .
(Ak x(0) )j (Ak x(0) )j (Ak x(0) )j (A x )j

106
S. Baskar and S. Sivaji Ganesh Spring 2022-23
 Section 7.1 Power Method

In view of (7.16), we now conclude that the sequence x(k) converges to 1

v
v1j 1
which
is an eigenvector corresponding to the dominant eigenvalue λ1 .

We now give a numerical example illustrating the power method procedure.

Example 7.1.7.
Consider the matrix  
3 0 0
A=  −4 6 2 .
16 −15 −5
The eigenvalues of this matrix are

λ1 = 3, λ2 = 1 and λ3 = 0.

The corresponding eigen vectors are

v 1 = (1, 0, 2)T , v 2 = (0, 2, −5)T and v 3 = (0, 1, −3)T .

Thus, the hypothesis (H1) and (H2) are satisfied. Choose the initial guess x0 =
(1, 0.5, 0.25)T , which also satisfies the hypothesis (H3).
The first ten terms of the iterative sequence in power method given by (7.7)-(7.8) for
the given matrix A are as follows:
Iteration No: 1

y 1 = Ax0 = (3.000000, −0.500000, 7.250000)T

µ1 = 7.250000
y1
x1 = = (0.413793, −0.068966, 1.000000)T
µ1
Iteration No: 2

y 2 = Ax1 = (1.241379, −0.068966, 2.655172)T

µ2 = 2.655172
y2
x2 = = (0.467532, −0.025974, 1.000000)T
µ2
Iteration No: 3

107
S. Baskar and S. Sivaji Ganesh Spring 2022-23
 Section 7.1 Power Method

y 3 = Ax2 = (1.402597, −0.025974, 2.870130)T

µ3 = 2.870130
y3
x3 = = (0.488688, −0.009050, 1.000000)T
µ3
Iteration No: 4

y 4 = Ax3 = (1.466063, −0.009050, 2.954751)T

µ4 = 2.954751
y4
x4 = = (0.496172, −0.003063, 1.000000)T
µ4
Iteration No: 5

y 5 = Ax4 = (1.488515, −0.003063, 2.984686)T

µ5 = 2.984686
y5
x5 = = (0.498717, −0.001026, 1.000000)T
µ5
Iteration No: 6

y 6 = Ax5 = (1.496152, −0.001026, 2.994869)T

µ6 = 2.994869
y6
x6 = = (0.499572, −0.000343, 1.000000)T
µ6
Iteration No: 7

y 7 = Ax6 = (1.498715, −0.000343, 2.998287)T

µ7 = 2.998287
y7
x7 = = (0.499857, −0.000114, 1.000000)T
µ7
Iteration No: 8

y 8 = Ax7 = (1.499571, −0.000114, 2.999429)T

µ8 = 2.999429
y8
x8 = = (0.499952, −0.000038, 1.000000)T
µ8

108
S. Baskar and S. Sivaji Ganesh Spring 2022-23
 Section 7.1 Power Method

Iteration No: 9

y 9 = Ax8 = (1.499857, −0.000038, 2.999809)T

µ9 = 2.999809
y9
x9 = = (0.499984, −0.000013, 1.000000)T
µ9
Iteration No: 10

y 10 = Ax9 = (1.499952, −0.000013, 2.999936)T

µ10 = 2.999936
y 10
x10 = = (0.499995, −0.000004, 1.000000)T
µ10

These ten iterates suggest that the sequence {µk } converges to the eigenvalue λ1 = 3
1
and the sequence {x(k) } converges to (0.5, 0, 1) = v 1 .
2

Remark 7.1.8 [Disadvantages of power method].

1. The Power method requires at the beginning that the matrix has only one
dominant eigenvalue, and this information is generally unavailable.

2. Even when there is only one dominant eigenvalue, it is not clear how to
choose the initial guess x(0) such that it has a non-zero component (c1 in the
notation of the theorem) along the eigenvector v 1 .

Note that in the above example, all the hypothesis are satisfied. Now let us ask the
question
“What happens when any of the hypotheses of power method is violated?”
We discuss these situations through examples.

Example 7.1.9 [Dominant eigenvalue is not unique (Failure of H1)].

Consider the matrix  
1 3 4
B= 0 2 1 ,
0 0 −2

109
S. Baskar and S. Sivaji Ganesh Spring 2022-23
 Section 7.1 Power Method

which has eigenvalues 1, −2, and 2. Clearly, the matrix B has two dominant eigen-
values, namely, −2 and 2. We start with an initial guess x(0) = (1, 1, 1) and the first
five iterations generated using power method are given below:

Iteration No: 1

y 1 = Ax0 = (8.000000, 3.000000, −2.000000)T

µ1 = 8.000000
y1
x1 = = (1.000000, 0.375000, −0.250000)T
µ1
Iteration No: 2

y 2 = Ax1 = (1.125000, 0.500000, 0.500000)T

µ2 = 1.125000
y2
x2 = = (1.000000, 0.444444, 0.444444)T
µ2
Iteration No: 3

y 3 = Ax2 = (4.111111, 1.333333, −0.888889)T

µ3 = 4.111111
y3
x3 = = (1.000000, 0.324324, −0.216216)T
µ3
Iteration No: 4

y 4 = Ax3 = (1.108108, 0.432432, 0.432432)T

µ4 = 1.108108
y4
x4 = = (1.000000, 0.390244, 0.390244)T
µ4
Iteration No: 5
y 5 = Ax4 = (3.731707, 1.170732, −0.780488)T
µ5 = 3.731707
y5
x5 = = (1.000000, 0.313725, −0.209150)T
µ5
It is observed that the sequence oscillates even till 1000 iterations as shown below:

Iteration No: 998

110
S. Baskar and S. Sivaji Ganesh Spring 2022-23
 Section 7.1 Power Method

y 998 = Ax997 = (1.103448, 0.413793, 0.413793)T

µ998 = 1.103448
y 998
x998 = = (1.000000, 0.375000, 0.375000)T
µ998
Iteration No: 999
y 999 = Ax998 = (3.625000, 1.125000, −0.750000)T
µ999 = 3.625000
y 999
x999 = = (1.000000, 0.310345, −0.206897)T
µ999
Iteration No: 1000
y 1000 = Ax999 = (1.103448, 0.413793, 0.413793)T
µ1000 = 1.103448
y 1000
x1000 = = (1.000000, 0.375000, 0.375000)T
µ1000
and so on. This is a clear indication that the power method is not converging in this
case.

Thus we conclude that the power method when applied to a matrix which has more
than one dominant eigenvalue may not converge.

Remark 7.1.10 [Dominant eigenvalue is not simple].

It is not necessary to have the dominant eigenvalue of algebraic multiplicity 1 in
order that the iterative sequences of power method converge. The important thing
is to have a unique dominant eigenvalue and it is allowed to have an algebraic
multiplicity r with r > 1. However it is necessary that the corresponding geometric
multiplicity should also be r to satisfy the hypothesis (H2) (also see later on, where
we discuss the situation where algebraic and geometric multiplicities do not match).
In such a case, power method computes only one eigenvector, as is usual.

Let us now illustrate the situation when the hypothesis (H3) is violated.

Example 7.1.11 [Failure of hypothesis (H3): Initial guess x(0) is such that c1 = 0].

111
S. Baskar and S. Sivaji Ganesh Spring 2022-23
 Section 7.1 Power Method

Consider the matrix (same as in Example 7.1.7)

 
3 0 0
A=  −4 6 2 ,
16 −15 −5

The eigenvalues of this matrix are

λ1 = 3, λ2 = 1 and λ3 = 0.

The corresponding eigenvectors are

v 1 = (1, 0, 2)T , v 2 = (0, 2, −5)T and v 3 = (0, 1, −3)T .

Thus, the hypothesis (H1) and (H2) are satisfied.

Here, we choose a different initial guess x0 = (0, 0.5, 0.25)T . Note that the hypothesis
(H3) that c1 (= 0 is violated here. However, we can see that c2 (= 0. The first four
iterations of the power method are as follows:

Iteration No: 1

y 1 = Ax0 = (0.000000, 3.500000, −8.750000)T

µ1 = −8.750000
y1
x1 = = (−0.000000, −0.400000, 1.000000)T
µ1
Iteration No: 2

y 2 = Ax1 = (0.000000, −0.400000, 1.000000)T

µ2 = 1.000000
y2
x2 = = (0.000000, −0.400000, 1.000000)T
µ2
Iteration No: 3

y 3 = Ax2 = (0.000000, −0.400000, 1.000000)T

µ3 = 1.000000
y3
x3 = = (0.000000, −0.400000, 1.000000)T
µ3
Iteration No: 4

112
S. Baskar and S. Sivaji Ganesh Spring 2022-23
 Section 7.1 Power Method

y 4 = Ax3 = (0.000000, −0.400000, 1.000000)T

µ4 = 1.000000
y4
x4 = = (0.000000, −0.400000, 1.000000)T
µ4
Thus, the power method converges to λ2 , which is the second dominant eigenvalue of
the given matrix.
Note that in the chosen initial guess, the first coordinate is zero and therefore, c1 in
(7.9) has to be zero. Thus, (7.4) reduces to
) % &k % &k *
λ 3 λn
Ak v = λk2 c2 v 2 + c3 v 3 + · · · + cn vn .
λ2 λ2

This makes the iteration to converge to λ2 , which is the next dominant eigenvalue.

Remark 7.1.12.
It is important that we understand the hypothesis (H3) on the initial guess x(0)
correctly. Note that (H3) says that the coefficient of v 1 (which was denoted by c1 )
should be non-zero when x(0) is expressed as

x(0) = c1 v 1 + c2 v 2 + · · · + cn v n .

Note that the coefficients c1 , c2 , · · · , cn are unique as v 1 , v 2 , · · · , v n form a basis

for Rn . For such a choice of x(0) , it may happen that the first coordinate may be
zero. That is, if x(0) is written in coordinate form as x(0) = (x1 , x2 , · · · , xn )T ,
(0) (0) (0)

it is possible that x1 = 0 and c1 (= 0. Thus, it is not necessary that the power

(0)

method will converge to the second dominant eigenvalue if the first coordinate of
the initial guess is zero. However, we may expect this to happen if c1 = 0. The
following example illustrates this fact.

Example 7.1.13.
Consider the matrix
 
91.4 −22.0 −44.8000

A = 175.2 −41.0 −86.4  .
105.2 −26.0 −51.4000

The eigenvalues of this matrix are λ1 = −5, λ2 = 3 and λ3 = 1. The corresponding

eigenvectors are v 1 = (3, 5, 4)T , v 2 = (2, 6, 1)T and v 3 = (1, −2, 3)T .

113
S. Baskar and S. Sivaji Ganesh Spring 2022-23
 Section 7.1 Power Method

Note that the matrix A satisfies the hypothesis (H1) since -5 is the unique dominant
eigenvalue and it is also a simple eigenvalue. The matrix A satisfies the hypothesis
(H2) as all eigenvalues are distinct and hence eigevectors form a basis for R3 . Thus
the fate of the power method iterates depends solely on the choice of the initial guess
x(0) and whether it satisfies the hypothesis (H3)
• Let us take the initial guess x(0) = (1, 0.5, 0.25)T . Note that c1 (= 0 for this ini-
tial guess. Thus the initial guess satisfies the hypothesis (H3) and the iterative
sequences generated by power method converges to the dominant eigenvalue
λ1 = −5 and the corresponding eigenvector (with a scalar multiple) 15 v 1 .

• Let us take the initial guess x(0) = (0, 0.5, 0.25)T . Note that c1 (= 0 for this ini-
tial guess. Thus the initial guess satisfies the hypothesis (H3) and the iterative
sequences generated by power method converges to the dominant eigenvalue
λ1 = −5 and the corresponding eigenvector (with a scalar multiple) 15 v 1 . Com-
pare this with Example 7.1.11. In the present case the first coordinate of the
initial guess vector is zero, just as in Example 7.1.11. In Example 7.1.11 the
power method iterate converged to the second dominant eigenvalue and the
corresponding eigenvector, which does not happen in the present case. The
reason is that in the Example 7.1.11, c1 = 0 for the initial guess chosen, but in
the current example c1 (= 0.

7.1.1 Inverse Power Method

From the basic linear algebra, we know that if λ is an eigenvalue of an invertible
matrix A, then λ−1 is an eigenvalue of A−1 . Hence, if the eigenvalues of A (after a
re-arrangement) are such that

|λ1 | ≥ |λ2 | ≥ . . . ≥ |λn−1 | > |λn |,

then we can apply the power method to the matrix A−1 to approximate the eigenvalue
λn , provided the other two hypotheses of Theorem 7.1.5 are satisfied.

The main difficulty in this idea is to compute A−1 . Instead, of first computing A−1 and
then applying the power method, we can obtain a LU factorization of A once and then
solve the system
Ay (k+1) = x(k)

at every iteration of the power method using one forward substitution and one backward
substitution. By keeping all the other steps of the power method unchanged, the
resulting method is the inverse power method for computing the eigenvalue of A having
the smallest absolute value and a corresponding eigen vector.

114
S. Baskar and S. Sivaji Ganesh Spring 2022-23
 Section 7.2 Gerschgorin’s Theorem

7.1.2 Shifted Inverse Power Method

We may use the inverse power method to obtain any eigenvalue of a matrix A. The idea
is to choose a number ν very close to the required eigenvalue λ and consider applying the
inverse power method to the shifted matrix (A − νI), provided this matrix is invertible.
Note that λ − ν is an eigenvalue of (A − νI). Further, if λ − ν happens to be the
smallest eigenvalue (in modulus) of (A − νI) and if all the hypotheses of Theorem 7.1.5
are satisfied for the matrix (A − νI)−1 , then the power method sequences {µk } and
{x(k) } converge to 1/(λ − ν) and a corresponding eigenvector of λ, respectively. The
resulting method is the shifted inverse power method.

7.2 Gerschgorin’s Theorem

An important tool in eigenvalue approximation is the ability to localize the eigenvalues,
and the most important tool in eigenvalue localization is the Gerschgorin’s theorem.
Gerschgorin’s Circle theorem helps us in localization of eigenvalues of a matrix. This
theorem explicitly constructs n disks in the complex plane with centers at the diagonal
elements of the matrix; and all the eigenvalues of the matrix lie in the union of these
disks.

Theorem 7.2.1 [Gerschgorin’s Circle Theorem].

Let A be an n × n matrix. For each k = 1, 2, · · · , n, define ρk by
n
'
ρk = |akj |, (7.21)
j=1
j$=k

and Dk denotes the closed disk in the complex plane with centre akk and radius ρk ,
i.e.,
5 6
Dk = z ∈ C : |z − akk | ≤ ρk . (7.22)
1. Each eigenvalue of A lies in one of the disks Dk . That is, no eigenvalue of A
lies in C \ ∪nk=1 Dk .
2. Suppose that among the disks D1 , D2 , · · · , Dn , there is a collection of m disks
whose union (denoted by R1 ) is disjoint from the union of the rest of the
n − m disks (denoted by R2 ). Then exactly m eigenvalues lie in R1 and n − m
eigenvalues lie in R2 (here each eigenvalue is counted as many times as its
algebraic multiplicity).
The disks Dk , k = 1, 2, . . . , n are called the Gerschgorin’s disks.

115
S. Baskar and S. Sivaji Ganesh Spring 2022-23
 Section 7.2 Gerschgorin’s Theorem

Proof.
We will prove only (i) as it is easy, and the proving (ii) is beyond the scope of this
course.
Let λ be an eigenvalue of A. Then there exists a v = (v1 , v2 , · · · , vn ) ∈ Rn and v (= 0
such that
Av = λv (7.23)
Let 1 ≤ r ≤ n be such that |vr | = max{|v1 |, |v2 |, · · · , |vn |}. The rth equation of the
system of equations (7.23) is given by (actually, of Av − λv = 0)

ar1 v1 + · · · + ar,r−1 vr−1 + (arr − λ)vr + ar,r+1 vr+1 + · · · + arn vn = 0

From the last equation, we get

v1 vr−1 vr+1 vn
λ − arr = ar1 + · · · + ar,r−1 + ar,r+1 + · · · + arn (7.24)
vr vr vr vr
Taking modulus on both sides of the equation (7.24), and using the triangle inequality
|a + b| ≤ |a| + |b| repeatedly we get

|v1 | |vr−1 | |vr+1 | |vn |

|λ − arr | ≤ |ar1 | + · · · + |ar,r−1 | + |ar,r+1 | + · · · + |arn | (7.25)
|vr | |vr | |vr | |vr |

In view of the choice of r, the components of the vector v satisfy |vs |

|vr |
≤ 1. The last
equation (7.25) becomes

|λ − arr | ≤ |ar1 | + · · · + |ar,r−1 | + |ar,r+1 | + · · · + |arn | (7.26)

Observe that the right hand side of the inequality (7.26) is ρr . This proves that
λ ∈ Dr .

Example 7.2.2.
For the matrix  
4 1 1
 0 2 1 ,
−2 0 9

116
S. Baskar and S. Sivaji Ganesh Spring 2022-23
 Section 7.2 Gerschgorin’s Theorem

the Gerschgorin’s disks are given by

5 6
D1 = z ∈ C : |z − 4| ≤ 2 ,
5 6
D2 = z ∈ C : |z − 2| ≤ 1 ,
5 6
D3 = z ∈ C : |z − 9| ≤ 2 .

Draw a picture of these disks and observe that D3 neither intersects D1 nor D2 . By
(ii) of Theorem 7.2.1, D3 has one eigenvalue and D1 ∪D2 has two eigenvalues counting
multiplicities. Note that the eigenvalues are approximately 4.6318, 1.8828 ∈ D1 ∪ D2
and 8.4853 ∈ D3 .

Remark 7.2.3.
Gerschgorin’s circle theorem is helpful in finding bound for eigenvalues. For the
matrix in Example 7.2.2, any number z in D1 satisfies |z| ≤ 6. Similarly any
number z in D2 satisfies |z| ≤ 3, and any number z in D3 satisfies |z| ≤ 11. Since
any eigenvalue λ lies in one of three disks, we can conclude that |λ| ≤ 11.

Remark 7.2.4.
The main disadvantage of the power method discussed in Section 7.1 is that if a
given matrix has more than one dominant eigenvalues, then the method may not
converge. So, for a given matrix, we do not know whether the power method will
converge or not. Also, as the power method is reasonably slow (see Example 7.1.13
for an illustration) we may have to perform reasonably large number of iterations
to come to know that the method is not actually converging.

Thus, a tool to find out whether the given matrix has a unique dominant eigenvalue
or not is highly desirable. The Gerschgorin theorem (Theorem 7.2.1) can sometimes
be used to see if power method can be used for a given matrix. For instance, in Ex-
ample 7.2.2, we see that the power method can be used to obtain an approximation
to the dominant eigenvalue.

Since a matrix A and its transpose (denoted by AT ) have same eigenvalues, we can apply
Gerschgorin Circle Theorem to AT and conclude the following corollary.

117
S. Baskar and S. Sivaji Ganesh Spring 2022-23
 Section 7.2 Gerschgorin’s Theorem

Corollary 7.2.5.
Let A be an n × n matrix. For each k = 1, 2, · · · , n, define τk by
n
'
τk = |ajk |, (7.27)
j=1
j$=k

and Bk denotes the closed disk in the complex plane with centre akk and radius τk .
That is,
5 6
Bk = z ∈ C : |z − akk | ≤ τk . (7.28)
1. Each eigenvalue of A lies in one of the disks Bk . That is, no eigenvalue of A
lies in C \ ∪nk=1 Bk .
2. Suppose that among the disks B1 , B2 , · · · , Bn , there is a collection of m disks
whose union (denoted by C1 ) is disjoint from the union of the rest of the n −
m disks (denoted by C2 ). Then exactly m eigenvalues lie in C1 and n − m
eigenvalues lie in C2 (here each eigenvalue is counted as many times as its
algebraic multiplicity).

Optimal Bounds
Using the Gerschgorin theorem, we wish to identify an annular region in the complex
plane of the form
5 6
z ∈ C : r ≤ |z| ≤ R , (7.29)

for some non-negative real numbers r and R, containing all the eigenvalues of a given
matrix.
Let A = (aij ) be an n × n matrix with real entries. For k = 1, 2, · · · , n, consider the
Gerschgorin disk Dk defined by (7.22). Then, for z ∈ Dk we have

|z − akk | ≤ ρk ,

where ρk is given by (7.21). Using the triangle inequality, we get

+ +
+ |z| − |akk | + ≤ |z − akk | ≤ ρk ,

from which we get

|z| − |akk | ≤ ρk and |akk | − |z| ≤ ρk .
Combining the above inequalities, we write

|akk | − ρk ≤ |z| ≤ |akk | + ρk .

118
S. Baskar and S. Sivaji Ganesh Spring 2022-23
 Section 7.2 Gerschgorin’s Theorem

Therefore, by the Gerschgorin theorem, all the eigenvalues of A are contained in the
annular region (7.29) where

r = min (|akk | − ρk ) and R = max (|akk | + ρk ).

1≤k≤n 1≤k≤n

If r turns out to be negative, then we replace it by 0.

Similarly, we can also obtain an annular region containing all the eigenvalues of A using
Corollary 7.2.5. This annular region is given by
5 6
z ∈ C : t ≤ |z| ≤ T ,

where
t = min (|akk | − τk ), T = max (|akk | + τk ),
1≤k≤n 1≤k≤n

and τk as in (7.27). If t turns out to be negative, then we replace it by 0.

The smallest annular region, obtained using the Gerschgorin theorem, that contains all
the eigenvalues of A is given by
5 6
z ∈ C : Λ∗ ≤ |z| ≤ Λ∗ ,

where
Λ∗ := max{r, t} and Λ∗ := min{R, T }.
We define Λ∗ and Λ∗ as the optimal bounds for the eigenvalues of A given by the
Gerschgorin theorem. Note that this is the best possible information that we can
obtain using the Gerschgorin theorem.

Example 7.2.6.
For the matrix  
6 0 2
 −1 −5 0 
−2 2 −3
the Gerschgorin disks can by obtained using (7.22) and are given by

D1 = {z ∈ C : |z−6| ≤ 2}, D2 = {z ∈ C : |z+5| ≤ 1}, D3 = {z ∈ C : |z+3| ≤ 4}.

The annular region corresponding to these disks is

5 6
z ∈ C : 0 ≤ |z| ≤ 8 .

119
S. Baskar and S. Sivaji Ganesh Spring 2022-23
 Section 7.3 Exercises

Similarly, the other annular region is given by

5 6
z ∈ C : 1 ≤ |z| ≤ 9 .

Thus, the smallest annular region, obtained using the Gerschgorin theorem, that
contains all the eigenvalues of A is given by
5 6
z ∈ C : 1 ≤ |z| ≤ 8

and the optimal bounds are Λ∗ = 1 and Λ∗ = 8.

7.3 Exercises
1. The matrix
 
2 0 0

A= 2 1 0
3 0 1

has eigenvalues λ1 = 2, λ = 1 and λ3 = 1 and the corresponding eigenvectors

may be taken as v1 = (1, 2, 3)T , v2 = (0, 1, 2)T and v3 = (0, 2, 1)T . Perform
3 iterations to find the eigenvalue and the corresponding eigen vector to which
the power method converges when we start the iteration with the initial guess
x(0) = (0, 0.5, 0.75)T . Without performing the iteration, find the eigenvalue and
the corresponding eigenvector to which the power method converges when we
start the iteration with the initial guess x(0) = (0.001, 0.5, 0.75)T . Justify your
answer.

2. The matrix  
5.4 0 0

A = −113.0233 −0.5388 −0.6461
−46.0567 −6.4358 −0.9612
has eigenvalues λ1 = 5.4, λ2 = 1.3 and λ3 = −2.8 with corresponding eigenvectors
v1 = (0.2, −4.1, 2.7)T , v2 = (0, 1.3, −3.7)T and v3 = (0, 2.6, 9.1)T . To which
eigenvalue and the corresponding eigenvector does the power method converge if
we start with the initial guess x(0) = (0, 1, 1)? Justify your answer.
3. Use Gerschgorin’s circle theorem to determine the intervals in which the eigen-
values of the matrix  
0.5 0 0.2
A= 0 3.15 −1  .
0.57 0 −7.43

120
S. Baskar and S. Sivaji Ganesh Spring 2022-23
 Section 7.3 Exercises

lie, given that all eigenvalues of A are real. Show that power method can be
applied for this matrix to find the dominant eigenvalue without computing eigen-
values explicitly. Compute the first three iterates of Power method sequences.

4. For this question, we take the matrix

 
−2.7083 −2.6824 0.4543
A =  0.1913 0.7629 0.1007  .
−0.3235 −0.4052 5.0453
Let v 1 , v 2 , v 3 denote eigenvectors corresponding to the eigenvalues λ1 , λ2 , λ3 re-
spectively of the matrix A which are given by λ1 ≈ 5.0187, λ2 ≈ −2.5313, λ3 ≈
0.6125 and v 1 ≈ (0.25, 0.13, 5.02)T , v 2 ≈ (2.53, −0.15, 0.1)T , v 3 ≈ (−0.49, 0.61, 0.02)T .
Answer the following questions:
i) Obtain the Gerschgorin disks associated to the matrix A and pictorially
represent them in the complex plane.
ii) Can Gerschgorin theorem be used to show that the matrix A has a unique
dominant eigenvalue? Justify your answer.
iii) Define the iterative sequences {µk } and x(k) using power method that con-
verge to λ1 and αv 1 for some constant α when the initial guess is x(0) =
(1, 1, 1)T . Perform one iteration.
iv) If we take the initial guess x(0) = (0, 1, 1)T , then show that the iterative
sequence obtained by power method converges to λj and Kv j for some j ∈
{1, 2, 3} and for some constant K. What is the value of j and possible values
of K?
(Hint: x(0) ≈ 0.3060v 1 + 0.1864v 2 + 1.6748v 3 . )
v) Give all possible initial guesses for which the sequence {µk } obtained using
power method converges to λ2 . Justify your answer.
vi) Give all possible initial guesses for which the sequence {µk } obtained using
power method converges to λ3 . Justify your answer.

5. Construct the iterative sequences using inverse power method for the matrix A
given in Exercise 4. Staring with x(0) = (1, 1, 1)T perform five iterations.

6. Using an appropriate shifted inverse power method for the matrix A given in
Exercise 4, construct the sequences {µk } and {x(k) } that converge to λ2 and an
eigenvector of λ2 , respectively. Perform adequate number of iterations to confirm
the convergence numerically.

121
S. Baskar and S. Sivaji Ganesh Spring 2022-23
 Section 7.3 Exercises

7. Use the Gerschgorin Circle theorem to determine bounds for the eigenvalues for
the following matrices. Also find optimum bounds wherever possible. Also draw
the pictures of all the regions given by Greschgorin circles.
   
1 0 0 4 −1 0
 −1 0 1 ,  −1 4 −1  ,
−1 −1 2 −1 −1 4
 
  1 0 −1 1
4.75 2.25 −0.25  
 2.25 4.75  2 2 −1 1 
1.25  ,  .
 0 1 3 −2 
−0.25 1.25 4.75
1 0 1 4

8. Prove that the following two statements concerning n × n matrices are equivalent.
i) Every diagonally dominant matrix is invertible.
ii) Each of the eigenvalues of a matrix A, belongs to at least one Gerschgorin
disk corresponding to A.

9. Prove that the eigenvalues of the matrix

 
6 2 1
 1 −5 0 
2 1 4
satisfy the inequality 1 ≤ |λ| ≤ 9.

10. Show that the imaginary parts of the eigenvalues of

 
3 1/3 2/3
 1 −4 0 
1/2 1/2 −1
all lie in the interval [−1, 1].

11. Let A denote the matrix  

−1 2 1
 2 7 0 
1 0 α
i) Gerschgorin theorem was used to conclude that the matrix A satisfies Hy-
pothesis (H1) of Power method. Find the set of all such values of α ∈ R.
ii) Gerschgorin theorem was used to conclude that the matrix A has distinct
eigenvalues. Find the set of all such values of α ∈ R.

122
S. Baskar and S. Sivaji Ganesh Spring 2022-23