Information Technology Reference
In-Depth Information
We now show that an algorithm to invert SPD matrices can be used to invert arbitrary
non-singular matrices by adding a circuit to multiply matrices.
LEMMA
6.5.2
If
M
is a non-singular
n × n
matrix, then the matrix
P
=
M
T
M
is symmetric
positive definite.
M
can be inverted by inverting
P
and then multiplying
P
−
1
by
M
T
.L t
f
(
n
)
SPD inverse
n
2
n
2
be the inverse function for
n
:
R
→R
×
n
SPD matrices over the field
R
.
Thenthesizeanddepthof
f
(
n
)
R
A
−
1
over
satisfy the following bounds:
C
f
(
n
)
A
−
1
C
f
(
n
)
SPD inverse
+
M
matrix
(
n
,
K
)
≤
SPD inverse
+
O
(log
n
)
Proof
To s h ow t h a t
P
is symmetric we note that
M
T
D
f
(
n
)
A
−
1
D
f
(
n
)
≤
M
T
=
M
T
M
. To show that it is
positive definite, we observe that
x
T
P
x
=
x
T
M
T
M
x
=(
M
x
)
T
M
x
⎛
⎞
2
n
n
⎝
⎠
=
m
i
,
j
x
j
i
=
1
j
=
1
which is positive unless the product
M
x
is identically zero for the non-zero vector
x
.But
this cannot be true if
M
is non-singular. Thus,
P
is symmetric and positive definite.
To i n v e r t
M
,invert
P
to produce
M
−
1
M
T
−
1
. If we multiply this product on the
right by
M
T
, the result is the inverse
M
−
1
.
6.5.2 Schur Factorization
We now de s c r i be
Schur factorization
.Representan
n
×
n
matrix
M
as the 2
×
2matrix
M
=
M
1,1
M
1,2
(6.7)
M
2,1
M
2,2
where
M
1,1
,
M
1,2
,
M
2,1
,and
M
2,2
are
k
×
k
,
k
×
n
−
k
,
n
−
k
×
k
,and
n
−
k
×
n
−
k
matrices,
1. Let
M
1,1
be invertible. Then by straightforward algebraic manipulation
M
can be factored as
M
=
≤
k
≤
n
−
1
M
1,1
IM
−
1
I
0
1,1
M
1,2
0
(6.8)
M
2,1
M
−
1
I
0
S
I
0
1,1
Here
I
and
O
denote identity and zero matrices (all entries are zero) of a size that conforms
to the size of other submatrices of those matrices in which they are found. This is the Schur
factorization. Also,
M
2,1
M
−
1
S
=
M
2,2
−
1,1
M
1,2
is the
Schur complement
of
M
. To show that
M
has this factorization, it suffices to carry out
the product of the above three matrices.
Search WWH ::
Custom Search