Elementary Matrix Theory

Definition
A matrix A of order (or size) m n is a rectangular array of mn elements
arranged in m rows and n columns. The element in the i th row and j th
column is called the (i, j ) -entry of the matrix and is denoted by aij .
a11 a12 a1n
a a22 a2 n
A [aij ] 21


am1 am 2 amn

An n n matrix is called a square matrix of order n . A matrix of order m 1 is

called a column vector, and one of order 1 n is called a row vector.

Here, consider matrices whose elements are, in general, complex numbers. Two
matrices A and B are equal when their corresponding elements are equal i.e.,
aij bij for all i , j (which implies that A and B are of the same order).

Matrix operations:
Addition: Matrices are added (or subtracted) element-wise:
[aij ] [bij ] [aij bij ] , which is of same order.

A matrix A [aij ] can also be multiplied by a scalar (complex number) k as

kA k[aij ] [kaij ] .

Matrix Multiplication
An m n matrix A can be multiplied with an p q matrix B if and only if
n
n p . Their product is defined as AB aik bkj .
k 1

Example
2 3 2 1 3 4 2 (1) 3 6 14 16
5 7
5 1 7 4 5 (1) 7 6 33 37
1 1

4 6
11 13 11 1 13 4 11 (1) 13 6 63 67
Matrix multiplication is associative, A( BC ) ( AB)C ; and distributive,
A( B C ) AB AC , but not commutative (in general), AB BA . Indeed, the
product BA may not even be defined, as in the case of the matrices in the above
example.

The Identity Matrix

The identity matrix I of order n is defined as the square matrix of order n with
(i, j ) -entry 1 if i j and 0 if i j for all i, j 1,2n .
1 0 0
0 1 0
I


0 0 1

Multiplying any matrix by an identity matrix of appropriate order results in the

same matrix, i.e., if A is any m n matrix, then I m A AI n A . It is easy to
show that the identity matrix I the only matrix with this property. For, suppose
K is another such matrix, then IK K , because of the property of I , and
IK I , because of the property of K , and thus, I K .

Transpose and Trace

The transpose of an m n matrix A [aij ]mn is defined as AT [a ji ]nm .

Example
1 0 9
1 5 1 4 5 3 2

If A 0 3 1 7 , then A
T .
1 1 5
9 2 5 1
4 7 1

Hermitian transpose

The conjugate transpose of A (also called the Hermitian transpose or

transjugate) is matrix A * obtained by replacing every element of AT by its
complex conjugate. Thus, if A [aij ]mn , then A* AT a ji .
nm
Example
2 i 4 3 2i 2i 1 i 6i

If A 1 i 1 3i
5 , then A* 4 1 3i 4 i .

6i 4 i 1 2i 3 2i 5 1 2i

Symmetric, Skew-symmetric, Hermitian matrices

A square matrix A is said to be

Symmetric if A A
T
(i)
Skew-symmetric if A A
T
(ii)
(iii) Hermitian of A A *

Note:The principal or main diagonal of a square matrix A [aij ] of order n

consists of the entries aii for every i 1,2n .

Trace of a matrix

The trace of a square matrix is the sum of all the elements on the main diagonal,
n
and is denoted by trace( A) or tr( A) aii .
i 1

Example
9 1 1
If A 3 2 1 , then tr( A) a11 a22 a33 9 (2) 5 12 .
4 7 5

Properties
1. ( A B)T AT BT and ( A B)* A * B * for all m n matrices A and B .
2. cA cAT and cA* c * A * for all matrices A and scalars c .
T

A * * A for all matrices A .

T
3. AT

4. AB BT AT and AB * B * A * (provided the product AB is defined).

T

5. tr( A B) tr( A) tr( B) for all n n matrices A and B .

6. tr(cA) c tr( A) for all square matrices A and scalars c .

7. tr AT tr( A) and tr A * tr( A) for all square matrices A .
8. tr( AB) tr( BA) (provided the product AB is defined and is a square matrix).
Example
3 1 2 7
Let A and B .
2 5 1 4

7 17 8 37
Then AB and BA .
1 34 11 19

We observe that tr( AB) 7 34 27 and tr( BA) 8 19 27 . Thus, although

the products AB and BA , and indeed, even the main diagonal entries of the
products are different, tr( AB) tr( BA) .

Determinants
For every square matrix A , we can associate a unique real (or complex)
number, called the determinant of A , and denoted by | A | or det( A) , having
certain important properties.

Definition
1. For a 1 1 matrix A [a11 ] , the determinant is defined to be | A | a11 .
2. For an n n matrix A [aij ] (where n 1 ), the determinant is defined as
n
| A | (1) j 1a1 j A(1| j )
j 1

where A(i | j ) denotes the (n 1) (n 1) matrix obtained by deleting the i th

