Free Encyclopedia of Mathematics 0.0.1
by the PlanetMath authors Aatu, ack, akrowne, alek thiery, alinabi, almann,
alozano, antizeus, antonio, aparna, ariels, armbrusterb, AxelBoldt, basseykay,
bbukh, benjaminfjones, bhaire, brianbirgen, bs, bshanks, bwebste, cryo, danielm,
Daume, debosberg, deiudi, digitalis, djao, Dr Absentius, draisma, drini, drummond, dublisk, Evandar, fibonaci, flynnheiss, gabor sz, GaloisRadical, gantsich,
gaurminirick, gholmes74, giri, greg, grouprly, gumau, Gunnar, Henry, iddo, igor,
imran, jamika chris, jarino, jay, jgade, jihemme, Johan, karteef, karthik, kemyers3, Kevin OBryant, kidburla2003, KimJ, Koro, lha, lieven, livetoad, liyang, Logan, Luci, m759, mathcam, mathwizard, matte, mclase, mhale, mike, mikestaflogan, mps, msihl, muqabala, n3o, nerdy2, nobody, npolys, Oblomov, ottocolori,
paolini, patrickwonders, pbruin, petervr, PhysBrain, quadrate, quincynoodles,
ratboy, RevBobo, Riemann, rmilson, ruiyang, Sabean, saforres, saki, say 10,
scanez, scineram, seonyoung, slash, sleske, slider142, sprocketboy, sucrose, superhiggs, tensorking, thedagit, Thomas Heye, thouis, Timmy, tobix, tromp, tz26, unlord, uriw, urz, vampyr, vernondalhart, vitriol, vladm, volator, vypertd, wberry,
Wkbj79, wombat, x bas, xiaoyanggu, XJamRastafire, xriso, yark et al.
edited by Joe Corneli & Aaron Krowne

Copyright c 2004 PlanetMath.org authors. Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software
Foundation; with no Invariant Sections, with no Front-Cover Texts, and with no
Back-Cover Texts. A copy of the license is included in the section entitled “GNU
Free Documentation License”.


Introduction
Welcome to the PlanetMath “One Big Book” compilation, the Free Encyclopedia of Mathematics. This book gathers in a single document the best of the hundreds of authors and
thousands of other contributors from the PlanetMath.org web site, as of January 4, 2004.
The purpose of this compilation is to help the efforts of these people reach a wider audience
and allow the benefits of their work to be accessed in a greater breadth of situations.
We want to emphasize is that the Free Encyclopedia of Mathematics will always be a work
in progress. Producing a book-format encycopedia from the amorphous web of interlinked
and multidimensionally-organized entries on PlanetMath is not easy. The print medium
demands a linear presentation, and to boil the web site down into this format is a difficult,
and in some ways lossy, transformation. A major part of our editorial efforts are going into
making this transformation. We hope the organization we’ve chosen for now is useful to
readers, and in future editions you can expect continuing improvements.

The “linearization” of PlanetMath.org is not the only editorial task we must perform.
Throughout the millenia, readers have come to expect a strict standard of consistency and
correctness from print books, and we must strive to meet this standard in the PlanetMath
Book as closely as possible. This means applying more editorial control to the book form
of PlanetMath than is applied to the web site. We hope you will agree that there is significant value to be gained from unifying style, correcting errors, and filtering out not-yet-ready
content, so we will continue to do these things.
For more details on planned improvements to this book, see the TODO file that came with
this archive. Remember that you can help us to improve this work by joining PlanetMath.org
and filing corrections, adding entries, or just participating in the community. We are also
looking for volunteers to help edit this book, or help with programming related to its production, or to help work on Noosphere, the PlanetMath software. To send us comments
about the book, use the e-mail address For general comments
and queries, use
Happy mathing,
Joe Corneli
Aaron Krowne
Tuesday, January 27, 2004
i

www.pdfgrip.com


Top-level Math Subject
Classificiations
00
01
03
05
06
08
11

12
13
14
15
16
17
18
19
20
22
26
28
30
31
32
33
34
35
37
39
40
41
42
43
44

General
History and biography
Mathematical logic and foundations
Combinatorics

Order, lattices, ordered algebraic structures
General algebraic systems
Number theory
Field theory and polynomials
Commutative rings and algebras
Algebraic geometry
Linear and multilinear algebra; matrix theory
Associative rings and algebras
Nonassociative rings and algebras
Category theory; homological algebra
$K$-theory
Group theory and generalizations
Topological groups, Lie groups
Real functions
Measure and integration
Functions of a complex variable
Potential theory
Several complex variables and analytic spaces
Special functions
Ordinary differential equations
Partial differential equations
Dynamical systems and ergodic theory
Difference and functional equations
Sequences, series, summability
Approximations and expansions
Fourier analysis
Abstract harmonic analysis
Integral transforms, operational calculus
ii


www.pdfgrip.com


45
46
47
49
51
52
53
54
55
57
58
60
62
65
68
70
74
76
78
80
81
82
83
85
86
90
91

92
93
94
97

Integral equations
Functional analysis
Operator theory
Calculus of variations and optimal control; optimization
Geometry
Convex and discrete geometry
Differential geometry
General topology
Algebraic topology
Manifolds and cell complexes
Global analysis, analysis on manifolds
Probability theory and stochastic processes
Statistics
Numerical analysis
Computer science
Mechanics of particles and systems
Mechanics of deformable solids
Fluid mechanics
Optics, electromagnetic theory
Classical thermodynamics, heat transfer
Quantum theory
Statistical mechanics, structure of matter
Relativity and gravitational theory
Astronomy and astrophysics
Geophysics

Operations research, mathematical programming
Game theory, economics, social and behavioral sciences
Biology and other natural sciences
Systems theory; control
Information and communication, circuits
Mathematics education

iii

www.pdfgrip.com


Table of Contents

lipschitz function 21
lognormal random variable 21
lowest upper bound 22
marginal distribution 22
measurable space 23
measure zero 23
minimum spanning tree 23
minimum weighted path length 24
mod 2 intersection number 25
moment generating function 27
monoid 27
monotonic operator 27
multidimensional Gaussian integral 28
multiindex 29
near operators 30
negative binomial random variable 36

normal random variable 37
normalizer of a subset of a group 38
nth root 38
null tree 40
open ball 40
opposite ring 40
orbit-stabilizer theorem 41
orthogonal 41
permutation group on a set 41
prime element 42
product measure 43
projective line 43
projective plane 43
proof of calculus theorem used in the Lagrange
method 44
proof of orbit-stabilizer theorem 45
proof of power rule 45
proof of primitive element theorem 47
proof of product rule 47
proof of sum rule 48
proof that countable unions are countable 48
quadrature 48
quotient module 49
regular expression 49
regular language 50
right function notation 51
ring homomorphism 51
scalar 51
schrodinger operator 51


