Transcript 3.III.

3.III. Matrix Operations
• In Section 3.II, matrix was defined in terms of linear maps.
• Operations on matrices will be defined to represent operations on linear maps.
• Matrix algebra is a linear algebra ( M, + , · ; R ).
3.III.1.
3.III.2.
3.III.3.
3.III.4.
Sums and Scalar Products
Matrix Multiplication
Mechanics of Matrix Multiplication
Inverses
3.III.1. Sums and Scalar Products
Definition:
The sum of maps
Sum of Maps of the Same Domain & Codomain
f, g : V → W is another map
h=f+g: V→W
Definition 1.3:
v  f(v) + g(v)
by
Matrix Addition & Scalar Multiplication
Let A = ( ai j ) & B = ( bi j ) be mn matrices.
Then C = A + B is an mn matrix with elements ci j  ai j + bi j .
And C = α A , with α  R, is an mn matrix with elements ci j  α ai j .
Theorem 1.5:
Matrix Representations
Let f, g : V → W be maps with bases B → D so that F = f B → D & G = g B → D .
Then
( f + g )B → D = F + G
Proof: Do it yourself.
&
(α f ) B → D = α G , where
α R
f, g : R2 → R2
Example 1.1:
F  fB  D
Then
 1 3
  2 0 
 1 0

B  D
f  v B D
g  v B D
f
G  gB  D
0 0
  1 2 
2 4

B  D
 1 3
 v1  3v2 
v
 1


  2 0 
 v    2v1 
 2 B 
 1 0


B  D
 v1 D
0 0
 v1 
  1 2 
v 
 2 B
2 4

B  D
 g   v B D  f  v B D  g  v B D
0


  v1  2v2 
 2v  4v 
2 D
 1
1 3 
 v1  3v2 
 v1 
  v1  2v2    1 2 
v 
 2 B
3 4 
 3v  4v 


2 D
 1
BD
 1 3  0 0   1 3 
F  G   2 0    1 2    1 2    f  g  B  D  hB  D
 1 0  2 4   3 4 

 
 

H
Exercise 3.III.1.
1. The trace of a square matrix is the sum of the entries on the main
diagonal (the 1,1 entry plus the 2,2 entry, etc.; we will see the significance of
the trace in Chapter Five).
Show that trace(H + G) = trace(H) + trace(G).
Is there a similar result for scalar multiplication?
3.III.2. Matrix Multiplication
Lemma 2.1: A composition of linear maps is linear, i.e.,
If
h : V → W and g : W → U are linear maps,
then
g  h : V → U is a linear map.
Proof: Composition of linear maps preserves linear combinations.
(see Hefferon, p.215)
Definition 2.3:
Matrix-Multiplicative Product
The matrix-multiplicative product of the mr matrix G and the rn matrix H is the
mn matrix P, where
r
pi j   g i k h k j  G i   H  j 
k 1
i.e.,

G H   gi1


gi 2


gi r  
 


h1 j
h2 j
hr j



 






pi j

P



P  j   G  H  j 
Theorem 2.6:
A composition of linear maps is represented by the matrix product of the representatives.
Proof:
Let h: V n → W r and g: W r → U m be linear maps with representations
RepB  Ch  h B  C  H
RepC  D g  g C  D  G
where B, C, and D are bases
of V, W and U, resp.
 v1 
 
Let v  V with RepB v  v B   
v 
 n B
If w = h(v)  W, then
w C  RepC  h  v     RepB  Ch   v B  H  v B
If x = g(w) = g  h (v)  U, then
x D  RepD  g h  v    Rep D  g  w     RepC  D g   w C  G  wC  G   H  v 
B
RepD  g h  v    G   H  v B 
r
r
n
k 1
k 1
j 1
G   H  v B   i   gi k wk   gi k  h k j v j
→
∴
RepD  g h  v     G  H   v B
RepB  D g h  G  H
 r

    gi k h k j  v j
j 1  k 1

n
n
  G  H i j v j
j 1
 v V
  RepC  D g    RepB  C h 