row and j th column of A (the determinant A(i | j ) is itself called the minor
and is denoted by M ij .

Example
1 2
1. Let A .
3 4
1 2
Then | A |
3 4
1 4 2 3
2 .
 1 3 1
2. Let A 1 1 2 .

2 1 2

1 3 1
Then | A | 1 1 2
2 1 2

1 2 1 2 1 1
1 3 1
1 2 2 2 2 1
11 (2) 2 1 3 (1) (2) 2 2 1 11 1 2

4 6 3

1 .

Inverse of a Matrix
For a square matrix A of order n , another matrix B of the same order is said to
be an inverse of A if AB BA I , the identity matrix of order n .

A square matrix that has no inverse is said to be singular, and one that has an
inverse is said to be non-singular or invertible.

Theorem
Every invertible matrix has a unique inverse.

Proof
Let A be an invertible matrix, and suppose B1 and B2 are inverses of A .

Then B2 B2 I (where I is the identity matrix of appropriate order)

B2 ( AB1 ) (as B1 is an inverse of A )

( B2 A) B1 (as matrix multiplication is associative)
IB1 (as B2 is an inverse of A )
B1 .
B2 B1 , i.e., the inverse of A is unique.

The unique inverse of A is denoted by A1 .

Example
1 3 1 4 7 5

If A 1 1 2 , then A 2 4 3 .
1

2 1 2 3 5 4

1 3 1 4 7 5 1 0 0
For, AA 1 1 2 2 4 3 0 1 0 .
1

2 1 2 3 5 4 0 0 1

Properties

1
1. A1 A for all invertible matrices A .

2. AB B 1 A1 for all invertible matrices A and B of the same order.

1

1 T
3. AT A1 for all invertible matrices A .

A square matrix is non-singular if and only if its determinant is non-zero. The

inverse of a non-singular matrix A can be calculated in terms of determinants of
A and its submatrices.

Definition
The cofactor Cij of A corresponding to the (i, j ) -entry is defined as
Cij (1)i j M ij , where M ij is the minor.
The cofactor matrix C of A is the matrix with (i, j ) -entry as the
cofactor Cij , for every i , j .
The adjoint (or adjugate) of A , denoted by adj A is the transpose of the
cofactor matrix C .
The inverse of a non-singular matrix A is given by the formula
1
A1 adj A
| A|

Example
1 0 2
Let A 2 3 1 .
1 2 1
 1 1 1
The cofactor matrix is C 4 1 2 and the determinant is | A | 3 .
6 3 3

1 4 6
Thus, adj A C T 1 1 3 .
1 2 3

1 4 6
1 1 3 .
adj A 1
A1
| A| 3
1 2 3

Special Matrices
A matrix A [aij ] be an n n (real or complex) matrix is said to be
1. diagonal if aij 0 for all i j .
2. tridiagonal if aij 0 for all i , j with | i j | 1 , i.e., all the entries of A are
zero except (possibly) for those on the main diagonal
( a11, a22 ann ), the superdiagonal ( a12 , a23 an1,n ), and the subdiagonal
( a21, a32 an,n1 ).
3. upper-triangular if aij 0 for i j , i.e., all entries below the main
diagonal are zero.
4. lower-triangular if aij 0 for i j , i.e., all entries above the main diagonal
are zero.
5. orthogonal if all its entries are real and AT A1 , i.e., AAT AT A I .
6. unitary if it has complex entries and A* A1 , i.e., AA* A * A I .

Exercises
1. Classify the following matrices as symmetric, skew-symmetric, Hermitian, or
none of these:
1 3
a.
3 4
 ex eix
b. ix
e e x
0 1 1
c. 1 0 1

1 1 0
2 1 i 3
d. 1 i 0 i

3 i 1
0 1 1
e. 1 0 1
1 1 0
1 1 1
f. 1 1 1
1 1 1
2 1 i 3
g. 1 i i i

3 i 1
x 2 9 x 2 2 x 1
2. Find the value of x such that A is
4 2 x 0
a. symmetric
b. skew-symmetric
3. Show that every skew-symmetric matrix A [aij ] of order n has all main
diagonal entries zero, i.e., a11 a22 ann 0 .
4. Show that every Hermitian matrix has only real numbers along the main
diagonal.
5. Find the determinant of the following:
1 1
a.
3 3
0 1 1
b. 1 0 1
1 1 0
 ex eix
c. ix
e e x
cos sin
d.
sin cos
e x e2 x
e. x
e 2e
2x

1 2 2
f. 1 3 0
0 2 1
6. Determine which of the following are invertible and find the inverse:
1 1
a.
3 3
1 1
b.
3 3
0 1 1
c. 1 0 1
1 1 0
0 1 1
d. 1 0 1
1 1 0
cos sin
e.
sin cos
1 x x2

f. 0 1 x
0 0 1

1 a b
g. 0 1 c , where a , b , c are any three complex numbers.

0 0 1
a 0 0
h. 0 b 0

0 0 c
7. Show that the inverse of every 3 3 upper-triangular matrices with non-zero
diagonal entries is also upper triangular.
Hint: If the i th row of A is multiplied by a non-zero constant p , then the i th
column of A1 gets divided by p . Use this property to reduce A to a matrix
of the same form as that in Exercise 6g.
8. Find the inverse of a general n n diagonal matrix with non-zero diagonal
entries.
9. Classify the following matrices as orthogonal, unitary, or neither:
1 0
a.
0 1
0 0 1
b. 0 1 0

1 0 0
1 1
c.
1 0
1 1
d.
1 1
1 1
2 2
e.
1 1
2 2
1 i
2 2
f.

1 i
2 2
cos sin
g.
sin cos

Elementary Row and Column Operations

A matrix is said to be in row-reduced echelon form (or reduced row echelon
form) if it satisfies the following conditions:

1. In each row, the first non-zero entry (called the leading entry) should be1.
2. The leading entry of every row is to the left of the leading entry, if any, of all
rows below it.
Note that zero rows (i.e., rows with all entries 0) are allowed, but the second
condition implies that all zero rows must occur below all non-zero rows (i.e.,
rows with at least one non-zero entry).

Example
Among the matrices given below, A and C are in row-reduced echelon form,
while B and D are not (why?).

1 0 2 1 1 0 2 1
A 0 0 1 4 B 0 0 0 0

0 0 0 0 0 0 1 4

1 2 0 0 1 5 1 2 0 0 1 5
C 0 1 0 4 3 3 D 0 1 0 4 3 3

0 0 0 1 1 2 0 1 0 5 4 1

The following three operations performed on a matrix are called elementary row
operations:
1. Interchange: Interchange any two rows. Ri R j denotes interchanging of
the i th and j th rows
2. Scaling: Multiply every entry of a row by the same non-zero scalar. Ri kRi
denotes multiplying the i th row by the scalar k .
3. Row Addition: Add a multiple of one row of the matrix to another row.
Ri Ri kR j denotes adding k times the j th row, to the i th row.

Note: These definitions are motivated by analogous operations that can be

performed on a given system of linear equations to obtain equivalent systems of
linear equations.

We can use elementary row operations to transform a matrix into its row-
reduced echelon form.

Example
4 8 0 0 4 20
A 3 5 0 4 6 12

2 6 0 9 5 14
 1 2 0 0 1 5 R1 R1 / 4
~ 3 5 0 4 6 12

2 6 0 9 5 14

1 2 0 0 1 5 R2 R2 3R1
~ 0 1 0 4 3 3 R3 R3 2 R1

0 2 0 9 7 4

1 2 0 0 1 5 R3 R3 2 R2
~ 0 1 0 4 3 3

0 0 0 1 1 2

Elementary column operations can also be defined, similar to elementary row

operations. Applying these operations, we can find the analogous column-
reduced echelon form of a matrix.

Example
4 8 0 0 4 20
A 3 5 0 4 6 12

2 6 0 9 5 14

4 0 0 0 0 0 C2 C2 2C1
~ 3 1 0 4 3 3 C5 C5 C1

2 2 0 9 7 4 C6 C6 5C1
4 0 0 0 0 0 C4 C4 4C2
~ 3 1 0 0 0 0 C5 C5 3C2

2 2 0 1 1 2 C6 C6 3C2

4 0 0 0 0 0 C5 C5 C4
~ 3 1 0 0 0 0 C6 C6 2C4

2 2 0 1 0 0
4 0 0 0 0 0 C3 C4
~ 3 1 0 0 0 0

2 2 1 0 0 0
Elementary Matrices
All the elementary row and column operations can be defined in terms of
multiplication by special matrices called elementary matrices.

Definition
An elementary matrix E is a square matrix that generates an elementary
row operation on a matrix A under the multiplication EA .

Example:

0 1 0 1 2 3
Let E 1 0 0 , A 4 5 6 .

0 0 1 7 8 9

0 1 0 1 2 3 4 5 6
EA 1 0 0 4 5 6 1 2 3 .

0 0 1 7 8 9 7 8 9
Thus, left-multiplication by E has the effect of interchanging the first and
second rows of A .

1 2 3 0 1 0 2 1 3
Now, AE 4 5 6 1 0 0 5 4 6 .

7 8 9 0 0 1 8 7 9
Right-multiplication by E , therefore, interchanging the first and second
columns of A .

Construction of Elementary Matrices

An elementary operation E of order n n that performs a specified elementary

row operation is obtained by performing the same operation on the identity
matrix of equal order.
 1 2 3 4
Example: Let A 5 6 7 8 . To construct an elementary matrix, say
9 10 11 12
1 0 0
E1 , that interchanges the first and third rows of A , consider I 0 1 0 . By
0 0 1
0 0 1
interchanging the first and third rows of I , we obtain E1 0 1 0 .
1 0 0

0 0 1 1 2 3 4 9 10 11 12
Then, E1 A 0 1 0 5 6 7 8 5 6 7 8 .
1 0 0 9 10 11 12 1 2 3 4

To construct an elementary matrix E2 that subtracts 5 times the first row of A

from the second row of A , perform the same operation on I :

1 0 0
E2 5 1 0

0 0 1

1 0 0 1 2 3 4 1 2 3 4
Then E2 A 5 1 0 5 6 7 8 0 4 8 12 .

0 0 1 9 10 11 12 9 10 11 12

However, E1 cannot be used for interchanging the first and third columns of A ,
as it is not possible to right-multiply A having order 3 4 by E1 having order
3 3 . Therefore, we need to obtain another elementary matrix, say E3 , from the
identity matrix of order 4 by interchanging the first and third columns (or
equivalently, rows).

0 0 1 0
0 1 0 0
Thus, E3 .
1 0 0 0

0 0 0 1
 0 0 1 0
1 2 3 4 3 2 1 4
1 0 0
Then, AE3 5 6 7 8 7 6 5 8
0
1 0 0 0
9 10 11 12
11 10 9 12
0 0 0 1

Rank and Inverse Using Row Operations

The rank of a matrix is the order of its largest non-singular square submatrix. It
is also possible to define and compute the rank in a different manner.

Definition
The row rank of a matrix is the number of non-zero rows in the echelon
form of that matrix.

1 2 4 2
0 0 1 2
Example: The rank of is 3, since this is in the echelon form of
0 0 0 1

0 0 0 0

the matrix and it contains three rows are non-zero.

The column rank of a matrix is the number of non-zero columns in the
echelon form of that matrix.

2 1 3 1 0 1 R1 R2
1 0 1 2 1 3
Example A ~
0 2 1 0 2 1

1 1 4 1 1 4
1 0 1 R2 R2 2 R1
0 1 1 R R R
~ 4 4 1
0 2 1

0 1 3
 1 0 1 R3 R3 2 R2
0 1 1 R4 R4 R2
~
0 0 1

0 0 4
1 0 1
0 1 1 R2 R2
~
0 0 1 R4 R4 4 R3

0 0 0

As there are three non-zero rows in the row-reduced echelon form of A , the row
rank of A is 3. Now, we find the column rank.
2 1 3
1 0 1
A
0 2 1

1 1 4

1 2 3 C1 C2
0 1 1
~
2 0 1

1 1 4
1 0 0 C2 C2 2C1
0 1 1 C3 C3 3C1
~
2 4 5

1 3 7
1 0 0 C3 C3 C2
0 1 0
~
2 4 1

1 3 4

As there are three non-zero columns in the column-reduced echelon form of A ,

the column rank of A is 3. We see that the row rank and column rank of A are
equal. Indeed, this is true in general, as stated in the following theorem.
Theorem
The row rank of a matrix is the same as the column rank, and the
common value is the rank of the matrix.

Inverse using elementary operations

It is also possible to find the inverse of a non-singular matrix using elementary

row (or column) operations. Consider a square matrix A of order n , and the
identity matrix I of the same order. We define an augmented matrix [ A | I ]
by appending the columns of I to the columns of A , on the right. Then we
reduce A in [ A | I ] to the identity matrix of order n by performing a series of
elementary row operations on the augmented matrix. When A has been reduced
to the identity matrix, I would have been reduced to A1 . If it is not possible to
reduce A to the identity matrix, then its row reduced form contains at least one
zero row, which means that A is singular and hence has no inverse.
1 0 2

Example: Find the inverse of the matrix A = 2 1 3
4 1 8

1 0 2 1 0 0 R1
Solution: [A | I] = 2 1 3 0 1 0 R 2
4 1 8 0 0 1 R 3

1 0 2 1 0 0
[A | I] = 0 1 1 2 1 0
0 1 0 4 0 1

1 0 2 1 0 0
0 1 1 2 1 0
0 0 1 6 1 1

1 0 0 11 2 2
0 1 0 4 0 1
0 0 1 6 1 1
 1 0 0 11 2 2
0 1 0 4 0 1 .
0 0 1 6 1 1

11 2 2
Therefore A-1 = 4 0 1.

6 1 1

4 1 2
Example: Find the inverse of the matrix A = 0 1 0

8 4 5

Solution:

Writing the given matrix side by side with the unit matrix of order 3, we have

4 1 2 1 0 0 R1
[A | I] = 0 1 0 0 1 0 R 2
8 4 5 0 0 1 R 3

R1
Perform the row transformations: R1 and R 3 R 3 2R1
4

1 1 1
1 0 0
4 2 4

[A | I] =
0 1 0 0 1 0


0 2 1 2 0 1

Perform the row transformations: R 3 R 3 2R 2

1 1
1 1 0 0
4 2 4

[A | I] =
0 1 0 0 1 0


0 0 1 2 2 1
 1
Perform the row transformations: R1 R1 R 2
4

1 1 1
1 0 0
2 4 4

[A | I] =
0 1 0 0 1 0


0 0 1 2 2 1

1
Perform the row transformations: R1 R1 R 3
2

5 3 1
1 0 0
4 4 2

[A | I] = = [ I | B]
0 1 0 0 1 0


0 0 1 2 2 1

5 3
1
4 4 2

Hence the inverse of the given matrix is B = A1 = .
0 1 0


2 2 1

Determine the inverse of the following matrices by using elementary row

operations:

1 0 1
1 1 0 2 2
1. A 2 2 1 Ans. A1 1 0 1
2 2
1 1 0 0 1 2

1 0 1
1 1 0 2 2
2. A 1 1 1 Ans. A1 1 0 1
2 2
1 1 0 0 1 1

 1 3 1 4 7 5
3. A 1 1 2 Ans. A1 2 4 3
2 1 2 3 5 4
1 1 1 1 1 1

4. A 1 0 1 Ans. A 1 1 0
1

1 1 0 1 0 1
5 8 1 5 11 6
5. A 0 2 1 Ans A1 4 9 5

4 3 1 8 17 10

Rank of a matrix and solving system of equations

The rank of a matrix A is the maximum number of linearly independent row

vectors (or column vectors) in A. A simple application of rank comes from the
fact that a linear system of equations AX=B has a solution if and only if the rank
of the coefficient matrix A is the same as the rank of the matrix [A|B] where [A|B]
denotes the coefficient matrix augmented by column vector B.
1 2 3 2

The rank of the matrix 0 0 1 2
is 3, since all the three rows are non-zero.
0 0 0 1

0 0 0 0

1 4 2 9
The rank of the matrix 0 1 0 0 is 2, since two rows are non-zero.

0 0 0 0

Problem: Find the rank of the following matrix using elementary row
transformations.

2 1 3 1
A =(4 0 2 6).
0 1 2 2

Solution: Clearly, rank (A) min {3, 4} = 3.

Apply row transformations,

Perform, R2 R2 - 2R1,

2 1 3 1
A (0 2 4 4).
0 1 2 2

R3 R3 + (1/2)R3,

2 1 3 1
A (0 2 4 4).
0 0 0 0

Rank(A) = 2

1 2 3 2
Example: Find the rank of 2 3 5 1 using elementary row transformation.
1 3 4 5 3 4

The rank of A min {3, 4} = 3.

1 2 3 2 R1
A = 2 3 5 1 R 2 [Firstly we use the leading entry in the first row 1 to make the
1 3 4 5 R 3

leading entries in second and third rows to zero].

1 2 3 2
Perform, R 2 R 2 2 R1, then A 0 1 1 3
R 3 R 3 R1 0 1 1 3

1 2 3 2
Perform, R 2 (1) R 2 then A 0 1 1 3
0 1 1 3

1 2 3 2
Perform, R3 R3 R 2 then A 0 1 1 3
0 0 0 0

The above matrix is in the echelon form having two non-zero rows. Hence the rank of A is 2.
 1 2 3
Example: Determine the rank of the matrix (1 4 2).
2 6 5

Solution: Apply R2 R2-R1, R3 R3-2R1

1 2 3
(0 2 1)
0 2 1

1 2 3
Apply R3 R3 - R1 (0 2 1).
0 0 0

Therefore the rank of the matrix is 2.

Exercises

Determine the rank of the following matrices by using elementary row

operations:

1 2 0
1. 1 1 1
Ans. Rank = 2
2 1 1
1 1 0
2. 2 2 1
Ans. Rank = 3
1 1 0
1 1 1 1
3. 1 1 1 2 Ans. Rank = 2
3 1 3 4
1 3 1 1
1 1 2 2
4. Ans. Rank = 4
2 1 2 1

1 2 2 2
1 1 1
5. 1 0 1 Ans. Rank = 3
1 1 0

Linear Equations-Consistency:
Definitions: A system of m linear equations in n unknowns x1, x2, , xn is a set of
equations of the form

a11 x1 + a12 x2 + + a1n xn = b1

a21 x1 + a22 x2 + + a2n xn = b2

... ... _______ (*) say.

... ...

am1 x1 + am2 x2 + ... + amn xn = bm.

The aij are given numbers, which are called the coefficients of the system. The bi are
also given numbers.

If the bi are all zero, then (*) is called a homogeneous system. If at least one bi is not
zero, then (*) is called a non-homogeneous system.

A solution of (*) is a set of numbers x1, x2, .., xn which satisfy all the m equations. If
the system (*) is homogeneous, it has at least one trivial solution x1 = 0, x2 = 0 xn =
0.

From the definition of matrix multiplication, we can write the above system (*) as

AX = B

a11 a12 .... a1n

a
21 a 22 .... a 2n
where A = .... .... .... .... is the coefficient matrix

.... .... .... ....
a m1 a m2 .... a mn
mn

x1 b1
x b
X = 2 and B = 2

n 1 m 1
xn b m

Note that X has n elements where as B has m elements.

 a11 a12 ..... a1 n b1

a 21 a 22 ..... a 2 n b2
The matrix A B or [A:B] = .... .... .... .... ....

.... .... .... .... ....

a m1 a m2 .... a mn bm

is called the augmented matrix. The matrix A B determines the system (*)

completely, since it contains all the given numbers appearing in (*).

Note: The matrix equation AX = B need not always have a solution. It may have no
solution or a unique solution or an infinite number of solutions.

Definition: A system of equations having no solution is called an inconsistent system.

A system of equations having one or more solution is called a consistent system.

Observations: Consider a system of non-homogeneous linear equations AX = B.

i) if rank A rank A B , then system is inconsistent.