Introduction i
Top-level Math Subject Classificiations ii
Table of Contents iv
GNU Free Documentation License lii
UNCLA – Unclassified 1
Golomb ruler 1
Hesse configuration 1
Jordan’s Inequality 2
Lagrange’s theorem 2
Laurent series 3
Lebesgue measure 3
Leray spectral sequence 4
Măobius transformation 4
Mordell-Weil theorem 4
Plateau’s Problem 5
Poisson random variable 5
Shannon’s theorem 6
Shapiro inequality 9
Sylow p-subgroups 9
Tchirnhaus transformations 9
Wallis formulae 10
ascending chain condition 10
bounded 10
bounded operator 11
complex projective line 12
converges uniformly 12
descending chain condition 13
diamond theorem 13
equivalently oriented bases 13
finitely generated R-module 14

fraction 14
group of covering transformations 15
idempotent 15
isolated 17
isolated singularity 17
isomorphic groups 17
joint continuous density function 18
joint cumulative distribution function 18
joint discrete density function 19
left function notation 20
lift of a submanifold 20
limit of a real function exits at a point 20

iv

www.pdfgrip.com


selection sort 52
semiring 53
simple function 54
simple path 54
solutions of an equation 54
spanning tree 54
square root 55
stable sorting algorithm 56
standard deviation 56
stochastic independence 56
substring 57
successor 57

sum rule 58
superset 58
symmetric polynomial 59
the argument principle 59
torsion-free module 59
total order 60
tree traversals 60
trie 63
unit vector 64
unstable fixed point 65
weak* convergence in normed linear space 65
well-ordering principle for natural numbers 65
00-01 – Instructional exposition (textbooks,
tutorial papers, etc.) 66
dimension 66
toy theorem 67
00-XX – General 68
method of exhaustion 68
00A05 – General mathematics 69
Conway’s chained arrow notation 69
Knuth’s up arrow notation 70
arithmetic progression 70
arity 71
introducing 0th power 71
lemma 71
property 72
saddle point approximation 72
singleton 73
subsequence 73
surreal number 73

00A07 – Problem books 76
Nesbitt’s inequality 76
proof of Nesbitt’s inequality 76

00A20 – Dictionaries and other general
reference works 78
completing the square 78
00A99 – Miscellaneous topics 80
QED 80
TFAE 80
WLOG 81
order of operations 81
01A20 – Greek, Roman 84
Roman numerals 84
01A55 – 19th century 85
Poincar, Jules Henri 85
01A60 – 20th century 90
Bourbaki, Nicolas 90
Erds Number 97
03-00 – General reference works (handbooks, dictionaries, bibliographies, etc.) 98
Burali-Forti paradox 98
Cantor’s paradox 98
Russell’s paradox 99
biconditional 99
bijection 100
cartesian product 100
chain 100
characteristic function 101
concentric circles 101
conjunction 102

disjoint 102
empty set 102
even number 103
fixed point 103
infinite 103
injective function 104
integer 104
inverse function 105
linearly ordered 106
operator 106
ordered pair 106
ordering relation 106
partition 107
pullback 107
set closed under an operation 108
signature of a permutation 109
subset 109
surjective 110

v

www.pdfgrip.com


quantifier 141
quantifier free 144
subformula 144
syntactic compactness theorem for first order logic
144
transfinite induction 144

universal relation 145
universal relations exist for each level of the arithmetical hierarchy 145
well-founded induction 146
well-founded induction on formulas 147
03B15 Higher-order logic and type theory 143
Hăartigs quantifier 143
Russells theory of types 143
analytic hierarchy 145
game-theoretical quantifier 146
logical language 147
second order logic 148
03B40 – Combinatory logic and lambdacalculus 150
Church integer 150
combinatory logic 150
lambda calculus 151
03B48 – Probability and inductive logic
154
conditional probability 154
03B99 – Miscellaneous 155
Beth property 155
Hofstadter’s MIU system 155
IF-logic 157
Tarski’s result on the undefinability of Truth 160
axiom 161
compactness 164
consistent 164
interpolation property 164
sentence 165
03Bxx – General logic 166
Banach-Tarski paradox 166

03C05 – Equational classes, universal algebra 168
congruence 168
every congruence is the kernel of a homomorphism 168
homomorphic image of a Σ-structure is a Σ-structure

transposition 110
truth table 111
03-XX – Mathematical logic and foundations 112
standard enumeration 112
03B05 – Classical propositional logic 113
CNF 113
Proof that contrapositive statement is true using
logical equivalence 113
contrapositive 114
disjunction 114
equivalent 114
implication 115
propositional logic 115
theory 116
transitive 116
truth function 117
03B10 – Classical first-order logic 118
1 bootstrapping 118
Boolean 119
Găodel numbering 120
Găodels incompleteness theorems 120
Lindenbaum algebra 127
Lindstrăoms theorem 128
Pressburger arithmetic 129
R-minimal element 129

Skolemization 129
arithmetical hierarchy 129
arithmetical hierarchy is a proper hierarchy 130
atomic formula 131
creating an infinite model 131
criterion for consistency of sets of formulas 132
deductions are 1 132
example of Gă
odel numbering 134
example of well-founded induction 135
first order language 136
first order logic 137
first order theories 138
free and bound variables 138
generalized quantifier 139
logic 140
proof of compactness theorem for first order logic
141
proof of principle of transfinite induction 141
proof of the well-founded induction principle 141

vi

www.pdfgrip.com


169
kernel 169
kernel of a homomorphism is a congruence 169
quotient structure 170

03C07 – Basic properties of first-order languages and structures 171
Models constructed from constants 171
Stone space 172
alphabet 173
axiomatizable theory 174
definable 174
definable type 175
downward Lowenheim-Skolem theorem 176
example of definable type 176
example of strongly minimal 177
first isomorphism theorem 177
language 178
length of a string 179
proof of homomorphic image of a Σ-structure is
a Σ-structure 179
satisfaction relation 180
signature 181
strongly minimal 181
structure preserving mappings 181
structures 182
substructure 183
type 183
upward Lowenheim-Skolem theorem 183
03C15 – Denumerable structures 185
random graph (infinite) 185
03C35 – Categoricity and completeness of
theories 187
κ-categorical 187
Vaught’s test 187
proof of Vaught’s test 187

03C50 – Models with special properties
(saturated, rigid, etc.) 189
example of universal structure 189
homogeneous 191
universal structure 191
03C52 – Properties of classes of models
192
amalgamation property 192
03C64 – Model theory of ordered structures; o-minimality 193

infinitesimal 193
o-minimality 194
real closed fields 194
03C68 – Other classical first-order model
theory 196
imaginaries 196
03C90 – Nonclassical models (Boolean-valued,
sheaf, etc.) 198
Boolean valued model 198
03C99 – Miscellaneous 199
axiom of foundation 199
elementarily equivalent 199
elementary embedding 200
model 200
proof equivalence of formulation of foundation
201
03D10 – Turing machines and related notions 203
Turing machine 203
03D20 – Recursive functions and relations,
subrecursive hierarchies 206