QED
Example 2.2, 4:
Let h : R4 → R2 and g : R2 → R3 with bases B  R4 , C  R2 , D  R3 so that
H  RepB  C  h   h B  C
→
1 1
G  RepC  D  g   gC  D   0 1 
1 0

C  D
 9 13 17 5 
4 6 8 2
 5 7 9 3
  5 7 9 3 

B  C 

 4 6 8 2 B  D
4 6 8 2


5
7
9
3

B  C
F  RepB  D  g h 
1 1
  0 1 
1 0

C  D
 v1 
v 
Let v B   2  then
 v3 
 
 v4  B
xD  G  wC
 v1 
v 
4 6 8 2
 4v1  6v2  8v3  2v4 
 2
wC  H  vB  


 5v  7v  9v  3v 
 5 7 9 3 B  C  v3 
2
3
4C
 1
 
 v4 B
1 1
 4v1  6v2  8v3  2v4 
  0 1 
 5v  7v  9v  3v 
2
3
4C
 1
1 0

C  D
x D   G  H  v B
 v1 
9
13
17
5


v 
 2
  5 7 9 3 
 v3 
4 6 8 2

B  D  v 
 4 B
G   H  vB    G  H  v B
 9v1  13v2  17v3  5v4 
  5v1  7v2  9v3  3v4 
 4v  6v  8v  2v 
2
3
4 D
 1
 9v1  13v2  17v3  5v4 
  5v1  7v2  9v3  3v4 
 4v  6v  8v  2v 
2
3
4 D
 1
suggests that matrix products are associative.
To be proved in Theorem 2.12 below.
g h
v
g h  v
h
v
h v
g
g h  v
RepB  D g h  G  H   RepC  D g    RepB  C h 
Matrix dimensions: m  r times r  n equals m  n.
Example 2.7:
Dimension mismatch
This product is not defined
 1 2 0   0 0 
 0 10 1.1  0 2 



Example 2.9:
Matrix multiplication need not commute.
 1 2   5 6   19 22 
 3 4   7 8    43 50 


 

 5 6   1 2   23 34 
 7 8   3 4    31 46 


 

Example 2.10:
 5 6   1 2 0   23 34 0 
 7 8   3 4 0    31 46 0 


 

1 2 0 5 6
 3 4 0   7 8  is not defined



Theorem 2.12:
Matrix products, if defined, are associative
(FG)H = F(GH)
and distributive over matrix addition
F(G + H) = FG + FH
and
(G + H)F = GF + HF.
Proof: Hefferon p.219
Via component-sumation formulae or the corresponding composite maps.
Exercises 3.III.2.
1. Represent the derivative map on Pn with respect to B → B where B is the
natural basis ( 1, x, …, xn ). Show that the product of this matrix with itself is
defined. What the map does it represent?
2. ( This will be used in the Matrix Inverses exercises.)
Here is another property of matrix multiplication that might be puzzling at first sight.
(a) Prove that the composition of the projections πx , πy : R3 → R3 onto the x and y
axes is the zero map despite that neither one is itself the zero map.
(b) Prove that the composition of the derivatives d2 /dx2, d3 /dx3 : P4 → P4 is the
zero map despite that neither is the zero map.
(c) Give a matrix equation representing the first fact.
(d) Give a matrix equation representing the second.
When two things multiply to give zero despite that neither is zero, each is said to
be a zero divisor.
3. The infinite-dimensional space P of all finite-degree polynomials gives a
memorable example of the non-commutativity of linear maps.
Let d/dx: P → P be the usual derivative and let s: P → P be the shift map.
a0  a1 x 
 an x
n
s
0  a0 x  a1 x 2 
 an x n 1
Show that the two maps don’t commute:
d/dx  s  s  d/dx
In fact, not only is d/dx  s  s  d/dx not the zero map, it is the identity map.
3.III.3. Mechanics of Matrix Multiplication
(AB)i j = ( Row i of A )  ( Column j of B )
1 1
 9 13 17 5 
