-
Notifications
You must be signed in to change notification settings - Fork 67
/
Copy pathTDApart3.html
443 lines (432 loc) · 34.5 KB
/
TDApart3.html
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
<!DOCTYPE html>
<html lang="en">
<head>
<meta charset="utf-8" />
<meta name="viewport" content="width=device-width,initial-scale=1">
<title>Δ ℚuantitative √ourney | Persistent Homology (Part 3)</title>
<link rel="shortcut icon" type="image/png" href="http://outlace.com/favicon.png">
<link rel="shortcut icon" type="image/x-icon" href="http://outlace.com/favicon.ico">
<link href="http://outlace.com/feeds/all.atom.xml" type="application/atom+xml" rel="alternate" title="Δ ℚuantitative √ourney Full Atom Feed" />
<link rel="stylesheet" href="http://outlace.com/theme/css/screen.css" type="text/css" />
<link rel="stylesheet" href="http://outlace.com/theme/css/pygments.css" type="text/css" />
<link rel="stylesheet" href="http://outlace.com/theme/css/print.css" type="text/css" media="print" />
<meta name="generator" content="Pelican" />
<meta name="description" content="" />
<meta name="author" content="Brandon Brown" />
<meta name="keywords" content="TDA,persistent-homology" />
</head>
<body>
<header>
<nav>
<ul>
<li><a href="http://outlace.com/">Home</a></li>
<li><a href="http://outlace.com/pages/about.html">About</a></li>
<li><a href="http://outlace.com/tags/">Tags</a></li>
<li><a href="http://outlace.com/categories/">Categories</a></li>
<li><a href="http://outlace.com/archives/{slug}/">Archives</a></li>
</ul>
</nav>
<div class="header_box">
<h1><a href="http://outlace.com/">Δ ℚuantitative √ourney</a></h1>
<h2>Science, Math, Statistics, Machine Learning ...</h2>
</div>
</header>
<div id="wrapper">
<div id="content"> <h4 class="date">Feb 23, 2017</h4>
<article class="post">
<h2 class="title">
<a href="http://outlace.com/TDApart3.html" rel="bookmark" title="Permanent Link to "Persistent Homology (Part 3)"">Persistent Homology (Part 3)</a>
</h2>
<h2>Topological Data Analysis - Part 3 - Persistent Homology</h2>
<p>This is Part 3 in a series on topological data analysis.
See <a href="TDApart1.html">Part 1</a> | <a href="TDApart2.html">Part 2</a> | <a href="TDApart4.html">Part 4</a> | <a href="TDApart5.html">Part 5</a></p>
<p>In this part we begin to apply our the math we learned from Parts 1-2 to actually calculating the interesting topological features of a simplicial complex.</p>
<h4>Back to simplicial homology</h4>
<p>We've finally covered enough group theory to be able to finish our calculations of homology groups on simplicial complexes. As you should recall, we had given definitions for the n-th homology group and the n-th Betti numbers.</p>
<p>Betti number's are what we ultimately want. They nicely summarize the topological properties of a simplicial complex. If we have a simplicial complex that forms a single circular object, then <span class="math">\(b_0\)</span> (the 0th Betti Number) represents the number of connected components which is 1, <span class="math">\(b_1\)</span> is the number of 1-dimensional holes (i.e. cycles) which is 1, and <span class="math">\(b_n, n \gt 1\)</span> are the higher-dimensional holes of which there are zero.</p>
<p>Let's see if we can calculate the Betti Numbers of a simple triangle simplicial complex. </p>
<p>Recall that <span class="math">\(\mathcal T = \text{ {{a}, {b}, {c}, [a, b], [b, c], [c, a]} }\)</span>. (Depicted below).
<img src="images/TDAimages/triangleSimplex.svg" /></p>
<p>Since we know, by visual inspection, that <span class="math">\(T\)</span> <em>should</em> have Betti numbers <span class="math">\(b_0 = 1\)</span> (1 connected component), <span class="math">\(b_1 = 1\)</span> (1 one-dimensional hole), we will only compute those Betti numbers.</p>
<p>Let's walk through the whole sequence of steps slowly. First we'll note the n-chains.</p>
<p>The 0-chain is the set of 0-simplices: <span class="math">\(\text{ {{a}, {b}, {c} } }\)</span>
The 1-chain is the set of 1-simplices: <span class="math">\(\text{ [a, b], [b, c], [c, a] }\)</span>
There are no higher-dimensional n-chains.</p>
<p>Now we can use the n-chains to define our <em>chain groups</em>. We're going to be using coefficients from <span class="math">\(\mathbb Z_2\)</span>, which is a field, and remember there are only 2 elements <span class="math">\(\{0,1\}\)</span> where <span class="math">\(1+1=0\)</span>. </p>
<p>The 0-chain group is defined as:
</p>
<div class="math">$$C_0 = \{\{x*(a,0,0)\}, \{y*(0,b,0)\}, \{z*(0,0,c)\} \mid x,y,z \in \mathbb Z_2\} \\$$</div>
<p>
Remember a group only has an addition operation defined but we're <em>building</em> the group by using a multiplication operation from the field <span class="math">\(\mathbb Z_2\)</span>. So this group is actually isomorphic to <span class="math">\(\mathbb Z_{2}^{3} = Z_{2} \oplus Z_{2} \oplus Z_{2}\)</span>.</p>
<p>But we also want to represent our chain groups as a vector space. This means it becomes a structure where elements can be scaled up or down (i.e. multiplication operation) by elements of a field (in our case <span class="math">\(\mathbb Z_2\)</span>) and added together, with all results still contained in the structure. If we only pay attention to the addition operation then we're basically looking at its group structure, whereas if we pay attention to both the multiplcation and addition operations then we are considering it as a vector space.</p>
<p>0-chain vector space is generated by:
</p>
<div class="math">$$\mathscr C_0 = \{\{x*(a,0,0)\}, \{y*(0,b,0)\}, \{z*(0,0,c)\} \mid x,y,z \in \mathbb Z_2\} \\$$</div>
<p>
(Yes it's the same set that forms the group from above).</p>
<p>The vector space is the set of elements we can multiply by 0 or 1, and add them together. For example, we can do: <span class="math">\(1*(a,0,0) + 1*(0,0,c) = (a,0,c)\)</span>. This vector space is so small <span class="math">\((2^3=8\ \text{elements})\)</span> we can actually list out all the elements. Here they are:</p>
<div class="math">$$\mathscr{C_0} = \begin{Bmatrix} (a,0,0), (0,b,0), (0,0,c), (a,b,0) \\
(a,b,c), (0,b,c), (a,0,c), (0,0,0) \end{Bmatrix} \\ $$</div>
<p>You can see that we can add any two elements in this vector space and the result will be another element in the vector space. A random example: <span class="math">\((a,0,c) + (a,b,c) = (a+a,0+b,c+c) = (0,b,0)\)</span>. Recall addition is component-wise. We can also multiply vectors by an element in our field <span class="math">\(\mathbb Z_2\)</span> but since our field is finite with only 2 elements, it's not very interesting, e.g. <span class="math">\(1*(a,b,0) = (a,b,0)\)</span> and <span class="math">\(0*(a,b,0) = (0,0,0)\)</span>, but none the less, the multiplication operation still results in an element within our vector space.</p>
<p>We can represent this vector space as a polynomial, so our 0-chain vector space can be defined equivalently as:
</p>
<div class="math">$$ \mathscr{C_0} = \{xa + yb + zc \mid z,y,z \in \mathbb Z_2\}$$</div>
<p>
We can easily translate a polynomial like <span class="math">\(a+b+c\)</span> to its ordered-set notation <span class="math">\((a,b,c)\)</span>. Or <span class="math">\(a+b\)</span> is <span class="math">\((a,b,0)\)</span>. The vector space seen as a set of polynomials looks like this:
</p>
<div class="math">$$ \mathscr{C_0} = \begin{Bmatrix} \text{ {a}, {b}, {c}, {a+b} $\\$
{a+b+c}, {b+c}, {a+c}, {0} } \end{Bmatrix} \\ $$</div>
<p>
It's more convenient to work with the polynomial form, in general, because we can make familiar algebraic equations like </p>
<div class="math">$$a+b=0 \\
a = -b \\
a = b $$</div>
<p>
(Recall that the inverse of an element in <span class="math">\(\mathbb Z_2\)</span> is just itself, hence <span class="math">\(-b = b\)</span> where "<span class="math">\(-\)</span>" denotes inverse).</p>
<blockquote>
<p><strong>NOTE</strong>: It is very important to keep track of whether we're talking about groups or vector spaces. I will use a normal letter <span class="math">\(C\)</span> to denote the chain <strong>group</strong> and the fancy script <span class="math">\(\mathscr{C}\)</span> to denote the chain <strong>(vector) space</strong>. They have the same underlying <em>set</em>, only different operations defined. If we talk about the group form we can only reference its addition operation, whereas if we talk about its vector space form we can talk about its multiplication and addition operation.</p>
</blockquote>
<p>Let's do the same for the 1-chains: <span class="math">\(\text{ [a, b], [b, c], [c, a] }\)</span>. We can use the 1-chain set to define another chain group, <span class="math">\(C_1\)</span>. It will be isomorphic to <span class="math">\(C_0\)</span> and hence <span class="math">\(\mathbb Z_{2}^{3}\)</span>.
</p>
<div class="math">$$C_1 = \{\ (\ x([a, b]), y([b, c]), z([c, a])\ ) \mid x,y,z \in \mathbb Z_2\ \} $$</div>
<p>We can define a vector space, <span class="math">\(\mathscr C_1\)</span>, using this chain group in the same way we did for <span class="math">\(C_0\)</span>. I will use the polynomial form henceforth. Remember, the chain group and vector space have the same set, its just that the vector space has two binary operations instead of one.</p>
<p>This is the full list of elements in the vector space:
</p>
<div class="math">$$\mathscr{C_1} = \begin{Bmatrix} \text{
{[a, b]}, {[b, c]}, {[c, a]}, {[a, b] + [b, c]}, $\\$
{[b, c] + [c, a]}, {[a, b] + [c, a]}, {[a, b] + [b, c] + [c, a]}, {0} } \end{Bmatrix} \\$$</div>
<p>Just for clarification about the boundary map, here is a diagram of it. This shows how the boundary operator maps each element in <span class="math">\(C_1\)</span> to an element in <span class="math">\(C_0\)</span>.
<img src="images/TDAimages/boundarymap1.png" /></p>
<p>Now we can start computing the first Betti number, <span class="math">\(b_0\)</span>.</p>
<p>Recall the definition of a Betti number is:</p>
<blockquote>
<p>The n-th Betti number, <span class="math">\(b_n = dim(H_n)\)</span>, where <span class="math">\(H_n\)</span> is the n-th homology group.</p>
</blockquote>
<p>And recall the definition of a homology group</p>
<blockquote>
<p>The <span class="math">\(n^{th}\)</span> Homology Group <span class="math">\(H_n\)</span> is defined as <span class="math">\(H_n\)</span> = Ker <span class="math">\(\partial_n \ / \ \text{Im } \partial_{n+1}\)</span>.</p>
</blockquote>
<p>Lastly, recall the definition of a kernel:</p>
<blockquote>
<p>The kernel of <span class="math">\(\partial(C_n)\)</span>, denoted <span class="math">\(\text{Ker}(\partial(C_n))\)</span> is the group of <span class="math">\(n\)</span>-chains <span class="math">\(Z_n \subseteq C_n\)</span> such that <span class="math">\(\partial(Z_n) = 0\)</span></p>
</blockquote>
<p>So first we need the kernel of the boundary of <span class="math">\(C_0\)</span>, Ker <span class="math">\(\partial(C_0)\)</span>. Remember the boundary map <span class="math">\(\partial\)</span> gives us a map from <span class="math">\(C_n \rightarrow C_{n-1}\)</span>.</p>
<p>In all cases, the boundary of a 0-chain is <span class="math">\(0\)</span>, thus the Ker <span class="math">\(\partial(C_0)\)</span> is the whole 0-chain.</p>
<div class="math">$$\text{Ker} \partial(C_0) = \{a, b, c\}$$</div>
<p> This forms another group we will denote <span class="math">\(Z_0\)</span> (or <span class="math">\(Z_n\)</span> generally), the group of 0-cycles, which in general is a subgroup of <span class="math">\(C_0\)</span>, i.e. <span class="math">\(Z_n \leq C_n\)</span>. With addition defined over <span class="math">\(\mathbb Z_2\)</span> then <span class="math">\(Z_0\)</span> is also ismorphic to <span class="math">\(\mathbb Z_2\)</span> and hence is the same as <span class="math">\(C_0\)</span>.</p>
<p>The other thing we need to find the homology group <span class="math">\(H_0\)</span> is <span class="math">\(\text{Im } \partial_{1}\)</span>. This forms a subgroup of <span class="math">\(Z_0\)</span> that we denote <span class="math">\(B_0\)</span> (or more generally <span class="math">\(B_n\)</span>) which is the group of boundaries of the (n+1)-chain. Hence, <span class="math">\(B_n \leq Z_n \leq C_n\)</span>.</p>
<div class="math">$$\partial{C_1} = \partial({[a, b], [b, c], [c, a]} = (a + b) + (b + c) + (c + a) \\
\partial{C_1} = (a + b) + (b + c) + (c + a) = (a + a) + (b + b) + (c + c) = (0) + (0) + (0) = 0 \\
\partial{C_1} = 0 $$</div>
<p>
So <span class="math">\(\text{Im } \partial_{1} = {0}\)</span></p>
<p>Thus we compute the quotient group <span class="math">\(H_0 = Z_0\ /\ B_0\)</span>, which in this case is:
</p>
<div class="math">$$Z_0 = \text { { {a, b, c}, {0} } } \\
B_0 = \{0\} $$</div>
<p>
so we take the left cosets of <span class="math">\(\{0\}\)</span> for the two elements in <span class="math">\(Z_0\)</span> to get the quotient group, which gives us:
</p>
<div class="math">$$ Z_0\ /\ B_0 = \text { { {a, b, c}, {0} } } = Z_0$$</div>
<p>So in general, if <span class="math">\(B_n = \{0\}\)</span> then <span class="math">\(Z_n\ /\ B_n = Z_n\)</span>. Hence <span class="math">\(H_0 = Z_0\)</span>.</p>
<p>The Betti number <span class="math">\(b_0\)</span> is the dimension of <span class="math">\(H_0 = Z_0\)</span>. What is the dimension of <span class="math">\(H_0\)</span>? Well, it has two elements, but the dimension is defined as the smallest set of generators for a group, and since this group is isomorphic to <span class="math">\(\mathbb Z_2\)</span>, it only has 1 generator. For <span class="math">\(\mathbb Z_2\)</span> the generator is <span class="math">\(1\)</span>, since the whole group can be formed by repeatedly applying the addition operation on <span class="math">\(1\)</span>, i.e. <span class="math">\(1+1=0, 1+1+1 = 1\)</span> and now we have the full <span class="math">\(\mathbb Z_2\)</span>. </p>
<p>So <span class="math">\(b_0 = dim(H_0) = 1\)</span>, which is what we expected, this simplicial complex has 1 connected component.</p>
<p>Now let's start calculating Betti <span class="math">\(b_1\)</span> for the 1-dimension. This time it will be a bit different because figuring out <span class="math">\(\text{Ker}\partial(C_1)\)</span> is going to be more involved. We're going to need to do some algebra.</p>
<p>So, we first want <span class="math">\(Z_1\)</span>, the group of 1-cycles. This is the set of 1-simplices whose boundary is 0. Remember the 1-chain is <span class="math">\(\{ [a,b], [b,c], [c,a]\}\)</span> and forms the 1-chain group <span class="math">\(C_1\)</span> when applied over <span class="math">\(\mathbb Z_2\)</span>. We will setup an equation like this:</p>
<div class="math">$$
\begin{aligned}
\mathscr C_1 &= \lambda_0([a,b]) + \lambda_1([b,c]) \lambda_2([c,a]) \text{ ... where $\lambda_n \in \mathbb Z_2$. $\\$ This is the general form of any element in the vector space $\mathscr C_1$} \\
\lambda_0([a,b]) + \lambda_1([b,c]) + \lambda_2([c,a]) &= 0 \text{ ... then take the boundary of that} \\
\partial(\lambda_0([a,b]) + \lambda_1([b,c]) + \lambda_2([c,a])) &= 0 \\
\lambda_0(a+b) + \lambda_1(b+c) + \lambda_2(c+a) &= 0 \\
\lambda_0{a} + \lambda_0{b} + \lambda_1{b} + \lambda_1{c} + \lambda_2{c} + \lambda_2{a} &= 0 \\
a(\lambda_0 + \lambda_2) + b(\lambda_0 + \lambda_1) + c(\lambda_1 + \lambda_2) &= 0 \text{ ...factor out the a,b,c} \\
\end{aligned}
$$</div>
<p>For this equation to be satisfied, then all the coefficients <span class="math">\(\lambda_n\)</span> for each term need to sum to 0 to make <span class="math">\(a,b,c\)</span> go to <span class="math">\(0\)</span>. That is, if the whole equation goes to <span class="math">\(0\)</span>, then each term like <span class="math">\(a(\lambda_0 + \lambda_2) = 0\)</span>, hence $(\lambda_0 + \lambda_2) = 0, $. So now we basically have a system of linear equations:</p>
<div class="math">$$\lambda_0 + \lambda_2 = 0 \\
\lambda_0 + \lambda_1 = 0 \\
\lambda_1 + \lambda_2 = 0 \\
\text{...now solve...} \\
\lambda_0 = \lambda_2 \\
\lambda_0 = \lambda_1 \\
\lambda_1 = \lambda_1 \\
\lambda_0 = \lambda_1 = \lambda_2 \\
\text{So for the equation above to be satisfied, all the coefficients $\lambda_n$ must be equal. Let's just replace all the lambdas with a single symbol, phi, i.e...} \\
\lambda_0, \lambda_1, \lambda_2 = \phi$$</div>
<p>Now, let's go back to the general expression for the 1-chain vector space <span class="math">\(\mathscr C_1 = \lambda_0([a,b]) + \lambda_1([b,c]) + \lambda_2([c,a])\)</span>. When we take the boundary of that and set it to 0, we get <span class="math">\(\lambda_0 = \lambda_1 = \lambda_2\)</span>, and I proposed we just replace those with one symbol, <span class="math">\(\phi\)</span>. </p>
<p>Hence, the cycle group:
</p>
<div class="math">$$Z_1 \leq \mathscr C_1 = \phi([a,b]) + \phi([b,c]) + \phi([c,a]) \\
Z_1 = \phi([a,b] + [b,c] + [c,a]), \text{ ...remember $\phi$ is from $\mathbb Z_2$ so it is either 0 or 1.}
$$</div>
<p>So the cycle group only contains two elements and is hence isomorphic to <span class="math">\(\mathbb Z_2\)</span>.</p>
<blockquote>
<p><strong>NOTE</strong>: I will introduce new notation. If two mathematical structures (e.g. groups) <span class="math">\(G_1, G_2\)</span> are isomorphic, we denote it as <span class="math">\(G_1 \cong G_2\)</span></p>
</blockquote>
<p>If <span class="math">\(\phi = 0\)</span>, then we get <span class="math">\(\phi([a,b] + [b,c] + [c,a]) = 0([a,b] + [b,c] + [c,a]) = 0 \\\)</span>
, whereas if <span class="math">\(\phi = 1\)</span>, then <span class="math">\(\phi([a,b] + [b,c] + [c,a]) = 1([a,b] + [b,c] + [c,a]) = [a,b] + [b,c] + [c,a] \\\)</span>
So the full group is:
</p>
<div class="math">$$Z_1 = \begin{Bmatrix} [a,b] + [b,c] + [c,a] \\ 0 \end{Bmatrix}$$</div>
<p>The boundary group <span class="math">\(B_1 = Im\partial(C_2)\)</span> but since <span class="math">\(C_2\)</span> is an empty set, <span class="math">\(B_1 = \{0\}\)</span>.</p>
<p>So once again we can compute the homology group:
</p>
<div class="math">$$H_1 = Z_1 / B_1 = \begin{Bmatrix} [a,b] + [b,c] + [c,a] \\ 0 \end{Bmatrix}$$</div>
<p>And Betti <span class="math">\(b_1 = dim(H_1) = 1\)</span> since we only have one generator in the group <span class="math">\(H_1\)</span>.</p>
<p>So that's it for that very simple simplicial complex. We'll move on to a bigger complex. This time I won't be as verbose and will use a lot of the simplifying notation and conventions that I've already defined or described.</p>
<p>Let's do the same but with a slightly more complicated simplicial complex that we've seen before:
</p>
<div class="math">$$S = \text{{[a], [b], [c], [d], [a, b], [b, c], [c, a], [c, d], [d, b], [a, b, c]}}$$</div>
<p> (Depicted below).
<img src="images/TDAimages/simplicialcomplex5b.svg" /></p>
<p>Notice we now have a 2-simplex [a, b, c], depicted as the filled in triangle.</p>
<p>This time we will use the full integer field <span class="math">\(\mathbb Z\)</span> for our coefficients, thus the resulting vector spaces will be infinite instead of finite spaces that we could list out. Since we're using <span class="math">\(\mathbb Z\)</span>, we must define what it means to be a "negative" simplex, e.g. what does <span class="math">\(-[c,a]\)</span> <em>mean</em>? Well we discussed this previously. Basically we define two ways a simplex can be oriented and opposite orientation to the original definition will be assigned the "negative" value of a simplex.</p>
<p>So <span class="math">\([a,c] = -[c,a]\)</span>. But what about <span class="math">\([a,b,c]\)</span>? There are more than two ways to permute a 3 element list, but there only two orientations. <br />
If you look at the oriented simplex from before:
<img src="images/TDAimages/trianglesimplex.svg" />
There are only two ways you can "go around" the loop. Either clockwise or counterclockwise.<br />
<span class="math">\([a,b,c]\)</span> is clockwise (and we'll call it positive).<br />
<span class="math">\([c,a,b]\)</span> is also clockwise (so <span class="math">\([c,a,b] = [a,b,c]\)</span>)<br />
<span class="math">\([a,c,b]\)</span> is a counterclockwise, as well as <span class="math">\([b,c,a]\)</span>, so <span class="math">\([a,b,c] = [c,a,b] = -[a,c,b] = -[b,c,a]\)</span>.<br /></p>
<p>Let's start by listing our chain groups.
</p>
<div class="math">$$ C_0 = \langle{a,b,c,d}\rangle \cong \mathbb Z^4 \\
C_1 = \langle{[a, b], [b, c], [c, a], [c, d], [d, b]}\rangle \cong \mathbb Z^5 \\
C_2 = \langle{[a, b, c]}\rangle \cong \mathbb Z \\ $$</div>
<p>Recall the angle brackets mean <em>span</em>, i.e. the set of all linear combinations of the elements between the angle brackets. This is obviously much more succinct than how we we're building the groups in our last example. And note how each group is isomorphic to the vector space <span class="math">\(\mathbb Z^n\)</span> where <span class="math">\(n\)</span> is the number of simplices in the n-chain.<br /></p>
<p>We can thus describe our <em>chain complex</em> as:</p>
<div class="math">$$C_2 \stackrel{\partial_1}\rightarrow C_1 \stackrel{\partial_0}\rightarrow C_0$$</div>
<p>We know, since we can easily visualize the simplicial complex, that it has one connected component and one 1-cycle (one 1-dimensional hole). Hence, Betti <span class="math">\(b_0 = 1, b_1 = 1\)</span>. But we need to calculate that for ourselves.</p>
<p>Let's start from the higher-dimensional chain group, the 2-chain group.</p>
<p>Remember, <span class="math">\(Z_n = \text{Ker}\partial(C_n)\)</span> the group of n-cycles, which is a subgroup of <span class="math">\(C_n\)</span>. And <span class="math">\(B_n = \text{Im}\partial(C_{n+1})\)</span> is the group of n-boundaries, which is a subgroup of the n-cycles. Hence <span class="math">\(B_n \leq Z_n \leq C_n\)</span>. Also recall, the homology group <span class="math">\(H_n = Z_n\ /\ B_n\)</span> and the n-th Betti number is the dimension of the n-th homology group.</p>
<p>To find <span class="math">\(Z_n\)</span>, we have to setup our expression for a general element in <span class="math">\(C_n\)</span>.
</p>
<div class="math">$$
\begin{aligned}
C_2 &= \lambda_0{[a,b,c]}, \lambda_0 \in \mathbb{Z} \\
Z_2 &= \text{Ker}\partial{(C_2)} \\
\partial{(C_2)} &= \lambda_0{([b,c])} - \lambda_0{([a,c])} + \lambda_0{([a,b])} \text{ ...set it equal to 0 to get Kernel} \\
\lambda_0{([b,c])} - \lambda_0{([a,c])} + \lambda_0{([a,b])} &= 0 \\
\lambda_0{([b,c] - [a,c] + [a,b])} &= 0 \\
\lambda_0 &= 0 \text{ ... there is only a single solution where $\lambda_0 = 0$, then $0=0$. } \\
\lambda_0{[a,b,c]} &= 0, \lambda_0 = 0 \text{ ... so nothing in $C_2$ goes to 0, thus it's only {0} in the Kernel} \\
... \\
\text{Ker}\partial{(C_2)} &= \{0\} \\
\end{aligned}
$$</div>
<p>Since there are no 3-simplices or higher, <span class="math">\(B_2 = {0}\)</span>. Thus Betti <span class="math">\(b_2 = dim(\{0\} / \{0\}) = 0\)</span>. This is what we expect, there are no 2-dimensional holes in the simplicial complex.</p>
<p>Let's do the same for <span class="math">\(C_1\)</span>.</p>
<div class="math">$$
\begin{aligned}
C_1 &= \lambda_0[a, b] + \lambda_1[b, c] + \lambda_2[c, a] + \lambda_3[c, d] + \lambda_4[d, b], \lambda_n \in \mathbb{Z} \\
Z_1 &= \text{Ker}\partial{(C_1)} \\
\partial{(C_1)} &= \lambda_0{(a - b)} + \lambda_1{(b - c)} + \lambda_2{(c - a)} + \lambda_3{(c - d)} + \lambda_4{(d - b)} \\
\text{ ...set it equal to 0 to get Kernel} \\
\lambda_0{(a - b)} + \lambda_1{(b - c)} + \lambda_2{(c - a)} + \lambda_3{(c - d)} + \lambda_4{(d - b)} &= 0 \\
\lambda_0a - \lambda_0b + \lambda_1b - \lambda_1c + \lambda_2c - \lambda_2a + \lambda_3c - \lambda_3d + \lambda_4d - \lambda_4b &= 0 \text { ...factor out the a,b,c,d}\\
a(\lambda_0 - \lambda_2) + b(\lambda_1 - \lambda_0 - \lambda_4) + c(\lambda_2 - \lambda_1 + \lambda_3) + d(\lambda_4 - \lambda_3) &= 0 \\
\text{Now we can setup a system of linear equations...} \\
\lambda_0 - \lambda_2 &= 0 \\
\lambda_1 - \lambda_0 - \lambda_4 &= 0 \\
\lambda_2 - \lambda_1 + \lambda_3 &= 0 \\
\lambda_4 - \lambda_3 &= 0 \\
\text{Solve the equations, plug the solutions back into the original $C_1$ expression...} \\
\lambda_0([a,b] + [b,c] + [c,a]) + \lambda_3([b,c] + \cancel{[a,c]} + [c,d] + \cancel{[c,a]} + [d,b]) &= \text{Ker}\partial{(C_1)} \\
\text{Ker}\partial{(C_1)} &= \lambda_0([a,b] + [b,c] + [c,a]) + \lambda_3([b,c] + [c,d] + [d,b]) \\
Z_1 = \text{Ker}\partial{(C_1)} &\cong \mathbb Z^2
\end{aligned}
$$</div>
<p>Now to get the boundaries <span class="math">\(B_1 = Im\partial(C_2)\)</span>.
</p>
<div class="math">$$
\begin{aligned}
\partial(C_2) &= \lambda_0{([b,c])} - \lambda_0{([a,c])} + \lambda_0{([a,b])} \text {... remember $-[a,c] = [c,a]$ ...} \\
\partial(C_2) &= \lambda_0{([b,c] + [c,a] + [a,b])} \\
B_1 = Im\partial(C_2) &= \{\lambda_0{([b,c] + [c,a] + [a,b])}\}, \lambda_0 \in \mathbb Z \\
B_1 &\cong Z \\
H_1 = Z_1\ /\ B_1 &= \{\lambda_0([a,b] + [b,c] + [c,a]) + \lambda_3([b,c] + [c,d] + [d,b])\}\ /\ \{\lambda_0{([b,c] + [c,a] + [a,b])}\} \\
H_1 &= \{\lambda_3([b,c] + [c,d] + [d,b])\} \cong \mathbb Z
\end{aligned}
$$</div>
<p>Another way to more easily take the quotient group <span class="math">\(H_1 = Z_1\ /\ B_1\)</span> is to just pay attention to what <span class="math">\(Z_n, B_n\)</span> are isomorphic to in terms of <span class="math">\(\mathbb Z^n\)</span>. In this case:
</p>
<div class="math">$$ Z_1 \cong \mathbb Z^2 \\
B_1 \cong \mathbb Z^1 \\
H_1 = \mathbb Z^2\ /\ \mathbb Z = \mathbb Z$$</div>
<p>So since <span class="math">\(H_1 \cong \mathbb Z\)</span>, the Betti number for <span class="math">\(H_1\)</span> is 1 because the dimension of <span class="math">\(\mathbb Z\)</span> is 1 (it only has one generator or basis).</p>
<p>So I think you get the point by now, I'm not going to go through all the details of calculating Betti <span class="math">\(b_0\)</span>, it should be 1 since there is only one connected component.</p>
<h5>Next time...</h5>
<p>We've learned how to calculate homology groups and Betti numbers of simple simplicial complexes by hand. But we're going to need to develop some new tools so that we can let computer algorithms handle these calculations for the real, and generally much larger, simplicial complexes. Next time we'll see how linear algebra gives us an efficient means of doing this.</p>
<h4>References (Websites):</h4>
<ol>
<li>http://dyinglovegrape.com/math/topology_data_1.php</li>
<li>http://www.math.uiuc.edu/~r-ash/Algebra/Chapter4.pdf</li>
<li>https://en.wikipedia.org/wiki/Group_(mathematics)</li>
<li>https://jeremykun.com/2013/04/03/homology-theory-a-primer/</li>
<li>http://suess.sdf-eu.org/website/lang/de/algtop/notes4.pdf</li>
<li>http://www.mit.edu/~evanchen/napkin.html</li>
</ol>
<h4>References (Academic Publications):</h4>
<ol>
<li>
<p>Basher, M. (2012). On the Folding of Finite Topological Space. International Mathematical Forum, 7(15), 745–752. Retrieved from http://www.m-hikari.com/imf/imf-2012/13-16-2012/basherIMF13-16-2012.pdf</p>
</li>
<li>
<p>Day, M. (2012). Notes on Cayley Graphs for Math 5123 Cayley graphs, 1–6.</p>
</li>
<li>
<p>Doktorova, M. (2012). CONSTRUCTING SIMPLICIAL COMPLEXES OVER by, (June).</p>
</li>
<li>
<p>Edelsbrunner, H. (2006). IV.1 Homology. Computational Topology, 81–87. Retrieved from http://www.cs.duke.edu/courses/fall06/cps296.1/</p>
</li>
<li>
<p>Erickson, J. (1908). Homology. Computational Topology, 1–11.</p>
</li>
<li>
<p>Evan Chen. (2016). An Infinitely Large Napkin.</p>
</li>
<li>
<p>Grigor’yan, A., Muranov, Y. V., & Yau, S. T. (2014). Graphs associated with simplicial complexes. Homology, Homotopy and Applications, 16(1), 295–311. http://doi.org/10.4310/HHA.2014.v16.n1.a16</p>
</li>
<li>
<p>Kaczynski, T., Mischaikow, K., & Mrozek, M. (2003). Computing homology. Homology, Homotopy and Applications, 5(2), 233–256. http://doi.org/10.4310/HHA.2003.v5.n2.a8</p>
</li>
<li>
<p>Kerber, M. (2016). Persistent Homology – State of the art and challenges 1 Motivation for multi-scale topology. Internat. Math. Nachrichten Nr, 231(231), 15–33.</p>
</li>
<li>
<p>Khoury, M. (n.d.). Lecture 6 : Introduction to Simplicial Homology Topics in Computational Topology : An Algorithmic View, 1–6.</p>
</li>
<li>
<p>Kraft, R. (2016). Illustrations of Data Analysis Using the Mapper Algorithm and Persistent Homology.</p>
</li>
<li>
<p>Lakshmivarahan, S., & Sivakumar, L. (2016). Cayley Graphs, (1), 1–9.</p>
</li>
<li>
<p>Liu, X., Xie, Z., & Yi, D. (2012). A fast algorithm for constructing topological structure in large data. Homology, Homotopy and Applications, 14(1), 221–238. http://doi.org/10.4310/HHA.2012.v14.n1.a11</p>
</li>
<li>
<p>Naik, V. (2006). Group theory : a first journey, 1–21.</p>
</li>
<li>
<p>Otter, N., Porter, M. A., Tillmann, U., Grindrod, P., & Harrington, H. A. (2015). A roadmap for the computation of persistent homology. Preprint ArXiv, (June), 17. Retrieved from http://arxiv.org/abs/1506.08903</p>
</li>
<li>
<p>Semester, A. (2017). § 4 . Simplicial Complexes and Simplicial Homology, 1–13.</p>
</li>
<li>
<p>Singh, G. (2007). Algorithms for Topological Analysis of Data, (November).</p>
</li>
<li>
<p>Zomorodian, A. (2009). Computational Topology Notes. Advances in Discrete and Computational Geometry, 2, 109–143. Retrieved from http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.50.7483</p>
</li>
<li>
<p>Zomorodian, A. (2010). Fast construction of the Vietoris-Rips complex. Computers and Graphics (Pergamon), 34(3), 263–271. http://doi.org/10.1016/j.cag.2010.03.007</p>
</li>
<li>
<p>Symmetry and Group Theory 1. (2016), 1–18. http://doi.org/10.1016/B978-0-444-53786-7.00026-5</p>
</li>
</ol>
<script type="text/javascript">if (!document.getElementById('mathjaxscript_pelican_#%@#$@#')) {
var align = "center",
indent = "0em",
linebreak = "false";
if (false) {
align = (screen.width < 768) ? "left" : align;
indent = (screen.width < 768) ? "0em" : indent;
linebreak = (screen.width < 768) ? 'true' : linebreak;
}
var mathjaxscript = document.createElement('script');
mathjaxscript.id = 'mathjaxscript_pelican_#%@#$@#';
mathjaxscript.type = 'text/javascript';
mathjaxscript.src = 'https://cdnjs.cloudflare.com/ajax/libs/mathjax/2.7.3/latest.js?config=TeX-AMS-MML_HTMLorMML';
var configscript = document.createElement('script');
configscript.type = 'text/x-mathjax-config';
configscript[(window.opera ? "innerHTML" : "text")] =
"MathJax.Hub.Config({" +
" config: ['MMLorHTML.js']," +
" TeX: { extensions: ['AMSmath.js','AMSsymbols.js','noErrors.js','noUndefined.js'], equationNumbers: { autoNumber: 'none' } }," +
" jax: ['input/TeX','input/MathML','output/HTML-CSS']," +
" extensions: ['tex2jax.js','mml2jax.js','MathMenu.js','MathZoom.js']," +
" displayAlign: '"+ align +"'," +
" displayIndent: '"+ indent +"'," +
" showMathMenu: true," +
" messageStyle: 'normal'," +
" tex2jax: { " +
" inlineMath: [ ['\\\\(','\\\\)'] ], " +
" displayMath: [ ['$$','$$'] ]," +
" processEscapes: true," +
" preview: 'TeX'," +
" }, " +
" 'HTML-CSS': { " +
" availableFonts: ['STIX', 'TeX']," +
" preferredFont: 'STIX'," +
" styles: { '.MathJax_Display, .MathJax .mo, .MathJax .mi, .MathJax .mn': {color: 'inherit ! important'} }," +
" linebreaks: { automatic: "+ linebreak +", width: '90% container' }," +
" }, " +
"}); " +
"if ('default' !== 'default') {" +
"MathJax.Hub.Register.StartupHook('HTML-CSS Jax Ready',function () {" +
"var VARIANT = MathJax.OutputJax['HTML-CSS'].FONTDATA.VARIANT;" +
"VARIANT['normal'].fonts.unshift('MathJax_default');" +
"VARIANT['bold'].fonts.unshift('MathJax_default-bold');" +
"VARIANT['italic'].fonts.unshift('MathJax_default-italic');" +
"VARIANT['-tex-mathit'].fonts.unshift('MathJax_default-italic');" +
"});" +
"MathJax.Hub.Register.StartupHook('SVG Jax Ready',function () {" +
"var VARIANT = MathJax.OutputJax.SVG.FONTDATA.VARIANT;" +
"VARIANT['normal'].fonts.unshift('MathJax_default');" +
"VARIANT['bold'].fonts.unshift('MathJax_default-bold');" +
"VARIANT['italic'].fonts.unshift('MathJax_default-italic');" +
"VARIANT['-tex-mathit'].fonts.unshift('MathJax_default-italic');" +
"});" +
"}";
(document.body || document.getElementsByTagName('head')[0]).appendChild(configscript);
(document.body || document.getElementsByTagName('head')[0]).appendChild(mathjaxscript);
}
</script>
<div class="clear"></div>
<div class="info">
<a href="http://outlace.com/TDApart3.html">posted at 00:30</a>
by Brandon Brown
· <a href="http://outlace.com/category/topological-data-analysis/" rel="tag">Topological Data Analysis</a>
·
<a href="http://outlace.com/tag/tda/" class="tags">TDA</a>
<a href="http://outlace.com/tag/persistent-homology/" class="tags">persistent-homology</a>
</div>
<div id="disqus_thread"></div>
<script type="text/javascript">
var disqus_shortname = 'outlace';
(function() {
var dsq = document.createElement('script'); dsq.type = 'text/javascript'; dsq.async = true;
dsq.src = '//' + disqus_shortname + '.disqus.com/embed.js';
(document.getElementsByTagName('head')[0] || document.getElementsByTagName('body')[0]).appendChild(dsq);
})();
</script>
<noscript>Please enable JavaScript to view the <a href="https://disqus.com/?ref_noscript" rel="nofollow">comments powered by Disqus.</a></noscript>
</article>
<div class="clear"></div>
<footer>
<p>
<!--- <a href="http://outlace.com/feeds/all.atom.xml" rel="alternate">Atom Feed</a> --->
<a href="mailto:outlacedev@gmail.com"><i class="svg-icon email"></i></a>
<a href="http://github.com/outlace"><i class="svg-icon github"></i></a>
<a href="http://outlace.com/feeds/all.atom.xml"><i class="svg-icon rss"></i></a>
</footer>
</div>
<div class="clear"></div>
</div>
<script type="text/javascript">
var gaJsHost = (("https:" == document.location.protocol) ? "https://ssl." : "http://www.");
document.write(unescape("%3Cscript src='" + gaJsHost + "google-analytics.com/ga.js' type='text/javascript'%3E%3C/script%3E"));
</script>
<script type="text/javascript">
try {
var pageTracker = _gat._getTracker("UA-65814776-1");
pageTracker._trackPageview();
} catch(err) {}</script>
</body>
</html>