ii) if rank A = rank A B = number of unknowns, then system has a unique

solution.
iii) if rank A = rank A B < number of unknowns, then system has an infinite

number of solutions.

Gauss Elimination Method

This is the elementary elimination method and it reduces the system of equations to an
equivalent upper triangular system which can be solved by back substitution. The
method is quite general and is well-adapted for computer operations.

Here we shall explain it by considering a system of three equations for sake of

simplicity.

Consider the equations

a1 x + b1y + c1z = d1
 a2x + b2y + c2z = d2 (i)

a3x + b3y + c3z = d3

Step I: To eliminate x from second and third equations.

a2
We eliminate x from the second equation by subtracting times the first equation
a1
from the second equation. Similarly we eliminate x from the third equation by
a3
eliminating times the first equation from the third equation. We thus, get the
a1
new system

a1 x + b 1 y + c 1 z = d1

b '2 y c'2 z d'2 (ii)

b '3 y c'3 z d'3

Here the first equation is called the pivotal equation and a1 is called the first pivot
element.

Step II: To eliminate y from third equation in (ii).

b '3
We eliminate y from the third equation of (ii) by subtracting times the second

b '2
equation from the third equation. We thus, get the new system

a1 x + b 1 y + c 1 z = d 1

b '2 y c'2 z d'2 ..(iii)

