Transcript 1 A

Chapter 1
Matrices and Systems of
Equations
1 Systems of Linear Equations
 a11x1  a12 x2    a1n xn  b1
 a x  a x   a x  b
 21 1 22 2
2n n
2



am1 x1  am 2 x2    amn xn  bm
(1)
Where the aij’s and bi’s are all real numbers, xi’s
are variables . We will refer to systems of the form
(1) as m×n linear systems.
Definition
Inconsistent : A linear system has no solution.
Consistent : A linear system has at least one solution.
Example
(ⅰ) x1 + x2 = 2
x1 − x2 = 2
(ⅱ) x1 + x2 = 2
x1 + x2 =1
(ⅲ)
x1 + x2 = 2
−x1 − x2 =-2
Definition
Two systems of equations involving the same variables
are said to be equivalent if they have the same solution
set.
Three Operations that can be used on a system
to obtain an equivalent system:
Ⅰ. The order in which any two equations are written may
be interchanged.
Ⅱ. Both sides of an equation may be multiplied by the
same nonzero real number.
Ⅲ. A multiple of one equation may be added to (or
subtracted from) another.
n×n Systems
Definition
A system is said to be in strict triangular form if in the kth
equation the coefficients of the first k-1 variables are all
zero and the coefficient of xk is nonzero (k=1, …,n).
Example The system
 3x1  2 x2  x3  1

x2  x3  2


2 x3  4

is in strict triangular form.
Example Solve the system
 x1  2 x2  x3  3

3x1  x2  3x3  1
2 x  3 x  x  4
2
3
 1
Elementary Row Operations:
Ⅰ. Interchange two rows.
Ⅱ. Multiply a row by a nonzero real number.
Ⅲ. Replace a row by its sum with a multiple of another row.
Example Solve the system
  x2  x3  x4  0
 x x x x 6
 1 2 3 4

2 x1  4 x2  x3  2 x4  1
3x1  x2  2 x3  2 x4  3
2 Row Echelon Form
 1
1

 1 1
 2  2

 0
0

1
 1
1

0
0

0

0
1
0
0
1
2
1
0
0
0
0
1 1

1  1
3 1

3  1

4 1
1
0
0
1
2
1
1
0
0
0
1
1
0
0
0
1
2
1
1
1
pivotal row
1

0
3

 1

0
1

0
0

0

0
1
0
0
0
0
1
1
2
1
1
1
1
2
1
1
1
2
5
3
3
1

0
0

0

0
1
0
0
0
0
1
1
0
0
0
1

0  pivotal row
3

 1

0
1
1
0
0
0
1
2
1
0
0
1 

0 
3 

 4

 3
Definition
A matrix is said to be in row echelon form
ⅰ. If the first nonzero entry in each nonzero row is 1.
ⅱ. If row k does not consist entirely of zeros, the
number of leading zero entries in row k+1 is greater
than the number of leading zero entries in row k.
ⅲ. If there are rows whose entries are all zero, they are
below the rows having nonzero entries.
Example Determine whether the following matrices are
in row echelon form or not.
 1 4 2  2 4 6  1 2 3

 
 
  0 0 0

 0 1 3   0 3 5   0 0 1  
 0 0 1  0 0 4  0 0 0  0 1 0

 
 

1 3 1 0


 0 0 1 3
 0 0 0 0


0 1


1 0
Definition
The process of using operations Ⅰ, Ⅱ, Ⅲ to transform a
linear system into one whose augmented matrix is in
row echelon form is called Gaussian elimination.
Definition
A linear system is said to be overdetermined if there
are more equations than unknows.
A system of m linear equations in n unknows is said to
be underdetermined if there are fewer equations than
unknows (m<n).
Example
 x1  x2  1

(a )  x1  x2  3
 x  2 x  2
2
 1
 x1  x2  x3  x4  x5  2

(b)  x1  x2  x3  2 x4  2 x5  3
 x  x  x  2 x  3x  2
4
5
 1 2 3
Definition
A matrix is said to be in reduced row echelon form if:
ⅰ. The matrix is in row echelon form.
ⅱ. The first nonzero entry in each row is the only
nonzero entry in its column.
Homogeneous Systems
A system of linear equations is said to be homogeneous
if the constants on the right-hand side are all zero.
Theorem 1.2.1 An m×n homogeneous system of linear
equations has a nontrivial solution if n>m.
3 Matrix Algebra
Matrix Notation
 a11 a12

 a21 a22
A
 

a
 m1 am 2
 a1n 

 a2 n 
 

 amn 
Vectors
row vector
column vector
X  x1 , x2 , , xn 
 x1 
 
 x2 
X  

 
x 
 n
1×n matrix
n×1 matrix
Definition
Two m×n matrices A and B are said to be equal if aij=bij
for each i and j.
Scalar Multiplication
If A is a matrix and k is a scalar, then kA is the matrix
formed by multiplying each of the entries of A by k.
Definition
If A is an m×n matrix and k is a scalar, then kA is the
m×n matrix whose (i, j) entry is kaij.
Matrix Addition
Two matrices with the same dimensions can be added
by adding their corresponding entries.
Definition
If A=(aij) and B=(bij) are both m×n matrices,then the
sum A+B is the m×n matrix whose (i, j) entry is aij+bij
for each ordered pair (i, j).
Example
 1 1 2 
