Table of Contents
Preface vii
Acknowledgments ix
Combinatorial Algebras and Their Properties 1
1 Introduction 3
1.1 Notational Preliminaries 8
2 Combinatorial Algebra 11
2.1 Six Group and Semigroup Algebras 11
2.1.1 The group of blades Bp,q 12
2.1.2 The abelian blade group p,qsym 18
2.1.3 The null blade semigroup Zn 19
2.1.4 The abelian null blade semigroup Znsym 21
2.1.5 The semigroup of idempotent blades Εn 22
2.1.6 The path semigroup Ωn 23
2.1.7 Summary 24
2.2 Clifford and Grassmann Algebras 26
2.2.1 Grassmann (exterior) algebras 27
2.2.2 Clifford algebras 28
2.2.3 Operator calculus on Clifford algebras 33
2.3 The Symmetric Clifford Algebra clp,qsym 36
2.4 The Idempotent-Generated Algebra clp,qidem 38
2.5 The n-Particle Zeon Algebra clnnil 40
2.6 Generalized Zeon Algebras 44
3. Norm Inequalities on Clifford Algebras 49
3.1 Norms on clp,qp50
3.2 Generating Functions 54
3.3 Clifford Matrices and the Clifford-Frobenius Norm 55
3.4 Powers of Clifford Matrices 58
Combinatorics and Graph Theory 61
4. Specialized Adjacency Matrices 63
4.1 Essential Graph Theory 63
4.2 Clifford Adjacency Matrices 66
4.3 Nilpotent Adjacency Matrices 71
4.3.1 Euler circuits 75
4.3.2 Conditional branching 75
4.3.3 Time-homogeneous random walks on finite graphs 77
5. Random Graphs 81
5.1 Preliminaries 81
5.2 Cycles in Random Graphs 83
5.3 Convergence of Moments 88
6. Graph Theory and Quantum Probability 91
6.1 Concepts 91
6.1.1 Operators as random variables 92
6.1.2 Operators as adjacency matrices 94
6.2 From Graphs to Quantum Random Variables 96
6.2.1 Nilpotent adjacency operators in infinite spaces 102
6.2.2 Decomposition of nilpotent adjacency operators 107
6.3 Connected Components in Graph Processes 108
6.3.1 Algebraic preliminaries 110
6.3.2 Connected components 112
6.3.3 Second quantization of graph processes 119
7. Geometric Graph Processes 125
7.1 Preliminaries 125
7.2 Dynamic Graph Processes 130
7.2.1 Vertex degrees in gn 143
7.2.2 Energy and Laplacian energy of geometric graphs 145
7.2.3 Convergence conditions and a limit theorem 147
7.3 Time-Homogeneous Walks on Random Geometric Graphs 150
Probability on Algebraic Structures 153
8. Time-Homogeneous Random Walks 155
8.1 Clnsym and Random Walks on Hypercubes 156
8.2 Multiplicative Walks on Clp,q 164
8.2.1 Walks on directed hypercubes 164
8.2.2 Random walks on directed hypercubes with loops 166
8.2.3 Properties of multiplicative walks 167
8.3 Induced Additive Walks on Clp,q 173
8.3.1 Variance of ϒN-ϒ 179
8.3.2 Variance of ξ N-ξ 181
8.3.3 Central limit theorems 183
9. Dynamic Walks in Clifford Algebras 189
9.1 Preliminaries 189
9.2 Expectation 192
9.3 Limit Theorems 198
9.3.1 Conditions for convergence 204
9.3.2 Induced additive walks 209
9.3.3 Central limit theorem 214
10. Iterated Stochastic Integrals 219
10.1 Preliminaries 219
10.2 Stochastic Integrals in Ctp,q 222
10.3 Graph-Theoretic Iterated Stochastic Integrals 228
10.3.1 Functions on partitions 229
10.3.2 The Clifford evolution matrix 231
10.3.3 Orthogonal polynomials 234
11. Partition-Dependent Stochastic Measures 237
11.1 Preliminaries 237
11.2 Cycle Covers, Independent Sets, and Partitions 237
11.3 Computations on Lattices of Partitions 245
11.3.1 Computations on lattice segments 248
11.3.2 Computations on restricted lattice segments 254
11.4 Free Cumulants 257
Operator Calculus 261
12. Appell Systems in Clifford Algebras 263
12.1 Essential Background 263
12.1.1 Appell systems 263
12.1.2 Clifford algebras 264
12.2 Operator Calculus on Clifford Algebras 265
12.3 Generalized Raising and Lowering Operators 268
12.4 Clifford Appell Systems 271
12.4.1 Heterogeneous Clifford Appell systems 276
12.4.2 Role of blade factorization in the construction of Appell systems 278
12.5 Fermion Algebras and the Fermion Field 279
13. Operator Homology and Cohomology 285
13.1 Introduction 285
13.2 Clifford Homology and Cohomology 286
13.3 Homology and Lowering Operators 288
13.4 Cohomology and Raising Operators 295
13.5 Matrix Representations of Lowering and Raising Operators 300
13.6 Graphs of Raising and Lowering Operators 300
13.7 Operators as Quantum Random Variables 304
Symbolic Computations 307
14. Multivector-Level Complexity 309
14.1 Preliminaries 309
14.2 Graph Problems 313
14.2.1 Cycles and paths 313
14.2.2 Edge-disjoint cycle decompositions of graphs 317
14.3 A Matrix-Free Approach to Representing Graphs 320
14.4 Other Combinatorial Applications 330
14.4.1 Computing the permanent 330
14.4.2 The set packing and set covering problems 332
15. Blade-Level Complexity 335
15.1 Blade Operations 335
15.2 Counting Cycles 337
15.2.1 Cycles of fixed length 349
15.2.2 Remarks on space complexity 350
15.3 Further Remarks on Complexity 351
16. Operator Calculus Approach to Minimal Path Problems 353
16.1 Path-Identfying Nilpotent Adjacency Matrices 353
16.2 Operator Calculus Approach to Multi-Constrained Paths 354
16.2.1 Feasible and optimal paths in m-weighted graphs 356
16.2.2 The dynamic multi-constrained path problem 358
16.3 Minimal Path Algorithms 360
16.4 Application: Precomputed Routing in a Store-and-Forward Satellite Constellation 363
16.4.1 Operator calculus implementation 364
16.4.2 The results 369
17. Symbolic Computations with Mathematica 377
17.1 CliffMath': Computations in Clifford Algebras of Arbitrary Signature 377
17.1.1 CliffMath' procedures 377
17.1.2 Examples 379
17.2 CliffSymNil': A Companion Package 383
17.2.1 CliffSymNil' procedures 383
17.2.2 Examples 384
17.3 CliffOC': Operator Calculus on Clifford Algebras 388
17.3.1 CliffOC procedures 389
17.3.2 Examples 390
17.4 "Fast Zeon" Implementation 397
Bibliography 399
Index 407
