In this section, I will show a depth-O(log2n) circuit for the inversion of n x n matrices known as Csanky's Algorithm, which is based on the method of Leverrier.
The determinant of an n x n matrix A, det(A), is:
A1,1a1 - A1,2a2 + A1,3a3 - ... - (-1)(n+1)*A1,nan
where A1,j is the entry in row 1 and column j of A and aj is the determinant of the matrix obtained be omitting the first row and column j of A. This is a recursive definition.
Example: The determinant of
é ê ê ë
a
b
c
d
ù ú ú û
is ad-bc.
A determinant of 0 means that the matrix is singular and does not have an inverse.
The characteristic Polynomial of a matrix A, is the determinant of xI - A for a variable x.
To complete a derivation of the Csanky algorithm, we must produce the coefficients
of the characteristic polynomial of A. For this, envoke Leverrier's theorem
which uses the trace of a matrix A or the sum of the elements on A's main
Diagonal.
Theorem 6.5.5) (Leverrier) The coeffiecients of the characteristic polynomial of the n x n matrix A satisfy the following identity, where sr = tr(A) for 1 <= r <= n:
é ê ê ê ê ê ê ë
1
0
0
...
0
s1
2
0
...
0
s2
s1
3
...
0
.
.
.
...
.
sn-1
...
s2
s1
n
ù ú ú ú ú ú ú û
é ê ê ê ê ê ê ë
cn-1
cn-2
cn-3
...
c0
ù ú ú ú ú ú ú û
= -
é ê ê ê ê ê ê ë
s1
s2
s3
...
sn
ù ú ú ú ú ú ú û
Csanky's algorithm computes the traces of the powers, namely the sr's,
and then inverts the lower triangular matrix given above, thereby solving
for the coefficients of the characteristic polynomial. The coefficients
are then used with a prefix computation to compute the inverse. Each of
the n sr's can be computed in O(n) steps once the powers of A have been formed. The lower triangular matrix is non-singluar and
can be inverted by a circuit with Mmatrix(n, K) operations and depth O(log2n), as shown in Theorem 6.5.1. THe following summarizes
these results.
Theorem 6.5.6) The matrix inverse function for non-singular n x n matrices over a field of characteristic zero, f(n)A-1 has
an algebraic circuit whose size and depth satisfy the following: