Gebali F. Analysis Of Computer And Communication Networks
Подождите немного. Документ загружается.
616 D Vectors and Matrices
D.7 Matrix Addition
If A is an m ×n matrix and B is an m ×n matrix, then we can add them to produce
an m × n matrix C
C = A +B (D.14)
where the elements of C are given by
c
ij
= a
ij
+b
ij
(D.15)
with 1 ≤ i ≤ m and 1 ≤ j ≤ n.
D.8 Matrix Multiplication
If A is an l × m matrix and B is an m × n matrix, then we can multiply them to
produce an l × n matrix C
C = AB (D.16)
where the elements of C are given by
c
ij
=
m
k=1
a
ik
b
kj
(D.17)
with 1 ≤ i ≤ l and 1 ≤ j ≤ n.
D.9 Inverse of a Matrix
Given the matrix A, its left inverse is defined by the equation
LA = I (D.18)
The right inverse is defined by the equation
AR = I (D.19)
When A is square, the left and the right inverses are equal and we denote the
inverse as A
−1
, which satisfies the equations
AA
−1
= A
−1
A = I (D.20)
D.10 Null Space of a Matrix 617
The inverse of the matrix is found by treating the above equation as a system
of simultaneous equations in the unknown matrix A
−1
. The matrix A
−1
is first
written as
A
−1
=
a
1
a
2
··· a
n
(D.21)
where n is the dimension of A.Theith column a
i
of A
−1
is treated as an unknown
vector that is to be found from the equation
Aa
i
=
0 ··· 010··· 0
t
(D.22)
where the vector on the RHS has 1 in the ith location. Gauss elimination is a useful
technique for finding the inverse of the matrix.
Not all matrices have inverses. A square matrix has an inverse only if its rank
equals the number of rows (rank is explained Section D.11).
D.10 Null Space of a Matrix
Given an m ×n matrix A, a nonzero n-vector x is said to be a null vector for A when
Ax = 0 (D.23)
All possible solutions of the above equation form the null space of A, which we
denote by null
(
A
)
.Ifn is the number of all possible and independent solutions, then
we have
n = null
(
A
)
(D.24)
Finding the null vectors x is done by solving (D.23) as a system of homogeneous
linear equations.
MATLAB offers the function null to find all the null vectors of a given ma-
trix. The function null(A) produces the null space basis vectors. The function
null(A,’r’) produces the null vectors in rational format for presentation pur-
poses. For example
A =
⎡
⎣
123
123
123
⎤
⎦
null(A,
r
) =
⎡
⎣
−2 −3
10
01
⎤
⎦
618 D Vectors and Matrices
D.11 The Rank of a Matrix
The maximum number of linearly independent rows or columns of a matrix A is the
rank of the matrix. This number r is denoted by
r = rank
(
A
)
(D.25)
A matrix has only one rank regardless of the number of rows or columns. An
m × n matrix (where m ≤ n)issaidtobefull rank when rank(A) = m.
The rank r of the matrix equals the number of pivots of the matrix when it is
transformed to its echelon form (see Section D.19.3 for definition of echelon form).
D.12 Eigenvalues and Eigenvectors
Eigenvalues and eigenvectors apply only to square matrices. Consider the special
situation when we have
Ax = x (D.26)
The number is called the eigenvalue and x is called the eigenvector.Math
packages help us find all possible eigenvalues and the corresponding eigenvectors
of a given matrix.
We can combine all the eigenvectors into the eigenvector matrix X whose
columns are the eigenvectors and we could write
AX= XD (D.27)
where
X =
x
1
x
2
··· x
n
(D.28)
D =
⎡
⎢
⎢
⎢
⎣
1
0 ··· 0
0
2
··· 0
.
.
.
.
.
.
.
.
.
.
.
.
00···
n
⎤
⎥
⎥
⎥
⎦
(D.29)
When the inverse X
−1
exists, we can diagonalize A in the form
A = XDX
−1
(D.30)
D.14 Triangularizing a Matrix 619
D.13 Diagonalizing a Matrix
We say that the square matrix A is diagonalized when it can be written in the form
(D.30). A matrix that has no repeated eigenvalues can always be diagonalized. If
some eigenvalues are repeated, then the matrix might or might not be diagonalizable.
A general rule for matrix diagonalization is as follows: A matrix is diagonalizable
only when its Jordan canonic form (JCF) is diagonal. Section 3.14.1 on page 103
discusses the Jordan canonic form of a matrix.
D.14 Triangularizing a Matrix
Sometimes it is required to change a given matrix A to an upper triangular matrix.
The resulting matrix is useful in many applications such as
1. Solving a system of linear equations.
2. Finding the eigenvector of a matrix given an eigenvalue.
3. Finding the inverse of a matrix.
Householder or Givens techniques can be used to triangularize the matrix. We
illustrate Givens technique here only. The idea is to apply a series of plane rotation,
or Givens rotation, matrices on the matrix in question in order to create zeros below
the main diagonal. We start with the first column and create zeros below the element
a
11
. Next, we start with the second column and create zeros below the element a
22
and so on. Each created zero does not disturb the previously created zeros. Further-
more, the plane rotation matrix is very stable and does not require careful choice of
the pivot element. Section D.19.7 discusses the Givens plane rotation matrices.
Assume, as an example, a 5 × 5matrixA and we are interested in eliminating
element a
42
, we choose the Givens rotation matrix G
42
G
42
=
⎡
⎢
⎢
⎢
⎢
⎣
1 0 000
0 c 0 s 0
0 0 100
0 −s 0 c 0
0 0 001
⎤
⎥
⎥
⎥
⎥
⎦
(D.31)
where c = cos θ and s = sin θ. Premultiplying a matrix A by G
42
modifies only
rows 2 and 4. All other rows are left unchanged. The elements in rows 2 and 4
become
a
2 j
= ca
2 j
+sa
4 j
(D.32)
a
4 j
=−sa
2 j
+ca
4 j
(D.33)
620 D Vectors and Matrices
The new element a
42
is eliminated from the above equation if we have
tan θ =
a
42
a
22
(D.34)
The following MATLAB code illustrates how an input matrix is converted to an
upper triangular matrix.
%File: givens.m
%The program accepts a matrix performs a seriesof
%Givens rotations to transform the matrix into an
%upper-triangular matrix.
%The new matrix is printed after eachzero is created.
%
%Input matrix to be triangularized
A=[-0.6 0.2 0.0
0.1 -0.5 0.6
0.5 0.3 -0.6]
n=3;
%iterate for first n-1 columns
for j=1:n-1
%cancel all subdiagonal elements
%in column j
for i=j+1:n
%calculate theta
theta=atan2(q(i,j),q(j,j))
for k=j:n
temp_x= A(j,k)*cos(theta)+A(i,k)*sin(theta);
temp_y=-A(j,k)*sin(theta)+A(i,k)*cos(theta);
%update new elements in rows i and j
A(j,k) = temp_x;
A(i,k) = temp_y;
end
A %print q after each iteration.
end
end
An example of using the Givens rotation technique is explained in the next
section.
D.15 Linear Equations
A system of linear equations has the form
Ax = b (D.35)
D.15 Linear Equations 621
where the coefficient matrix A is a given n × n nonsingular matrix so that the
system possesses a unique solution. The vector b is also given. The unknown vector
x is to be found. The system is said to be homogeneous when b is zero, otherwise
the system is said to be nonhomogeneous. Before we discuss methods for obtaining
the solution to the above equation, we define first some elementary row operations
[3], [2]:
1. Interchange of two rows.
2. Multiplication of a row by a nonzero constant.
3. Addition of a constant multiple of one row to another row.
Each of the above elementary row operations is implemented by multiplying
the matrix from the left by an appropriate matrix E called an elementary matrix.
The three elementary matrices corresponding to the above three elementary row
operations are illustrated below for 4 ×4 matrices [4]:
⎡
⎢
⎢
⎣
1000
0010
0100
0001
⎤
⎥
⎥
⎦
,
⎡
⎢
⎢
⎣
1000
0 a 00
0010
0001
⎤
⎥
⎥
⎦
,
⎡
⎢
⎢
⎣
1000
0100
a 010
0001
⎤
⎥
⎥
⎦
(D.36)
There are two classes of numerical methods for finding a solution. The direct
methods guarantee to find a solution in one step. This is the recommended approach
for general situations and for small values of n.Theiterative methods start with an
assumed solution then try to refine this assumption until the succeeding estimates
of the solution converge to within a certain error limit. This approach is useful for
large values of n and for sparse matrices where A has a large number of zeros.
The advantage of iterative solutions is that they practically eliminate arithmetic
roundoff errors and produce results with accuracy close to the machine precision
[5]. We discuss the two approaches in the following sections. We refer the reader
to Appendix E for a discussion of the techniques used by MATLAB to numerically
find the solution.
In the following section, we review the useful techniques for solving systems of
linear equations.
D.15.1 Gauss Elimination
Gauss elimination solves a system of linear equations by transforming A into upper
triangular form using elementary row operations. The solution is then found using
back-substitution. To create a zero at position (2,1), we need to multiply row 2 by
a
21
/a
11
, then subtract this row from row 1. This is equivalent to a row operation
matrix of the form
622 D Vectors and Matrices
E
21
=
⎡
⎣
100
e 10
001
⎤
⎦
with e =−
a
21
a
11
(D.37)
The reader could verify that this matrix performs the desired operation and cre-
ates a zero at position (2,1).
We illustrate this using an example of a 3 ×3 system for a matrix with rank 2:
⎡
⎣
−0.50.30.2
0.3 −0.40.5
0.20.1 −0.7
⎤
⎦
⎡
⎣
s
0
s
1
s
2
⎤
⎦
=
⎡
⎣
0
0
0
⎤
⎦
(D.38)
Step 1 Create a zero in the (2,1) position using the elementary matrix E
21
E
21
=
⎡
⎣
100
r 10
001
⎤
⎦
with e =−
a
21
a
11
which gives
T
1
= E
21
A =
⎡
⎣
−0.50.30.2
0 −0.22 0.62
0.20.1 −0.7
⎤
⎦
Step 2 Create a zero in the (31) position using the elementary matrix E
31
E
31
=
⎡
⎣
100
010
r 01
⎤
⎦
with r =−
a
31
a
11
which gives
T
2
= E
31
T
1
=
⎡
⎣
−0.50.30.2
0 −0.22 0.62
00.22 −0.62
⎤
⎦
Step 3 Create a zero in the (3, 2) position using the elementary matrix E
32
E
32
=
⎡
⎣
100
010
0 e 1
⎤
⎦
with e =−
a
32
a
22
D.15 Linear Equations 623
which gives
T
3
= E
32
T
2
=
⎡
⎣
−0.50.30.2
0 −0.22 0.62
000
⎤
⎦
Note that the triangularization operation produced a row of zeros, indicating
that the rank of this matrix is indeed 2.
Step 4 Solve for the components of s assuming s
3
= 1
s =
2.0909 2.8182 1
After normalization, the true state vector becomes
s =
0.3538 0.4769 0.1692
D.15.2 Gauss–Jordan Elimination
Gauss–Jordan elimination is a powerful method for solving a system of linear equa-
tions of the form
Ax = b (D.39)
where A is a square matrix of dimension n ×n and x and b are column vectors with
n components each. The above equation can be written in the form
Ax = Ib (D.40)
where I is the n × n unit matrix.
We can find the unknown vector x by multiplying by the inverse of matrix A to
get the solution
x = A
−1
b (D.41)
It is not recommended to find the inverse as mentioned above. Gauss elimination
and Gauss–Jordan elimination techniques are designed to find the solution without
the need to find the inverse of the matrix. This solution in the above equation can be
written in the form
Ix = A
−1
b (D.42)
Comparing (D.40) to (D.42), we conclude that we find our solution if some-
how we were able to convert the matrix A to I using repeated row operation.
624 D Vectors and Matrices
Gauss–Jordan elimination does exactly that by constructing the augmented matrix
AI
and converting it to the matrix
IA
−1
.
Example D.1 Solve the following set of linear equations:
2x
1
−x
2
= 0
−x
1
+2x
2
−x
3
= 3
−x
2
+2x
3
= 2
We have
A =
⎡
⎣
2 −10
−12−1
0 −12
⎤
⎦
b =
032
t
The augmented matrix is
AI
=
⎡
⎣
2 −10100
−12−1010
0 −12001
⎤
⎦
→
⎡
⎣
2 −1 0100
03−2120
0 −1 2001
⎤
⎦
row 1 +2row2
→
⎡
⎣
2 −1 0100
03−2120
0 0 4123
⎤
⎦
row 2 +3row3
So far, we have changed our system matrix A into an upper triangular matrix.
Gauss elimination would be exactly that and our solution could be found by forward
substitution.
Gauss–Jordan elimination continues by eliminating all elements not on the main
diagonal using row operations:
[
AI
]
→
⎡
⎣
60−2420
03−2120
00 4123
⎤
⎦
3row1+ row 2
→
⎡
⎣
120 0963
03−2120
00 4123
⎤
⎦
2row1+ row 3
→
⎡
⎣
1200963
060363
004123
⎤
⎦
2row2+ row 3
D.15 Linear Equations 625
Now we can simplify to get the unit matrix as follows
IA
−1
=
⎡
⎣
100
3
4
1
2
1
4
010
1
2
1
1
2
001
1
4
1
2
3
4
⎤
⎦
As a result, we now know the matrix A
−1
, and the solution to our system of
equations is given by
x = A
−1
b
=
243
t
D.15.3 Row Echelon Form and Reduced Row Echelon Form
The row echelon forms tells us the important information about a system of lin-
ear equations such as whether the system has a unique solution, no solution, or an
infinity of solutions.
We start this section with a definition of a pivot. A pivot is the first nonzero
element in each row of a matrix. A matrix is said to be in row echelon form if it has
the following properties [7]:
1. Rows of all zeros appear at the bottom of the matrix.
2. Each pivot has the value 1.
3. Each pivot occurs in a column that is strictly to the right of the pivot above it.
Amatrixissaidtobeinreduced row echelon form if it satisfies one additional
property
4. Each pivot is the only nonzero entry in its column.
MATLAB offers the function rref to find the reduced row echelon form of a
matrix.
Consider the system of equations
x
1
+2x
2
+3x
3
= 1
2x
1
+3x
2
+4x
3
= 4
3x
1
+3x
2
+5x
3
= 3
The augmented matrix is given by
Ab
=
⎡
⎣
1231
2344
3353
⎤
⎦