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

combination of the blue rows of S is zero:

α r , s c nr + s , J = 0

(10.7)

r∈ Γ s∈ Λ r

Here 0 is a column vector of zeros, one per blue row. Again, J is the set of columns of C in
the submatrix S .
Column j of the n γ ) n columns

of S and is bad otherwise. Let G be the indices of the good columns in B and let g =

× n matrix B is good if it is associated with at least ( 1 −

| G | .

Then there are g ≥ ( 1 − γ ) n good columns and b ≤ γn bad columns in B ( g + b = n )

because, if not, g ≤ ( 1 − γ ) n − 1 and the number of columns altogether in S is at most

γ ) n , which is an increasing function of g whose value is less than n 2 γ 2 n 2 gn + b ( 1 − −

when g 1, which is less than the number of columns of S .

Since B has at least g =

≤ ( 1 − γ ) n −

| G |≥ ( 1 − γ ) n good columns and B is γ -nice, any set of up to

rows are linearly independent. In particular, the rows of B indexed by Λ r are linearly
independent. This implies that

γn

α r , s b s , G = 0

s∈ Λ r

where 0 is a zero column with | Λ r | rows. Thus, there must be a column index t ∈ G such

that

α r , s b s , t = 0

(10.8)

s∈ Λ r

Let K =

{ j | nj + t ∈ J }

be the columns of S corresponding to the good column of B

with index t . It follows that

| K |≥ ( 1 − γ ) n

.
Let u i = c i , J∩K , the intersection of the i th row of S with columns whose indices are in
K . Similarly, let v i be the intersection of the i th row of A with columns in K . It follows
from the definition of C that u ni + j = b j , t v i .From( 10.7 )wehavethat

α r , s c nr + s , J∩K = 0

r∈ Γ s∈ Λ r

v r = 0

α r , s b s , t

r ∈ Γ s ∈ Λ r

However, the rows | Γ | rows v r constitute a γn ×| K | submatrix of the γ -nice matrix A

where | K |≥ ( 1 − γ ) n . Since its rows are linearly independent, each of the coefficients

s∈ Λ r α r , s b s , t must be zero, contradicting the statement of ( 10.8 ). It follows that C =
A B is γ 2 -ok. ⊗

10.13 Applications of the Borodin-Cook Method
In this section we illustrate the Borodin-Cook method of Section 10.11 by applying it to a
variety of representative problems.