Chicago Journal of Theoretical Computer Science

The MIT Press

Volume 1997 Article 5 31 December 1997

ISSN 1073–0486. MIT Press Journals, Five Cambridge Center, Cambridge, MA 02142-1493 USA; (617)253-2889; journals-orders@mit.edu, journals-info@mit.edu. Published one article at a time in L^{A}TEX source form on the Internet. Pagination varies from copy to copy. For more information and other articles see:

• http://mitpress.mit.edu/CJTCS/

• http://www.cs.uchicago.edu/publications/cjtcs/

• ftp://mitpress.mit.edu/pub/CJTCS

• ftp://cs.uchicago.edu/pub/publications/cjtcs Mahajan and Vinay Determinant (Info)

The Chicago Journal of Theoretical Computer Science is abstracted or indexed in Research Alert,◯^{R}SciSearch,◯^{R}Current Contents◯^{R}/Engineering Computing & Technology, and CompuMath Citation Index.◯^{R}

\begin{matrix}c \\ ◯ \end{matrix}1997 The Massachusetts Institute of Technology. Subscribers are licensed to use journal articles in a variety of ways, limited only as required to insure fair attribution to authors and the journal, and to prohibit use in a competing commercial product. See the journal’s World Wide Web site for further details. Address inquiries to the Subsidiary Rights Manager, MIT Press Journals; (617)253-2864; journals-rights@mit.edu.

The Chicago Journal of Theoretical Computer Science is a peer-reviewed scholarly journal in theoretical computer science. The journal is committed to providing a forum for significant results on theoretical aspects of all topics in computer science.

Editor in chief: Janos Simon

Consulting editors: Joseph Halpern, Stuart A. Kurtz, Raimund Seidel

Editors:

Martin Abadi  Greg Frederickson John Mitchell
Pankaj Agarwal Andrew Goldberg Ketan Mulmuley
Eric Allender Georg Gottlob Gil Neiger
Tetsuo Asano  Vassos Hadzilacos David Peleg
Laszló Babai  Juris Hartmanis Andrew Pitts
Eric Bach  Maurice Herlihy James Royer
Stephen Brookes Ted Herman  Alan Selman
Jin-Yi Cai  Stephen Homer  Nir Shavit
Anne Condon  Neil Immerman  Eva Tardos
Cynthia Dwork Howard Karloff  Sam Toueg
David Eppstein Philip Klein  Moshe Vardi
Ronald Fagin  Phokion Kolaitis Jennifer Welch
Lance Fortnow Stephen Mahaney Pierre Wolper
Steven Fortune Michael Merritt

Managing editor: Michael J. O’Donnell

Electronic mail: chicago-journal@cs.uchicago.edu

[ii]

Determinant: Combinatorics, Algorithms, and Complexity^{∗}

Meena Mahajan  V. Vinay

31 December, 1997

Abstract

We prove a new combinatorial characterization of the determi-

Abstract-1

nant. The characterization yields a simple combinatorial algorithm for computing the determinant. Hitherto, all (known) algorithms for the determinant have been based on linear algebra. Our combinatorial algorithm requires no division, and works over arbitrary commutative rings. It also lends itself to efficient parallel implementations.

It has been known for some time now that the complexity class

Abstract-2

GapL characterizes the complexity of computing the determinant of matrices over the integers. We present a direct proof of this characterization.

1 Introduction

The determinant has been a subject of study for over 200 years. Its history

1-1

can be traced back to Leibnitz, Cramer, Vandermode, Binet, Cauchy, Jacobi, Gauss, and others. Given its importance in linear algebra in particular and in geometry in general, it is not surprising that a galaxy of great mathematicians investigated the determinant from varied viewpoints.

The algorithmic history of the determinant is as old as the mathemati-

1-2

cal concept itself. After all, the determinant was invented to solve systems of linear equations. Much of the initial effort was expended on proving the

Mahajan and Vinay Determinant §1

1 so-called “Cramer’s rule,” “Laplace expansion,” and the “Cauchy-Binet theorem,” and these led to a variety of interesting algebraic identities. The first definitions of determinant used inversions as a means of computing the signs of permutations. Cauchy realized that the sign of a permutation can be more easily computed by considering the permutation’s cycle decomposition: if k is the number of cycles in the decomposition of a permutation over S_{n}, he showed that (−1)^{n−k} computes the sign. In a sense, Cauchy appears to have started the combinatorial approach to determinants.

∗A preliminary version of this paper appeared in [MV97a].

The so-called “Gaussian elimination” is a standard procedure for calcu-

1-3

lating the determinant. It converts a given matrix into an upper triangular matrix using elementary row operations, which maintain the value of the determinant, and uses O(n^{3}) operations. It can be shown that the sizes of numbers in the intermediate steps are small, and this gives rise to a polynomial time algorithm. This algorithm, however, appears to be sequential. In its present form, the algorithm would require division, rendering it useless over arbitrary rings. To use this method over a ring, one considers a field extension (e.g., for computing the determinant over integers, compute using rationals). While theoretically correct, this procedure often introduces a computational problem; for instance, over integers, because of the divisions involved, this method may needlessly introduce floating point errors. Thus, in several situations, a division-free method that still has polynomial bit complexity would be preferable to Gaussian elimination.

Numerical analysts have looked closely at the problem of computing the

1-4

determinant, and also the associated problem of computing the characteristic polynomial of a given matrix. An authoritative book on this subject is due to Fadeev and Fadeeva [FF63]. The book lists more than half a dozen methods for computation of the characteristic polynomial. The most important among them seem to be Krylov’s method, Leverier’s method, and Samuelson’s method. Csanky [Csa76] observes that Leverier’s method may be implemented in NC^{2}. However, Leverier’s method uses division, and hence is unsuitable over arbitrary fields. (The method is applicable only over fields of characteristic zero or over fields with characteristic greater than the dimension of the matrix, so the algorithm cannot be used, in general, over finite fields.) Berkowitz [Ber84] observes that Samuelson’s method [Sam42] is division free and may be implemented in NC^{2}. Valiant [Val92] analyzes the nature of monomials that result from Samuelson’s method. Independently, Chistov [Chi85] uses arithmetic over polynomials to come up with a division-free NC^{2} algorithm. Thus the Samuelson-Berkowitz algorithm, as

2 well as Chistov’s algorithm, can be used over any commutative ring.

Vinay [Vin91a], Damm [Dam91], and Toda [Tod91] observed indepen-

1-5

