Bayro-Corrochano E., Scheuermann G. Geometric Algebra Computing: in Engineering and Computer Science

Подождите немного. Документ загружается.

438 R. Schott and G.S. Staples

Notation To simplify the notation, tr(Λ

) is replaced by τ

in the remainder of the

paper.

Using the Coppersmith–Winograd algorithm, multiplying two n × n matrices

can be done in O(n

2.376

) time [5]. It is not clear that the same asymptotic speedup

can be accomplished for the C case. However, in the remainder of the paper, β

will represent the exponent associated with matrix multiplication. In the worst case,

multiplication of two n × n matrices with entries in C

nil

requires n

Cops, so

β ≤3.

Corollary 1 Enumerating the k-cycles in a ﬁnite graph on n vertices requires

O(n

logk) Cops in C

nil

Corollary 2 Enumerating the Hamiltonian cycles in a ﬁnite graph on n vertices

requires O(n

logn) Cops in C

nil

Corollary 3 Let Λ be the nilpotent adjacency matrix of an n-vertex graph G. Let

m,

denote the number of -tuples of pairwise disjoint m-cycles appearing in the

graph G, where m ≥3 and 1 ≤ ≤n/m. Then



(τ

)





=(2m)



!X

m,

. (16)

Computational Complexity Reductions Using Clifford Algebras 439

The following proposition is an immediate corollary of Theorem 1.

Proposition 1 (Graph circumference) Let G be a graph on n vertices with nilpotent

adjacency matrix Λ. The length of the longest cycle in G is the largest integer k such

that

=0. (17)

Corollary 4 Computing the circumference of a graph on n vertices requires

O(n

logn) Cops in C

nil

Proof Computing τ

requires O(n

logn) Cops. 

Example 2 The circumference and girth of the graph in Fig. 2 are computed using

Mathematica.

Fig. 2 A randomly generated graph on 16 vertices

440 R. Schott and G.S. Staples

Corollary 5 (Graph girth) Let G be a graph on n vertices with nilpotent adjacency

matrix Λ. The length of the shortest cycle in G is the smallest integer k such that

=0. (18)

The complexity of computing a graph’s girth can now be determined in the same

manner as the complexity of computing circumference.

Corollary 6 Computing the girth of a graph on n vertices requires O(n

logn)

Cops in C

nil

In the next proposition, C denotes the diagonal matrix Diag(ζ

,...,ζ

).Itisused

to account for the initial vertices of paths in G.

Proposition 2 (Longest path) Let G be a graph on n vertices with nilpotent adja-

cency matrix Λ. The length of the longest path in G is the largest integer k such

that

CΛ

=0. (19)

Here, 0 denotes the n ×n zero matrix.

Corollary 7 Computing the length of the longest path in a graph on n vertices

requires O(n

(logn)

) Cops in C

nil

Proof The maximum possible path length is n. For each 1 ≤k ≤n, computing CΛ

requires O(n

logk +n

) = O(n

logn) Cops. Using binary search then requires

testing O(log n) values of k in Proposition 2. 

4 Matrix-Free Approach to Representing Graphs

Some of the complexity results recalled in the previous section can be improved

by eliminating the nilpotent adjacency matrix. Moreover, the matrix-free approach

facilitates additional results such as the enumeration of matchings.

Let G =(V , E) be a graph on n vertices. The adjacency structure of G is repre-

sented uniquely within C

nil

Γ =



}∈E(G)

}

. (20)

In particular, note that Γ is a sum of bivectors representing edges of G by using

each edge’s incident vertices as indices.

Denote by C

nil

⊗ R[t] the ring of polynomials in the unknown t with C

nil

coefﬁcients.

Computational Complexity Reductions Using Clifford Algebras 441

Proposition 3 Let G be a graph on n vertices with Γ ∈ C

nil

as deﬁned in (20).

Let M denote the number of edges in a maximal matching of G. Then, e

tΓ

is a

polynomial in C

nil

⊗R[t], and

M =deg

tΓ

. (21)

Proof Note that each edge of G is uniquely identiﬁed by the pair of vertices with

which it is adjacent. Let k be a nonnegative integer such that k ≤

. From con-

struction of Γ it follows that Γ

is a sum of blades representing k-subsets of edges

