|
Slide 1 |
Suppose A(n × n) is of full rank and we wish to
Properties /linear- graph -solver.html">solve a set of n
equations in n unknowns ,i.e.
Ab = g  g (n × 1) , b (n × 1)
Since A-1 A = I, the solution is b = A-1 g.
What happens if A is less than full rank? |
|
Slide 2 |
Definition: A generalized inverse of an m× n
matrix A is any
n × m matrix C such that
ACA = A.
We use  to denote a generalized
inverse of A.
C is not unique. For example (verify this on your own) : each of
the two 3 × 2 matrices
 and
 is a
generalized inverse of the 2 × 3 matrix
|
|
Slide 3 |
Properties:
1. For any matrix A and any non zero scalar k, (1/k) is a
generalized inverse of kA.
2. For any matrix A, - is a generalized inverse of
-A.
3. For any matrix A', ()' is a generalized inverse of
A'. |
|
Slide 4 |
Exercise: For any matrix A,
1. Show that rank(A)=rank(A)=rank(A).
2. Show that rank() ≥ rank(A). |
|
Slide 5 |
Now going back to solving Ab = g, suppose g ∈ C(A)
(solutions to this linear system exist).
Lemma. Let C be a generalized inverse of A, then
 (or
g )is a solution.
Proof: Suppose b is a solution to Ab = g.
which implies that is a solution.
The solutions are not unique. Consider
where z is an arbitrary n × 1 vector.
 |
|
Slide 6 |
A generalized inverse C of a matrix A is said to
be reflexive if
CAC = C.
Exercise: Let  and
 re present any generalized inverses of
a matrix A. Then, the matrix  is a reflexive
generalized inverse of A. |
|
Slide 7 |
Theorem: Let C be a generalized inverse of A,
show that C is
reflexive if and only if rank(C)=rank(A).
Proof: The “only if” part is straightforward by noting
rank() ≥ rank(A) for any A. (Exercise)
The “if” part is a bit complicated. Need a couple lemmas (see
be low and the next slide).
Lemma. Let A represent an m × n matrix, then the n × n
matrix A and the m ×m matrix A are both
idempotent.
Proof: (A)(A) = (AA) = A. |
|
Slide 8 |
Lemma. Let A represent an m × n matrix and C an n
×m
matrix. Then if AC is idempotent and rank(AC)=rank(C),
then A is a generalized inverse of C.
First note that rank(AC)=rank(C) implies that
R(AC) = R(C). This means that any v ∈ R(C), v ∈ R(AC).
Specifically, for each of the 1 × m row vector of C, say,
 ,
there exists a m × 1 vector  such that
 . This
implies that C = V AC where  . Then we
have
CAC = V ACAC = V AC = C. Therefore, A is a generalized
inverse of C. |
|
Slide 9 |
Example: Suppose A(n × n) having rank r. Then by
the spectral
decomposition theorem  .
Consider  , then
as  and
 for i ≠ j. Therefore.
and
Consequently C is a reflexive inverse of A. |
|
Slide 10 |
The Moore-Penrose Inverse
Definition The Moore-Penrose inverse of an m × n matrix A,
denoted by  , is an n ×m matrix satisfies the following
condition:
1. AA = A (i.e., is a generalized inverse of A);
2. A = (i.e., A is a generalized inverse of );
3. (A)' = A, (i.e., A is symmetric);
4. (A)' = A, (i.e., A is symmetric).
For any m × n matrix A, the Moore-Penrose inverse exists
and it is unique. How to find the Moore-Penrose inverse? –
via Singular Value Decomposition (later) |
|
Slide 11 |
Non negative Definite Matrices
Definition An n × n matrix A is said to be nonnegative
definite if x'Ax ≥ 0 for every x in Rn.
For a nonnegative definite matrix A, if the null vector 0 is the
only value x for which x'Ax = 0, then A is called positive
definite; otherwise, it is said to be positive semidefinite .
For example, I is positive definite, because for all x,
 ; and JJ0 is positive semidefinite
because . |
|
Slide 12 |
Properties:
1. Let k > 0 represent a (positive) scalar. If A is positive
(semi)definite, then kA is positive (semi)definite.
2. If A and B are nonnegative definite, then A + B are
nonnegative definite.
3. Any positive definite matrix is nonsingular.
Proof: If A is singular, then must exist nonnull vector x
such that Ax = 0, then we have x'Ax = 0, A cannot be
positive definite. |
|
Slide 13 |
Lemma. Let A represent an n × n matrix and P
represent an
n × p matrix. Then if A is nonnegative definite, then P'AP is
nonnegative definite.
Proof: For all x in  , x'(P'AP)x = (Px)'A(Px) ≥ 0 because
 and A is nonnegative definite.
Corollary. Let X represent an arbitrary n × p matrix. The
p × p matrix X'X is nonnegative definite.
Theorem. Every eigenvalue of a nonnegative definite matrix
is nonnegative.
Proof: Ax = λx, x'Ax = x' λx, hence
 . |
|
Slide 14 |
Singular Value Decomposition
Define X (n × p) having rank r and p ≤ n.
XX' (n×n) and X'X (p×p) have the same nonzero eigenvalues
Proof:
On the other hand,
Thus if  is a nonzero eigenvalue for
XX', it must be an
eigenvalue for X'X, and vice versa. |
|
Slide 15 |
Definition: Let X(n× p) have rank r . Let
where  , i = 1, 2, · · · , r are
eigenvectors for XX' associated
with the nonzero eigenvalues, chosen to be orthogonormal;
and  , i = 1, 2, · · · , r are eigenvectors for
X'X associated
with the nonzero eigenvalues, chosen to be orthogonormal.
Singular Value Decomposition (SVD):  . The
Moore-Penrose inverse is given by  . |