c''3 z d ' 3

Here the second equation is the pivotal equation and b'2 is the new pivot element.

Step III: To evaluate the unknowns

The values of x, y, z are found from the reduced system (iii) by back substitution.

This also can be derived from the augmented matrix of the system (i),

a1 b1 c1 d1
[A|B] = a b2 c2 d 2 (iv)
2
a 3 b3 c3 d1

Using elementary row transformation, reduce the coefficient matrix A to an upper

triangular matrix.

a1 b1 c1 d1
That is., [A|B] ~ 0 b '2 c '2 d'2 ..(v)
0 0 c'3 d ' 3

From (v) the system of linear equations is equivalent to

a1 x + b 1 y + c 1 z = d1

b '2 y c'2 z d'2

c3 ''z d3 ''

By back substitution we get z, y and x constituting the exact solution of the system (i).

Note: The method will fail if one of the pivot elements a1, b '2 or c3 '' vanishes. In
such cases the method can be modified by rearranging the rows so that the pivots are
non-zero. If this is impossible, then the matrix is singular and the equations have no
solution.

Example: Test for consistency and solve:

5x + 3y + 7z = 4, 3x + 26y + 2z = 9, 7x +2y +10z = 5.

5 3 7 4
Solution: We have 3 26 2 9

7 2 10 5
Apply R1 3R1, R2 5R2

15 9 21 12
15 130 10 45

7 2 10 5

Apply R2 R2 - R1

15 9 21 12
0 121 11 33

7 2 10 5

Apply R1 (7/8)R1, R3 5R3, R2 (1/11)R1

35 21 49 28
0 11 1 3

35 10 50 25

Apply R3 R3 R1 + R2, R1 (1/7)R1

5 3 7 4
0 11 1 3

0 0 0 0

Therefore the rank of the coefficient matrix and the augmented matrix both are
2. Hence the equations are consistent. The given system is equivalent to

5x + 3y + 7z = 4, 11y - z = 3.

Therefore x = 7/11, y = 3/11, and z = 0.

Example: Sole by Gauss elimination method 5x - y + z = 10, 2x + 4y = 12, x +y

+5z = -1.

1 1 5 1
Solution: The augmented matrix is 2 4 0 12

5 1 1 10
Apply R2 R2 - 2R1, R3 R3 -5R1

1 1 5 1

0 2 10 14
0 6 24 15

Apply R2 (1/2)R2

1 1 5 1
0 1 5 7

0 6 24 15

Apply R3 R3 + 6R2

1 1 5 1
0 1 5 7

0 0 54 57

Apply R3 (-1/54)R3

1 1 5 1
0 1 5 7

0 0 1 1.0556

Therefore x = 2.556, y = 1.722, z = -1.056

Exercises and Answers

1. Solve the system
x-z-2 = 0

y- z + 2 = 0

x + y - 2z = 0
Answer: Rank (A) = Rank (A:B) = 2 < the number of unknowns = 3. Therefore the
system is consistent, and have infinite number of solutions, which involve n r = 3
2 = 1 constant (s).
Gauss Jordon Method:

Example: Balance the following chemical equation with the help of Gauss
Jordan Method

C2H6 + O2 CO2 + H2O

Solution: We have to find positive integers x, y, z, w such that

(x) C2H6 +(y) O2 (z) CO2 + (w) H2O.
Because the number of atoms of each element must be same on each side of the
above equation, we get
Carbon (C): 2x = z,
Hydrogen (H): 6x = 2w,
Oxygen (O): 2y = 2z + w.
This gives us the system
2x + 0y - z + 0w = 0

6x + 0y + 0z - 2w = 0

0x + 2y - 2z - w = 0

Gauss Jordan elimination gives

1
1 0 0 0
3

0 7
1 0 0
6
2
0 0 1 0
3

 We get x = (1/3)k; y = (7/6)k; z = (2/3)k; w = k. Take k = 6. Thus we get
the balanced chemical equation as follows:
2C2H6 + 7O2 4CO2 + 6H2O.

Example: Using GaussJordan method, find the inverse of the matrix

4 1 2
A = 0 1 0

8 4 5

Solution:
Writing the given matrix side by side with the unit matrix of order 3, we have

4 1 2 1 0 0 R1
[A | I ] = 0 1 0 0 1 0 R2

8 4 5 0 0 1 R3

Perform the row transformations

R
1 1 1 1 0 0 R1 1
4 2 4 4

~ 0 1 0 0 1 0 R2


0 2 1 2 0 1 R3 R3 2 R1

1 1 1 1 0 0
4 2 4 R1

~ 0 1 0 0 1 0 R2


0 0 1 2 2 1 R3 R3 2 R2

1
1 0 1 1 0 R1 R1 1 R2
2 4 4 4

~
0 1 0 0 1 0 R2

0 0 1 2 2 1 R3
 5 3 1 1