of G. Moreover, by the null-square property of the vertex labels ζ

, such k-subsets

of edges must represent k-matchings of G, since two edges incident with a common

vertex would result in a blade with a squared generator.

Let V

denote the collection of subsets of V representing the vertices incident

with edges in a k-matching of G and note that |V

|=2k.Fori ∈V

,letα

denote

the number of k-matchings on the vertex set i

, observe that Γ



= 0 for all >

and that Γ

=k!



i∈V

. Hence,

tΓ

∞



k=0

(tΓ )

n/2



k=0

(tΓ )

n/2



k=0



i∈V

. (22)

It follows immediately that deg

tΓ

= k if and only if k is the greatest integer

for which a k-matching of G exists. 

Example 3 Figure 3 shows Mathematica code used to generate the random bipartite

graph on 14 vertices pictured below and compute the size of a maximal matching.

Fig. 3 Mathematica code for matchings example

442 R. Schott and G.S. Staples

The Mathematica package Combinatorica is used to corroborate the result of Propo-

sition 3.

Corollary 8 The problem of computing the size of a maximal matching in a graph

on n vertices is of complexity O(n) in C

nil

Proof Evaluating e

tΓ

is accomplished by computing t

n/2

, which requires

O(log(n/2)) Cops in C

nil

when successive squaring is used. Computing all inter-

mediate powers, summing and multiplying scalars results in O(n) Cops. 

Recalling that a perfect matching of a graph on an even number n of vertices is a

matching containing n/2 vertices, the following result is immediate.

Corollary 9 Counting the perfect matchings of a bipartite graph on n vertices is of

complexity O(logn) in C

nil

In light of this result, an improvement on the matrix permanent is expected. It

is known that counting the perfect matchings of a bipartite graph is of the same

complexity as computing the permanent of its adjacency matrix.

The problem of computing the permanent of a matrix is known to be P-

complete [3, 23]. Methods of approximating the permanent using Clifford algebras

have also been discussed [4].

Proposition 4 Let M =(m

)

n×n

denote an arbitrary n × n matrix. Let {ζ

}

1≤i≤n

denote commutative null-square generators of C

nil

, and deﬁne a



j=1

for each i =1, 2,...,n. Then,



i=1

=per(M)ζ

[n]

. (23)

Computational Complexity Reductions Using Clifford Algebras 443

Proof Recall the deﬁnition of the matrix permanent:

per(M) :=



σ ∈S



i=1

iσ(i)

. (24)

Note that i =j ⇒σ(i)=σ(j).

Now consider the product



i=1



i=1

i 1

+···+m

)



,...,k

)∈[n]

···m

···ζ

. (25)

The null-square property of the collection {ζ

} implies that the sum is over n-

tuples of distinct integers:



,...,k

)∈[n]

···m

···ζ



,...,k

)∈[n]

i=j ⇒k

=k

···m

···ζ



σ ∈S

1σ(1)

2σ(2)

···m

nσ (n)

[n]

=per(M)ζ

[n]

. (26)



An immediate corollary gives the complexity of computing the permanent of an

n ×n matrix.

Corollary 10 Computing the permanent of an arbitrary n ×n matrix requires O(n)

Cops in C

nil

Example 4 A randomly generated binary matrix is generated, and its permanent is

computed in Fig. 4.

The corresponding elements of C

nil

appear in Fig. 5.

The product



i=1

is computed in Fig. 6. Note that the loop performs 15 =

n −1 multiplications in C

nil

Allowing cycles of length two, the permanent of a graph’s adjacency matrix

counts the number of cycle covers of the graph. This is clear from the deﬁnition

of permanent (24) when one recalls that every permutation σ ∈S

can be written as

a product of disjoint cycles.

444 R. Schott and G.S. Staples

Fig. 4 Random matrix and its permanent

Corollary 11 (Complexity of cycle covers) Counting the cycle covers of a ﬁnite

graph on n vertices requires O(n) Cops in C

nil

Example 5 The graph associated with the matrix appearing in Example 4 is shown

in Fig. 7. The number of cycle covers of this graph is 9.

We now introduce a method for computing the girth and counting the proper

cycle covers of a graph. The adjacency structure of a graph G on n vertices is rep-

resented within C

