Space–Time Tradeoffs - Models of Computation: Exploring the Power of Computing - page 512

Proof Let E = ( A

⊗ C T ) B . The goal is to show that the results in the n 2 ×

1 column

vector E are the same as those in the n

n matrix D but in a different order. In particular,
we show that the ni + j entry in the former, namely e ni + j ,1 ,isequaltothe ( i , j ) entry in
D ,namely d i , j .
Given a matrix F ,let f i , j denote its entry in the i th row and j th column. Let f i , −
and f − , j denote the i th row and j th column of F , respectively. Let rows and columns of
matrices be numbered consecutively from zero.
The matrix A

×

C T consists of blocks of n consecutive rows with the i th block con-
taining [ a i ,1 C T , a i ,2 C T , ... , a i , n C T ] .Thu ,the ni + j th entry of E ,namely e ni + j ,1 ,
is the j th entry in the product [ a i ,1 C T , a i ,2 C T , ... , a i , n C T ] B , as shown below, where
( c − , j ) T ( b k , − ) T

⊗

is the inner product of the row vector ( c − , j ) T with the column vector

( b k , − ) T .

n− 1

a i , k ( c − , j ) T ( b k , − ) T e ni + j ,1 =

k = 0

n− 1 n− 1

= a i , k c l , j b k , l

k = 0 l = 0

n− 1 n− 1

= a i , k b k , l c l , j

k = 0 l = 0

= d i , j

This is the desired conclusion.

With this as background, we state the space-time results to compute the product of three
matrices.
THEOREM 10.13.5 There is an integer n 0 > 0 such that for n>n 0 the time T and space
S used by any general branching program to compute the product of three n × n matrices over a

R

commutative ring must satisfy the following inequality:

ST =Ω( n 4 log )

Proof Given a general branching program to compute ABC , no more space or time are
used when the matrices A and C are given specific values. Let them each be γ -nice for
some 0

|R|

1 / 2. The existence of such matrices is established in Lemma 10.12.1 .
From Lemma 10.12.2 we know that the matrix A

≤ γ ≤

⊗ C T

is γ 2 -ok. The result follows from

Theorem 10.13.3 since A

⊗ C T

is n 2

× n 2 .

We are now prepared to state space-time bounds for matrix inversion.

THEOREM 10.13.6 There is an integer n 0 > 0 such that for n>n 0 the time T and space S
used by any general branching program to compute the inverse of a non-singular n

× n matrix over

R

a commutative ring must satisfy the following inequality:

ST =Ω( n 4 log

|R|

)

This lower bound can be achieved to within a multiplicative factor over the range Ω( n 2 ) ≤ T ≤

O ( n 3 ) .