1 0 0
Let
A   2 0 3  , I   0 1 0 
 1 1 2 
0 0 1




Then calculate 2 A  3I 。
Matrix Multiplication
Definition
If A=(aij) is an m×n matrix and B=(bij) is an n×r matrix,
then the product AB=C=(cij) is the m×r matrix whose
entries are defined by
n
cij = ai1b1j + ai2b2j +…+ ainbnj =  aikbkj.
k=1
Example
4
1
0
3
, B    1
1. If A  
2
 2 1 0

1
1 ,
0 
then calculate AB.
2. If A   1 1 , B   1  1, then calculate AB and BA.
2 2
1 1




Matrix Multiplication and Linear Systems
Case 1 One equation in Several Unknows
If we let A  (a1 a2  an ) and
 x1 
 
 x2 
X  

 
x 
 n
then we define the product AX by
AX  a1 x1  a2 x2  an xn
Case 2 M equations in N Unknows
 a11 a12  a1n 


a
a22  a2 n 
If we let A   21
and
 



a

a

a
m2
mn 
 m1
 x1 
 
 x2 
X  

 
x 
 n
then we define the product AX by
 a11x1  a12 x2   a1n xn 


 a21x1  a22 x2   a2 n xn 
AX  




 a x  a x  a x 
mn n 
 m1 1 m 2 2
Definition
If a1, a2, … , an are vectors in Rm and c1, c2, … , cn are scalars,
then a sum of the form
c1a1+c2a2+‥‥cnan
is said to be a linear combination of the vectors a1, a2, … , an .
Theorem 1.3.1 (Consistency Theorem for Linear Systems)
A linear system AX=b is consistent if and only if b can be
written as a linear combination of the column vectors of
A.
Theorem 1.3.2 Each of the following statements is
valid for any scalars k and l and for any matrices A, B
and C for which the indicated operations are defined.
1. A+B=B+A
2. (A+B)+C=A+(B+C)
3. (AB)C=A(BC)
4. A(B+C)=AB+AC
5. (A+B)+C=AC+BC
6. (kl)A=k(lA)
7. k(AB)=(kA)B=A(kB)
8. (k+l)A=kA+lA
9. k(A+B)=kA+kB
The Identity Matrix
Definition
The n×n identity is the matrix I  ( ij ) where
1
 ij  
0
if i  j
if i  j
Matrix Inversion
Definition
An n×n matrix A is said to be nonsingular or invertible
if there exists a matrix B such that AB=BA=I.
Then matrix B is said to be a multiplicative inverse of A.
Definition
An n×n matrix is said to be singular if it does not have
a multiplicative inverse.
Theorem 1.3.3 If A and B are nonsingular n×n
matrices, then AB is also nonsingular and (AB)-1=B-1A-1
The Transpose of a Matrix
Definition
The transpose of an m×n matrix A is the n×m matrix B
defined by
bji=aij
for j=1, …, n and i=1, …, m. The transpose of A is
denoted by AT.
Algebra Rules for Transpose:
1. (AT)T=A
2. (kA)T=kAT
3. (A+B)T=AT+BT
4. (AB)T=BTAT
Definition
An n×n matrix A is said to be symmetric if AT=A.
4. Elementary Matrices
If we start with the identity matrix I and then perform
exactly one elementary row operation, the resulting matrix
is called an elementary matrix.
Type I. An elementary matrix of type I is a matrix obtained by
interchanging two rows of I.
Example Let
then
 0 1 0


E1   1 0 0 
0 0 1


 0 1 0   a11 a12


E1 A   1 0 0   a21 a22
0 0 1  a

  31 a32
and let A be a 3×3 matrix
a13   a21 a22
 
a23    a11 a12
a33   a31 a32
a23 

a13 
a33 
 a11 a12 a13   0 1 0   a12 a11 a13 


 

AE1   a21 a22 a23   1 0 0    a22 a21 a23 
a a
 0 0 1  a

a
a
a
 31 32 33  
  32 31 33 
Type II. An elementary matrix of type II is a matrix obtained by
multiplying a row of I by a nonzero constant.
Example Let
then
1 0 0


E2   0 1 0 
 0 0 3


 1 0 0   a11 a12


E2 A   0 1 0   a21 a22
 0 0 3  a

  31 a32
 a11 a12

AE2   a21 a22
a
 31 a32
and let A be a 3×3 matrix
a13   a11 a12
a13 
 

a23    a21 a22 a23 
a33   3a31 3a32 3a33 
a13   1 0 0   a11 a12 3a13 

 

a23   0 1 0    a21 a22 3a23 
a33   0 0 3   a31 a32 3a33 
Type III. An elementary matrix of type III is a matrix obtained
from I by adding a multiple of one row to another row.
Example Let
 1 0 3


E3   0 1 0 
0 0 1


 1 0 3   a11 a12


E3 A   0 1 0   a21 a22
0 0 1  a

  31 a32
 a11