dently that DET (as a complexity class) has an exact characterization. They showed that over integers, DET is exactly GapL. That is, any function that is logspace reducible to computing the determinant of a matrix over integers can be computed as the difference of two #L functions. Here, a #L function corresponds to the number of accepting paths in an NL machine; a GapL function corresponds to the difference between the number of accepting paths and the number of rejecting paths in an NL machine, or equivalently, to the difference between two #L functions. This characterization of DET establishes a telling parallel between the complexity of the two major algorithmic problems; namely, the complexity of the permanent vs. the determinant. While Valiant [Val79] shows that computing the permanent is GapP complete, the determinant is complete for GapL; both are complete for counting versions of nondeterministic classes. An interesting feature of the three independent proofs cited above is that they all rely on Samuelson’s method to convert the problem of computing the determinant to iterated matrix multiplication. In this paper, we present a direct and self-contained proof of this theorem.

We give the first combinatorial algorithm for computing the determinant.

1-6

We do this by extending the definition of a permutation to a clow sequence (“clow” being the acronym for “closed walk”). Using a combinatorial proof, we establish that all clow sequences that are not permutations cancel each other, leaving precisely the permutations. We then show how clow sequences may be realized in a simple graph-theoretic model. The model is described by a tuple ⟨G, s, t_{+}, t_{−}⟩, where G is a directed acyclic graph (DAG), and s, t_{+}, t_{−} are distinguished vertices in G. Let paths(G, s, t) compute the number of paths from s to t in G. Then the integer function computed by ⟨G, s, t_{+}, t_{−}⟩ is paths(G, s, t_{+}) − paths(G, s, t_{−}). The model yields a polynomial time algorithm via simple dynamic programming techniques (see Table 1). It characterizes GapL exactly, and also contains characterizations in terms of arithmetic skew circuits [Ven92, Tod91] and arithmetic branching programs, yielding NC^{2} and GapL algorithms (see Tables 2 and 3). The results stand out in contrast to Nisan’s results [Nis91], which show that the determinant cannot be computed by a polynomial-size branching program over a noncommutative semi-ring.

The size of the DAG we construct is about O(n^{4}), with O(n^{6}) edges, and

1-7

may be implemented on an arithmetic skew circuit with O(n^{6}) wires. This 3 compares favorably with the O(n^{18}) implementation of Toda. (In [Tod92], Toda notes that Samuelson’s method can be implemented on arithmetic skew circuits of size n^{18}.)

Our combinatorial proof is inspired by Straubing, who gives a purely

1-8

combinatorial interpretation and a very elegant proof of the Cayley-Hamilton theorem [Str83].

Various other parallel algorithms for computing the determinant (includ-

1-9

ing Chistov’s method and the Samuelson-Berkowitz method) can also be interpreted combinatorially, and correctness can also be proved using purely combinatorial techniques. The objects generated by these algorithms turn out to be variations of clow sequences. Such interpretations for some algorithms are found in [MV97b].

Of course, the combinatorial approach cannot replace the algebraic one

1-10

altogether. However, it can (as we feel it does in this case) offer interesting insights into the nature of a seemingly purely algebraic problem.

2 The Combinatorics

We will start with the definition of the determinant of an n-dimensional

2-1

matrix, A:

det(A) = ∑_{σ∈S_{n}} sgn(σ) ∏_{i} a_{iσ(i)}

The summation is over all permutations on n elements. The sign of a permutation is defined in terms of the number of inversions:

sgn(σ) = (−1)^{number of inversions in σ}

To move to a combinatorial setting, we interpret the matrix A as a

2-2

weighted, directed graph G_{A} on n vertices, where the weight on the directed edge ⟨i, j⟩ is a_{ij}. A permutation in S_{n} therefore corresponds to a cycle cover: the cycle decomposition of the permutation, when interpreted as a graph, induces a partition on the vertex set into disjoint cycles.

This definition cannot be directly converted into an efficient algorithm for

2-3

the determinant, because the number of monomials in the above definition is n!. Since enumeration is out of the question, any algorithm should implicitly count over all monomials. The bottleneck in doing so directly is that these

4 permutations are not easily “factorizable” to allow for a simple implementation. We will get around this problem by enlarging the summation from cycle covers to clow sequences.

A clow is a walk ⟨w_{1}, …, w_{l}⟩ starting from vertex w_{1} and ending at the

2-4

same vertex, where any ⟨w_{i}, w_{i+1}⟩ is an edge in the graph. Vertex w_{1} is the least-numbered vertex in the clow, and is called the head of the clow. We also require that the head occur only once in the clow. This means that there is exactly one incoming edge (⟨w_{l}, w_{1}⟩) and one outgoing edge (⟨w_{1}, w_{2}⟩) at w_{1} in the clow.

A clow sequence is a sequence of clows W = ⟨C_{1}, …, C_{k}⟩ with two prop-

2-5

erties:

1. the sequence is ordered: head(C_{1}) < head(C_{2}) < ⋯ < head(C_{k}), and

2. the total number of edges (counted with multiplicity) adds to exactly n.

A cycle cover is a special type of clow sequence. We will now show how

2-6

to associate a sign with a clow sequence that is consistent with the definition of the sign of a cycle cover. The sign of a cycle cover can be shown to be (−1)^{n+k}, where n is the number of vertices in the graph, and k is the number of components in the cycle cover. The sign of a clow sequence is defined to be (−1)^{n+k}, where n is the number of vertices in the graph, and k is the number of clows in the sequence.

We will also associate a weight with a clow sequence that is consistent

2-7

with the contribution of a cycle cover. The weight of a clow C, w(C), is the product of the weights of the edges in the walk while accounting for multiplicity. For example, w(⟨1, 2, 3, 2, 3⟩) = a_{12}a_{23}^{2}a_{32}a_{31}. The weight of a clow sequence W = ⟨C_{1}, …, C_{k}⟩ is w(W) = ∏_{i} w(C_{i}).

Theorem 1

det(A) = ∑_{W: a clow sequence} sgn(W)w(W)

Proof of Theorem 1 We prove this by showing that the contribution of

Proof of Theorem 1-1

clow sequences that are not cycle covers is zero. Consequently, only the cycle covers contribute to the summation, yielding exactly the determinant.

5

Case 1  Case 2 head v v  head  v

Figure 1: Pairing clow sequences of opposing signs

Our proof defines an involution on a signed set. An involution φ on a

Proof of Theorem 1-2

set is a bijection with the property that φ^{2} is the identity map on the set. The domain is the set of all clow sequences, and their signs define a natural partition of the domain into two sets.

We will now define an involution on this signed set. It has the property

Proof of Theorem 1-3

that a clow sequence that is not a cycle cover is paired with another clow sequence over the same multiset of edges, but with opposing sign. The fixed points of the involution are precisely the cycle covers. This is sufficient to establish the theorem.

The desired involution is the following. Let W = ⟨C_{1}, …, C_{k}⟩ be a clow

Proof of Theorem 1-4

sequence. Choose the smallest i such that ⟨C_{i+1}, …, C_{k}⟩ is a set of disjoint (simple) cycles. If i = 0, the involution maps W to itself. These are obviously cycle covers and the only fixed points. Otherwise, having chosen i, traverse C_{i} starting from the head until one of two things happen:

1. we hit a vertex that touches one of ⟨C_{i+1}, …, C_{k}⟩, or

2. we hit a vertex that completes a simple cycle within C_{i}.

Let us call the vertex v. Given the way we chose i, such a v must exist. Vertex v cannot satisfy both of the above conditions: if v completes a cycle

6 and it touches cycle C_{j}, its previous occurrence (which exists, or else there can be no cycle at v) also touches C_{j}, and the traversal would have stopped at that occurrence.

Case 1-1 Case 1 Suppose v touches C_{j}. We map W to a clow sequence:

W′ = ⟨C_{1}, …, C_{i−1}, C′_{i}, C_{i+1}, …, C_{j−1}, C_{j+1}, … C_{k}⟩

The modified clow, C′_{i}, is obtained by merging C_{i} and C_{j} as follows: insert the cycle C_{j} into C_{i} at the first occurence (from the head) of v. For example, let C_{i} = ⟨8, 11, 10, 14⟩ and C_{j} = ⟨9, 10, 12⟩. Then the new clow is ⟨8, 11, 10, 12, 9, 10, 14⟩. Figure 1 illustrates the mapping.

The head of C′_{i} is clearly the head of C_{i}. The new sequence has the same

Case 1-2

multiset of edges and hence the same weight as the original sequence. It also has one component less than the original sequence.

In the new sequence, vertex v in cycle C′_{i} would have been chosen by our

Case 1-3

traversal, and it satisfies Case 2.

Case 1 □

Case 2 Suppose v completes a simple cycle C in C_{i}. By our earlier argument,

Case 2-1

cycle C cannot touch any of the later cycles. We now modify the sequence W by deleting C from C_{i} and introducing C as a new clow in an appropriate position, depending on the minimum labeled vertex in C, which we make the head of C. For example, let C_{i} = ⟨8, 11, 10, 12, 9, 10, 14⟩. Then C_{i} changes to ⟨8, 11, 10, 14⟩, and the new cycle C = ⟨9, 10, 12⟩ is inserted in the clow sequence.

To show that the modified sequence continues to be a clow sequence, note

Case 2-2

that the head of C is greater than the head of C_{i}; hence C occurs after C_{i}. Also, the head of C is distinct from the heads of C_{j} (i < j ≤ k). In fact, C is disjoint from all cycles C_{j} (i < j ≤ k). (Otherwise, Case 1 would have been true.) Further, the new sequence has the same multiset of edges and hence the same weight as the original sequence. It also has one component more than the original sequence.

Figure 1 illustrates the mapping. In the new sequence, vertex v in cycle

Case 2-3

C′_{i} would have been chosen by our traversal, and it satisfies Case 1.

Case 2 □

7 In both of the above cases, the new sequence constructed maps back to the

Proof of Theorem 1-5

original sequence; therefore, the mapping is a weight-preserving involution. Furthermore, the number of clows in the two sequences differ by one, and hence the signs are opposing. This completes the proof.

Proof of Theorem 1 □

Corollary 1

det(A) = ∑_{W: a clow sequence with head of first clow 1} sgn(W)w(W)

Proof of Corollary 1 In the involution defined above, the head of the first clow in the clow sequence remains unchanged. Also, the head of the first cycle in any cycle cover must be the vertex 1.

Proof of Corollary 1 □

3 The Sequential Algorithm

Given an n×n matrix A, we define a layered, directed acyclic graph H_{A} with

3-1

three special vertices, s, t_{+}, and t_{−}, having the following property:

det(A) = ∑_{ρ: s ⇝ t_{+} path} w(ρ) − ∑_{η: s ⇝ t_{−} path} w(η)

Here the weight of a path is simply the product of the weights of the edges appearing in it. The idea is that s ⇝ t_{+} (s ⇝ t_{−} ) paths will be in one-to-one correspondence with clow sequences of positive (negative) sign.

The vertex set of H_{A} is {s, t_{+}, t_{−}} ∪ {[p, h, u, i] | p ∈ {0, 1}, h, u ∈ 3-2

{1, …, n}, i ∈ {0, …, n − 1}}. If a path from s reaches a vertex of the form [p, h, u, i], this indicates that in the clow sequence being constructed along this path, p is the parity of the quantity “n + the number of components already constructed,” h is the head of the clow currently being constructed, u is the vertex that the current clow has reached, and i edges have been traversed so far (in this and preceding clows). Finally, an s ⇝ t_{+} (s ⇝ t_{−} ) path will correspond to a clow sequence where n + the number of components in the sequence is even (odd).

The edge set of H_{A} consists of the following types of edges:

3-3

8 1. ⟨s, [b, h, h, 0]⟩ for h ∈ {1, …, n}, b = n mod 2; this edge has weight 1,

2. ⟨[p, h, u, i], [p, h, v, i + 1]⟩ if v > h and i + 1 < n; this edge has weight a_{uv},

3. ⟨[p, h, u, i], [\overline{p}, h′, h′, i + 1]⟩ if h′ > h and i + 1 < n; this edge has weight a_{uh},

4. ⟨[p, h, u, n − 1], t_{+}⟩ if p = 1; this edge has weight a_{uh}, and

5. ⟨[p, h, u, n − 1], t_{−}⟩ if p = 0; this edge has weight a_{uh}.

Theorem 2 For an n-dimensional matrix A, let H_{A} be the graph described above. Then

det(A) = ∑_{ρ: s ⇝ t_{+} path} w(ρ) − ∑_{η: s ⇝ t_{−} path} w(η)

Proof of Theorem 2 We will establish a one-to-one correspondence be-

Proof of Theorem 2-1

tween s ⇝ t_{+} (s ⇝ t_{−}) paths and clow sequences of positive (negative) sign, preserving weights. The result then follows from Theorem 1.

Let W = ⟨C_{1}, …, C_{k}⟩ be a clow sequence of positive sign (i.e., n + k is

Proof of Theorem 2-2

even). We will demonstrate a path from s to t_{+} in H_{A}. Let h_{i} be the head of clow C_{i}, and let n_{i} be the number of edges in clows C_{1}, …, C_{i−1}. The path we construct will go through the vertices [p, h_{i}, h_{i}, n_{i}], where p = 0 if n + i is odd, and p = 1 otherwise. From s, clearly we can go to the first such vertex [n mod 2, h_{1}, h_{1}, 0]. Assume that the path has reached [p, h_{i}, h_{i}, n_{i}]. Let the clow C_{i} be the sequence ⟨h_{i}, v_{1}, …, v_{l−1}⟩, a closed walk of length l. Starting from [p, h_{i}, h_{i}, n_{i}], H_{A} has a path through vertices [p, h_{i}, v_{1}, n_{i} + 1], [p, h_{i}, v_{2}, n_{i} + 2], …, [p, h_{i}, v_{l−1}, n_{i} + (l − 1)], and finally [\overline{p}, h_{i+1}, h_{i+1}, n_{i} + l], which is the vertex [\overline{p}, h_{i+1}, h_{i+1}, n_{i+1}]. At the last clow, starting from [1, h_{k}, h_{k}, n_{k}], H_{A} has a path tracing out the vertices of clow C_{k} and finally making a transition to t_{+}. Clearly, the weight of the path is identical to the weight of the clow sequence. See Figure 2.