primitive recursive 206
03D25 – Recursively (computably) enumerable sets and degrees 207
recursively enumerable 207
03D75 – Abstract and axiomatic computability and recursion theory 208
Ackermann function 208
halting problem 209
03E04 – Ordered sets and their cofinalities; pcf theory 211
another definition of cofinality 211
cofinality 211
maximal element 212
partitions less than cofinality 213
well ordered set 213
pigeonhole principle 213
proof of pigeonhole principle 213
tree (set theoretic) 214
κ-complete 215
Cantor’s diagonal argument 215
Fodor’s lemma 216
Schroeder-Bernstein theorem 216
Veblen function 216
additively indecomposable, 217

vii

www.pdfgrip.com


cardinal number 217
cardinal successor 217
cardinality 218

cardinality of a countable union 218
cardinality of the rationals 219
classes of ordinals and enumerating functions 219
club 219
club filter 220
countable 220
countably infinite 221
finite 221
fixed points of normal functions 221
height of an algebraic number 221
if A is infinite and B is a finite subset of A, then
A \ B is infinite 222
limit cardinal 222
natural number 223
ordinal arithmetic 224
ordinal number 225
power set 225
proof of Fodor’s lemma 225
proof of Schroeder-Bernstein theorem 225
proof of fixed points of normal functions 226
proof of the existence of transcendental numbers
226
proof of theorems in aditively indecomposable
227
proof that the rationals are countable 228
stationary set 228
successor cardinal 229
uncountable 229
von Neumann integer 229
von Neumann ordinal 230

weakly compact cardinal 231
weakly compact cardinals and the tree property
231
Cantor’s theorem 232
proof of Cantor’s theorem 232
additive 232
antisymmetric 233
constant function 233
direct image 234
domain 234
dynkin system 234
equivalence class 235

fibre 235
filtration 236
finite character 236
fix (transformation actions) 236
function 237
functional 237
generalized cartesian product 238
graph 238
identity map 238
inclusion mapping 239
inductive set 239
invariant 240
inverse function theorem 240
inverse image 241
mapping 242
mapping of period n is a bijection 242
partial function 242

partial mapping 243
period of mapping 243
pi-system 244
proof of inverse function theorem 244
proper subset 246
range 246
reflexive 246
relation 246
restriction of a mapping 247
set difference 247
symmetric 247
symmetric difference 248
the inverse image commutes with set operations
248
transformation 249
transitive 250
transitive 250
transitive closure 250
Hausdorff’s maximum principle 250
Kuratowski’s lemma 251
Tukey’s lemma 251
Zermelo’s postulate 251
Zermelo’s well-ordering theorem 251
Zorn’s lemma 252
axiom of choice 252
equivalence of Hausdorff’s maximum principle,
Zorn’s lemma and the well-ordering theorem 252
equivalence of Zorn’s lemma and the axiom of

viii


www.pdfgrip.com


Martin’s axiom 283
Martin’s axiom and the continuum hypothesis
283
Martin’s axiom is consistent 284
a shorter proof: Martin’s axiom and the continuum hypothesis 287
continuum hypothesis 288
forcing 288
generalized continuum hypothesis 289
inaccessible cardinals 290
✸ 290
♣ 290
Dedekind infinite 291
Zermelo-Fraenkel axioms 291
class 291
complement 293
delta system 293
delta system lemma 293
diagonal intersection 293

choice 253
maximality principle 254
principle of finite induction 254
principle of finite induction proven from wellordering principle 255
proof of Tukey’s lemma 255
proof of Zermelo’s well-ordering theorem 255
axiom of extensionality 256

axiom of infinity 256
axiom of pairing 257
axiom of power set 258
axiom of union 258
axiom schema of separation 259
de Morgan’s laws 260
de Morgan’s laws for sets (proof) 261
set theory 261
union 264
universe 264
von Neumann-Bernays-Gdel set theory 265
FS iterated forcing preserves chain condition 267
chain condition 268
composition of forcing notions 268
composition preserves chain condition 268
equivalence of forcing notions 269
forcing relation 270
forcings are equivalent if one is dense in the other
270
iterated forcing 272
iterated forcing and composition 273
name 273
partial order with chain condition does not collapse cardinals 274
proof of partial order with chain condition does
not collapse cardinals 274
proof that forcing notions are equivalent to their
composition 275
complete partial orders do not add small subsets
280
proof of complete partial orders do not add small

subsets 280
✸ is equivalent to ♣ and continuum hypothesis
281
Levy collapse 281
proof of ✸ is equivalent to ♣ and continuum hypothesis 282

intersection 294
multiset 294
proof of delta system lemma 294
rational number 295
saturated (set) 295
separation and doubletons axiom 295
set 296
03Exx – Set theory 299
intersection 299
03F03 – Proof theory, general 300
NJp 300
NKp 300
natural deduction 301
sequent 301
sound,, complete 302
03F07 – Structure of proofs 303
induction 303
03F30 – First-order arithmetic and fragments 307
Elementary Functional Arithmetic 307
PA 308
Peano arithmetic 308
03F35 – Second- and higher-order arithmetic and fragments 310
ACA0 310


ix

www.pdfgrip.com


05A19 – Combinatorial identities 342
RCA0 310
Pascal’s rule 342
Z2 310
05A99 – Miscellaneous 343
comprehension axiom 311
principle of inclusion-exclusion 343
induction axiom 311
principle of inclusion-exclusion proof 344
03G05 – Boolean algebras 313
05B15 – Orthogonal arrays, Latin squares,
Boolean algebra 313
Room squares 346
M. H. Stone’s representation theorem 313
03G10 – Lattices and related structures example of Latin squares 346
graeco-latin squares 346
314
latin square 347
Boolean lattice 314
magic square 347
complete lattice 314
05B35 – Matroids, geometric lattices 348
lattice 315
matroid 348
03G99 – Miscellaneous 316

polymatroid 353
Chu space 316
05C05 – Trees 354
Chu transform 316
AVL tree 354
biextensional collapse 317
Aronszajn tree 354
example of Chu space 317
Suslin tree 354
property of a Chu space 318
05-00 – General reference works (hand- antichain 355
books, dictionaries, bibliographies, etc.) 319balanced tree 355
binary tree 355
example of pigeonhole principle 319
branch 356
multi-index derivative of a power 319
child node (of a tree) 356
multi-index notation 320
05A10 – Factorials, binomial coefficients, complete binary tree 357
digital search tree 357
combinatorial functions 322
digital tree 358
Catalan numbers 322
example of Aronszajn tree 358
Levi-Civita permutation symbol 323
example of tree (set theoretic) 359
Pascal’s rule (bit string proof) 325
extended binary tree 359
Pascal’s rule proof 326
external path length 360

Pascal’s triangle 326
Upper and lower bounds to binomial coefficient internal node (of a tree) 360
leaf node (of a tree) 361
328
parent node (in a tree) 361
binomial coefficient 328
proof that ω has the tree property 362
double factorial 329
root (of a tree) 362
factorial 329
tree 363
falling factorial 330
weight-balanced binary trees are ultrametric 364
inductive proof of binomial theorem 331
weighted path length 366
multinomial theorem 332
05C10 – Topological graph theory, imbedmultinomial theorem (proof) 333
proof of upper and lower bounds to binomial co- ding 367
Heawood number 367
efficient 334
05A15 – Exact enumeration problems, gen- Kuratowski’s theorem 368
Szemer´edi-Trotter theorem 368
erating functions 336
crossing lemma 369
Stirling numbers of the first kind 336
crossing number 369
Stirling numbers of the second kind 338