AE3   a21
a
 31
a12
a22
a32
and let A be a 3×3 matrix
a13   a11  3a31 a12  3a32
 
a23    a21
a22
a33   a31
a32
a13   1

a23   0
a33   0
0
1
0
3   a11
 
0    a21
1   a31
a12
a22
a32
a13  3a33 

a23 
a33 
3a11  a13 

3a21  a23 
3a31  a33 
In general, suppose that E is an n×n elementary
matrix. E is obtained by either a row operation or a
column operation.
If A is an n×r matrix, premultiplying A by E has the
effect of performing that same row operation on A. If B
is an m×n matrix, postmultiplying B by E is equivalent
to performing that same column operation on B.
Example
Let
 a11 a12 a13 
 a31 a32  3a33 a33 
A   a21 a22 a23  , B   a21 a22  3a23 a23 
a a a 
 a a  3a a 
 31 32 33 
13
13 
 11 12
Find the elementary matrices P1 ， P2，such that B  P1 AP2 .
Theorem 1.4.1 If E is an elementary matrix, then E is
nonsingular and E-1 is an elementary matrix of the
same type.
Definition
A matrix B is row equivalent to A if there exists a finite
sequence E1, E2, … , Ek of elementary matrices such that
B=EkEk-1‥‥E1A
Theorem 1.4.2 (Equivalent Conditions for Nonsingularity)
Let A be an n×n matrix. The following are equivalent:
(a) A is nonsingular.
(b) Ax=0 has only the trivial solution 0.
(c) A is row equivalent to I.
Theorem 1.4.3 The system of n linear equations in n
unknowns Ax=b has a unique solution if and only if A
is nonsingular.
A method for finding the inverse of a matrix
If A is nonsingular, then A is row equivalent to I and
hence there exist elementary matrices E1, …, Ek such
that
EkEk-1‥‥E1A=I
multiplying both sides of this
equation on the right by A-1
EkEk-1‥‥E1I=A-1
row operations
Thus
(A I)
(I A-1)
Example Compute A-1 if
4 3
1


A   1  2 0 
2

2
3


Example Solve the system
 x1  4 x2  3x3  12

  x1  2 x2  12
2 x  2 x  3x  8
2
3
 1
Diagonal and Triangular Matrices
An n×n matrix A is said to be upper triangular if aij=0 for i>j
and lower triangular if aij=0 for i<j.
A is said to be triangular if it is either upper triangular or
lower triangular.
An n×n matrix A is said to be diagonal if aij=0 whenever i≠j .
5. Partitioned Matrices
1 -2
2 1
C=
4
1
1 3
1
1
C11
C12
C21
C22
=
3 3
2
-1 2
4 6
2
2 4
=(b1, b2, b3)
-1
B= 2
2
3
1
1
1
4
1
AB=A(b1, b2, b3)=(Ab1, Ab2, Ab3)
In general, if A is an m×n matrix and B is an n×r that has
been partitioned into columns (b1, …, br), then the block
multiplication of A times B is given by
AB=(Ab1, Ab2, … , Abr)
 a (1, :) 


 a (2, :) 
If we partition A into rows, then A  
 


 a (m, :) 


Then the product AB can be partitioned into rows as follows:
 a(1, :) B 


 a(2, :) B 
AB  




 a(m, :) B 


Block Multiplication
Let A be an m×n matrix and B an n×r matrix.
Case 1 B=(B1 B2), where B1 is an n×t matrix and B2
is an n×(r-t) matrix.
AB= A(b1, … , bt, bt+1, … , br)
= (Ab1, … , Abt, Abt+1, … , Abr)
= (A(b1, … , bt), A(bt+1, … , br))
= (AB1 AB2)
Case 2
 A1 
A=   ,where A1 is a k×n matrix and A2
 A2 
is an (m-k)×n matrix.
Thus
 A1 
 A1 B 
  B  

 A2 
 A2 B 
Case 3 A=(A1
 B1 
A2) and B=   , where A1 is an m×s matrix
 B2 
and A2 is an m×(n-s) matrix, B1 is an s×r matrix and B2 is an
(n-s)×r matrix.
Thus
 A1
 B1 
A2    A1B1  A2 B2
 B2 
Case 4 Let A and B both be partitioned as follows：
A11 A12
k
A21 A22
m-k
A=
s
n-s
B11 B12
s
B21 B22
n-s
B=
t
r-t
Then
 A11

 A21
A12  B11

A22  B21
B12   A11B11  A12 B21
  
B22   A21B11  A22 B21
A11B12  A12 B22 

A21B12  A22 B22 
In general, if the blocks have the proper
dimensions, the block multiplication can be
carried out in the same manner as ordinary
matrix multiplication.
Example
Let
1
0
A
0
0

0
1
0
0
0
0
1
0
2
3
1
4
Then calculate AB.
1
5 

 2 , B   2
1
6 
0

0 
0

0
3
1
0
0
4
 1
3 ,
1
0 
Example
 A11
Let A be an n×n matrix of the form 
 0
0 

A22 
where A11 is a k×k matrix (k<n). Show that
A is nonsingular if and only if A11 and A22
are nonsingular.