4
6
8
2
 
0 1


5
7
9
3

  5 7 9 3 

  4 6 8 2
 1 0 




Lemma 3.7:
( Row i of A )  B = ( Row i of AB )
1 1
 9 13 17 5 
4
6
8
2
 
 0 1


5
7
9
3

  5 7 9 3 

 4 6 8 2
 1 0 




A  ( Column j of B ) = ( Column j of AB )
1 1
 9 13 17 5 
 0 1  4 6 8 2    5 7 9 3

  5 7 9 3 

  4 6 8 2
 1 0 




Definition 3.2:
Unit Matrix
A matrix with all zeroes except for a one in the i, j entry is an i, j unit matrix.
Let U be an i, j unit matrix, then
• U A → Copy row j of A to row i of zero matrix of appropriate dimensions.
• A U → Copy col i of A to col j of zero matrix of appropriate dimensions.
0 1
8 9 4
5
6
7
 
 0 0 


0
0
0






 0 0 8 9 4  0 0 0




0 2
 2 8 2  9 2  4
5
6
7
 
0 0


0
0
0






 0 08 9 4  0
0
0 



0 1
5
6
7


 0 5

 8 9 4   0 0   0 8

  0 0 



0 2
5
6
7


 0 2  5

 8 9 4   0 0    0 2  8

0 0 



0 1
8 9 4
 0 0 5 6 7    0 0 0

8 9 4 

 5 6 7
 1 0 




1 1
5  8 6  9 7  4
5
6
7
 
 0 0 


0
0
0

8 9 4 

  0
 0 0 
0
0 



Let U be an i, j unit matrix, then
• U A → Copy row j of A to row i of zero matrix of appropriate dimensions.
• A U → Copy col i of A to col j of zero matrix of appropriate dimensions.
U   uk l    k i  l j 
 UA k l   uk m aml
m
m
 A  j 
 UA  k   
 0
→
 AU k l   ak m uml
m
→
   k i  m j aml   k i a j l
k i
if
k i
  ak m  m i  l j  ak i  l j
m
 A i 
 0
 AU  l   
if
l j
l j
Definition 3.8:
Main Diagonal
The main diagonal (or principal diagonal or diagonal) of a square matrix
goes from the upper left to the lower right.
Definition 3.9:
Identity Matrix
I nn
1 0
0 1



0 0
0
0 


1
 I n n  i j   i j
A mn Inn  A mn  Imm A mn
Definition 3.12: Diagonal Matrix
A diagonal matrix is square and has zeros off the main diagonal.
A nn
 a11 0
 0 a
22



0
 0
0 
0 


ann 
 diag  a11, a22 ,
, ann 
 A nn i j  aii  i j
Definition 3.14: Permutation Matrix
A permutation matrix is square and is all zeros except for a single one in each
row and column.
From the left (right) these matrices permute rows (columns).
 0 0 1  1 2 3  7 8 9 
 1 0 0  4 5 6   1 2 3


 

 0 1 0  7 8 9  4 5 6


 

 1 2 3  0 0 1   2 3 1 
 4 5 6 1 0 0   5 6 4


 

 7 8 9 0 1 0  8 9 7


 

3rd row to 1st
1st row to 2nd
2nd row to 3rd
1st column to 3rd
2nd column to 1st
3rd column to 2nd
Definition 3.18: Elementary Reduction Matrices
The elementary reduction matrices are obtained from identity matrices with
one Gaussian operation. We denote them:
1
 2
 3
i  k i
I 
 Mi  k 
i   j
I 
 Pi , j
 j  k i   j
I  Ci , j  k 
1 0 0  a
C2 , 3  3 A   0 1 0   c
0 3 1 e


1 0 0
M2  3   0 3 0 
0 0 1


 1 0 0
P2, 3   0 0 1 
 0 1 0


1 0 0
C2 , 3  3   0 1 0 
0 3 1


b  a
b
d    c
d
f   3c  e 3d 