1 0 0 R R1 R3
4 4 2 1 2

~ 0 1 0 0 1 0 R2


0 0 1 2 2 1 R3

= [ I | B]
Hence the inverse of the given matrix is
5 3
1
4 4 2
B = A1 =
0 1 0


2 2 1

Example: Solve the following system of equations by Gauss Jordon method.

3x + y + 2z = 3
2x 3y z = 3 . (i)
x + 2y + z = 4

The system (i) can be written as AX = B

3 1 2 x 3
where A = 2 3 1 , X y and B 3

1 2 1 z 4

Now AX = B X = A1 B .. (ii)
Writing the given matrix side by side with the unit matrix of order 3, we have

3 1 2 1 0 0 R1
[A | I] = 2 3 1 0 1 0 R 2
1 2 1 0 0 1 R 3

Continue row transformations (please refer the earlier lesson for inverse
computation), we obtain
 1 3 5

8 8 8

A1 =
3 1 7
8 8 8

7 5 11

8 8 8

Equation (ii) becomes

1 3 5
8 8 8
x 3
y 3 1 7 3
8 8 8
z 7 4

5

11
8 8 8

3 9 20
8 8 8
1
= 9 3 28
2
8 8 8
1
21 15 44

8 8 8

x 1
y 2

z 1
3 1 3 1

This implies that x = 1, y = 2, z = 1.

ITERATIVE METHODS:
We shall now describe the iterative or indirect methods, which start from an approximation to
the true solution and if convergent, derive a sequence of closer approximations the cycle of
computations being repeated till the required accuracy is obtained. This means that in a direct
method the amount of computation is fixed, while in an iterative method the amount of
computation depends on the accuracy required. In the case of matrices with a large number of
zero elements, it will be advantageous to use iterative methods which preserve these
elements.

Jacobis Method:
Let the system be given by
 a11 x1 a12 x2 a13 x3 ... a1n xn b1

a21 x1 a22 x2 a23 x3 ... a2 n xn b2
a31 x1 a32 x2 a33 x3 ... a3n xn b1

.
.

a n1x 2 +a n2 x 2 +a n3 x 3 +...+a nn x n = b n

In which the diagonal elements aii do not vanish. If this is not the case, then the equations
should be rearranged so that this condition is satisfied. Now, we rewrite the system above as
b1 a12 a a
x1 x2 13 x3 ... 1n xn
a11 a11 a11 a11
b2 a21 a a
x2 x1 23 x2 ... 2 n xn
a22 a22 a22 a22
.
.
bn an1 a a
xn x1 n 2 x2 ... n , n 1 xn 1
ann ann ann ann

Let x1(0) , x2(0) ,....., xn(0) be the initial approximation to the solution.

If x1( k ) , x2( k ) ,....., xn( k ) denotes the approximation to the solution at kth iteration, then the solution
at (k +1)th iteration is given by
b1 a12 ( k ) a13 ( k ) a
x1( k 1) x2 x3 ... 1n xn ( k )
a11 a11 a11 a11
b2 a21 ( k ) a23 ( k ) a
x2( k 1) x1 x2 ... 2 n xn ( k )
a22 a22 a22 a22
.
.
bn an1 ( k ) an 2 ( k ) a
xn ( k 1) x1 x2 ... n ,n 1 xn 1( k )
ann ann ann ann

This method is due to Jacobi and is called the method of simultaneous displacements.
Gauss Seidel Method:
In Jacobis method, to obtain the values at the (k+1)th iteration, only kthiteration values are
used. A simple modification to the above method sometimes yields faster convergence and
isdescribed below.
Here, along with the kth iteration values, all available (k + 1)thiteration values are used. It is
clear, therefore, that this method uses an improved component as soon as it is available and it
is called the method of successive displacements, or the Gauss Seidel method.
The Jacobi and Gauss Seidel methods converge, for any choice of the first approximation
xj(0) (j= 1, 2, , n), if every equation of the system satisfies the condition that sum of the
absolute values of the coefficients aij/aii is almost equal to, or in at least one equation less than
unity, i.e. provided that
n

j = 1, j1
a ij / a ii 1, i =1, 2,..., n

where the < sign should be valid in the case of at least one equation. A matrix A
satisfying the above condition is known as a diagonally dominant matrix. It can be shown
that the Gauss Seidel method converges twice as fast as the Jacobi method. The working of
the methods is illustrated in the following examples.

Example: We consider the equations.

3x + 20y z = 18
2x 3y + 20z = 25
20x + y 2z = 17
After partial pivoting we can rewrite the system as follows:
20 x + y 2z = 17
3x + 20 yz = 18 (1)
2x 3y + 20 z =25
Solve for x, y, z respectively
1
x = 17 y 2z
20

1
y = 18 3x z (2)
20

1
z = 25 2x 3y
20

we start from an initial approximation

x = x (0) = 0, y = y (0) = 0, z = z(0) = 0.
Substituting these on the right hand sides of the equations (2), we get
 17
x = x (1) = = 0.85
20

18
y = y (1) = = 0.9
20

25
z = z(1) = = 1.25,
20

where (x(1), y(1), z(1)) = (0.85, 0.9, 1.25) are the first approximated values.
Putting these values on the right hand sides of the equations (2) we obtain
x = x (2) = 1 [17 (0.9) + 2 1.25] = 1.0200
20

y = y(2) = 1 [ 18 3 0.85 + 1.25] = 0.965

20

z = z(2) = 1 [ 25 2 0.85 + 3 (0.9)]= 1.1515

20

The second approximated values of x, y, z are

(x(2), y(2), z(2)) = (1.0200, 0.965, 1.515).
Substituting these values on the right hand sides of the equations (2), we have
x = x(3) = 1.0134

y = y(3) = 0.9954

z = z(3) = 1.0032

Continuing this process, we get

The values in the 5th and 6th iterations being practically the same, we can stop
the iterations. Hence the solution is

Iteration number (n) Variables

x y z
3 1.0134 -0.9954 1.0032
4 1.0009 -1.0018 0.9993
5 1.000 -1.0002 0.9996
6 1.0000 -1.0000 1.0000
Therefore x = 1, y = 1, z = 1.

Example: Find the solution to the following system of equations

83x + 11y 4z = 95
7x + 52y + 13z = 104
3x + 8y + 29z = 71
using Jacobis iterative method for the first five iterations.
Solution: The given system is diagonally dominant.
Rewrite the given system as
95 11 4
x y z
83 83 83
104 7 13
y x z ..........(1)
52 52 52
71 3 8
z x y
29 29 29

Take the initial approximation vector as x = x (0) = 0, y = y (0)

= 0, z =
z(0) = 0.
Then the first approximation is
x (1) 1.1446

y 2.0000
(1)
.........(2)
(1)

z 2.4483

Now using equation (1), the second approximation is computed from the
equations as

x (2) = 1.1446 - 0.1325y(1) + 0.0482z (1)

y(2) = 2.0 - 0.1346x (1) + 0.25z (1)
...............(3)
z(2) = 2.4483 - 0.1035x (1) - 0.2759z (1)

Substituting equation (2) into equation (3), we get the second approximation as
 x (2) 0.9976

y 1.2339
(2)
.........(4)
(2)

z 1.7424

Proceed in a similar way, we get the third, fourth and fifth approximations to the
required solution and they are tabulated as below.

Iteration number (n) Variables

x y z
1 1.1446 2.0000 2.4483
2 0.9976 1.2339 1.7424
3 1.0651 1.4301 2.0046
4 1.0517 1.3555 1.9435
5 1.0587 1.3726 1.9665

Example: Apply Gauss Seidal iteration method to solve the equations