Conversely, let ρ be an s ⇝ t_{+} path in H_{A}. In the sequence of vertices

Proof of Theorem 2-3

visited along this path, the second component of the vertex labels is monotonically nondecreasing and takes, say, k distinct values h_{1}, …, h_{k}. Also, the first component changes exactly when the second component changes, and is n mod 2 at h_{1} and 1 at h_{k} (to allow an edge to t_{+}), so n + k must be even.

9

1  2  4 7  5  3  8  6 10  9 11 1  2  4 7  5  8  6 10  9 11^{[0, 1, 1, 0]}^{[0, 1, 7, 1]}  ^{[0, 1, 2, 3]}^{[0, 1, 2, 5]}^{[0, 1, 4, 2]}^{[0, 1, 5, 4]}  ^{[1, 3, 10, 7]}^{[1, 3, 8, 8]}  ^{[0, 6, 6, 9]}^{[0, 6, 11, 10]}^{[0, 6, 9, 11]} 3 ^{[1, 3, 3, 6]} s  parity of number of components current vertex edges seen so far head of current clow

Figure 2: From a clow sequence to a path 10

Chicago Journal of Theoretical Computer Science 1997-5 Consider the maximal segment of the path with second component h_{i}.

Proof of Theorem 2-4

The third components along this segment constitute a clow with leader h_{i} in G_{A}. When this clow is completely traversed, a new clow with a larger head must be started, and the parity of the number of components must change. But this is precisely modeled by the edges of H_{A}. Therefore, ρ corresponds to a clow sequence of positive sign in G_{A}.

A similar argument shows the correspondence between paths from s to

Proof of Theorem 2-5

t_{−} and clow sequences with negative sign, preserving weights.

Proof of Theorem 2 □

Now, to evaluate det(A), we merely need to evaluate the weighted sums of

3-4

paths. But this can easily be done using simple dynamic programming techniques; we give a polynomial time algorithm that evaluates this expression and hence computes det(A).

We say that a vertex [p, h, u, i] is at layer i in H_{A}. Vertices t_{+} and t_{−} are

3-5

at layer n. The algorithm proceeds by computing, in stages, the sum of the weighted paths from s to any vertex at layer i in H_{A}. After n stages, it has the values at t_{+} and t_{−}, and therefore it also has det(A). See Table 1.

This algorithm processes each edge in H_{A} exactly once, and for each edge,

3-6

it performs one addition and one multiplication. The total number of vertices in H_{A} is 2n^{3} + 3. However, H_{A} is quite a sparse graph; the total number of edges is at most 4n^{4}. The overall running time is therefore O(n^{4}). In fact, if G_{A} has m edges, then H_{A} has only O(mn^{2}) edges, so for sparse matrices, the algorithm is faster.

The number of operations (addition or multiplication) is O(n^{4}). The

3-7

largest partial product at any stage is m^{n}|a_{max}|^{n}, where a_{max} is the largest entry in A, m is the number of edges in G_{A}, and m^{n} is an upper bound on the number of clow sequences. This can be represented with N = n log m + n log |a_{max}| bits, so each operation needs at most M(N) time, where M(t) is the time required to multiply two t-bit numbers. Clearly, even in terms of bit complexity, the algorithm needs only polynomial time.

The space used in this implementation is also polynomial; however, it is

3-8

only O(n^{2}), since at any stage the values at only two adjacent layers need to be stored. (Again, there are O(n^{2}) values to be stored; each may require up to N bits.)

11 # Initialize values to 0 For u, v, i ∈ [n], p ∈ {0, 1} do V ([p, u, v, i − 1]) = 0 V (t_{+}) = 0 V (t_{−}) = 0 # Set selected values at layer 0 to 1 b = n mod 2 For u ∈ [n], do V ([b, u, u, 0]) = 1 # Process outgoing edges from each layer For i = 0 to n − 2 do

For u, v ∈ [n] such that u ≤ v, and p ∈ {0, 1}, do

For w ∈ {u + 1, …, n} do
V ([p, u, w, i + 1]) = V ([p, u, w, i + 1]) + V ([p, u, v, i]) · a_{vw}

V ([p̄, w, w, i + 1]) = V ([p̄, w, w, i + 1]) + V ([p, u, v, i]) · a_{vu}

For u, v ∈ [n] such that u ≤ v, and p ∈ {0, 1}, do V (t_{+}) = V (t_{+}) + V ([1, u, v, n − 1]) · a_{vu}

V (t_{−}) = V (t_{−}) + V ([0, u, v, n − 1]) · a_{vu}

# Compute the determinant Return V (t_{+}) − V (t_{−})

Table 1: A sequential algorithm for the determinant

4 Computing the Characteristic Polynomial

Our technique can be used as easily to compute all coefficients of the charac-

4-1

teristic polynomial Φ_{A}(λ) = det(λI_{n} − A) = c_{n}λ^{n} + c_{n−1}λ^{n−1} + ⋯ + c_{1}λ + c_{0} of the matrix A. In fact, we will show that the graph defined in the previous section already does so. Rewriting det(λI_{n} − A) in terms of cycle covers and regrouping terms, we see that c_{r}, the coefficient of λ^{r} in Φ_{A}(λ), can be computed by summing, over all permutations of σ with at least r fixed points, the weight of the permutation outside these fixed points:

c_{r} = ∑_{S⊆[1,...,n]:|S|=r} ∑_{σ∈S_{n}:j∈S⇒σ(j)=j} sgn(σ) ∏_{i∉S}(−a_{iσ(i)})

If σ fixes all of the points in S, let sgn(σ|S) denote the parity of the number of components of σ, not counting the fixed-point cycles of S (+1 if the parity

12 is even, and −1 otherwise). Then

c_{r} = ∑_{S⊆[1,...,n]:|S|=r} ∑_{σ∈S_{n}:j∈S⇒σ(j)=j} sgn(σ|S) ∏_{i∉S}(a_{iσ(i)})

But each term here is the weight of a partial cycle cover, covering exactly n−r vertices. To compute this sum, not surprisingly, we look at partial clow sequences! An l-clow sequence is a sequence of clows (ordered by strictly increasing head) with total number of edges exactly l, accounting for multiplicity. Its sign is (−1)^{k}, where k is the number of clows in the sequence. The involution on the set of l-clow sequences is defined in the same fashion as in Section 2, and shows that the net contribution of sequences that are not partial cycle covers is zero. So now instead of H_{A}, we construct H_{A}(r) with n − r layers, with paths corresponding to (n − r)-clow sequences. We then compute the weights of s ⇝ t_{+} and s ⇝ t_{−} paths in this reduced graph, and report the difference as c_{r}.