x


www.pdfgrip.com


Dirac theorem 396
Euler circuit 397
Fleury’s algorithm 397
Hamiltonian cycle 398
Hamiltonian graph 398
Hamiltonian path 398
Ore’s theorem 398
Petersen graph 399
hypohamiltonian 399
traceable 399
05C60 – Isomorphism problems (reconstruction conjecture, etc.) 400
graph isomorphism 400
05C65 – Hypergraphs 402
Steiner system 402
finite plane 402
hypergraph 403
linear space 404
05C69 – Dominating sets, independent sets,
cliques 405
Mantel’s theorem 405
clique 405
proof of Mantel’s theorem 405
05C70 – Factorization, matching, covering
and packing 407
Petersen theorem 407
Tutte theorem 407
bipartite matching 407

edge covering 409
matching 409
maximal bipartite matching algorithm 410
maximal matching/minimal edge covering theorem 411
05C75 – Structural characterization of types
of graphs 413
multigraph 413
pseudograph 413
05C80 – Random graphs 414
examples of probabilistic proofs 414
probabilistic method 415
05C90 – Applications 417
Hasse diagram 417
05C99 – Miscellaneous 419
Euler’s polyhedron theorem 419
Poincar´e formula 419

graph topology 369
planar graph 370
proof of crossing lemma 370
05C12 – Distance in graphs 372
Hamming distance 372
05C15 – Coloring of graphs and hypergraphs 373
bipartite graph 373
chromatic number 374
chromatic number and girth 375
chromatic polynomial 375
colouring problem 376
complete bipartite graph 377
complete k-partite graph 378

four-color conjecture 378
k-partite graph 379
property B 380
05C20 – Directed graphs (digraphs), tournaments 381
cut 381
de Bruijn digraph 381
directed graph 382
flow 383
maximum flow/minimum cut theorem 384
tournament 385
05C25 – Graphs and groups 387
Cayley graph 387
05C38 – Paths and cycles 388
Euler path 388
Veblen’s theorem 388
acyclic graph 389
bridges of Knigsberg 389
cycle 390
girth 391
path 391
proof of Veblen’s theorem 392
05C40 – Connectivity 393
k-connected graph 393
Thomassen’s theorem on 3-connected graphs 393
Tutte’s wheel theorem 394
connected graph 394
cutvertex 395
05C45 – Eulerian and Hamiltonian graphs
396
Bondy and Chvtal theorem 396


xi

www.pdfgrip.com


equivalence relation 443
Turan’s theorem 419
06-XX – Order, lattices, ordered algebraic
Wagner’s theorem 420
structures 445
block 420
join 445
bridge 420
meet 445
complete graph 420
06A06 – Partial order, general 446
degree (of a vertex) 421
directed set 446
distance (in a graph) 421
infimum 446
edge-contraction 421
sets that do not have an infimum 447
graph 422
supremum 447
graph minor theorem 422
upper bound 448
graph theory 423
06A99 – Miscellaneous 449
homeomorphism 424

dense (in a poset) 449
loop 424
partial order 449
minor (of a graph) 424
poset 450
neighborhood (of a vertex) 425
quasi-order 450
null graph 425
well quasi ordering 450
order (of a graph) 425
06B10 – Ideals, congruence relations 452
proof of Euler’s polyhedron theorem 426
order in an algebra 452
proof of Turan’s theorem 427
06C05 – Modular lattices, Desarguesian
realization 427
lattices 453
size (of a graph) 428
modular lattice 453
subdivision 428
06D99 – Miscellaneous 454
subgraph 429
distributive 454
wheel graph 429
distributive lattice 454
05D05 – Extremal set theory 431
06E99 – Miscellaneous 455
LYM inequality 431
Boolean ring 455
Sperner’s theorem 432

08A40 – Operations, polynomials, primal
05D10 Ramsey theory 433
algebras 456
Erdăos-Rado theorem 433
coefficients of a polynomial 456
Ramsey’s theorem 433
08A99 – Miscellaneous 457
Ramsey’s theorem 434
binary operation 457
arrows 435
filtered algebra 457
coloring 436
11-00 – General reference works (handproof of Ramsey’s theorem 437
05D15 – Transversal (matching) theory 438 books, dictionaries, bibliographies, etc.) 459
Euler phi-function 459
Hall’s marriage theorem 438
Euler-Fermat theorem 460
proof of Hall’s marriage theorem 438
Fermat’s little theorem 460
saturate 440
Fermat’s theorem proof 460
system of distinct representatives 440
Goldbach’s conjecture 460
05E05 – Symmetric functions 441
Jordan’s totient function 461
elementary symmetric polynomial 441
reduction algorithm for symmetric polynomials Legendre symbol 461
Pythagorean triplet 462
441
06-00 – General reference works (hand- Wilson’s theorem 462

books, dictionaries, bibliographies, etc.) 443arithmetic mean 462

xii

www.pdfgrip.com


proof of Lucas’s theorem 486
ceiling 463
computation of powers using Fermat’s little the- 11A15 – Power residues, reciprocity 487
Euler’s criterion 487
orem 463
Gauss’ lemma 487
congruences 464
Zolotarev’s lemma 489
coprime 464
cubic reciprocity law 491
cube root 464
proof of Euler’s criterion 493
floor 465
proof of quadratic reciprocity rule 494
geometric mean 465
quadratic character of 2 495
googol 466
quadratic reciprocity for polynomials 496
googolplex 467
quadratic reciprocity rule 497
greatest common divisor 467
quadratic residue 497
group theoretic proof of Wilson’s theorem 467

11A25 – Arithmetic functions; related numharmonic mean 467
bers; inversion formulas 498
mean 468
Dirichlet character 498
number field 468
Liouville function 498
pi 468
Mangoldt function 499
proof of Wilson’s theorem 470
proof of fundamental theorem of arithmetic 471 Mertens’ first theorem 499
Moebius function 499
root of unity 471
11-01 – Instructional exposition (textbooks, Moebius in version 500
arithmetic function 502
tutorial papers, etc.) 472
multiplicative function 503
base 472
non-multiplicative function 505
11-XX – Number theory 474
totient 507
Lehmer’s Conjecture 474
unit 507
Sierpinski conjecture 474
11A41 – Primes 508
prime triples conjecture 475
11A05 – Multiplicative structure; Euclidean Chebyshev functions 508
algorithm; greatest common divisors 476 Euclid’s proof of the infinitude of primes 509
Mangoldt summatory function 509
Bezout’s lemma (number theory) 476
Mersenne numbers 510

