Transcript Non-singular matrix and Gauss

ENGG2013 Unit 7
Non-singular matrix
and Gauss-Jordan elimination
Jan, 2011.
Outline
• Matrix arithmetic
– Matrix addition, multiplication
• Non-singular matrix
• Gauss-Jordan elimination
kshum
ENGG2013
2
The love function: a normal case
Function L
Domain
Function L’
Range
Range
Boy 1
Girl A
Girl A
Boy 1
Boy 2
Girl B
Girl B
Boy 2
Boy 3
Girl C
Girl C
Boy 3
Boy 4
Girl D
Girl D
Boy 4
Boy 5
Girl E
Girl E
Boy 5
L(Boy 1) = Girl A,
kshum
Domain
but
L’(Girl A) = Boy 4.
ENGG2013
3
The love function: a utopian case
Function L
Domain
Function L’
Domain
Range
Range
Boy 1
Girl A
Girl A
Boy 1
Boy 2
Girl B
Girl B
Boy 2
Boy 3
Girl C
Girl C
Boy 3
Boy 4
Girl D
Girl D
Boy 4
Boy 5
Girl E
Girl E
Boy 5
This function L’ is the inverse of L
kshum
ENGG2013
4
The love function: no inverse
Function L
Domain
Domain
Range
Range
Boy 1
Girl A
Girl A
Boy 1
Boy 2
Girl B
Girl B
Boy 2
Boy 3
Girl C
Girl C
Boy 3
Boy 4
Girl D
Girl D
Boy 4
Boy 5
Girl E
Girl E
Boy 5
This is not a function
This function L has no inverse
kshum
ENGG2013
5
Undo-able
Rotate 90 degrees clockwise
Multiplied by
Rotate 90 degrees counter-clockwise
Multiplied by
A matrix which represents a reversible
process is called invertible or non-singular.
kshum
ENGG2013
6
Objectives
• How to determine whether a matrix is
invertible?
• If a matrix is invertible, how to find the
corresponding inverse matrix?
kshum
ENGG2013
7
MATRIX ALGEBRA
kshum
ENGG2013
8
Matrix equality
• Two matrices are said to be equal if
1. They have the same number of rows and the
same number of columns (i.e. same size).
2. The corresponding entry are identical.
kshum
ENGG2013
9
Matrix addition and
scalar multiplication
• We can add two matrices if they have the
same size
• To multiply a matrix by a real number, we just
multiply all entries in the matrix by that
number.
kshum
ENGG2013
10
Matrix multiplication
• Given an mn matrix A and a pq matrix B, their product AB
is defined if n=p.
• If n = p, we define their product, say C = AB, by computing the
(i,j)-entry in C as the dot product of the i-th row of A and the
j-th row of B.
m q
kshum
mn
ENGG2013
pq
11
Examples
is undefined.
is undefined.
kshum
ENGG2013
12
Square matrix
• A matrix with equal number of columns and rows is
called a square matrix.
• For square matrices of the same size, we can freely
multiply them without worrying whether the product is
well-defined or not.
– Because multiplication is always well-defined in this case.
• The entries with the same column and row index are
called the diagonal entries.
– For example:
kshum
ENGG2013
13
Compatibility with
function composition
Multiplied by
Multiplied by
Multiplied by
kshum
ENGG2013
14
Order does matter in multiplication
Rotate 90 degrees
Reflection around x-axis
Multiplied by
Multiplied by
Are they the same?
kshum
Reflection around x-axis
Rotate 90 degrees
Multiplied by
Multiplied by
ENGG2013
15
Non-commutativity
• For real numbers, we have 35 = 53.
– Multiplication of real numbers is commutative.
• For matrices, in general AB  BA.
– Multiplication of matrices is non-commutative.
– For example
kshum
ENGG2013
16
Associativity
• For real numbers, we have (34)5 = 3(45).
– Multiplication of real numbers is associative.
• For any three matrices A, B, C, it is always true
that (AB)C = A(BC), provided that the
multiplications are well-defined.
– Multiplication of matrices is associative.
kshum
ENGG2013
17
INVERTIBLE MATRIX
kshum
ENGG2013
18
Identity matrix
• A square matrix whose diagonal entries are all
one, and off-diagonal entries are all zero, is
called an identity matrix.
• We usually use capital letter I for identity
matrix, or add a subscript and write In if we
want to stress that the size is nn.
kshum
ENGG2013
19
Multiplication by identity matrix
is trivial
• Identity matrix is like a do-nothing process.
– There is no change after multiplication by the
identity matrix
Multiplied by
• IA = A for any A.
• BI = B for any B.
kshum
ENGG2013
20
Invertible matrix
• Given an nn matrix A, if we can find a matrix A’, such that
then A is said to be invertible, or non-singular.
• This matrix A’ is called an inverse of A.
Multiplied by
Multiplied by
A
A’
Multiplied by
In
kshum
ENGG2013
21
Example
implies
kshum
Rotate 90 CW
Rotate 90 CCW
Multiplied by
Multiplied by
ENGG2013
is invertible.
22
Matrix inverse may not exist
• If matrix A induces a many-to-one mapping,
then we cannot hope for any inverse.
has no inverse
kshum
ENGG2013
23
Naïve method for computing
matrix inverse
• Consider
• Want to find A’ such that A A’= I
• Solve for p, q, r, s in
kshum
ENGG2013
24
Uniqueness of matrix inverse
• Before we discuss how to compute matrix
inverse, we first show there is at most one A’
such that A A’ = A’ A = I.
• Suppose on the contrary that there is
another matrix A’’ such that A A’’ = A’’ A = I.
• We want to prove that A’ = A’’.
kshum
ENGG2013
25
Proof of uniqueness
Defining property of A’’
Multiply by A’ from the left
I times anything is the same thing
Matrix multiplication is associative
Defining property of A’
I times anything is the same thing
kshum
ENGG2013
26
Notation
• Since the matrix inverse (if exists) is unique,
we use the symbol A-1 to represent the unique
matrix which satisfies
• We say that A-1 is the inverse of A.
kshum
ENGG2013
27
A convenient fact
• To check that a matrix B is the inverse of A, it
is sufficient to check either
1. BA = I, or
2. AB = I.
• It can be proved that (1) implies (2), and (2)
implies (1).
– The details is left as exercise.
kshum
ENGG2013
28
GAUSS-JORDAN ELIMINATION
kshum
ENGG2013
29
Row operation using matrix
• Recall that there are three kind of elementary
row operations
1. Row exchange
2. Multiply a row by a non-zero constant
3. Replace a row by the sum of itself and a constant
multiple of another row.
• We can perform elementary row operation
by matrix multiplication (from the left).
• All three kinds of operation are invertible.
kshum
ENGG2013
30
Row exchange
• Example: exchange row 2 and row 3
Multiply the same matrix from the left again, we
get back the original matrix.
kshum
ENGG2013
31
Multiply a row by a constant
• Multiply the first row by -1.
Multiply the same matrix from the left again, we
get back the original matrix.
kshum
ENGG2013
32
Row replacement
• Add the first row to the second row
Multiply by another matrix from the left to undo
kshum
ENGG2013
33
Elementary matrix (I)
• Three types of elementary matrices
Col. j
Col. i
1. Exchange row i and row j
Row i
Row j
kshum
ENGG2013
34
Elementary matrix (II)
Col. i
2. Multiply row i by m
Row i
kshum
ENGG2013
35
Elementary matrix (III)
Col. j
Col. i
3. Add s times row i to row j
Row i
Row j
kshum
ENGG2013
36
Row reduction
• A series of row reductions is the same as
multiplying from the left a series of
elementary matrices.
…
E1, E2, E3, … are elementary matrices.
kshum
ENGG2013
37
If we can row reduce to identity
• Then A is non-singular, or invertible.
(Matrix
multiplication is
associative)
kshum
ENGG2013
38
Gauss-Jordan elimination
• It is convenient to append an identity matrix
to the right
• We can interpret it as
If we can row reduce A to the identity by a series of
row operations
then we can apply the same series of row
operations to I and obtain the inverse of A.
kshum
ENGG2013
39
Algorithm
• Input: an nn matrix A.
• Create an n  2n matrix M
– The left half is A
– The right half is In
• Try to reduce the expanded matrix M such that
the left half is equal to In.
• If succeed, the right half of M is the inverse of A.
• If you cannot reduce the left half of M to , then A
is not invertible, a.k.a. singular.
kshum
ENGG2013
40
Example
• Find the inverse of
1. Create a 36 matrix
2. After some row reductions
we get
• Answer:
kshum
ENGG2013
41