Actually, all coefficients can be computed using the single graph H_{A}, by

4-2

introducing n copies of t_{+} and t_{−} (one for each coefficient). Further, in this graph, if the ith layer reports a nonzero value, we can immediately conclude that the matrix has rank at least i. However, we do not know how to infer small rank from this construction.

Note that our graphs H_{A}, or H_{A}(r) for computing the coefficient c_{r}, have

4-3

a very regular structure: the edge connectivity across layers is identical. By dropping layer information from the vertices, we can construct a graph (finitestate automaton) with O(n^{2}) vertices. Then to compute c_{r} for 0 ≤ r ≤ n−1, we find the contribution of s ⇝ t_{+} or t_{−} paths in this graph of length exactly n − r.

5 Improving the Algorithm

The algorithm of Section 3 can be made more efficient if the number of ver-

5-1

tices and edges in the graph H_{A} can be pruned. One simple saving is obtained by noting that we do not really need two copies of each vertex [p, u, v, i] for the two values of p. Instead, we can keep one copy, and where in the original H_{A} this component was to be changed via an edge ⟨[p, u, v, i], [\overline{p}, x, y, i + 1]⟩ of weight w, we now have an edge from [u, v, i] to [x, y, i+1] with weight −w. This reduces the number of vertices by a factor of 2. More crucially, it allows the dynamic programming algorithm to do subtractions and cancellations at

13 earlier layers, so the size of partial products, and hence the bit complexity, decreases.

Another pruning which also results in a saving by a constant factor (but

5-2

with a larger constant than above) follows from this simple observation: paths going through vertices of the form [p, h, u, i] with h > i+1 cannot correspond to cycle covers. This is because in a cycle cover, all vertices are covered exactly once, so at layer i, with n − i vertices still to be covered, the head (minimum element) of the current cycle cannot be greater than i. Alternatively, once h becomes the head, at least h − 1 edges should have been seen in preceding cycles. We also can require our clow sequences to satisfy this property. We formalize the prefix property as follows: a clow sequence W = ⟨C_{1}, …, C_{k}⟩ has the prefix property if for 1 ≤ j ≤ k, the total lengths of the clows C_{1}, …, C_{j−1} are at least head(C_{j}) − 1.

It is easy to verify that the involution defined in Section 2 also works

5-3

on such restricted clow sequences: φ(W) has the prefix property if and only if W does. So we may instead construct a pruned version of H_{A} which generates only such clow sequences. (Consider the induced subgraph of H_{A} obtained by deleting all vertices [p, h, u, i] where h > i + 1.) This will lead to an algorithm with essentially the same complexity, but smaller constants. Pruning, however, is not without its drawbacks: after pruning, we can no longer directly extract the coefficients of the characteristic polynomial.

Interestingly, clow sequences with the prefix property are precisely the

5-4

terms computed by Samuelson’s method for computing the determinant. As observed by Valiant^{1} in [Val92], the correctness of Samuelson’s algorithm gives a proof, based on linear algebra, that such sequences that are not cycle covers “cancel” out. Our involution gives a combinatorial proof of this fact (for details, see [MV97b]).

Of course, if the algorithm is to be used to compute the coefficient c_{r} of

5-5

the characteristic polynomial, then we cannot use this kind of prefix property. The right prefix property for computing c_{r} would be that in the clow sequence W = ⟨C_{1}, …, C_{k}⟩; for 1 ≤ j ≤ k, the total lengths of the clows C_{1}, …, C_{j−1} should be at least head(j)−1−r. The graph H_{A}(r) can be pruned consistent with this property. However, if a single graph is to be used to compute all coefficients, then we must work with the unpruned version.

14

1There is a minor technical error in Valiant’s formulation. He claims that Samuelson’s algorithm generates all clow sequences, referred to there as loop covers. However, his preceding discussion makes it clear that clow sequences without the prefix property are not generated.

Mahajan and Vinay Determinant §6.1

6 Parallel Algorithms: GapL and NC Implementations

In this section, we describe two different approaches toward obtaining paral-

6-1

lel algorithms that exploit the combinatorial Theorem 1. The first approach is to apply the standard divide-and-conquer technique to compute the contributions of all clow sequences, and so directly obtain an NC or PRAM algorithm. The second approach is indirect; we first show how our algorithm places the integer determinant in the class of functions GapL, and then appeal to standard parallelizations of GapL functions. This approach is particularly interesting from the complexity-theory point of view, since the GapL implementation gives a very good instance of how to effectively use nondeterminism in a space-bounded computation.

6.1 PRAM and NC Algorithms

The signed and weighted sum of all clow sequences can be evaluated in par-

6.1-1

allel using the standard divide-and-conquer technique, yielding an NC^{2} algorithm for the determinant. We describe the algorithm below. We first show how to construct an arithmetic SAC^{1} circuit for computing the determinant (an arithmetic polynomially sized circuit with O(log n) depth, where the + gates have unbounded fanin but each × gate has constant fanin). We then show how to implement this circuit as an OROW PRAM algorithm, requiring O(log^{2} n) parallel time. Owner-restricted PRAMs, first introduced in [DR86], are the most restrictive of the PRAM models. In owner-write-restricted PRAMs, each cell is “owned” by one processor, and this is the only processor allowed to write into the cell. In owner-read-restricted PRAMs, a processor is associated with each cell, and only this processor can read the cell’s contents. In an owner-read owner-write (OROW) PRAM, the processor owning a cell for writing is in general different from the processor owning the same cell for reading. For more details, see [DR86, Ros91, FLR96]. We also analyze the bit complexity of our algorithm, and show an implementation in Boolean NC^{2}.

The goal is to sum up the contribution of all clow sequences at the output

6.1-2

gate of the circuit. The output gate is a sum, over all 1 ≤ k ≤ n, of C_{k}, where C_{k} is the sum of the contributions of all clow sequences with exactly k clows. To compute C_{k}, we use a divide-and-conquer approach on the number

15 of clows: any clow sequence contributing to C_{k} can be suitably split into two partial clow sequences, with the left sequence having 2^{⌈log k⌉−1} clows. The heads of all clows in the left part must be less than the head of the first clow in the rightmost part. And the lengths of the left and the right partial clow sequences must add up to n. We can carry this information in the gate label. Let gate g[p, l, u, v] sum up the weights of all partial clow sequences with p clows, l edges, head of first clow u, and heads of all clows at most v. (We need not consider gates where l < p or u > v.) Then C_{k} = g[k, n, 1, n], D_{k} = (−1)^{n+k}C_{k}, and the output is ∑_{k=1}^{n} D_{k}. Further,