Euclid’s algorithm 476
Thue’s lemma 510
Euclid’s lemma 478
composite number 511
Euclid’s lemma proof 478
prime 511
fundamental theorem of arithmetic 479
prime counting function 511
perfect number 479
prime difference function 512
smooth number 480
prime number theorem 512
11A07 – Congruences; primitive roots; residue
prime number theorem result 513
systems 481
proof of Thue’s Lemma 514
Anton’s congruence 481
semiprime 515
Fermat’s Little Theorem proof (Inductive) 482
sieve of Eratosthenes 516
Jacobi symbol 483
test for primality of Mersenne numbers 516
Shanks-Tonelli algorithm 483
11A51 – Factorization; primality 517
Wieferich prime 483
Fermat Numbers 517
Wilson’s theorem for prime powers 484
Fermat compositeness test 517
factorial module prime powers 485
Zsigmondy’s theorem 518

proof of Euler-Fermat theorem 485

xiii

www.pdfgrip.com


divisibility 518
division algorithm for integers 519
proof of division algorithm for integers 519
square-free number 520
squarefull number 520
the prime power dividing a factorial 521
11A55 – Continued fractions 523
Stern-Brocot tree 523
continued fraction 524
11A63 – Radix representation; digital problems 527
Kummer’s theorem 527
corollary of Kummer’s theorem 528
11A67 Other representations 529
Sierpinski Erdă
os egyptian fraction conjecture 529
adjacent fraction 529
any rational number is a sum of unit fractions
530
conjecture on fractions with odd denominators
532
unit fraction 532
11A99 – Miscellaneous 533
ABC conjecture 533

Suranyi theorem 533
irrational to an irrational power can be rational
534
triangular numbers 534
11B05 – Density, gaps, topology 536
Cauchy-Davenport theorem 536
Mann’s theorem 536
Schnirelmann density 537
Sidon set 537
asymptotic density 538
discrete space 538
essential component 539
normal order 539
11B13 Additive bases 541
Erdăos-Turan conjecture 541
additive basis 542
asymptotic basis 542
base con version 542
sumset 546
11B25 – Arithmetic progressions 547
Behrend’s construction 547
Freiman’s theorem 548

Szemer´edi’s theorem 548
multidimensional arithmetic progression 549
11B34 Representation functions 550
Erdăos-Fuchs theorem 550
11B37 Recurrences 551
Collatz problem 551
recurrence relation 551

11B39 – Fibonacci and Lucas numbers and
polynomials and generalizations 553
Fibonacci sequence 553
Hogatt’s theorem 554
Lucas numbers 554
golden ratio 554
11B50 Sequences (mod m) 556
Erdăos-Ginzburg-Ziv theorem 556
11B57 Farey sequences; the sequences ?
557
Farey sequence 557
11B65 – Binomial coefficients; factorials;
q-identities 559
Lucas’s Theorem 559
binomial theorem 559
11B68 – Bernoulli and Euler numbers and
polynomials 561
Bernoulli number 561
Bernoulli periodic function 561
Bernoulli polynomial 562
generalized Bernoulli number 562
11B75 Other combinatorial number theory 563
Erdăos-Heilbronn conjecture 563
Freiman isomorphism 563
sum-free 564
11B83 – Special sequences and polynomials 565
Beatty sequence 565
Beatty’s theorem 566
Fraenkel’s partition theorem 566
Sierpinski numbers 567

palindrome 567
proof of Beatty’s theorem 568
square-free sequence 569
superincreasing sequence 569
11B99 – Miscellaneous 570
Lychrel number 570

xiv

www.pdfgrip.com


closed form 571
11C08 – Polynomials 573
content of a polynomial 573
cyclotomic polynomial 573
height of a polynomial 574
length of a polynomial 574
proof of Eisenstein criterion 574
proof that the cyclotomic polynomial is irreducible
575
11D09 – Quadratic and bilinear equations
577
Pell’s equation and simple continued fractions
577
11D41 – Higher degree equations; Fermat’s
equation 578
Beal conjecture 578
Euler quartic conjecture 579
Fermat’s last theorem 580

11D79 – Congruences in many variables
582
Chinese remainder theorem 582
Chinese remainder theorem proof 583
11D85 – Representation problems 586
polygonal number 586
11D99 – Miscellaneous 588
Diophantine equation 588
11E39 – Bilinear and Hermitian forms 590
Hermitian form 590
non-degenerate bilinear form 590
positive definite form 591
symmetric bilinear form 591
Clifford algebra 591
11Exx – Forms and linear algebraic groups
593
quadratic function associated with a linear functional 593
11F06 – Structure of modular groups and
generalizations; arithmetic groups 594
Taniyama-Shimura theorem 594
11F30 – Fourier coefficients of automorphic forms 597
Fourier coefficients 597
11F67 – Special values of automorphic Lseries, periods of modular forms, cohomology, modular symbols 598

Schanuel’s conjecutre 598
period 598
11G05 – Elliptic curves over global fields
600
complex multiplication 600
11H06 – Lattices and convex bodies 602

Minkowski’s theorem 602
lattice in Rn 602
11H46 – Products of linear forms 604
triple scalar product 604
11J04 – Homogeneous approximation to
one number 605
Dirichlet’s approximation theorem 605
11J68 – Approximation to algebraic numbers 606
Davenport-Schmidt theorem 606
Liouville approximation theorem 606
proof of Liouville approximation theorem 607
11J72 – Irrationality; linear independence
over a field 609
nth root of 2 is irrational for n ≥ 3 (proof using
Fermat’s last theorem) 609
e is irrational (proof) 610
irrational 610
square root of 2 is irrational 611
11J81 – Transcendence (general theory)
612
Fundamental Theorem of Transcendence 612
Gelfond’s theorem 612
four exponentials conjecture 612
six exponentials theorem 613
transcendental number 614
11K16 – Normal numbers, radix expansions, etc. 615
absolutely normal 615
11K45 – Pseudo-random numbers; Monte
Carlo methods 617
pseudorandom numbers 617

quasirandom numbers 618
random numbers 619
truly random numbers 619
11L03 – Trigonometric and exponential sums,
general 620
Ramanujan sum 620
11L05 – Gauss and Kloosterman sums; gen-

xv

www.pdfgrip.com


11P05 – Waring’s problem and variants
648
Lagrange’s four-square theorem 648
Waring’s problem 648
proof of Lagrange’s four-square theorem 649
11P81 – Elementary theory of partitions
651
pentagonal number theorem 651
11R04 – Algebraic numbers; rings of algebraic integers 653
Dedekind domain 653
Dirichlet’s unit theorem 653
Eisenstein integers 654
Galois representation 654
Gaussian integer 658
algebraic conjugates 659
algebraic integer 659
algebraic number 659

algebraic number field 659
calculating the splitting of primes 660
characterization in terms of prime ideals 661
ideal classes form an abelian group 661
integral basis 661
integrally closed 662
transcendental root theorem 662
11R06 – PV-numbers and generalizations;
other special algebraic numbers 663
Salem number 663
11R11 – Quadratic extensions 664
prime ideal decomposition in quadratic extensions of Q 664
11R18 – Cyclotomic extensions 666
Kronecker-Weber theorem 666
examples of regular primes 667
prime ideal decomposition in cyclotomic exten11N32 – Primes represented by polynomi- sions of Q 668
als; other multiplicative structure of poly- regular prime 669
11R27 – Units and factorization 670
nomial values 644
regulator 670
Euler four-square identity 644
11N56 – Rate of growth of arithmetic func- 11R29 – Class numbers, class groups, discriminants 672
tions 645
Existence of Hilbert Class Field 672
highly composite number 645
class number formula 673
11N99 – Miscellaneous 646
discriminant 673
Chinese remainder theorem 646
ideal class 674