3x1 + 20x2 x3 = 18
2x1 3x2 +20x3 = 25
20x1 + x2 2x3 =17
We write the equations in the form (after partial pivoting),
20x1 + x2 2x3 = 17
3x1 + 20x2 x3 = 18
20x1 x2 + 2x3 = 17
1
and x1 = [17 x2 + 2x3 ] (i)
20
1
x2 = [18 3x1 + x3 ] (ii)
20
1
x3 = [25 2x1 + 3x2 ] (iii)
20

Initial approximation: x1 x1(0) 0 , x 2 x (0)

2 0 , x3 x3 0 .
(0)
First iteration:

Taking x 2 x (0)
2 0 , x 3 x 3 0 in (i), we get x1 = 0.85
(0) (1)

Taking x1 x1(1) 0.85, x3 x3(0) 0 in (ii), we have

1
2
x (1) [18 3 0.85 + 0 ] = 1.0275
20

2 1.0275 in (iii), we obtain

Taking x1 x1(1) 0.85, x 2 x (1)

1
x 3(1) [ 25 2 0.85 + 3 (1.0275)] = 1.0109
20

Therefore x1(1) 0.85, x (1)

2 1.0275, x 3 1.0109 .
(1)

Second iteration:
1
x1(2) [17 3 (1.0275) + 2 1.0109] = 1.0025
20

1
2
x (2) [18 3 (1.0025) + 1.0109] = 0.9998
20

1
x 3(2) [25 2 1.0025 + 3 (0.9998)] = 0.9998
20

2 1.0000 , x 3 1.0000
(3)
Similarly in third iteration, we get x1(3) 1.0000 , x (3)
The values in the 2nd and 3rd iterations being practically the same, we can stop
the iterations. Hence the solution is x1 = 1, x2 = 1, x3 = 1
Example: Find the solution of the following system of equations
1 1 1
x y z
4 4 2
1 1 1
xy w
4 4 2
1 1 1
xz w
4 4 2
1 1 1
y zw
4 4 2
using Gauss-Seidel method and perform the first five iterations.
Solution: The given system of equations can be rewritten as
x = 0.5 + 0.25y + 0.25z
y = 0.5 + 0.25x + 0.25w ... (1)
z = 0.25 + 0.25x + 0.25w
w = 0.25 + 0.25y + 0.25z
Taking the initial approximation as y = z = 0 on the right side of the equation
(1) we get x(1) = 0.5.
Taking z = 0 and w = 0 and the current value of x, we get
y(1) = 0.5 + (0.25)(0.5) + 0 = 0.625 from the second equation of (1).
Now taking w = 0 and the current value of x, we get
z(3) = 0.25 + (0.25) (0.5) + 0 = 0.375 from the third equation of (1).
Lastly, using the current values of y and z, the fourth equation of (1) gives
w(1) = 0.25 + (0.25)(0.625) + (0.25)(0.375) = 0.5.
The Gauss-Seidal iterations for the given set of equations can be written as
x(r+1) = 0.5 + 0.25y(r) + 0.25z(r)
y(r+1) = 0.5 + 0.25x(r+1) + 0.25w(r) ... (1)
z(r+1) = 0.25 + 0.25x(r+1) + 0.25w(r)
w(r+1) = 0.25 + 0.25y(r+1) + 0.25z(r+1)
Now, by Gauss-Seidel procedure, the second and the subsequent
approximations can be obtained and the sequence of the first five
approximations is tabulated below.
Iteration number (n) Variables
x y z w
1 0.5 0.625 0.375 0.5
2 0.75 0.8125 0.5625 0.59375
3 0.84375 0.85938 0.60938 0.61719
4 0.86719 0.87110 0.62110 0.62305
5 0.87305 0.87402 0.62402 0.62451
Eigenvalues and Eigenvectors

Introduction

A problem which arises frequently in applications of linear algebra and matrix

theory is that of finding the values of scalar parameter for which there exists
vectors x 0 satisfying

Ax x (1)

where A is any square matrix of order n . Such a problem is called as an

Eigenvalue problem or Characteristic value problem. If x 0 satisfies (1) for a
given , then A operating on x yields a scalar multiple of x .

Clearly, x 0 is one solution of (1) for any . But we are looking for vectors
x 0 which satisfy (1).

Ax x ( A I ) x 0

Where I is the nth order identity matrix. The determinant of this matrix ( A I )
equated to zero,

a11 a12 .... a1n

a21 a22 .... a2 n
i.e, A I 0 (2)
.... .... .... ....
an1 an 2 .... ann

is called as the characteristic equation of the matrix A . On expanding the

determinant, the characteristic equation takes the form

(1)n n k1 n1 k2 n2 ..... kn 0 (3)

Where the ki s are expressible in terms of the elements aij of the matrix A .

The roots of the characteristic equation of A are called as the Eigenvalues or

latent roots or the characteristic roots of the matrix A .

The vectors x 0 which satisfy (1) are called the Eigenvectors or latent vectors
of A . The determinant A I , which is a polynomial in , is called as the
characteristic polynomial of A .

The matrix equation (2) represents n homogenous linear equations

 (a11 ) x1 a12 x2 ..... a1n xn 0
a21 x1 (a22 ) x2 ..... a2 n xn 0
(4)
.... .... .... ....
an1 x1 an 2 x2 ..... (ann ) xn 0

Which will have a non-trivial solution if and only if the coefficient matrix is
singular, i.e, if A I 0 .

The characteristic equation of A has n roots (need not be distinct) and

corresponding to each root, the equation (4) will have a non-zero solution,
which is the eigenvector or latent vector.

5 4
Example: Find the eigenvalues and eigenvectors of A = .
1 2

Solution: The characteristic equation is A I 0

5 4
i.e, 0 or 2 7 6 0
1 2

or ( 6)( 1) 0

6,1

If x [ x1 x2 ] is an eigenvector corresponding to the eigenvalue , then

5 4 x1
( A I )x 0.
1 2 x2

1 4 x1
Corresponding to 6 , we have 0 which gives only one
1 4 x2
dependent equation x1 4 x2 0 .

x1 x2
giving the eigenvector (4,1) .
4 1

4 4 x
Corresponding to 1 , we have
1
0 which gives only one dependent
1 1 x2
equation x1 x2 0 .
 x1 x2
giving the eigenvector (1, 1) .
1 1

Example 3: Find all eigen values and the corresponding eigen vectors of the
matrix
8 6 2
A = 6 7 4
2 4 3

0 0
The characteristic equation of A is A I = 0 where I =
0 0 .
0 0

8 6 2
That is, 6 7 4 = 0.
2 4 3

Expanding we get
(8 ) [(7) (3) 16] + 6 [6 (3) + 8] + 2 [24 2 (7) ] = 0

3 + 18 2 45 = 0

That is, 3 18 2 + 45 = 0, on simplification.

( 3) ( 15) = 0

Therefore = 0, 3, 15 are the eigen values of A.

If x, y, z be the components of an eigen vector corresponding to the eigen value

, then we have

8 6 2 x 0
(A I) X = 6 7 4
y 0 .

2 4 3 z 0

That is, (8 ) x 6y + 2z = 0
6x + (7)y 4z = 0
2x 4y + (3 )z = 0
Case I: Let = 0 we have
8x 6y + 2z = 0 (i)
6x + 7y 4z = 0 (ii)
2x 4y + 3z = 0 (iii)

Applying the rule of cross multiplication for (i) and (ii)

x y z
=
6 2 8 2 8 6
7 4 6 4 6 7

x y z

24 14 32 12 56 36
x y z x y z
or
10 20 20 1 2 2

Therefore (x, y, z) are proportional to (1, 2, 2) and we can write x = 1k, y = 2k,
z = 2k where k ( 0) is an arbitrary constant. However it is enough to keep the
values of (x, y, z) in the simplest form x = 1, y = 2, z = 2 (putting k = 1). These
values satisfy all the equations simultaneously.

1

Thus the eigen vector X1 corresponding to the eigen value = 0 is 2 .