g[p, l, u, v] = \begin{cases}∑_{\begin{matrix}2^{q}≤r≤2^{q}+(l−p) \\ u<w≤v \end{matrix}} g[2^{q}, r, u, w − 1] · g[p − 2^{q}, l − r, w, v] & p > 1 \\ g[l, u] & p = 1 \end{cases}

where q = ⌈log p⌉ − 1, i.e., 2^{q} < p ≤ 2^{q+1}. The gate g[l, u] sums up the weights of all clows of length l with head u. This gate is also evaluated in a divide-and-conquer fashion. A clow with head u is either a self-loop if l = 1, or it must first visit some vertex v > u, find a path of length l − 2 to some vertex w > u through vertices all greater than u, and then return to u. So

g[l, u] = \begin{cases}a_{uu} & l = 1 \\ ∑_{v>u} a_{uv} · a_{vu} & l = 2 \\ ∑_{v,w>u} a_{uv} · c[l − 2, u, v, w] · a_{wu} & otherwise \end{cases}

The gate c[l, u, v, w] sums the weights of all length l paths from v to w going through vertices greater than u. The required values can be computed in O(log n) layers as follows:

\begin{aligned}c[1, u, v, w] & = a_{vw} \\ c[2^{s} + i, u, v, w] & = ∑_{x>u} c[2^{s}, u, v, x] · c[i, u, x, w] \end{aligned}

for s = 0 to ⌈log n⌉−1, i = 1 to 2^{s}. The final circuit description is summarized in a bottom-up fashion in Table 2.

16 # Initialize values for paths of length 1 For u, v, w ∈ [n] : v, w > u do in parallel

c[1, u, v, w] = a_{vw} # Evaluate values of paths of lengths up to 2^{s} For s = 0 to ⌈log n⌉ − 1

For 1 ≤ i ≤ 2^{s} and for u, v, w ∈ [n] : v, w > u do in parallel

c[2^{s} + i, u, v, w] = ∑_{x>u} c[2^{s}, u, v, x] · c[i, u, x, w]

# Evaluate values of single clows For l, u ∈ [n] do in parallel

If l = 1 then g[l, u] = a_{uu}

If l = 2 then g[l, u] = ∑_{v>u} a_{uv} · a_{vu}
If l > 2 then g[l, u] = ∑_{v,w>u} a_{uv} · c[l − 2, u, v, w] · a_{wu}

# Initialize values of partial clow sequences with one clow For l, u, v ∈ [n] : u ≤ v do in parallel

g[1, l, u, v] = g[l, u] # Evaluate values of partial clow sequences with up to 2^{s} clows For s = 0 to ⌈log n⌉ − 1

For 1 ≤ i ≤ 2^{s} and for l, u, v ∈ [n] : (u ≤ v) ∧ (l ≥ 2^{s} + i) do in parallel

g[2^{s} + i, l, u, v] = ∑_{2^{s} ≤ r ≤ l − i; u < w ≤ v} g[2^{s}, r, u, w − 1] · g[i, l − r, w, v]

# Evaluate the sum of clow sequences For k ∈ [n] do in parallel

D_{k} = (−1)^{n+k}g[k, n, 1, n] # Evaluate the determinant Return det(A) = ∑_{k=1}^{n} D_{k}

Table 2: An arithmetic SAC^{1} algorithm for the determinant

Assigning a gate to each variable c[l, u, v, w] or g[l, u] or g[p, l, u, v] or D_{k}

6.1-3

in this algorithm, we obtain an arithmetic circuit with O(n^{4}) gates and depth O(log n). Each + gate has fanin at most O(n^{2}), and each × gate has fanin at most 3. Therefore this is an arithmetic SAC^{1} circuit.

To obtain the desired PRAM implementation, we must first eliminate

6.1-4

the large fanin and fanout gates. Suppose we replace each + gate having fanin f by a binary tree of + gates (i.e., a bounded fanin subcircuit). The

17 number of edges only doubles, and the depth increases by log f. To handle fanout, we reverse the process: we introduce an inverted binary tree of “copy” gates above each gate (a bounded fanout subcircuit). Again, the number of edges only doubles. Note that in the SAC^{1} circuit described above, the maximum fanin of any + gate is O(n^{2}), so the total number of edges in the circuit is O(n^{6}). Applied to the circuit, this procedure yields a bounded fanin, bounded fanout circuit of depth O(log^{2} n) with O(n^{6}) edges. Placing a processor on each gate and associating a memory cell with each edge gives an EREW PRAM algorithm that requires O(n^{6}) processors and runs in O(log^{2} n) parallel time. Reusing processors across layers will give an EREW PRAM algorithm performing O(n^{6}) work and running in O(log^{2} n) parallel time. A little reflection will convince the reader that this EREW implementation satisfies the owner-write and owner-read restrictions; thus we have an OROW PRAM implementation.

Let us consider the bit complexity of the above algorithm. (In the PRAM

6.1-5

model, each addition and each multiplication is considered to be a unitcost operation.) All operations in the SAC^{1} circuit are on N-bit numbers; recall that N = n log n + n log |a_{max}|, where a_{max} is the largest entry in A. Each operation in the above algorithm involves either adding n^{2} numbers or multiplying three numbers, and can be performed in NC^{1} . Plugging in these Boolean circuits at each gate gives a Boolean NC^{2} circuit that computes the determinant.

6.2 The Integer Determinant and GapL

In this section we demonstrate how #L functions (first studied in [ÀJ93])

6.2-1

can be used to compute the determinant. In particular, we show that the determinant can be expressed as the difference of two #L functions, i.e., as a GapL function. This, coupled with the fact that functions in #L can be computed in Boolean NC^{2} (and subtraction is in NC^{1}), provides another approach toward building small-depth circuits for the determinant.

To place things in perspective, we first sketch the history of research

6.2-2

efforts directed toward the connections between the determinant and the function class #L . We denote by Det the function which, given a matrix with integer entries, evaluates to the determinant of the matrix.

Cook [Coo85] introduced NC^{1} reductions; he used NC^{1} Turing reductions

6.2-3

to formally define and study many parallel complexity classes. The decision to use reductions with oracle gates as opposed to many-one NC^{1} reductions

18 is deliberate; in Cook’s view, oracle reductions are more suitable for the study of functions than many-one reductions. Among the parallel complexity classes introduced, Cook defined DET^{∗} to be the class of functions that NC^{1} reducible to Det. Cook also listed many complete problems for DET^{∗}; the most important of them was Iterated Matrix Product (over integers). He observed that Samuelson’s method in fact establishes an NC^{1} reduction from Det to IterMatProd. In the other direction,

IterMatProd ≤ MatrixPowering ≤ MatrixInversion ≤ Det

(All reductions are NC^{1} reductions.)

Unfortunately, the relation NC^{1} ⊆ DLOG does not relativize [Wil87].

6.2-4

This caused some confusion earlier in many papers dealing with the determinant as a complexity class.