f 
The Gauss’s method and Gauss-Jordan reduction can be accomplished
by a single matrix that is the product of elementary reduction matrices.
Corollary 3.22:
For any matrix H there are elementary reduction matrices R1, . . . , Rr
such that Rr Rr1 ··· R1 H is in reduced echelon form.
Exercises 3.III.3
1. The need to take linear combinations of rows and columns in tables of
numbers arises often in practice. For instance, this is a map of part of Vermont
and New York.
In part because of Lake Champlain,
there are no roads directly connecting
some pairs of towns. For instance,
there is no way to go from Winooski to
Grand Isle without going through
Colchester. (Of course, many other
roads and towns have been left off to
simplify the graph. From top to
bottom of this map is about forty miles.)
Continued next page.
(a) The incidence matrix of a map is the square matrix whose i, j entry is the
number of roads from city i to city j. Produce the incidence matrix of this map
(take the cities in alphabetical order).
(b) A matrix is symmetric if it equals its transpose. Show that an incidence
matrix is symmetric. (These are all two-way streets. Vermont doesn’t have
many one-way streets.)
(c) What is the significance of the square of the incidence matrix? The cube?
2. The trace of a square matrix is the sum of the entries on its diagonal (its
significance appears in Chapter Five). Show that trace(GH) = trace(HG).
3. A square matrix is a Markov matrix if each entry is between zero and one
and the sum along each row is one. Prove that a product of Markov matrices
is Markov.
3.III.4. Inverses
Example 4.1:
Let π: R3 → R2 be the projection map
and η : R2 → R3 be the embedding
 x
 y
 
z
 
 x
 y
 
 x
 y
 
 x
 y
 
0
 
The composition π η: R2 → R2 is the identity map on R2 :
 x 
 y
 
 x
 y
 
0
 

 x
 y
 
π is a left inverse map of η.
η is a right inverse map of π.
The composition η  π : R3 → R3 is not the identity map on R3 :
 x
 y
 
z
 

 x
 y
 

 x
 y
 
0
 
π has no left inverse.
η has no right inverse.
π η= id
The zero map has neither left nor right inverse.
Definition 4.2:
Left / Right Inverse & Invertible Matrices
A matrix G is a left inverse matrix of the matrix H if GH = I .
It is a right inverse matrix if HG = I .
A matrix H with a two-sided inverse is an invertible matrix.
That two-sided inverse is called the inverse matrix and is denoted H1 .
Lemma 4.3:
If a matrix has both a left inverse and a right inverse then the two are equal.
Proof: Statement is true on the corresponding linear maps.
Theorem 4.4:
A matrix is invertible if and only if it is nonsingular (square).
Proof: Statement is true on the corresponding linear maps (1-1).
Lemma 4.5:
A product of invertible matrices is invertible: ( GH )1 = H 1 G 1
Proof: Statement is true on the corresponding linear maps.
Lemma 4.8:
A matrix is invertible  it can be written as the product of elem reduction matrices.
The inverse can be computed by applying to I the same row steps, in the same order,
as are used to Gauss-Jordan reduce the invertible matrix.
Proof: An invertible matrix is row equivalent to I.
Let R be the product of the required elementary reduction matrices so that RA = I.
Then
AXI
→
RAXRI
→
XRI
Example 4.10:
Example 4.11:
A Non-Invertible Matrix
Corollary 4.12:
The inverse for a 22 matrix exists and equals
if and only if ad  bc  0.
g assumed 1-1






HG  


GH  








   1 0
  0 1

 

 1 0 0
 


0
1
0
 

  0 0 1


Right inverse of H and
left inverse of G exists
Left inverse of H and
right inverse of G
doesn’t exist
Exercises 3.III.4
1. Show that the matrix  1 0 1 
0 1 0


has infinitely many right inverses.
Show also that it has no left inverse.
2. Show that if T is square and if T4 is the zero matrix then
1  T 
1
 1  T  T2  T3
Generalize.
3. Prove: if the sum of the elements of a square matrix is k, then the sum of
the elements in each row of the inverse matrix is 1/k.