proof of chinese remainder theorem 646

eralizations 622
Gauss sum 622
Kloosterman sum 623
Landsberg-Schaar relation 623
derivation of Gauss sum up to a sign 624
11L40 – Estimates on character sums 625
Plya-Vinogradov inequality 625
11M06 – ζ(s) and L(s, χ) 627
Ap´ery’s constant 627
Dedekind zeta function 627
Dirichlet L-series 628
Riemann θ-function 629
Riemann Xi function 630
Riemann omega function 630
functional equation for the Riemann Xi function
630
functional equation for the Riemann theta function 631
generalized Riemann hypothesis 631
proof of functional equation for the Riemann theta
function 631
11M99 – Miscellaneous 633
Riemann zeta function 633
formulae for zeta in the critical strip 636
functional equation of the Riemann zeta function
638
value of the Riemann zeta function at s = 2 638
11N05 – Distribution of primes 640
Bertrand’s conjecture 640

Brun’s constant 640
proof of Bertrand’s conjecture 640
twin prime conjecture 642
11N13 – Primes in progressions 643
primes in progressions 648

xvi

www.pdfgrip.com


ray class group 675
11R32 – Galois theory 676
Galois criterion for solvability of a polynomial by
radicals 676
11R34 – Galois cohomology 677
Hilbert Theorem 90 677
11R37 – Class field theory 678
Artin map 678
Tchebotarev density theorem 679
modulus 679
multiplicative congruence 680
ray class field 680
11R56 – Ad`
ele rings and groups 682
adle 682
idle 682
restricted direct product 683
11R99 – Miscellaneous 684
Henselian field 684

valuation 685
11S15 – Ramification and extension theory 686
decomposition group 686
examples of prime ideal decomposition in number fields 688
inertial degree 691
ramification index 692
unramified action 697
11S31 – Class field theory; p-adic formal
groups 699
Hilbert symbol 699
11S99 – Miscellaneous 700
p-adic integers 700
local field 701
11Y05 – Factorization 703
Pollard’s rho method 703
quadratic sieve 706
11Y55 – Calculation of integer sequences
709
Kolakoski sequence 709
11Z05 – Miscellaneous applications of number theory 711
τ function 711
arithmetic derivative 711
example of arithmetic derivative 712
proof that τ (n) is the number of positive divisors

of n 712
12-00 – General reference works (handbooks, dictionaries, bibliographies, etc.) 714
monomial 714
order and degree of polynomial 715
12-XX – Field theory and polynomials 716

homogeneous polynomial 716
subfield 716
12D05 – Polynomials: factorization 717
factor theorem 717
proof of factor theorem 717
proof of rational root theorem 718
rational root theorem 719
sextic equation 719
12D10 – Polynomials: location of zeros
(algebraic theorems) 720
Cardano’s derivation of the cubic formula 720
Ferrari-Cardano derivation of the quartic formula
721
Galois-theoretic derivation of the cubic formula
722
Galois-theoretic derivation of the quartic formula
724
cubic formula 728
derivation of quadratic formula 728
quadratic formula 729
quartic formula 730
reciprocal polynomial 730
root 731
variant of Cardano’s derivation 732
12D99 – Miscellaneous 733
Archimedean property 733
complex 734
complex conjugate 735
complex number 737
examples of totally real fields 738

fundamental theorem of algebra 739
imaginary 739
imaginary unit 739
indeterminate form 739
inequalities for real numbers 740
interval 742
modulus of complex number 743
proof of fundamental theorem of algebra 744
proof of the fundamental theorem of algebra 744

xvii

www.pdfgrip.com


real and complex embeddings 744
real number 746
totally real and imaginary fields 747
12E05 – Polynomials (irreducibility, etc.)
748
Gauss’s Lemma I 748
Gauss’s Lemma II 749
discriminant 749
polynomial ring 751
resolvent 751
de Moivre identity 754
monic 754
Wedderburn’s Theorem 754
proof of Wedderburn’s theorem 755
second proof of Wedderburn’s theorem 756

finite field 757
Frobenius automorphism 760
characteristic 761
characterization of field 761
example of an infinite field of finite characteristic
762
examples of fields 762
field 764
field homomorphism 764
prime subfield 765
12F05 – Algebraic extensions 766
a finite extension of fields is an algebraic extension 766
algebraic closure 767
algebraic extension 767
algebraically closed 767
algebraically dependent 768
existence of the minimal polynomial 768
finite extension 769
minimal polynomial 769
norm 770
primitive element theorem 770
splitting field 770
the field extension R/Q is not finite 771
trace 771
12F10 – Separable extensions, Galois theory 772
Abelian extension 772
Fundamental Theorem of Galois Theory 772
Galois closure 773

Galois conjugate 773

Galois extension 773
Galois group 773
absolute Galois group 774
cyclic extension 774
example of nonperfect field 774
fixed field 774
infinite Galois theory 774
normal closure 776
normal extension 776
perfect field 777
radical extension 777
separable 777
separable closure 778
12F20 – Transcendental extensions 779
transcendence degree 779
12F99 – Miscellaneous 780
composite field 780
extension field 780
12J15 – Ordered fields 782
ordered field 782
13-00 – General reference works (handbooks, dictionaries, bibliographies, etc.) 783
absolute value 783
associates 784
cancellation ring 784
comaximal 784
every prime ideal is radical 784
module 785
radical of an ideal 786
ring 786
subring 787

tensor product 787
13-XX – Commutative rings and algebras
789
commutative ring 789
13A02 – Graded rings 790
graded ring 790
13A05 – Divisibility 791
Eisenstein criterion 791
13A10 – Radical theory 792
Hilbert’s Nullstellensatz 792
nilradical 792
radical of an integer 793
13A15 – Ideals; multiplicative ideal theory

xviii

www.pdfgrip.com


794
contracted ideal 794
existence of maximal ideals 794
extended ideal 795
fractional ideal 796
homogeneous ideal 797
ideal 797
maximal ideal 797
principal ideal 798
the set of prime ideals of a commutative ring
with identity 798

13A50 – Actions of groups on commutative rings; invariant theory 799
Schwarz (1975) theorem 799
invariant polynomial 800
13A99 – Miscellaneous 801
Lagrange’s identity 801
characteristic 802
cyclic ring 802
proof of Euler four-square identity 803
proof that every subring of a cyclic ring is a cyclic
ring 804
proof that every subring of a cyclic ring is an
ideal 804
zero ring 805
13B02 – Extension theory 806
algebraic 806
module-finite 806
13B05 – Galois theory 807
algebraic 807
13B21 – Integral dependence 808
integral 808
13B22 – Integral closure of rings and ideals ; integrally closed rings, related rings
(Japanese, etc.) 809
integral closure 809
13B30 – Quotients and localization 810
fraction field 810
localization 810
multiplicative set 811
13C10 – Projective and free modules and
ideals 812
example of free module 812

13C12 – Torsion modules and ideals 813
torsion element 813

13C15 – Dimension theory, depth, related
rings (catenary, etc.) 814
Krull’s principal ideal theorem 814
13C99 – Miscellaneous 815
Artin-Rees theorem 815
Nakayama’s lemma 815
prime ideal 815
proof of Nakayama’s lemma 816
proof of Nakayama’s lemma 817
support 817
13E05 – Noetherian rings and modules 818
Hilbert basis theorem 818
Noetherian module 818
proof of Hilbert basis theorem 819
finitely generated modules over a principal ideal
domain 819
13F07 – Euclidean rings and generalizations 821
Euclidean domain 821
Euclidean valuation 821
proof of Bezout’s Theorem 822
proof that an Euclidean domain is a PID 822
13F10 – Principal ideal rings 823
Smith normalform 823
13F25 – Formal power series rings 825
formal power series 825
13F30 – Valuation rings 831
discrete valuation 831

discrete valuation ring 831
13G05 – Integral domains 833
Dedekind-Hasse valuation 833
PID 834
UFD 834
a finite integral domain is a field 835
an artinian integral domain is a field 835
example of PID 835
field of quotients 836
integral domain 836
irreducible 837
motivation for Euclidean domains 837
zero divisor 838
13H05 – Regular local rings 839
regular local ring 839
13H99 – Miscellaneous 840
local ring 840

xix

www.pdfgrip.com


height of a prime ideal 866
semi-local ring 841
invertible sheaf 866
13J10 – Complete rings, completion 842
locally free 867
completion 842
normal irreducible varieties are nonsingular in

13J25 – Ordered rings 844
codimension 1 867
ordered ring 844
sheaf of meromorphic functions 867
13J99 – Miscellaneous 845
very ample 867
topological ring 845
14C20 – Divisors, linear systems, invert13N15 – Derivations 846
ible sheaves 869
derivation 846
13P10 Polynomial ideals, Gră
obner bases divisor 869
Rational and birational maps 870
847
general type 870
Grăobner basis 847
14-00 General reference works (hand- 14F05 – Vector bundles, sheaves, related
books, dictionaries, bibliographies, etc.) 849constructions 871
direct image (functor) 871
Picard group 849
´
14F20 – Etale
and other Grothendieck topoloaffine space 849
gies and cohomologies 872
affine variety 849
site 872
dual isogeny 850
14F25 – Classical real and complex cohofinite morphism 850
mology 873
isogeny 851

Serre duality 873
line bundle 851
sheaf cohomology 874
nonsingular variety 852
14G05 – Rational points 875
projective space 852
Hasse principle 875
projective variety 854
14H37 – Automorphisms 876
quasi-finite morphism 854
Frobenius morphism 876
14A10 – Varieties and morphisms 855
14H45 – Special curves and curves of low
Zariski topology 855
genus 878
algebraic map 856
Fermat’s spiral 878
algebraic sets and polynomial ideals 856
archimedean spiral 878
noetherian topological space 857
folium of Descartes 879
regular map 857
spiral 879
structure sheaf 858
14H50 – Plane and space curves 880
14A15 – Schemes and morphisms 859
torsion (space curve) 880
closed immersion 859
14H52 – Elliptic curves 881
coherent sheaf 859

Birch and Swinnerton-Dyer conjecture 881
fibre product 860
Hasse’s bound for elliptic curves over finite fields
prime spectrum 860
882
scheme 863
L-series of an elliptic curve 882
separated scheme 864
Mazur’s theorem on torsion of elliptic curves 884
singular set 864
Mordell curve 884
14A99 – Miscellaneous 865
Nagell-Lutz theorem 885
Cartier divisor 865
Selmer group 886
General position 865
bad reduction 887
Serre’s twisting theorem 866
conductor of an elliptic curve 890
ample 866

xx

www.pdfgrip.com


diagonally dominant matrix 920
elliptic curve 890
eigenvalue (of a matrix) 921
height function 894

eigenvalue problem 922
j-invariant 895
eigenvalues of orthogonal matrices 924
rank of an elliptic curve 896
eigenvector 925
supersingular 897
the torsion subgroup of an elliptic curve injects exactly determined 926
free vector space over a set 926
in the reduction of the curve 897
in a vector space, λv = 0 if and only if λ = 0 or
14H99 – Miscellaneous 900
v is the zero vector 928
Riemann-Roch theorem 900
invariant subspace 929
genus 900
least squares 929
projective curve 901
linear algebra 930
proof of Riemann-Roch theorem 901
14L17 – Affine algebraic groups, hyperal- linear least squares 932
linear manifold 934
gebra constructions 902
matrix exponential 934
affine algebraic group 902
matrix operations 935
algebraic torus 902
14M05 – Varieties defined by ring con- nilpotent matrix 938
ditions (factorial, Cohen-Macaulay, semi- nilpotent transformation 938
non-zero vector 939
normal) 903

off-diagonal entry 940
normal 903
14M15 – Grassmannians, Schubert vari- orthogonal matrices 940
orthogonal vectors 941
eties, flag manifolds 904
overdetermined 941
Borel-Bott-Weil theorem 904
partitioned matrix 941
flag variety 905
pentadiagonal matrix 942
14R15 – Jacobian problem 906
proof of Cayley-Hamilton theorem 942
Jacobian conjecture 906
15-00 – General reference works (hand- proof of Schur decomposition 943
books, dictionaries, bibliographies, etc.) 907singular value decomposition 944
skew-symmetric matrix 945
Cholesky decomposition 907
square matrix 946
Hadamard matrix 908
strictly upper triangular matrix 946
Hessenberg matrix 909
If A ∈ Mn (k) and A is supertriangular then symmetric matrix 947
theorem for normal triangular matrices 947
An = 0 910
triangular matrix 948
Jacobi determinant 910
tridiagonal matrix 949
Jacobi’s Theorem 912
under determined 950
Kronecker product 912

unit triangular matrix 950
LU decomposition 913
unitary 951
Peetre’s inequality 914
vector space 952
Schur decomposition 915
vector subspace 953
antipodal 916
zero map 954
conjugate transpose 916
zero vector in a vector space is unique 955
corollary of Schur decomposition 917
zero vector space 955
covector 918
15-01 – Instructional exposition (textbooks,
diagonal matrix 918
tutorial papers, etc.) 956
diagonalization 920

xxi

www.pdfgrip.com


circulant matrix 956
matrix 957
15-XX – Linear and multilinear algebra;
matrix theory 960
linearly dependent functions 960
15A03 – Vector spaces, linear dependence,

rank 961
Sylvester’s law 961
basis 961
complementary subspace 962
dimension 963
every vector space has a basis 964
flag 964
frame 965
linear combination 968
linear independence 968
list vector 968
nullity 969
orthonormal basis 970
physical vector 970
proof of rank-nullity theorem 972
rank 973
rank-nullity theorem 973
similar matrix 974
span 975
theorem for the direct sum of finite dimensional
vector spaces 976
vector 976
15A04 – Linear transformations, semilinear transformations 980
admissibility 980
conductor of a vector 980
cyclic decomposition theorem 981
cyclic subspace 981
dimension theorem for symplectic complement
(proof) 981
dual homomorphism 982

dual homomorphism of the derivative 983
image of a linear transformation 984
invertible linear transformation 984
kernel of a linear transformation 985
linear transformation 985
minimal polynomial (endomorphism) 986
symplectic complement 987
trace 988

15A06 – Linear equations 989
Gaussian elimination 989
finite-dimensional linear problem 991
homogeneous linear problem 992
linear problem 993
reduced row echelon form 993
row echelon form 994
under-determined polynomial interpolation 994
15A09 – Matrix inversion, generalized inverses 996
matrix adjoint 996
matrix inverse 997
15A12 – Conditioning of matrices 1000
singular 1000
15A15 – Determinants, permanents, other
special matrix functions 1001
Cayley-Hamilton theorem 1001
Cramer’s rule 1001
cofactor expansion 1002
determinant 1003
determinant as a multilinear mapping 1005
determinants of some matrices of special form

1006
example of Cramer’s rule 1006
proof of Cramer’s rule 1008
proof of cofactor expansion 1008
resolvent matrix 1009
15A18 – Eigenvalues, singular values, and
eigenvectors 1010
Jordan canonical form theorem 1010
Lagrange multiplier method 1011
Perron-Frobenius theorem 1011
characteristic equation 1012
eigenvalue 1012
eigenvalue 1013
15A21 – Canonical forms, reductions, classification 1015
companion matrix 1015
eigenvalues of an involution 1015
linear involution 1016
normal matrix 1017
projection 1018
quadratic form 1019
15A23 – Factorization of matrices 1021
QR decomposition 1021

xxii

www.pdfgrip.com


15A30 – Algebraic systems of matrices 1023 inner product space 1051
proof of Cauchy-Schwarz inequality 1052

ideals in matrix algebras 1023
self-dual 1052
15A36 – Matrices of integers 1025
skew-symmetric bilinear form 1053
permutation matrix 1025
spectral theorem 1053
15A39 – Linear inequalities 1026
15A66 – Clifford algebras, spinors 1056
Farkas lemma 1026
15A42 – Inequalities involving eigenvalues geometric algebra 1056
15A69 – Multilinear algebra, tensor prodand eigenvectors 1027
ucts 1058
Gershgorin’s circle theorem 1027
Einstein summation convention 1058
Gershgorin’s circle theorem result 1027
basic tensor 1059
Shur’s inequality 1028
15A48 – Positive matrices and their gen- multi-linear 1061
outer multiplication 1061
eralizations; cones of matrices 1029
tensor 1062
negative definite 1029
tensor algebra 1065
negative semidefinite 1029
tensor array 1065
positive definite 1030
tensor product (vector spaces) 1067
positive semidefinite 1030
tensor transformations 1069
primitive matrix 1031

15A72 – Vector and tensor algebra, theory
reducible matrix 1031
of invariants 1072
15A51 – Stochastic matrices 1032
bac-cab rule 1072
Birkoff-von Neumann theorem 1032
cross product 1072
proof of Birkoff-von Neumann theorem 1032
15A57 – Other types of matrices (Hermi- euclidean vector 1073
rotational invariance of cross product 1074
tian, skew-Hermitian, etc.) 1035
15A75 – Exterior algebra, Grassmann alHermitian matrix 1035
direct sum of Hermitian and skew-Hermitian ma- gebras 1076
contraction 1076
trices 1036
exterior algebra 1077
identity matrix 1037
15A99 – Miscellaneous topics 1081
skew-Hermitian matrix 1037
Kronecker delta 1081
transpose 1038
15A60 – Norms of matrices, numerical range,dual space 1081
applications of functional analysis to ma- example of trace of a matrix 1083
generalized Kronecker delta symbol 1083
trix theory 1041
linear functional 1084
Frobenius matrix norm 1041
modules are a generalization of vector spaces 1084
matrix p-norm 1042
proof of properties of trace of a matrix 1085

self consistent matrix norm 1043
15A63 – Quadratic and bilinear forms, in- quasipositive matrix 1086
trace of a matrix 1086
ner products 1044
Cauchy-Schwarz inequality 1044
Volume 2
adjoint endomorphism 1045
anti-symmetric 1046
16-00 – General reference works (handbilinear map 1046
books, dictionaries, bibliographies, etc.) 1088
dot product 1049
every orthonormal set is linearly independent 1050 direct product of modules 1088
direct sum 1089
inner product 1051

xxiii

www.pdfgrip.com


exact sequence 1089
quotient ring 1090
16D10 – General module theory 1091
annihilator 1091
annihilator is an ideal 1091
artinian 1092
composition series 1092
conjugate module 1093
modular law 1093
module 1093

proof of modular law 1094
zero module 1094
16D20 – Bimodules 1095
bimodule 1095
16D25 – Ideals 1096
associated prime 1096
nilpotent ideal 1096
primitive ideal 1096
product of ideals 1097
proper ideal 1097
semiprime ideal 1097
zero ideal 1098
16D40 – Free, projective, and flat modules
and ideals 1099
finitely generated projective module 1099
flat module 1099
free module 1100
free module 1100
projective cover 1100
projective module 1101
16D50 – Injective modules, self-injective
rings 1102
injective hull 1102
injective module 1102
16D60 – Simple and semisimple modules,
primitive rings and ideals 1104
central simple algebra 1104
completely reducible 1104
simple ring 1105
16D80 – Other classes of modules and ideals 1106

essential submodule 1106
faithful module 1106
minimal prime ideal 1107
module of finite rank 1107

simple module 1107
superfluous submodule 1107
uniform module 1108
16E05 – Syzygies, resolutions, complexes
1109
n-chain 1109
chain complex 1109
flat resolution 1110
free resolution 1110
injective resolution 1110
projective resolution 1110
short exact sequence 1111
split short exact sequence 1111
von Neumann regular 1111
16K20 – Finite-dimensional 1112
quaternion algebra 1112
16K50 – Brauer groups 1113
Brauer group 1113
16K99 – Miscellaneous 1114
division ring 1114
16N20 – Jacobson radical, quasimultiplication 1115
Jacobson radical 1115
a ring modulo its Jacobson radical is semiprimitive 1116
examples of semiprimitive rings 1116
proof of Characterizations of the Jacobson radical 1117

properties of the Jacobson radical 1118
quasi-regularity 1119
semiprimitive ring 1120
16N40 – Nil and nilpotent radicals, sets,
ideals, rings 1121
Koethe conjecture 1121
nil and nilpotent ideals 1121
16N60 – Prime and semiprime rings 1123
prime ring 1123
16N80 – General radicals and rings 1124
prime radical 1124
radical theory 1124
16P40 – Noetherian rings and modules 1126
Noetherian ring 1126
noetherian 1126
16P60 – Chain conditions on annihilators
and summands: Goldie-type conditions ,

xxiv

www.pdfgrip.com