In particular, Damm’s claim [Dam91] that the logspace many-one reduc-

6.2-5

tion closure of Det is equivalent to L^{#L}, and Vinay’s claim [Vin91a] that DET^{∗} is equivalent to L^{#L}, are both in error. Also, Immerman and Landau erroneously claimed in the conference version of their paper [IL95] that the quantifier-free projection closure of Det, qfp(Det), equals DET^{∗}.

Buntrock et al. [BDHM92] show that L^{#L} is contained in DET^{∗}. Vinay

6.2-6

and Damm use the following chain to establish their results:

IterMatProd ≤ DiffL ⊆ L^{#L} ⊆ DET^{∗}

Wilson’s results [Wil87] imply that “IterMatProd is complete for DET^{∗}” is inadequate to show that “DET^{∗} equals L^{#L}.” And the proof technique of Buntrock et al. [BDHM92] fails when DET^{∗} is replaced with the weaker logspace many-one reduction closure of the determinant.

In fact, the correct statement should be as follows [Vin91b, Tod91]:

6.2-7

Theorem 3 DET^{∗} = NC^{1}(#L).

Immerman and Landau [IL95] and Toda [Tod91] observe that the Samuelson-

6.2-8

Berkowitz algorithm is in fact a (first-order) projection from Det to IterMatProd. Consequently, by defining (a possibly new class) DET as the logspace manyone closure of the determinant, and by defining GapL as the class containing differences of two #L functions, one can hope for the following theorem:

Theorem 4 DET = GapL.

19 This result was essentially discovered independently by Vinay, Damm,

6.2-9

and Toda (see [Vin91a, Vin91b, Dam91, Tod91, Tod92]) around the same time. The proofs are somewhat different, though. Damm, inspired by Babai and Fortnow’s [BF91] characterization of #P, used (positive) arithmetic straight-line programs with restricted multiplications (the (P)ARM model) to characterize #L. These programs are equivalent to skew arithmetic circuits; in fact, in the #P setting, this equivalence was already known (see [BF91]). Toda and Vinay show how Det is equivalent to the difference between the number of (s, t) paths in two directed acyclic graphs. All the proofs rely on the Samuelson-Berkowitz algorithm. We will now present a complete proof of this theorem.

Proof of Theorem 4 In the forward direction, the result can be seen in a particularly direct way from our sequential implementation of clow sequences in Section 3. Observe that given A, the construction of H_{A} is logspace uniform, and tracing out s ⇝ t_{+} or s ⇝ t_{−} paths can be done by an NL machine. (We must be careful here: the partial products along a path can be too large to be stored in logspace. To traverse an edge of weight |w|, the NL machine should simply branch into w paths and remember only the sign. This way, a path of weight w in H_{A} will generate |w| accepting/rejecting paths of the NL machine.) Essentially, H_{A} gives us a uniform polynomial size, polynomial width branching program, corresponding precisely to GapL.

Table 3 lists the code for an NL machine computing, through its gap

6.2-10

function, the determinant of a matrix A with non-negative integral entries. (Negative integers can be accommodated by appropriately updating the parity variable.) Most steps are easily seen to be possible on an NL machine. The l-way branching is the only step which must be done carefully. Since l can be n bits long, it cannot be stored on the worktape. Instead, the NL machine has to step through the bit description of l on the input tape, and branch accordingly. The details are shown in Table 4.

In the other direction, we follow Toda, who follows Valiant [Val79]. It

6.2-11

essentially suffices to show that counting s ⇝ t paths in an acyclic graph G_{1} (a canonical complete problem for #L) can be reduced to computing the determinant of a matrix. We first replace each edge in G_{1} by a path of length 2, and add edges ⟨t, s⟩ and {⟨u, u⟩ | u ∉ {s, t}}. An s ⇝ t path in G_{1} then corresponds exactly to a cycle cover in this new graph G_{2}, and all cycle covers in G_{2} have a positive sign. The number of s ⇝ t paths in G_{1} therefore

20 Nondeterministically choose head ∈ {1, …, n}. current = head count = 0 If n is odd, then parity = 1 else parity = 0 # [parity, head, current, count] is the vertex traced out in # a clow sequence of G_{A} or an s ⇝ t_{+} or s ⇝ t_{−} path in H_{A} While count < n − 1 do

Nondeterministically choose next ∈ {head, …, n}.

count = count + 1

Branch l-ways, where l = A[current, next].

If next > head then current = next

else Nondeterministically choose newhead ∈ {head + 1, …, n}. parity = (parity + 1) mod2 head = newhead current = head

# At this point, count = n − 1 Branch l-ways, where l = A[current, head]. parity = (parity + 1) mod2 If parity = 0 then accept, otherwise reject.

Table 3: A GapL algorithm for the determinant over non-negative integers

equals det(adj(G_{2})), which equals perm(adj(G_{2})) (by adj(G_{2}) we mean the adjacency matrix of the graph G_{2}).

A canonical complete problem for GapL is counting the difference between

6.2-12

s ⇝ t_{+} paths and s ⇝ t_{−} paths in an acyclic graph G_{1}. To reduce this to computing the determinant of a matrix, a minor modification of the above procedure suffices. We first replace each edge in G_{1} by a path of length 2 as above, then add node x, and add edges ⟨t_{+}, s⟩, ⟨t_{−}, x⟩, ⟨x, s⟩, and {⟨u, u⟩ | u ≠ s}. Each s ⇝ t_{+} path in G_{1} then corresponds to a cycle cover of positive sign in this new graph G_{2} (there are no cycles of even length in the corresponding cycle cover). Also, each s ⇝ t_{−} path in G_{1} corresponds to a cycle cover of negative sign in G_{2}. So the GapL function equals det(adj(G_{2})).

Proof of Theorem 4 □

21 Input: k bits a_{k−1}, …, a_{1}, a_{0} specifying the number l = ∑_{i=0}^{k−1} 2^{i}a_{i} Goal: To produce exactly l paths ending in some prespecified configuration C;

any extra paths produced should be rejecting. NL algorithm

j = 0

While j < k do

Branch 3-ways

On Branch 1, if a_{j} = 0 then reject and exit loop

otherwise enter configuration C and exit loop

On Branches 2 and 3, increment j Endwhile

Table 4: NL code to produce l accepting paths, given l in binary

What is striking is a complexity theoretic analog of the classical Det vs.

6.2-13

Perm problem: they are complete for GapL and GapP, respectively.^{2} A corollary of the proof above shows that for every integer matrix A, there is an integer matrix B whose dimensions are polynomially related to the dimensions of A, such that the determinant of A is the permanent of B. Of course, we do not know if Perm can be reduced to Det in logspace/polynomial time.

The future of the class DET^{∗} is not clear. Allender and Ogihara [AO96]

6.2-14

note that there is no reason to believe that NL is a subset of GapL(=DET). (We mean subset in the following sense: a language is in GapL if its characteristic function is in GapL.) This is because the 0–1 valued functions in DET must differ in at most one accepting path. (However, a recent result of Reinhardt and Allender [RA97] shows that the inclusion is true in a nonuniform setting.) On the other hand, notice that NL is contained in DET^{∗}. In fact, Allender and Ogihara [AO96] consider AC^{0}(Det) and show

perm(A) = ∑_{σ∈S_{n}} ∏_{i} a_{iσ(i)}

Mahajan and Vinay Determinant (Ref)

22 that AC^{0}(Det) corresponds to a certain counting hierarchy LH that may be defined on #L. They also claim (without proof) that if AC^{0}(Det) and DET^{∗} coincide, LH collapses.

2Here, Perm denotes the function which, given an n-dimensional matrix A with integer entries, evaluates to the permanent of A:

Two nice applications of the GapL characterization in Theorem 4 have

6.2-15

been the drastic simplification of Jung’s theorem on PL (see [AO96]) and the characterization of the complexity of computing the rank of a matrix (see [ABO96]).

Acknowledgements

We thank Eric Allender for setting us on the track of pursuing the determinant problem, and for supplying us with several interesting references. We thank an anonymous referee for pointing out that our EREW algorithm from Section 6.1 is even an OROW algorithm.

Acknowledgement of support: Part of this work was done when Meena Mahajan was visiting the Department of Computer Science and Automation, IISc, Bangalore.

References

[ABO96] E. Allender, R. Beals, and M. Ogihara. The complexity of matrix rank and feasible systems of linear equations. In Proceedings of the 28th ACM Symposium on Theory of Computing, pages 161– 167, New York, 1996. ACM.

[ÀJ93] C. Àlvarez and B. Jenner. A very hard log-space counting class. Theoretical Computer Science, 107:3–30, 1993.

[AO96] E. Allender and M. Ogihara. Relationships among PL, #L, and the determinant. RAIRO Theoretical Information and Applications, 30:1–21, 1996.

[BDHM92] G. Buntrock, C. Damm, U. Hertrampf, and C. Meinel. Structure and importance of logspace MOD-classes. Mathematical Systems Theory, 25:223–237, 1992.

23 [Ber84] S. J. Berkowitz. On computing the determinant in small parallel

time using a small number of processors. Information Processing Letters, 18:147–150, 1984.

[BF91] L. Babai and L. Fortnow. Arithmetization: A new method in structural complexity theory. Computational Complexity, 1(1):41–66, 1991.

[Chi85] A. L. Chistov. Fast parallel calculation of the rank of matrices over a field of arbitrary characteristic. In Proceedings of the International Conference Foundations of Computation Theory, volume 199 of Lecture Notes in Computer Science, pages 63–69, Berlin, 1985. Springer.

[Coo85] S. Cook. A taxonomy of problems with fast parallel algorithms. Information and Control, 64:2–22, 1985.

[Csa76] L. Csanky. Fast parallel inversion algorithm. SIAM Journal of Computing, 5:818–823, 1976.

[Dam91] C. Damm. DET=L^{(#L)}. Technical Report Informatik-Preprint 8, Fachbereich Informatik der Humboldt–Universität zu Berlin, 1991.

[DR86] P. Dymond and W. Ruzzo. Parallel RAMs with owned global memory and deterministic context-free language recognition. In Proceedings of the 13th International Colloquium on Automata, Languages and Computing, volume 226 of Lecture Notes in Computer Science, pages 95–104, Berlin, 1986. Springer.

[FF63] D. Fadeev and V. Fadeeva. Computational Methods in Linear Algebra. Freeman, San Francisco, CA, 1963.

[FLR96] H. Fernau, Klaus-Jörn Lange, and Klaus Reinhardt. Advocating ownership. In V. Chandu and V. Vinay, editors, Proceedings of the 16th Foundations of software technology and theoretical Computer Science, volume 1180 of Lecture Notes in Computer Science, pages 286–297, Berlin, December 1996. Springer.

[IL95] N. Immerman and S. Landau. The complexity of iterated multi-

plication. Information and Control, 116(1):103–116, 1995. 24 [MV97a] M. Mahajan and V. Vinay. A combinatorial algorithm for the de-

terminant. In Proceedings of the 8th Annual ACM-SIAM Symposium on Discrete Algorithms, pages 730–738, New Orleans, USA, January 1997.

[MV97b] M. Mahajan and V. Vinay. Determinant: Old algorithms, new insights. Technical Report IMSc-TR97/08/34, The Institute of Mathematical Sciences, Madras, India, 1997.

[Nis91] N. Nisan. Lower bounds for non-commutative computation. In Proceedings of the 23rd Annual Symposium on Theory of Computing, pages 410–418, New York, 1991. ACM.

[RA97] K. Reinhardt and E. Allender. Making nondeterminism unambiguous. In Proceedings of the 38th IEEE Symposium on Foundations of Computer Science, Los Alamitos, CA, 1997. IEEE.

[Ros91] P. Rossmanith. The owner concept for PRAMs. In Proceedings of the 8th Symposium on Theoretical Aspects of Computer Science, STACS, volume 480 of Lecture Notes in Computer Science, pages 172–183, Berlin, 1991. Springer.

[Sam42] P. A. Samuelson. A method of determining explicitly the coefficients of the characteristic polynomial. Annals of Mathatical Statistics, 13:424–429, 1942.

[Str83] H. Straubing. A combinatorial proof of the Cayley-Hamilton theorem. Discrete Mathematics, 43:273–279, 1983.

[Tod91] S. Toda. Counting problems computationally equivalent to the determinant. manuscript, 1991.

[Tod92] S. Toda. Classes of arithmetic circuits capturing the complexity of computing the determinant. IEICE Transactions on Information and Systems, E75-D:116–124, 1992.

[Val79] L. G. Valiant. The complexity of computing the permanent. Theoretical Computer Science, 8:189–201, 1979.

[Val92] L. G. Valiant. Why is Boolean complexity theory difficult? In

M. S. Paterson, editor, Boolean Function Complexity. Cambridge 25 University Press, 1992. London Mathematical Society Lecture Notes Series 169.

[Ven92] H. Venkateswaran. Circuit definitions of nondeterministic complexity classes. SIAM Journal on Computing, 21:655–670, 1992.

[Vin91a] V. Vinay. Counting auxiliary pushdown automata and semiunbounded arithmetic circuits. In Proceedings of the 6th Structure in Complexity Theory Conference, volume 223 of Lecture Notes in Computer Science, pages 270–284, Berlin, 1991. Springer.

[Vin91b] V. Vinay. Semi-unboundedness and complexity classes. PhD thesis, Indian Institute of Science, Bangalore, July 1991.

[Wil87] C. B. Wilson. Relativized NC. Mathematical Systems Theory, 20:13–29, 1987.

26