3nil

⊗C

nil

|E|

Ξ =



}∈E(G)

}

. (27)

Here, each edge {v

} of G is associated with a single generator ζ

of C

nil

|E|

while each vertex is associated with a generator of C

3nil

Computational Complexity Reductions Using Clifford Algebras 445

Fig. 5 Elements of C

nil

associated with random binary matrix of Fig. 4

Fig. 6 Product



i=1

=per(A)ζ

[16]

Fig. 7 Graph associated with

matrix A of Example 4

Observe that a path of length m in a connected graph consists of m edges and

m +1 vertices. Hence, any path is also a tree. However, in order for a tree to be a

path, each vertex must be incident with no more than two vertices. Labeling vertices

with elements ξ

satisfying ξ

=0 allows us to “sieve out” paths.

Recall that the term proper cycle refers to any cycle of length greater than two.

It is now possible to obtain an upper bound on the number of Hamiltonian

paths in a graph by considering the dimension of the smallest subspace containing

Ξ



(2(n−1),n)

. For convenience, the following notation is deﬁned.

446 R. Schott and G.S. Staples

Deﬁnition 5 Let A be an algebra, and let u ∈A. Then the dimension of u is deﬁned

as the dimension of the smallest linear subspace S of A such that u ∈ S. In other

words,

dim(u) = min

{S:A⊇Su}

dim(S). (28)

Proposition 5 Let G be a graph on n vertices with Ξ ∈ C

3nil

⊗C

nil

|E|

as deﬁned

in (27). Let X denote the number of coverings of vertices of G by a Hamiltonian

path or exactly one path and one or more disjoint proper cycles. Then,

dim





(n,n−1)



=X. (29)

Proof Each nonzero coefﬁcient of the expansion of Ξ



(n,n−1)

corresponds to a

unique subgraph G



of G having n vertices and n −1 edges. Moreover, each vertex

has maximum degree two. In light of Lemmas 1 and 2, it follows that either G



is a

Hamiltonian path or G



consists of exactly one path and one or more disjoint proper

cycles as connected components. 

An immediate consequence of Proposition 5 is the following result concerning

Hamiltonian paths.

Corollary 12 Let G be a graph on n vertices with Ξ ∈C

3nil

⊗C

nil

|E|

as deﬁned in

(27). Let H denote the number of Hamiltonian paths in G. Then,

dim





(n,n−1)



=0 ⇒ H =0, (30)

and

H ≤dim





(n,n−1)



. (31)

Proposition 6 Let G be a graph on n vertices with Ξ ∈ C

3nil

⊗C

nil

|E|

as deﬁned

in (27). Let k be a positive integer. Then each term in the expansion of Ξ



(k,k)

rep-

resents a covering of G with proper cycles; that is, each term represents a subgraph



whose connected components are disjoint cycles of minimum length 3.

Proof By properties of Ξ ∈ C

3nil

⊗ C

nil

|E|

, each term of Ξ

 corresponds to a

subgraph G



of G having k vertices and k edges. Moreover, the degree of each

vertex is less than or equal to two. By Lemma 2, the connected components of G



are cycles. Since edges are labeled with null-square generators of C

nil

|E|

, these cycles

contain no repeated edges and are therefore proper. 

An immediate consequence of Proposition 6 is the following result concerning

Hamiltonian cycles.

Computational Complexity Reductions Using Clifford Algebras 447

Corollary 13 Let G be a graph on n vertices with Ξ ∈ C

3nil

⊗C

nil

|E|

as deﬁned

in (27). Let Z

denote the number of Hamiltonian cycles in G. Then,

dim





(n,n)



=0 ⇒ Z

=0, (32)

and

≤dim





(n,n)



. (33)

Example 6 For each k = 3, 4,...,8, the grade (k, k) part of Ξ

is computed us-

ing Mathematica for a randomly generated graph on eight vertices. Each nonzero

term of Ξ



(k,k)

corresponds to a covering of a k-vertex subgraph using disjoint

cycles of length j ≤ k. The fact that Ξ



(8,8)

= 0 implies that the graph contains

no Hamiltonian cycles.

In the Mathematica implementation of products of null-cubes, the multiindex is

deﬁned by a vector in Z

according to



j=1

. (34)