Cost of a walk in a weighted graph \(G = (V, E, c)\):
Note 1: ETH::A&D
Deck: ETH::A&D
Note Type: Horvath Classic
GUID:
modified
Note Type: Horvath Classic
GUID:
PF|EmWOMd:
Before
Front
Back
Cost of a walk in a weighted graph \(G = (V, E, c)\):
sum of the weight of it's edges: \(\sum_{i = 0}^{l - 1} c(v_i, v_i+1)\)
After
Front
Cost of a walk in a weighted graph \(G = (V, E, c)\)?
Back
Cost of a walk in a weighted graph \(G = (V, E, c)\)?
Sum of the weight of it's edges: \(\sum_{i = 0}^{l - 1} c(v_i, v_{i+1})\)
Field-by-field Comparison
| Field | Before | After |
|---|---|---|
| Front | Cost of a walk in a weighted graph \(G = (V, E, c)\) |
Cost of a walk in a weighted graph \(G = (V, E, c)\)? |
| Back | Sum of the weight of it's edges: \(\sum_{i = 0}^{l - 1} c(v_i, v_{i+1})\) |
Note 2: ETH::A&D
Deck: ETH::A&D
Note Type: Horvath Cloze
GUID:
modified
Note Type: Horvath Cloze
GUID:
n=wUJ;@Xl(
Before
Front
In BFS enter/leave ordering, the FIFO queue guarantees that the enter order = leave order within a given level.
Back
In BFS enter/leave ordering, the FIFO queue guarantees that the enter order = leave order within a given level.
After
Front
In BFS enter/leave ordering, the FIFO queue guarantees that the enter order equals the leave order within a given level.
Back
In BFS enter/leave ordering, the FIFO queue guarantees that the enter order equals the leave order within a given level.
Field-by-field Comparison
| Field | Before | After |
|---|---|---|
| Text | In BFS enter/leave ordering, the FIFO queue guarantees that {{c1:: the <b>enter</b> order |
In BFS enter/leave ordering, the FIFO queue guarantees that {{c1:: the <b>enter</b> order equals the <b>leave</b> order}} within a given level. |
Note 3: ETH::A&D
Deck: ETH::A&D
Note Type: Horvath Classic
GUID:
modified
Note Type: Horvath Classic
GUID:
rK[r{Nqt?9
Before
Front
In a directed graph can we have \((u, v) \land (v, u) \in E\)?
Back
In a directed graph can we have \((u, v) \land (v, u) \in E\)?
Yes
After
Front
In a directed graph can we have \((u, v) \land (v, u) \in E\)?
Back
In a directed graph can we have \((u, v) \land (v, u) \in E\)?
Yes.
Field-by-field Comparison
| Field | Before | After |
|---|---|---|
| Back | Yes | Yes. |
Note 4: ETH::A&D
Deck: ETH::A&D
Note Type: Horvath Classic
GUID:
modified
Note Type: Horvath Classic
GUID:
vE[;wMoI5.
Before
Front
Optimal substructure of cheapest paths:
Back
Optimal substructure of cheapest paths:
A cheapest path in a weighted graph (without negative cycles) has the optimal substructure property: any subpath is itself the cheapest path between it's endpoints.
After
Front
What is the optimal substructure property of shortest paths?
Back
What is the optimal substructure property of shortest paths?
Any subpath of a shortest path is itself the shortest path between its endpoints (requires no negative cycles).
Field-by-field Comparison
| Field | Before | After |
|---|---|---|
| Front | What is the optimal substructure property of shortest paths? | |
| Back | A |
Any subpath of a shortest path is itself the shortest path between its endpoints (requires no negative cycles). |
Note 5: ETH::A&D
Deck: ETH::A&D
Note Type: Algorithms
GUID:
modified
Note Type: Algorithms
GUID:
y@l`JCIJ<4
Before
Front
Runtime of BFS (Breadth First Search)?
Back
Runtime of BFS (Breadth First Search)?
\(O(|V|+|E|)\) (Adjacency List)
The runtime of BFS:
The runtime of BFS:
- each loop we take \(O(1 + \deg(u))\) time (go through the vertex \(u\)'s edges
- We loop a total of \(|V|\) times (we visit each edge max. 1 time)
After
Front
Runtime of BFS (Breadth First Search)?
Back
Runtime of BFS (Breadth First Search)?
\(O(|V|+|E|)\) (Adjacency List)
The runtime of BFS:
The runtime of BFS:
- each loop we take \(O(1 + \deg(u))\) time (go through the vertex \(u\)'s edges
- We loop a total of \(|V|\) times (we visit each edge max. 1 time)
Field-by-field Comparison
| Field | Before | After |
|---|---|---|
| Requirements | Directed Graph |
Directed Graph.<br><br>Note that (negative) cycles are accepted, as we are looking for the "shortest" (not cheapest) path. |
| Use Case | Shortest Path in a directed graph, Bipartite |
Shortest Path in a directed graph, Bipartite test |
Note 6: ETH::A&D
Deck: ETH::A&D
Note Type: Horvath Cloze
GUID:
modified
Note Type: Horvath Cloze
GUID:
yX`f0NZg((
Before
Front
The triangle inequality in a weighted graph is \(d(u, v) \leq d(u, w) + d(w, v)\)
Back
The triangle inequality in a weighted graph is \(d(u, v) \leq d(u, w) + d(w, v)\)
This holds as if the path through \(w\) was actually cheaper, then \(d(u, v)\) would be wrong.
Does not hold in graphs with negative cycles.
Does not hold in graphs with negative cycles.
After
Front
The triangle inequality in a weighted graph is \(d(u, v) \leq d(u, w) + d(w, v)\).
Back
The triangle inequality in a weighted graph is \(d(u, v) \leq d(u, w) + d(w, v)\).
This holds, since if the path through \(w\) was actually cheaper, then \(d(u, v)\) would be wrong.
Does not hold in graphs with negative cycles.
Does not hold in graphs with negative cycles.
Field-by-field Comparison
| Field | Before | After |
|---|---|---|
| Text | The {{c1::<b>triangle inequality</b>}} in a weighted graph is {{c2::\(d(u, v) \leq d(u, w) + d(w, v)\)}} | The {{c1::<b>triangle inequality</b>}} in a weighted graph is {{c2::\(d(u, v) \leq d(u, w) + d(w, v)\)}}. |
| Extra | This holds |
This holds, since if the path through \(w\) was actually cheaper, then \(d(u, v)\) would be wrong.<br><br>Does not hold in graphs with negative cycles. |
Note 7: ETH::A&D
Deck: ETH::A&D
Note Type: Algorithms
GUID:
modified
Note Type: Algorithms
GUID:
z{8WPibSbC
Before
Front
Runtime of Dijkstra's Algorithm?
Back
Runtime of Dijkstra's Algorithm?
\(O((|E| + |V|) \log |V|)\) (or \(O(|V|^2)\)
The runtime is calculated from \(O(n + (\#\text{extract-min} + \#\text{decrease-key}) \cdot \log n)\) which gives \(O((n + m) \cdot \log n)\).
The runtime is calculated from \(O(n + (\#\text{extract-min} + \#\text{decrease-key}) \cdot \log n)\) which gives \(O((n + m) \cdot \log n)\).
After
Front
Runtime of Dijkstra's Algorithm?
Back
Runtime of Dijkstra's Algorithm?
\(O((|V| + |E|) \log |V|)\) (or \(O(|V|^2)\)
The runtime is calculated from \(O(n + (\#\text{extract-min} + \#\text{decrease-key}) \cdot \log n)\) which gives \(O((n + m) \cdot \log n)\).
The runtime is calculated from \(O(n + (\#\text{extract-min} + \#\text{decrease-key}) \cdot \log n)\) which gives \(O((n + m) \cdot \log n)\).
Field-by-field Comparison
| Field | Before | After |
|---|---|---|
| Runtime | \(O((| |
\(O((|V| + |E|) \log |V|)\) (or \(O(|V|^2)\)<br><br>The runtime is calculated from \(O(n + (\#\text{extract-min} + \#\text{decrease-key}) \cdot \log n)\) which gives \(O((n + m) \cdot \log n)\). |
Note 8: ETH::DiskMat
Deck: ETH::DiskMat
Note Type: Horvath Cloze
GUID:
modified
Note Type: Horvath Cloze
GUID:
Au5Kz9Rp2H
Before
Front
\(F\)\(\vdash\)\( \vdash F \lor G\) and \(F \vdash G \lor F\) are valid derivation rules.
Back
\(F\)\(\vdash\)\( \vdash F \lor G\) and \(F \vdash G \lor F\) are valid derivation rules.
After
Front
\(F\) \(\vdash\) \(F \lor G\) and \(F \vdash G \lor F\) are valid derivation rules.
Back
\(F\) \(\vdash\) \(F \lor G\) and \(F \vdash G \lor F\) are valid derivation rules.
Field-by-field Comparison
| Field | Before | After |
|---|---|---|
| Text | {{c1::\(F\) |
{{c1::\(F\) }} \(\vdash\) {{c2::\(F \lor G\)}} and {{c2::\(F \vdash G \lor F\)}} are valid derivation rules. |
Note 9: ETH::DiskMat
Deck: ETH::DiskMat
Note Type: Horvath Cloze
GUID:
modified
Note Type: Horvath Cloze
GUID:
Bv6Pw3Tn8L
Before
Front
Prop. Logic Dervation rules: {{c1::\(\{F, F \rightarrow G\}\)}}\( \vdash\) \( G\).
Back
Prop. Logic Dervation rules: {{c1::\(\{F, F \rightarrow G\}\)}}\( \vdash\) \( G\).
(modus ponens)
After
Front
Derivation rule of modus ponens:
{{c1::\(\{F, F \rightarrow G\}\)}} \( \vdash\) \( G\)
{{c1::\(\{F, F \rightarrow G\}\)}} \( \vdash\) \( G\)
Back
Derivation rule of modus ponens:
{{c1::\(\{F, F \rightarrow G\}\)}} \( \vdash\) \( G\)
{{c1::\(\{F, F \rightarrow G\}\)}} \( \vdash\) \( G\)
Field-by-field Comparison
| Field | Before | After |
|---|---|---|
| Text | Derivation rule of modus ponens:<br><br>{{c1::\(\{F, F \rightarrow G\}\)}} \( \vdash\) {{c2:: \( G\)}} | |
| Extra |
Note 10: ETH::DiskMat
Deck: ETH::DiskMat
Note Type: Horvath Cloze
GUID:
modified
Note Type: Horvath Cloze
GUID:
Cw7Qx4Vm9M
Before
Front
Prop. Logic Dervation rules: {{c1::\(\{F \lor G, F \rightarrow H, G \rightarrow H\}\)}}\(\vdash\)\( \vdash H\).
Back
Prop. Logic Dervation rules: {{c1::\(\{F \lor G, F \rightarrow H, G \rightarrow H\}\)}}\(\vdash\)\( \vdash H\).
(case distinction)
After
Front
Derivation rule of case distinction:
{{c1::\(\{F \lor G, F \rightarrow H, G \rightarrow H\}\)}} \(\vdash\) \(H\)
{{c1::\(\{F \lor G, F \rightarrow H, G \rightarrow H\}\)}} \(\vdash\) \(H\)
Back
Derivation rule of case distinction:
{{c1::\(\{F \lor G, F \rightarrow H, G \rightarrow H\}\)}} \(\vdash\) \(H\)
{{c1::\(\{F \lor G, F \rightarrow H, G \rightarrow H\}\)}} \(\vdash\) \(H\)
Field-by-field Comparison
| Field | Before | After |
|---|---|---|
| Text | Derivation rule of case distinction:<br><br>{{c1::\(\{F \lor G, F \rightarrow H, G \rightarrow H\}\)}} \(\vdash\){{c2:: \(H\)}} | |
| Extra |
Note 11: ETH::DiskMat
Deck: ETH::DiskMat
Note Type: Horvath Cloze
GUID:
modified
Note Type: Horvath Cloze
GUID:
Ga8Ty4Rl9M
Before
Front
A formula in propositional logic is defined recursively:
- An atomic formula is a formula
- If \(F\) and \(G\) are formulas, then also \(\lnot F\), \(F \lor G\), \(F \land G\).
- An atomic formula is a formula
- If \(F\) and \(G\) are formulas, then also \(\lnot F\), \(F \lor G\), \(F \land G\).
Back
A formula in propositional logic is defined recursively:
- An atomic formula is a formula
- If \(F\) and \(G\) are formulas, then also \(\lnot F\), \(F \lor G\), \(F \land G\).
- An atomic formula is a formula
- If \(F\) and \(G\) are formulas, then also \(\lnot F\), \(F \lor G\), \(F \land G\).
After
Front
A formula in propositional logic is defined recursively:
- An atomic formula is a formula
- If \(F\) and \(G\) are formulas, then also \(\lnot F\), \(F \lor G\), \(F \land G\).
Back
A formula in propositional logic is defined recursively:
- An atomic formula is a formula
- If \(F\) and \(G\) are formulas, then also \(\lnot F\), \(F \lor G\), \(F \land G\).
Field-by-field Comparison
| Field | Before | After |
|---|---|---|
| Text | A formula in propositional logic is defined recursively:<br> |
A formula in propositional logic is defined recursively:<br><ol><li>{{c2::An atomic formula is a formula}}</li><li>If \(F\) and \(G\) are formulas, then also {{c3::\(\lnot F\), \(F \lor G\), \(F \land G\)}}.</li></ol> |
Note 12: ETH::DiskMat
Deck: ETH::DiskMat
Note Type: Horvath Classic
GUID:
modified
Note Type: Horvath Classic
GUID:
IY+[tV3KDj
Before
Front
State Lemma 5.18 about the units of a ring and the property they satisfy? (Proof included)
Back
State Lemma 5.18 about the units of a ring and the property they satisfy? (Proof included)
Lemma 5.18: For a ring \(R\), \(R^*\) is a group (the multiplicative group of units of \(R\)).
Proof idea: Every element of \(R^*\) has an inverse by definition, so axiom G3 holds. The other group axioms (associativity, neutral element) are inherited from the ring.
After
Front
State Lemma 5.18 about the units of a ring and the property their set satisfies? (Proof included)
Back
State Lemma 5.18 about the units of a ring and the property their set satisfies? (Proof included)
Lemma 5.18: For a ring \(R\), \(R^*\) is a group (the multiplicative group of units of \(R\)).
Proof idea: Every element of \(R^*\) has an inverse by definition, so axiom G3 holds. The other group axioms (associativity, neutral element) are inherited from the ring.
Field-by-field Comparison
| Field | Before | After |
|---|---|---|
| Front | <p>State Lemma 5.18 about the units of a ring and the property the |
<p>State Lemma 5.18 about the units of a ring and the property their set satisfies? <i>(Proof included)</i></p> |
Note 13: ETH::DiskMat
Deck: ETH::DiskMat
Note Type: Horvath Classic
GUID:
modified
Note Type: Horvath Classic
GUID:
M035/^ZEJ$
Before
Front
What is the number of subgroups of \(\mathbb{Z}_n\)?
Back
What is the number of subgroups of \(\mathbb{Z}_n\)?
The number of divisors of \(n\) (as the order of each subgroup divides the group order (which is n here) by Lagrange).
if \(n\) is written \(n = p_1^{e_1} \cdot p_2^{e_2} \cdots p_k^{e_k}\) then it is \(\prod_{i=1}^k (e_i+1)\)
Note: This only holds because \(\mathbb{Z}_n\) is cyclic and therefore the subgroups are unique.
if \(n\) is written \(n = p_1^{e_1} \cdot p_2^{e_2} \cdots p_k^{e_k}\) then it is \(\prod_{i=1}^k (e_i+1)\)
Note: This only holds because \(\mathbb{Z}_n\) is cyclic and therefore the subgroups are unique.
After
Front
What is the number of subgroups of \(\mathbb{Z}_n\)?
Back
What is the number of subgroups of \(\mathbb{Z}_n\)?
The number of divisors of \(n\) (as the order of each subgroup divides the group order (which is n here) by Lagrange).
If \(n\) is written \(n = p_1^{e_1} \cdot p_2^{e_2} \cdots p_k^{e_k}\) then it is \(\prod_{i=1}^k (e_i+1)\).
Note: This only holds because \(\mathbb{Z}_n\) is cyclic and therefore the subgroups are unique.
If \(n\) is written \(n = p_1^{e_1} \cdot p_2^{e_2} \cdots p_k^{e_k}\) then it is \(\prod_{i=1}^k (e_i+1)\).
Note: This only holds because \(\mathbb{Z}_n\) is cyclic and therefore the subgroups are unique.
Field-by-field Comparison
| Field | Before | After |
|---|---|---|
| Back | The number of divisors of \(n\) (as the order of each subgroup divides the group order (which is n here) by Lagrange). <br> |
The number of divisors of \(n\) (as the order of each subgroup divides the group order (which is n here) by Lagrange). <br><br>If \(n\) is written \(n = p_1^{e_1} \cdot p_2^{e_2} \cdots p_k^{e_k}\) then it is \(\prod_{i=1}^k (e_i+1)\).<br><br><i>Note:</i> This only holds because \(\mathbb{Z}_n\) is cyclic and therefore the subgroups are unique. |
Note 14: ETH::DiskMat
Deck: ETH::DiskMat
Note Type: Horvath Cloze
GUID:
modified
Note Type: Horvath Cloze
GUID:
grVf##]DMH
Before
Front
Lemma 5.17(4): If a ring \(R\) is non-trivial (has more than one element), then \(1 \neq 0\). (Proof in Extra)
Back
Lemma 5.17(4): If a ring \(R\) is non-trivial (has more than one element), then \(1 \neq 0\). (Proof in Extra)
Proof: Assume \(1 = 0\) for contradiction. For any \(a \in R\)
- \(a = a \cdot 1\)
- \(a = a \cdot 0\) (by assumption)
- \(a = 0\)
- Thus there is only the zero element, which is a contradiction to the non-triviality.
After
Front
If a ring \(R\) is non-trivial (has more than one element), then \(1 \neq 0\). (Proof in Extra)
Back
If a ring \(R\) is non-trivial (has more than one element), then \(1 \neq 0\). (Proof in Extra)
Proof: Assume \(1 = 0\) for contradiction. For any \(a \in R\)
- \(a = a \cdot 1\)
- \(a = a \cdot 0\) (by assumption)
- \(a = 0\)
- Thus there is only the zero element, which is a contradiction to the non-triviality.
Lemma 5.17(4)
Field-by-field Comparison
| Field | Before | After |
|---|---|---|
| Text | <p> |
<p>If a ring \(R\) is {{c1::non-trivial (has more than one element)}}, then {{c2::\(1 \neq 0\)}}. <i>(Proof in Extra)</i></p> |
| Extra | Proof: Assume \(1 = 0\) for contradiction. For any \(a \in R\)<br><ol><li>\(a = a \cdot 1\)</li><li>\(a = a \cdot 0\) (by assumption)</li><li>\(a = 0\)</li><li>Thus there is only the zero element, which is a contradiction to the non-triviality.</li></ol> | Proof: Assume \(1 = 0\) for contradiction. For any \(a \in R\)<br><ol><li>\(a = a \cdot 1\)</li><li>\(a = a \cdot 0\) (by assumption)</li><li>\(a = 0\)</li><li>Thus there is only the zero element, which is a contradiction to the non-triviality.</li></ol><div><strong>Lemma 5.17(4)</strong><br></div> |
Note 15: ETH::DiskMat
Deck: ETH::DiskMat
Note Type: Horvath Classic
GUID:
modified
Note Type: Horvath Classic
GUID:
hAzQO,E_+E
Before
Front
What property does the order of elements in finite groups have?
Back
What property does the order of elements in finite groups have?
Lemma 5.6: In a finite group \(G\), every element has a finite order.
(This doesn't hold for infinite groups - elements can have infinite order.)
Proof: Since the order is finite, elements must repeat. That means, there exist \(m > n \geq 0\) s.t. \(g^m = g^n\)
\(\implies g^{m-n} = e\)
After
Front
What property do the orders of elements in finite groups have?
Back
What property do the orders of elements in finite groups have?
Lemma 5.6: In a finite group \(G\), every element has a finite order.
(This doesn't hold for infinite groups - elements can have infinite order.)
Proof: Since the order is finite, elements must repeat. That means, there exist \(m > n \geq 0\) s.t. \(g^m = g^n\)
\(\implies g^{m-n} = e\)
Field-by-field Comparison
| Field | Before | After |
|---|---|---|
| Front | <p>What property do |
<p>What property do the orders of elements in finite groups have?</p> |
Note 16: ETH::DiskMat
Deck: ETH::DiskMat
Note Type: Horvath Cloze
GUID:
modified
Note Type: Horvath Cloze
GUID:
ymyo>YcM?L
Before
Front
Lemma 5.22(1): If \(D\) is an integral domain, then \(D[x]\) is also an integral domain.
Back
Lemma 5.22(1): If \(D\) is an integral domain, then \(D[x]\) is also an integral domain.
After
Front
If \(D\) is an integral domain, then \(D[x]\) also is an integral domain.
Back
If \(D\) is an integral domain, then \(D[x]\) also is an integral domain.
Lemma 5.22(1)
Field-by-field Comparison
| Field | Before | After |
|---|---|---|
| Text | <p> |
<p>If \(D\) is an {{c1::integral domain}}, then \(D[x]\) {{c2::also is an integral domain}}.</p> |
| Extra | <strong>Lemma 5.22(1)</strong> |
Note 17: ETH::EProg
Deck: ETH::EProg
Note Type: Horvath Classic
GUID:
modified
Note Type: Horvath Classic
GUID:
G#$#7KW!b}
Before
Front
instanceof can result in a Compile / Runtime / No error?
Back
instanceof can result in a Compile / Runtime / No error?
instanceof never throws an exception, just compile errors.After
Front
instanceof can result in a Compile-/Runtime-/No error?
Back
instanceof can result in a Compile-/Runtime-/No error?
instanceof never throws an exception, just compile errors.Field-by-field Comparison
| Field | Before | After |
|---|---|---|
| Front | instanceof can result in a Compile |
instanceof can result in a Compile-/Runtime-/No error? |
Note 18: ETH::EProg
Deck: ETH::EProg
Note Type: Horvath Cloze
GUID:
modified
Note Type: Horvath Cloze
GUID:
i2g|!nNV|m
Before
Front
We can omit everything but the semicolons in the for loop for(...)
Back
We can omit everything but the semicolons in the for loop for(...)
After
Front
We can omit everything but the semicolons in a for-loop.
Back
We can omit everything but the semicolons in a for-loop.
Field-by-field Comparison
| Field | Before | After |
|---|---|---|
| Text | We can omit everything but {{c1::the semicolons}} in |
We can omit everything but {{c1::the semicolons}} in a for-loop. |
Note 19: ETH::LinAlg
Deck: ETH::LinAlg
Note Type: Horvath Classic
GUID:
modified
Note Type: Horvath Classic
GUID:
AXk(.4O|pc
Before
Front
Why is \(R\) upper triangular in the QR decomp?
Back
Why is \(R\) upper triangular in the QR decomp?
\(R\) is upper triangular because each \(q_k\) is orthogonal to every \(a_i\) for \(i < k\) (all after it), thus they are \(0\).
You can see here, since \(q_2, \dots, q_m\) are by construction orthogonal to \(q_1\) thus \(a_1\), all entries below \(1\) in the first column are \(0\). The same goes for all entries below \(2\) in the second column.
You can see here, since \(q_2, \dots, q_m\) are by construction orthogonal to \(q_1\) thus \(a_1\), all entries below \(1\) in the first column are \(0\). The same goes for all entries below \(2\) in the second column.
After
Front
Why is \(R\) upper triangular in the QR decomposition?
Back
Why is \(R\) upper triangular in the QR decomposition?
\(R\) is upper triangular because each \(q_k\) is orthogonal to every \(a_i\) for \(i < k\) (all after it), thus they are \(0\).
You can see here, since \(q_2, \dots, q_m\) are by construction orthogonal to \(q_1\) thus \(a_1\), all entries below \(1\) in the first column are \(0\). The same goes for all entries below \(2\) in the second column.
You can see here, since \(q_2, \dots, q_m\) are by construction orthogonal to \(q_1\) thus \(a_1\), all entries below \(1\) in the first column are \(0\). The same goes for all entries below \(2\) in the second column.
Field-by-field Comparison
| Field | Before | After |
|---|---|---|
| Front | Why is \(R\) upper triangular in the QR decomp? | Why is \(R\) upper triangular in the QR decomposition? |
Note 20: ETH::LinAlg
Deck: ETH::LinAlg
Note Type: Horvath Cloze
GUID:
modified
Note Type: Horvath Cloze
GUID:
Bs.wqkt>9r
Before
Front
Every set of \(n\) linearly independent vectors spans {{c1:: \(\mathbb{R}^n\)}}.
Back
Every set of \(n\) linearly independent vectors spans {{c1:: \(\mathbb{R}^n\)}}.
This is from the script.
After
Front
Every set of \(n\) linearly independent vectors spans {{c1::\(\mathbb{R}^n\)}}.
Back
Every set of \(n\) linearly independent vectors spans {{c1::\(\mathbb{R}^n\)}}.
This is from the script.
Field-by-field Comparison
| Field | Before | After |
|---|---|---|
| Text | Every set of \(n\) {{c1:: |
Every set of \(n\) {{c1::linearly independent}} vectors spans {{c1::\(\mathbb{R}^n\)}}. |
Note 21: ETH::LinAlg
Deck: ETH::LinAlg
Note Type: Horvath Cloze
GUID:
modified
Note Type: Horvath Cloze
GUID:
FjSbP7PsTQ
Before
Front
\(A^\dagger A\) is the projection matrix on \(C(A^\top)\)
Back
\(A^\dagger A\) is the projection matrix on \(C(A^\top)\)
After
Front
\(A^\dagger A\) is the projection matrix onto \(C(A^\top)\).
Back
\(A^\dagger A\) is the projection matrix onto \(C(A^\top)\).
Field-by-field Comparison
| Field | Before | After |
|---|---|---|
| Text | \(A^\dagger A\) is {{c1::the projection matrix on |
\(A^\dagger A\) is {{c1::the projection matrix onto \(C(A^\top)\)}}. |
Note 22: ETH::LinAlg
Deck: ETH::LinAlg
Note Type: Horvath Cloze
GUID:
modified
Note Type: Horvath Cloze
GUID:
G1|bG=ffVu
Before
Front
Let \(Q\) be the \(m \times n\) matrix whose columns are an orthonormal basis of \(C(A)\).
Then the projection matrix that projects to \(C(A)\) is given by \(QQ^\top\). Proof Included
Back
Let \(Q\) be the \(m \times n\) matrix whose columns are an orthonormal basis of \(C(A)\).
Then the projection matrix that projects to \(C(A)\) is given by \(QQ^\top\). Proof Included
\(A^\top A\) simplifies to \(I\) in the case where our \(A\) is orthogonal. Thus \(P = A (A^\top A)^{-1} A^\top\) simplifies to \(P = AA^\top\).
After
Front
Let \(Q\) be the \(m \times n\) matrix whose columns are an orthonormal basis of \(C(A)\).
Then the projection matrix that projects to \(C(A)\) is given by \(QQ^\top\). Proof Included
Back
Let \(Q\) be the \(m \times n\) matrix whose columns are an orthonormal basis of \(C(A)\).
Then the projection matrix that projects to \(C(A)\) is given by \(QQ^\top\). Proof Included
\(Q^\top Q\) simplifies to \(I\) in the case where our \(Q\) is orthogonal.
Thus \(P = Q (Q^\top Q)^{-1} Q^\top\) simplifies to \(P = QQ^\top\).
Thus \(P = Q (Q^\top Q)^{-1} Q^\top\) simplifies to \(P = QQ^\top\).
Field-by-field Comparison
| Field | Before | After |
|---|---|---|
| Extra | \( |
\(Q^\top Q\) simplifies to \(I\) in the case where our \(Q\) is orthogonal. <br><br>Thus \(P = Q (Q^\top Q)^{-1} Q^\top\) simplifies to \(P = QQ^\top\). |
Note 23: ETH::LinAlg
Deck: ETH::LinAlg
Note Type: Horvath Classic
GUID:
modified
Note Type: Horvath Classic
GUID:
G2Hf{n(RiQ
Before
Front
How do we get the \(QR\) decomp for \(A\) with linearly independent columns?
Back
How do we get the \(QR\) decomp for \(A\) with linearly independent columns?
- \(Q\) is the result of Gram-Schmidt on \(A\)
- \(R = Q^\top A\)
After
Front
How do we get the \(QR\) decomposition for \(A\) with linearly independent columns?
Back
How do we get the \(QR\) decomposition for \(A\) with linearly independent columns?
- \(Q\) is the result of Gram-Schmidt on \(A\)
- \(R = Q^\top A\)
Field-by-field Comparison
| Field | Before | After |
|---|---|---|
| Front | How do we get the \(QR\) decomp for \(A\) with linearly independent columns? | How do we get the \(QR\) decomposition for \(A\) with linearly independent columns? |
Note 24: ETH::LinAlg
Deck: ETH::LinAlg
Note Type: Horvath Cloze
GUID:
modified
Note Type: Horvath Cloze
GUID:
K=a-HUOVwC
Before
Front
Three equivalent statements:
(i) {{c1::\(T_A : \mathbb{R}^m \rightarrow \mathbb{R}^m\) is bijective.}}
(ii) There is an \(m \times m\) matrix \(B\) such that \(BA = I\).
(iii) The columns of \(A\) are linearly independent.
(i) {{c1::\(T_A : \mathbb{R}^m \rightarrow \mathbb{R}^m\) is bijective.}}
(ii) There is an \(m \times m\) matrix \(B\) such that \(BA = I\).
(iii) The columns of \(A\) are linearly independent.
Back
Three equivalent statements:
(i) {{c1::\(T_A : \mathbb{R}^m \rightarrow \mathbb{R}^m\) is bijective.}}
(ii) There is an \(m \times m\) matrix \(B\) such that \(BA = I\).
(iii) The columns of \(A\) are linearly independent.
(i) {{c1::\(T_A : \mathbb{R}^m \rightarrow \mathbb{R}^m\) is bijective.}}
(ii) There is an \(m \times m\) matrix \(B\) such that \(BA = I\).
(iii) The columns of \(A\) are linearly independent.
The third one can be derived from the fact that if \(BA = I\), there is only a single \(x \in \mathbb{R}^m\) such that \(A \textbf{x} = 0\).
It is also intuitively clear that if not all columns were linearly independent, we'd actually have a tall linear transformation and would be losing information.
It is also intuitively clear that if not all columns were linearly independent, we'd actually have a tall linear transformation and would be losing information.
After
Front
Three equivalent statements:
- {{c1::\(T_A : \mathbb{R}^m \rightarrow \mathbb{R}^m\) is bijective.}}
- There is an \(m \times m\) matrix \(B\) such that \(BA = I\).
- The columns of \(A\) are linearly independent.
Back
Three equivalent statements:
- {{c1::\(T_A : \mathbb{R}^m \rightarrow \mathbb{R}^m\) is bijective.}}
- There is an \(m \times m\) matrix \(B\) such that \(BA = I\).
- The columns of \(A\) are linearly independent.
The third one can be derived from the fact that if \(BA = I\), there is only a single \(x \in \mathbb{R}^m\) such that \(A \textbf{x} = 0\).
It is also intuitively clear that if not all columns were linearly independent, we'd actually have a tall linear transformation and would be losing information.
It is also intuitively clear that if not all columns were linearly independent, we'd actually have a tall linear transformation and would be losing information.
Field-by-field Comparison
| Field | Before | After |
|---|---|---|
| Text | Three equivalent statements:<br>< |
Three equivalent statements:<br><ol><li>{{c1::\(T_A : \mathbb{R}^m \rightarrow \mathbb{R}^m\) is bijective.}}</li><li>{{c2::There is an \(m \times m\) matrix \(B\) such that \(BA = I\).}}</li><li>{{c3::The columns of \(A\) are linearly independent.}}</li></ol> |
Note 25: ETH::LinAlg
Deck: ETH::LinAlg
Note Type: Horvath Cloze
GUID:
modified
Note Type: Horvath Cloze
GUID:
OE;g^EoLnT
Before
Front
The \(R\) in QR-decomposition is upper triangular and invertible
Back
The \(R\) in QR-decomposition is upper triangular and invertible
After
Front
The \(R\) in QR-decomposition is upper triangular and invertible.
Back
The \(R\) in QR-decomposition is upper triangular and invertible.
Field-by-field Comparison
| Field | Before | After |
|---|---|---|
| Text | The \(R\) in QR-decomposition is {{c1::<i>upper triangular</i>}} and {{c1::<i>invertible</i>}} | The \(R\) in QR-decomposition is {{c1::<i>upper triangular</i>}} and {{c1::<i>invertible</i>}}. |
Note 26: ETH::LinAlg
Deck: ETH::LinAlg
Note Type: Horvath Cloze
GUID:
modified
Note Type: Horvath Cloze
GUID:
QGIRdw&4iR
Before
Front
For \(A \in \mathbb{R}^{m \times n}\) with \(\text{rank}(A) = n\), the pseudoinverse \(A^\dagger\) is a left inverse of \(A\), meaning \[ A^\dagger A = I \]Proof Included
Back
For \(A \in \mathbb{R}^{m \times n}\) with \(\text{rank}(A) = n\), the pseudoinverse \(A^\dagger\) is a left inverse of \(A\), meaning \[ A^\dagger A = I \]Proof Included
Proof: Since \(A\) has full column rank, \(A^\top A\) invertible and then \(A^\dagger A = ((A^\top A)^{-1} A^\top)A\) \(= (A^\top A)^{-1} (A^\top A) = I\).
After
Front
For \(A \in \mathbb{R}^{m \times n}\) with \(\text{rank}(A) = n\), the pseudoinverse \(A^\dagger\) is a left inverse of \(A\), meaning: \[ A^\dagger A = I \]Proof Included
Back
For \(A \in \mathbb{R}^{m \times n}\) with \(\text{rank}(A) = n\), the pseudoinverse \(A^\dagger\) is a left inverse of \(A\), meaning: \[ A^\dagger A = I \]Proof Included
Proof: Since \(A\) has full column rank, \(A^\top A\) invertible and then \(A^\dagger A = ((A^\top A)^{-1} A^\top)A\) \(= (A^\top A)^{-1} (A^\top A) = I\).
Field-by-field Comparison
| Field | Before | After |
|---|---|---|
| Text | For \(A \in \mathbb{R}^{m \times n}\) with \(\text{rank}(A) = n\), the pseudoinverse \(A^\dagger\) is {{c1::a left inverse}} of \(A\), meaning |
For \(A \in \mathbb{R}^{m \times n}\) with \(\text{rank}(A) = n\), the pseudoinverse \(A^\dagger\) is {{c1::a left inverse}} of \(A\), meaning: \[{{c1:: A^\dagger A = I }}\]<i>Proof Included</i> |
Note 27: ETH::LinAlg
Deck: ETH::LinAlg
Note Type: Horvath Classic
GUID:
modified
Note Type: Horvath Classic
GUID:
dle9WT5o|g
Before
Front
What is the pseudoinverse in the case where \(A \in \mathbb{R}^{n \times m}\) has independent rows?
Back
What is the pseudoinverse in the case where \(A \in \mathbb{R}^{n \times m}\) has independent rows?
Because \(rank(A) = r = m\) and thus \(n \geq m\)
We know \(x = x_r + x_n\) for \(x_r \in R(A)\) and \(x_n \in N(A)\) thus we pick \(x = x_r + 0\) to get the smallest norm.
- \(C(A)\)spans \(\mathbb{R}^m\) (columns span the space)
- \(R(A) \subseteq\) \(\mathbb{R}^n\)
We know \(x = x_r + x_n\) for \(x_r \in R(A)\) and \(x_n \in N(A)\) thus we pick \(x = x_r + 0\) to get the smallest norm.
After
Front
What is the pseudoinverse in the case where \(A \in \mathbb{R}^{n \times m}\) has independent rows?
Back
What is the pseudoinverse in the case where \(A \in \mathbb{R}^{n \times m}\) has independent rows?
Because \(rank(A) = r = m\) and thus \(n \geq m\)
We know \(x = x_r + x_n\) for \(x_r \in R(A)\) and \(x_n \in N(A)\) thus we pick \(x = x_r + 0\) to get the smallest norm.
- \(C(A)\) spans \(\mathbb{R}^m\) (columns span the space)
- \(R(A) \subseteq\) \(\mathbb{R}^n\)
We know \(x = x_r + x_n\) for \(x_r \in R(A)\) and \(x_n \in N(A)\) thus we pick \(x = x_r + 0\) to get the smallest norm.
Field-by-field Comparison
| Field | Before | After |
|---|---|---|
| Back | Because \(rank(A) = r = m\) and thus \(n \geq m\)<ul><li>\(C(A)\)spans \(\mathbb{R}^m\) (columns span the space)</li><li>\(R(A) \subseteq\) \(\mathbb{R}^n\)</li></ul>There could be multiple \(x \in \mathbb{R}^n\) that map to \(T_A(x) = b\). We pick the one with the smallest norm \(||x||^2\).<br>We know \(x = x_r + x_n\) for \(x_r \in R(A)\) and \(x_n \in N(A)\) thus we pick \(x = x_r + 0\) to get the smallest norm.<br><br><div> <img src="paste-4707a6f9abbe720721f1a4ab781ab8c8fda3c76a.jpg"></div> | Because \(rank(A) = r = m\) and thus \(n \geq m\)<ul><li>\(C(A)\) spans \(\mathbb{R}^m\) (columns span the space)</li><li>\(R(A) \subseteq\) \(\mathbb{R}^n\)</li></ul>There could be multiple \(x \in \mathbb{R}^n\) that map to \(T_A(x) = b\). We pick the one with the smallest norm \(||x||^2\).<br><br>We know \(x = x_r + x_n\) for \(x_r \in R(A)\) and \(x_n \in N(A)\) thus we pick \(x = x_r + 0\) to get the smallest norm.<br><br><div> <img src="paste-4707a6f9abbe720721f1a4ab781ab8c8fda3c76a.jpg"></div> |
Note 28: ETH::LinAlg
Deck: ETH::LinAlg
Note Type: Horvath Classic
GUID:
modified
Note Type: Horvath Classic
GUID:
f?EhyxxJ04
Before
Front
Rewrite \(A^\dagger = R^\dagger C^\dagger\) in terms of A, R, C:
Back
Rewrite \(A^\dagger = R^\dagger C^\dagger\) in terms of A, R, C:
\(A^\dagger = R^\top {(RR^\top)}^{-1} {(C^\top C)}^{-1} C^\top =\) \(R^\top {(C^\top C R R^\top)}^{-1} C^\top =\) \(R^\top {(C^\top A R^\top)}^{-1}C^\top\).
After
Front
Rewrite \(A^\dagger = R^\dagger C^\dagger\) in terms of \(A\), \(R\), \(C\):
Back
Rewrite \(A^\dagger = R^\dagger C^\dagger\) in terms of \(A\), \(R\), \(C\):
\(\begin{aligned}
A^\dagger &= R^\top (RR^\top)^{-1} (C^\top C)^{-1} C^\top \\
&= R^\top (C^\top C R R^\top)^{-1} C^\top \\
&= R^\top (C^\top A R^\top)^{-1} C^\top
\end{aligned}\)
Field-by-field Comparison
| Field | Before | After |
|---|---|---|
| Front | Rewrite \(A^\dagger = R^\dagger C^\dagger\) in terms of |
Rewrite \(A^\dagger = R^\dagger C^\dagger\) in terms of \(A\), \(R\), \(C\): |
| Back | \(A^\dagger = R^\top |
\(\begin{aligned} A^\dagger &= R^\top (RR^\top)^{-1} (C^\top C)^{-1} C^\top \\ &= R^\top (C^\top C R R^\top)^{-1} C^\top \\ &= R^\top (C^\top A R^\top)^{-1} C^\top \end{aligned}\) |
Note 29: ETH::LinAlg
Deck: ETH::LinAlg
Note Type: Horvath Cloze
GUID:
modified
Note Type: Horvath Cloze
GUID:
gRXLRWq0n1
Before
Front
Let \(A\) be an \(m \times n\) matrix with linearly independent columns. The QR decomposition is given by \[ A = QR \]where
- \(Q\) is an \(m \times n\) matrix with orthonormal columns (they are the output of Gram-Schmidt)
- \(R\) is an upper triangular matrix given by \(R = Q^\top A\).
Back
Let \(A\) be an \(m \times n\) matrix with linearly independent columns. The QR decomposition is given by \[ A = QR \]where
- \(Q\) is an \(m \times n\) matrix with orthonormal columns (they are the output of Gram-Schmidt)
- \(R\) is an upper triangular matrix given by \(R = Q^\top A\).
After
Front
Let \(A\) be an \(m \times n\) matrix with linearly independent columns. The QR decomposition is given by: \[ A = QR \]where
- \(Q\) is an \(m \times n\) matrix with orthonormal columns (they are the output of Gram-Schmidt)
- \(R\) is an upper triangular matrix given by \(R = Q^\top A\).
Back
Let \(A\) be an \(m \times n\) matrix with linearly independent columns. The QR decomposition is given by: \[ A = QR \]where
- \(Q\) is an \(m \times n\) matrix with orthonormal columns (they are the output of Gram-Schmidt)
- \(R\) is an upper triangular matrix given by \(R = Q^\top A\).
Field-by-field Comparison
| Field | Before | After |
|---|---|---|
| Text | <div>Let \(A\) be an \(m \times n\) matrix with {{c1::<b>linearly independent</b>}}<b> </b>columns. The QR decomposition is given by |
<div>Let \(A\) be an \(m \times n\) matrix with {{c1::<b>linearly independent</b>}}<b> </b>columns. The QR decomposition is given by: \[ A = QR \]where</div><div><ul><li>\(Q\) is {{c1::an \(m \times n\) matrix with orthonormal columns (they are the output of Gram-Schmidt) }}</li><li>\(R\) is {{c2:: an upper triangular matrix given by \(R = Q^\top A\)}}.</li></ul></div> |
Note 30: ETH::LinAlg
Deck: ETH::LinAlg
Note Type: Horvath Cloze
GUID:
modified
Note Type: Horvath Cloze
GUID:
gmHrq^j=e&
Before
Front
\(QQ^\top A = A\) because \(QQ^\top \) is the projection onto \(A\), and \(C(Q) = C(A)\).
Back
\(QQ^\top A = A\) because \(QQ^\top \) is the projection onto \(A\), and \(C(Q) = C(A)\).
After
Front
\(QQ^\top A = A\) because \(QQ^\top \) is the projection onto \(A\), and \(C(Q) = C(A)\).
Back
\(QQ^\top A = A\) because \(QQ^\top \) is the projection onto \(A\), and \(C(Q) = C(A)\).
Field-by-field Comparison
| Field | Before | After |
|---|---|---|
| Text | \(QQ^\top A = {{c1::A}}\) because {{c1:: |
\(QQ^\top A = {{c1::A}}\) because {{c1::\(QQ^\top \) is the projection onto \(A\), and \(C(Q) = C(A)\)}}. |
Note 31: ETH::LinAlg
Deck: ETH::LinAlg
Note Type: Horvath Classic
GUID:
modified
Note Type: Horvath Classic
GUID:
l
Before
Front
How do we solve \(Ax = b\) using RREF
Back
How do we solve \(Ax = b\) using RREF
We run \(\text{RREF}(A, b)\) and solve the resulting equation using back-substitution.
After
Front
How do we solve \(Ax = b\) using RREF?
Back
How do we solve \(Ax = b\) using RREF?
We run \(\text{RREF}(A, b)\) and solve the resulting equation using back-substitution.
Field-by-field Comparison
| Field | Before | After |
|---|---|---|
| Front | How do we solve \(Ax = b\) using RREF | How do we solve \(Ax = b\) using RREF? |
Note 32: ETH::LinAlg
Deck: ETH::LinAlg
Note Type: Horvath Classic
GUID:
modified
Note Type: Horvath Classic
GUID:
p:TgRlDdKr
Before
Front
What is the pseudoinverse in the case where \(A \in \mathbb{R}^{n \times m}\) has independent columns?
Back
What is the pseudoinverse in the case where \(A \in \mathbb{R}^{n \times m}\) has independent columns?
Because \(rank(A) = r = n\) and thus \(m \geq n\)
- \(R(A)\) spans \(\mathbb{R}^n\)(rows span the space)
- \(C(A) \subseteq\) \(\mathbb{R}^m\) (as \(A\) is not necessarily square)
We therefore first project into \(b\) into \(C(A)\) and then invert, which is Least Squares
After
Front
What is the pseudoinverse in the case where \(A \in \mathbb{R}^{n \times m}\) has independent columns?
Back
What is the pseudoinverse in the case where \(A \in \mathbb{R}^{n \times m}\) has independent columns?
Because \(rank(A) = r = n\) and thus \(m \geq n\)
- \(R(A)\) spans \(\mathbb{R}^n\)(rows span the space)
- \(C(A) \subseteq\) \(\mathbb{R}^m\) (as \(A\) is not necessarily square)
We therefore first project \(b\) into \(C(A)\) and then invert, which is Least Squares.
Field-by-field Comparison
| Field | Before | After |
|---|---|---|
| Back | Because \(rank(A) = r = n\) and thus \(m \geq n\)<br><ul><li>\(R(A)\) spans \(\mathbb{R}^n\)(rows span the space)</li><li>\(C(A) \subseteq\) \(\mathbb{R}^m\) (as \(A\) is not necessarily square)</li></ul><div>We therefore first project |
Because \(rank(A) = r = n\) and thus \(m \geq n\)<br><ul><li>\(R(A)\) spans \(\mathbb{R}^n\)(rows span the space)</li><li>\(C(A) \subseteq\) \(\mathbb{R}^m\) (as \(A\) is not necessarily square)</li></ul><div>We therefore first project \(b\) into \(C(A)\) and then invert, which is <b>Least Squares.</b></div><br><div> <img src="paste-455009459e5a5c70fa5574bdbcedcfb838341523.jpg"></div> |
Note 33: ETH::LinAlg
Deck: ETH::LinAlg
Note Type: Horvath Classic
GUID:
modified
Note Type: Horvath Classic
GUID:
u8Qxy,>bCQ
Before
Front
Let \(A \in \mathbb{R}^{m \times m}\). \(A\) is invertible if:
Back
Let \(A \in \mathbb{R}^{m \times m}\). \(A\) is invertible if:
There is a \(m \times m\) matrix \(B\) such that \(BA = I\).
Exists only if \(A\) has linearly independent columns
Exists only if \(A\) has linearly independent columns
After
Front
Let \(A \in \mathbb{R}^{m \times m}\). \(A\) is invertible if:
Back
Let \(A \in \mathbb{R}^{m \times m}\). \(A\) is invertible if:
There is a \(m \times m\) matrix \(B\) such that \(BA = I\).
Exists only if \(A\) has linearly independent columns.
Exists only if \(A\) has linearly independent columns.
Field-by-field Comparison
| Field | Before | After |
|---|---|---|
| Back | There is a \(m \times m\) matrix \(B\) such that \(BA = I\).<br><br><i>Exists only if </i>\(A\)<i> has linearly independent columns</i> | There is a \(m \times m\) matrix \(B\) such that \(BA = I\).<br><br><i>Exists only if </i>\(A\)<i> has linearly independent columns.</i> |
Note 34: ETH::LinAlg
Deck: ETH::LinAlg
Note Type: Horvath Cloze
GUID:
modified
Note Type: Horvath Cloze
GUID:
ve7Q_/^p1y
Before
Front
For \(A \in \mathbb{R}^{m \times n}\) with \(\text{rank}(A) = m\), we define the pseudo-inverse \(A^\dagger \in \mathbb{R}^{n \times m}\) as \[ A^\dagger = {{c1::A^\top (A A^\top)^{-1} }}\]
Back
For \(A \in \mathbb{R}^{m \times n}\) with \(\text{rank}(A) = m\), we define the pseudo-inverse \(A^\dagger \in \mathbb{R}^{n \times m}\) as \[ A^\dagger = {{c1::A^\top (A A^\top)^{-1} }}\]
For an \(A\) with full column-rank, we basically define, \(A^\dagger\) as the transpose of the pseudoinverse of the transpose:
After
Front
For \(A \in \mathbb{R}^{m \times n}\) with \(\text{rank}(A) = m\), we define the pseudo-inverse \(A^\dagger \in \mathbb{R}^{n \times m}\) as:\[ A^\dagger = {{c1::A^\top (A A^\top)^{-1} }}\]
Back
For \(A \in \mathbb{R}^{m \times n}\) with \(\text{rank}(A) = m\), we define the pseudo-inverse \(A^\dagger \in \mathbb{R}^{n \times m}\) as:\[ A^\dagger = {{c1::A^\top (A A^\top)^{-1} }}\]
For an \(A\) with full column-rank, we basically define, \(A^\dagger\) as the transpose of the pseudoinverse of the transpose:
Field-by-field Comparison
| Field | Before | After |
|---|---|---|
| Text | For \(A \in \mathbb{R}^{m \times n}\) with \(\text{rank}(A) = m\), we define the <b>pseudo-inverse</b> \(A^\dagger \in \mathbb{R}^{n \times m}\) as |
For \(A \in \mathbb{R}^{m \times n}\) with \(\text{rank}(A) = m\), we define the <b>pseudo-inverse</b> \(A^\dagger \in \mathbb{R}^{n \times m}\) as:\[ A^\dagger = {{c1::A^\top (A A^\top)^{-1} }}\] |
Note 35: ETH::LinAlg
Deck: ETH::LinAlg
Note Type: Horvath Cloze
GUID:
modified
Note Type: Horvath Cloze
GUID:
v~twgkx^)U
Before
Front
For \(A \in \mathbb{R}^{m \times n}\) with \(\text{rank}(A) = r\) and CR decomposition \(A = CR\), we define the pseudoinverse \(A^\dagger\) as \[ A^\dagger = R^\dagger C^\dagger \]
Back
For \(A \in \mathbb{R}^{m \times n}\) with \(\text{rank}(A) = r\) and CR decomposition \(A = CR\), we define the pseudoinverse \(A^\dagger\) as \[ A^\dagger = R^\dagger C^\dagger \]
We can rewrite this as \(A^\dagger = R^\top {(RR^\top)}^{-1} {(C^\top C)}^{-1} C^\top =\) \(R^\top {(C^\top C R R^\top)}^{-1} C^\top =\) \(R^\top {(C^\top A R^\top)}^{-1}C^\top\).
After
Front
For \(A \in \mathbb{R}^{m \times n}\) with \(\text{rank}(A) = r\) and CR decomposition \(A = CR\), we define the pseudoinverse \(A^\dagger\) as: \[ A^\dagger = R^\dagger C^\dagger \]
Back
For \(A \in \mathbb{R}^{m \times n}\) with \(\text{rank}(A) = r\) and CR decomposition \(A = CR\), we define the pseudoinverse \(A^\dagger\) as: \[ A^\dagger = R^\dagger C^\dagger \]
We can rewrite this as:
\(\begin{aligned} A^\dagger &= R^\top (RR^\top)^{-1} (C^\top C)^{-1} C^\top \\ &= R^\top (C^\top C R R^\top)^{-1} C^\top \\ &= R^\top (C^\top A R^\top)^{-1} C^\top \end{aligned}\)
\(\begin{aligned} A^\dagger &= R^\top (RR^\top)^{-1} (C^\top C)^{-1} C^\top \\ &= R^\top (C^\top C R R^\top)^{-1} C^\top \\ &= R^\top (C^\top A R^\top)^{-1} C^\top \end{aligned}\)
Field-by-field Comparison
| Field | Before | After |
|---|---|---|
| Text | For \(A \in \mathbb{R}^{m \times n}\) with \(\text{rank}(A) = r\) and CR decomposition \(A = CR\), we define the pseudoinverse \(A^\dagger\) as |
For \(A \in \mathbb{R}^{m \times n}\) with \(\text{rank}(A) = r\) and CR decomposition \(A = CR\), we define the pseudoinverse \(A^\dagger\) as: \[ A^\dagger = {{c1::R^\dagger C^\dagger }}\] |
| Extra | We can rewrite this as |
We can rewrite this as:<br><br>\(\begin{aligned} A^\dagger &= R^\top (RR^\top)^{-1} (C^\top C)^{-1} C^\top \\ &= R^\top (C^\top C R R^\top)^{-1} C^\top \\ &= R^\top (C^\top A R^\top)^{-1} C^\top \end{aligned}\) |