Information Technology Reference
In-Depth Information
THEOREM
6.5.4
The matrix inverse function
f
(
n
)
A
−
1
for arbitrary non-singular
n
×
n
matrices
over an arbitrary field
R
can be computed by an algebraic circuit whose size and depth satisfy the
following bounds:
A
−
1
=Θ(
M
matrix
(
n
,
K
))
D
f
(
n
)
C
f
(
n
)
A
−
1
=
O
(
n
log
2
n
)
Proof
To invert a non-singular
n
n
matrix
M
that is not SPD, form the product
P
=
M
T
M
(which is SPD) with one instance of MULT[
n
] and then invert it. Then multi-
ply
P
−
1
by
M
T
on the right with a second instance of MULT[
n
]. To invert
P
,compute
its
LDL
T
factorization and invert it by forming
L
T
−
1
D
−
1
L
−
1
. Inverting
LDL
T
re-
quires one application of TRI INV[
n
], one application of SCALE[
n
], and one application of
MULT[
n
], in addition to the steps used to form the factorization. Thus, three applications
of MULT[
n
] are used in addition to the factorization steps. The following bounds hold:
C
f
(
n
)
×
A
−
1
4
M
matrix
(
n
,
K
)+
n
2
≤
≤
4
.
5
M
matrix
(
n
)
A
−
1
=
O
n
log
2
n
+
O
(log
n
)=
O
n
log
2
n
The lower bound on
C
f
(
n
)
D
f
(
n
)
A
−
1
follows from Lemma
6.5.1
.
6.5.5 Fast Matrix Inversion*
In this section we present a depth-
O
(log
2
n
)
circuit for the inversion of
n
n
matrices known
as
Csanky's algorithm
, which is based on the method of Leverrier. Since this algorithm uses
a number of well-known matrix functions and properties that space precludes explaining in
detail, advanced knowledge of matrices and polynomials is required for this section.
The determinant of an
n
×
×
n
matrix
A
,
det(
A
)
, is defined below in terms of the set of all
permutations
π
of the integers
.Herethe
sign
of
π
, denoted
σ
(
π
)
,isthenumber
of swaps of pairs of integers needed to realize
π
from the identity permutation.
det(
A
)=
π
{
1, 2,
...
,
n
}
n
1
)
σ
(
π
)
(
−
a
i
,
π
(
i
)
i
=
1
Here
i
=
1
a
i
,
π
(
i
)
is the product
a
1,
π
(
1
)
···
a
n
,
π
(
n
)
.The
characteristic polynomial
of a
matrix
A
,namely,
φ
A
(
x
)
in the variable
x
, is the determinant of
xI
−
A
,where
I
is the
n
×
n
identity matrix:
φ
A
(
x
)= det(
xI
A
)
=
x
n
+
c
n−
1
x
n−
1
+
c
n−
2
x
n−
2
+
−
···
+
c
0
If
x
is set to zero, this equation implies that
c
0
=det(
A
)
.Aso, tcanbeshownthat
φ
A
(
A
)=
0, a fact known as the
Cayley-Hamilton theorem
: A matrix satisfies its own
characteristic polynomial. This implies that
A
A
n−
1
+
c
n−
1
A
n−
2
+
c
n−
2
A
n−
3
+
−
+
c
1
=
···
−
c
0
I
Thus, when
c
0
=
0theinverseof
A
can be computed from
A
−
1
=
−
c
0
A
n−
1
+
c
n−
1
A
n−
2
+
c
n−
2
A
n−
3
+
+
c
1
1
···
Search WWH ::
Custom Search