2

Case II: Let = 3 and the corresponding equations are

5x 6y + 2z = 0 (iv)
6x + 4y 4z = 0 (v)
2x 4y 1z = 0 (vi)

From (iv) and (v) we have

x y z

6 2 5 2 5 6
4 4 6 4 6 4

x y z
That is,
16 8 16
 x y z
That is,
2 1 2

2
Thus X2 = 1 is the eigen vector corresponding to = 3.
2

Case III: Let = 15 and the associated equations are

7x 6y + 2z = 0 (vii)

6x 8y 4z = 0 (viii)

2x 4y 12z = 0 (ix)

From (vii) and (viii) we have

x y z

40 40 20

x y z
That is,
2 2 1

2
Thus X3 = 2 is the eigen vector corresponding to = 15.
1

1 2 2
Therefore = 0, 3, 15 are the eigen values of A and 2 ,
1 and 2 are
2 2 1

the corresponding eigen vectors.

Example: Find the eigen values and eigen vectors of the matrix A =

3 1 -1
2 2 -1

2 2 0

Solution: The characteristic equation is A I = 0

 3 1 1 0 0
2 2 1 0 0 0 = 0

2 2 0 0 0

3 1 1
2 2 1 = 0
2 2

3 52 + 8 4 = 0.

= 1, 2, 2

Thus the characteristic values are 1 and 2.

Part (ii): Suppose the characteristic vector corresponding to the characteristic

value 1 is . Then (A I) = 0

3 1 1 1 0 0 1

2 2 1 0 1 0 2 = 0

2 2 0 0 0 1
3

2 1 1 1 0
2 1 1 2 = 0 .

2 2 1 3 0

The set of equations is given below

21 + 2 - 3 = 0 ..(i)

21 + 2 - 3 = 0 ...(ii)

21 + 22 - 3 = 0 ..(iii)

Use (i) and (iii).

21 + 22 - 3 = 0 .(iii)
21 + 2 - 3 = 0 ..(i)

------------------------
2 = 0
-----------------------

Thus 2 = 0. Substituting this in (i), we get 21 + 2 - 3 = 0 ..(i))

21 - 3 = 0

1 = 3.
1 2

If 1 = 1, then we get

1 = 1, 2 = 0, 3 = 2.

= (1, 2, 3) = (1, 0, 2)

1
= 0 is the characteristic vector corresponding to the characteristic value1.

2

Part (iii): Suppose a characteristic vector corresponding to the characteristic

value 2 is . Then (A 2I) = 0

3 1 1 2 0 0 1

2 2 1 0 2 0 2 = 0

2 2 0 0 0 2
3

1 1 1 1 0
2 0 1 2 = 0

2 2 2 3 0

The related system of equations is

1 + 2 - 3 = 0 ..(i)
 21 - 3 = 0 .(ii)

3 = 21

21 + 22 23 = 0 .(iii)

(or 1 + 2 - 3 = 0) 3 = 1 + 2

Now we use (i) and (ii).

Now 21 = 1 + 2 1 = 2.

So 1 = 2 and 3 = 21

If 1 = 1, then 2 = 1 and 3 = 2.

1
Thus = 1 is a characteristic vector corresponding to the characteristic value

2

2.

Example: Find all the eigen roots and the eigen vector corresponding to the
6 2 2
least eigen root of the matrix A = 2 3 1 .
2 1 3

Solution: The characteristic equation of A is A I = 0.

6 2 2
This implies 2 3 1 0.
2 1 3

Expanding we obtain, 3-12 2 + 36 -32 = 0. (1)

By inspection, = 2 is a root. Then ( - 2) is a factor of the (1).
Therefore dividing equation (1) with ( - 2). We get that 2 -10 + 16 = 0.
This means ( -2)( - 8) = 0. Therefore the eigen values are = 2, 2, 8.
We find the eigen vector corresponding the eigen value = 2.
When = 2, the set of equations are
4x -2y + 2z = 0
-2x + y - z = 0
2x- y + z = 0
The above set of equations represents a single independent equation, 2x - y + z
= 0 and hence we can choose two variables z = k1 and y = k2.
k 2 k1
x 2

Therefore X1 = y = k 2 is the eigen vector corresponding to = 2 where
z k
1

k1, k2 are not simultaneously equal to zero.

Problems

Find the eigenvalues and eigenvectors of the matrices:

2 1 1 2 0 1
a) 1 1 2 b) 0 2 0

1 2 1 1 0 2

Properties of Eigenvalues

1. Any square matrix A and its transpose A ' have the same eigenvalues.

2. The eigenvalues of a triangular matrix are just the diagonal elements of the
matrix.

3. The eigenvalues of an idempotent matrix are either zero or unity.

4. The sum of the eigenvalues of a matrix is the sum of the elements of the
principal diagonal.

5. The product of the eigenvalues of a matrix A is equal to its determinant.

1
6. If is an eigenvalue of a matrix A , then is the eigenvalue of A1 .

1
7. If is an eigenvalue of an orthogonal matrix, then is also its eigenvalue.

8. If 1, 2 ,....n are the eigenvalues of a matrix A , then Am has the eigenvalues
1m , 2m ,.....n m where m is a positive integer.

Cayley-Hamilton Theorem

Every square matrix satisfies its own characteristic equation.

i.e if the characteristic equation for the nth order square matrix A is

A I (1)n n k1 n1 k2 n2 ..... kn 0 , then

(1)n An k1 An1 k2 An2 ..... kn I 0 . (5)

Multilying (5) by A1 , we get (1)n An1 k1 An2 ..... kn1I kn A1 0 .

1
A1 (1)n An1 k1 An2 .... kn 1I .
kn

This result gives the inverse of A in terms of n 1 powers of A and is

considered as a practical method for the computation of the inverse of the large
matrices.

From the above example, since 3 182 + 45 = 0 is the characteristic equation

8 6 2
of the matrix A = 6 7 4 we have by Cayley-Hamilton Theorem,

2 4 3
A3 18A2 + 45A = O where O is the null matrix of order 3.

Inverse of a square matrix: (using Cayley Hamilton theorem):

If A is a square matrix of order 3 (for convenience) then its characteristic

equation | A I | = 0 can be put in the form 3 + k1 2 + k2 + k3 = 0.

Then by Cayley Hamilton theorem, we have

A3 + k1 A2 + k2 A + k3 I = O

Post multiplying by A1, we have

A2 + k1 A + k2 I + k3 A1 = O, since A1A = I, IA = A
 1
Therefore A1 = [ A2 + k1 A + k2 I ].
k3

Example: Apply Cayley-Hamilton theorem compute the inverse of the matrix

0 1 2
A = 1 2 3 and verify the answer.
3 1 1

Solution: The characteristic equation of A is | A I | = 0.

0 1 2
That is, 1 2 3 0 ..(1)
3 1 1

On expanding, we get 3 32 -8 + 2 = 0.
Applying Cayley-Hamilton theorem, A3 3A2 -8A + 2I = O.
Post multiplying with A-1 we have,
1 2
A2-3A-8I +2A-1 = O. This implies A-1 = (A 3A 8I) (2)
2

0 1 2 0 1 2 7 4 5
Now A = AA = 1 2 3 1 2 3 = 11 8 11
2
3 1 1 3 1 1 4 6 10

Thus (ii), becomes

7 4 5 0 3 6 8 0 0
1
11 8 11 3 6 9 0 8 0 .
2
4 6 10 9 3 3 0 0 8

Therefore
1 1 1
1
A = 8 6 2 .
-1
2
5 3 1

It can be verified that AA-1 = I.

Example: Verify Cayley Hamilton theorem and compute the inverse of the
matrix
 1 1 1
A = 3 2 3
1 1 2

The characteristic equation of A is | A I | = 0. Therefore

1 1 1
A I 3 2 3 = 0
1 1 2

Therefore 3 52 + + 1 = 0, is the characteristic equation of A.

We have to show that A3 5A2 + A + I = O (replacing by A).

1 1 1 1 1 1 5 4 6
A = A. A = 3 2 3 3 2 3 12 10 15
2
1 1 2 1 1 2 6 5 8

1 1 1 5 4 6 23 19 29
3
A = A.A = 2 3 2 3 12 10 15 57 47 72

1 1 2 6 5 8 29 24 37

L.H.S. of A3 5 A2 + A + I becomes,

23 19 27 5 4 6 1 1 1 1 0 0
57 47 72 5 12 10 15 3 2 3 0 1 0

29 24 37 6 5 8 1 1 2 0 0 1

23 25 1 1 19 20 1 0 29 30 1 0
= 57 60 3 0 47 50 2 1 72 75 3 0
29 30 1 0 24 25 1 0 37 40 2 1

0 0 0
= 0 0 0 = O
0 0 0

Therefore A3 5A2 + A + I = 0
Hence Cayley Hamilton theorem is verified.
To find the inverse of A
We have A3 5A2 + A + I = O. Post multiplying by A1 we have
A2 5A + I + A1 = O
Therefore A1 = A2 + 5A I

5 4 6 1 1 1 1 0 0 1 1 1
A 1
= 12 10 15 5 3 2 3 0 1 0

A 1
= 3 1 0
6 5 8 1 1 2 0 0 1 1 0 1

1 2
Example: Using Cayley-Hamilton theorem, find A8 , if A .
2 1

1 2
Solution: The characteristic equation of A is given by 0 or
2 1
2 5 0 .

A8 ( A2 )4 ( A2 5I 5I )4
( A2 5I )4 4( A2 5I )3 5I 6( A2 5I )2 (5I ) 2 4( A2 5I )(5I )3 (5I ) 4

By Cayley-Hamilton theorem, A2 5I 0 .

A8 (5I )4 625I .

2 2 1
Example: If A 1 3 1 , then find the eigenvalues of A1 and hence, find its
1 2 2
determinant.

Solution: The eigenvalues of A are given by the roots of its characteristic

equation, i.e A I 3 7 2 11 5 0 .

5,1,1 .

1
If is an eigenvalue of A , then is an eigenvalue of A1 .

1
Therefore, the eigenvalues of A1 are ,1,1 .
5
 1
A1 .
5

Problems:

1. Verify Cayley-Hamilton theorem for the following matrices and find its
2 1 1 7 2 2 3 2 4
inverse: a) 1 2 1 b) 6 1 2 c) 4 3 2

1 1 2 6 2 1 2 4 3

2 1 2
2. If A 1 2 1 , find A4 .
1 1 2

2 3 4
3. Find the eigenvalues of A 2 A I where A 0 4 2 .
2

0 0 3

Iterative method to obtain largest eigenvalue of a matrix

(Rayleigh Power method)

Consider the matrix equation Ax x which gives the following homogenous

system of equations
(a11 ) x1 a12 x2 ..... a1n xn 0
a21 x1 (a22 ) x2 ..... a2 n xn 0
.... .... .... ....
an1 x1 an 2 x2 ..... (ann ) xn 0

In many applications, it is required to compute numerically the largest

eigenvalue and the corresponding eigenvector.

We start with a column vector x which is as near the solution as possible and
evaluate Ax , which is written as (1) x(1) after normalisation, that is, we obtain
(1) from Ax which is largest in magnitude. Hence, the resulting vector x (1) will
have largest component unity. This gives the first approximation (1) to the
largest eigenvalue and x (1) to the eigenvector. Similarly, we evaluate
Ax(1) (2) x(2) which gives the second approximation. We repeat this process till
x(r) x( r 1) becomes negligible. Then, ( r ) will be the largest eigenvalue of A and
x ( r ) , the corresponding eigenvector.
This iterative method to find the dominant eigenvalue of a matrix is known as
Rayleighs power method.

For the initial approximation, we can take the vector x [1 0 0]' , if it is not
explicitly provided.

Note: To find the smallest eigenvalue of A , apply the Rayleighs power method
1
to A1 and obtain its largest eigenvalue. Since is an eigenvalue of A1 if is

an eigenvalue of A , the resultant largest eigenvalue of A1 is the smallest
eigenvalue of A .

Example: Determine the largest eigen value and the corresponding eigen vector
2 0 1
of the matrix A = 0 2 0 by power method taking the initial vector as [1, 1,
1 0 2

1]t.
1
(0) t
Solution: Given X = (1, 1, 1) = 1 is the initial eigen vector
1

2 0 1 1 2 1
AX (0)
= 0 2 0 0 0 2 0 = (1) X(1)

1 0 2 0 1 0.5

2
( Since 2 is the largest value in 0 )
1

2 0 1 1 2.5 1
AX (1)
= 0 2 0 0 0 2 5 0 = (2) X(2)

1 0 2 0.5 2 0.8

2 0 1 1 2.8 1
AX (2)
= 0 2 0 0 0 2 8 0 = (3) X(3)

1 0 2 0.8 2.6 0.93

 2 0 1 1 2.93 1
AX (3)
= 0 2 0 0 0 2 93 0 = (4) X(4)

1 0 2 0.93 2.86 0.98

2 0 1 1 2.98 1
AX(4) = 0 2 0 0 0 2 98 0 = (5) X(5)

1 0 2 0.98 2.96 0.99

2 0 1 1 2.99 1
AX (5)
= 0 2 0 0 0 2.99 0 = (6) X(6)

1 0 2 0.99 2.98 0.997

2 0 1 1 2.997 1
AX (6)
= 0 2 0 0 0 2.997 0 = (7) X(7).

1 0 2 0.997 2.994 0.999

Therefore we can conclude that the largest eigen value is approximately 3 and

the corresponding eigen vector is (1, 0, 1)t.

Example: Determine the largest eigen value and the corresponding eigen vector
6 2 2
of the matrix A = 2 3 1 by power method taking the initial vector as
2 1 3

[1, 1, 1]t.
1
(0) t
Solution: Given X = (1, 1, 1) = 1 is the initial eigen vector
1

6 2 2 1 6 1
AX (0)
= 2 3 1 1 0 6
0 = (1) X(1)

2 1 3 1 4 0.67

6
( Since 6 is the largest value in 0 )
4

 6 2 2 1 7.34 1.0
AX (1)
= 2 3 1 0 2.67 7.34 0.36 = (2) X(2)

2 1 3 0.67 4.01 0.55

6 2 2 1 7.82 1.0
AX (2)
= 2 3 1 0.36 3.63 7.82 0.46 = (3) X(3)

2 1 3 0.55 4.01 0.51

6 2 2 1 7.94 1.0
AX (3)
= 2 3 1 0.45 3.89 7.94 0.69 = (4) X(4)

2 1 3 0.51 4.01 0.51

6 2 2 1 7.98 1
AX (4)
= 2 3 1 0.49 3.97 7.98 0.5 = (5) X(5)

2 1 3 0.51 3.99 0.5

6 2 2 1 8 1
AX (5)
= 2 3 1 0.5 4 8 0.5 = (6) X(6).

2 1 3 0.5 4 0.5

Therefore the largest eigen value is = (6) = 8 and the corresponding eigen

vector X = X(6) = (1, 0.5, 0.5)t.

Problems:

1. Find the largest eigenvalue and the corresponding eigenvector of the matrix
1 3 2
4 4 1 using the initial approximation 1 0 0 ' . Carry out 4 iterations.

6 3 5

2. Find the dominant eigenvalue and the corresponding eigenvector of the

6 2 2
matrix 2 3 1 . Take an appropriate initial approximation and carry out 4
2 1 3
iterations.