5 ms·

This is nice, but I wish he showed it in mathematical syntax too. I don't understand some of the calculations because I don't know much about Clojure. Or Linear

by deft 9y ago

This is nice, but I wish he showed it in mathematical syntax too. I don't understand some of the calculations because I don't know much about Clojure. Or Linear Algebra.

dragandj 9y ago
The idea is that you follow this with a math Linear Algebra textbook. There is a recommended textbook, but any will do. I am not a mathematician, and there is not enough space in a blog post do develop everything step by step anyway. This should be a math->programming link, not a self-contained book.
flavio81 9y ago
For the syntax, just take a little time to review the Clojure syntax. I guarantee you that the syntax is as simple as it gets for a programming language!! You might happen to like it. Or you might happen to hate it, but, either way, I guarantee you that you will understand it quickly.
drostie 9y ago
So the transform is what we'd write as a matrix as: [-4 -6] [ 3 5] This matrix corresponds to the following linear transform: if you hand in the pair (x, y) it gives you the pair T(x, y) = (-4x - 6y, 3x + 5y). The word "linear" means that T(x1 + x2, y1 + y2) = T(x1, y1) + T(x2, y2) for all x1, x2, y1, y2 and that T(k x, k y) = k T(x, y) for all k. This has a nice interpretation in terms of the "vector space" underneath; a linear transform "distributes over vector addition" and "commutes with scalar multiplication." In fact vector spaces are super-general. The set of infinite sequences of real numbers `[a0, a1, a2, ...]` is a very nice vector space, and the Fibonacci recurrence F[n] = F[n - 1] + F[n - 2] is linear in such infinite sequences. It can be solved by F[n] = p^n for two bases p=b1, p=b2, and then you can see that any other sequence obeying that recurrence relation must have the form F[n] = A b1^n + B b2^n for some constants A, B. It's the same principles of linear algebra which get you there. (Exercise: solve the Fibonacci recurrence for b1, b2 and find A and B such that F[0] = 0, F[1] = 1, the normal Fibonacci numbers.) Anyway, back to the matrix. As you can see the trace of this matrix (sum of diagonal entries) is 1, and the determinant (for a 2x2 matrix, the product of the diagonal entries minus the product of the other two entries) is -20 + 18 = -2. It turns out that the trace is always the sum of the eigenvalues and the determinant is always the product of them, giving a nice way to understand this as the eigenvalues +2 and -1, the only two numbers that you can multiply together to get -2 and sum together to get +1. If we know that these are the eigenvalues then we would calculate the eigenvectors by looking for a non-trivial nullspace, T(x) = k x implying that T2(x) = T(x) - k x maps this nontrivial vector x to 0. Since the - k x is the diagonal matrix diag(-k, -k), we are looking at for k = +2 the matrix [-4 -6] + [-2 0] = [-6 -6] [ 3 5] [ 0 -2] [ 3 3] Now that looks like a very degenerate transform! T(x, y) = (-6 x - 6 y, 3 x + 3 y), what's going to map this to (0, 0)? Just x = -y will do perfectly nicely. So (1, -1) is one representative eigenvector for an entire eigendirection (t, -t) for all t. Plugging that into the original we also see T(1, -1) = (-4 + 6, 3 - 5) = (2, -2), proving that this is all 100% self-consistent. The other eigenvector comes from, [-4 -6] + [+1 0] = [-3 -6] [ 3 5] [ 0 +1] [ 3 6] This takes a little more thinking, the eigenvector is (2, -1) representing the eigendirection (2t, -t) for all t. Now what's the basic reason that you're doing all of this? Here's what: the eigenbasis. These vectors are not orthogonal, but they do span the space with a skewed coordinate system. Any vector (x, y) = a (2, -1) + b (1, -1) Call these new components {a, b} with curly braces. To solve for it explicitly, notice that {1, -1} = (1, 0) and {1, -2} = (0, 1). So x (1, 0) + y (0, 1) = x {1, -1} + y {1, -2} = {x + y, -x - 2y}, and we can find that a = x + y, b = -x -2y. Now if you pay the pain of using these skewed coordinates to begin with, then the matrix has a very nice representation in these coordinates: T{a, b} = {-a, 2b}. It just treats both of these coordinates independently, scaling them without mixing them. If you want to repeat it n times, it will just be T^n {a, b} = {(-1)^n a, 2^n b}. (Exercise: one of those roots b1, b2 for the Fibonaccis, let's say b2, has absolute magnitude less than 1, hence its exponentiations drift towards 0. Program an algorithm to calculate the Nth Fibonacci as `round(A*pow(b1, n))` and see how it does.) What complicates things a little is that usually your vector space is also an inner product space, and often that inner product has a nice structure (a, b) . (x, y) = a x + b y, in the orthogonal coordinates. It loses this structure in the skewed coordinates. Fortunately the physicists have a very nice notation for these cases coming from their work in relativity: it is to write vectors with both "upper indices" and "lower indices". The idea is that if we're using the basis (2, -1), (1, -1) then for each vector of the basis, we find a vector which has two properties: first, it's orthogonal to all of the other vectors of the basis; second, its dot product with the vector that it corresponds to is 1. These vectors form the "dual basis". So the vectors perpendicular to (1, -1) have the shape (t, t) for all t, we dot (2, -1) . (t, t) = 2t - t = t, so we choose t=1 and find that the dual vector to (2, -1) is (1, 1). Similarly the vectors perpendicular to (2, -1) have shape (t, 2t), dotting this with (1, -1) gives t - 2 t = -t, setting that to 1 says that t = -1, so the dual vector to (1, -1) is (-1, -2). [These mirror the expression {a, b} = {x + y, x - 2 y} above, and for good reason.] So the idea is that we represent every vector in two ways, with its "contravariant components" v^1, v^2 such that v^1 (2, -1) + v^2 (1, -1) is our vector, and its "covariant components" v_1, v_2 such that v_1 (1, 1) + v_2 (-1, -2) is also our vector. When we do this we discover that actually we get dot products back to a nice diagonal form even in a skewed coordinate system, that form is u_1 v^1 + u_2 v^2 + ... = u^1 v_1 + u^2 v_2 + ... . If you've got a nice crystal structure in physics, you might have, say, that the electrical conductivity really "wants" to be expressed in these skewed coordinates, where if you go down any of the natural directions of the crystal the material responds via Ohm's law. If it has slightly different resistances in slightly different crystal directions, say, then because the crystal is a skewed coordinate system, if you apply an electric field in an arbitrary physical direction you will in general create a current in a slightly different physical direction. But in the skewed coordinates it just looks like `J = {s1 E1, s2 E2, s3 E3}` corresponding to a diagonal conductivity tensor `diag(s1, s2, s3)` ... it's just that when you're not in the crystal structure you can't quite see that this material wants to flow in a couple of skewed directions preferentially.
- deft 9y ago
  Wow, thank you for this! I appreciate it and am going through it now :)

by deft 9y ago

This is nice, but I wish he showed it in mathematical syntax too. I don't understand some of the calculations because I don't know much about Clojure. Or Linear Algebra.

dragandj 9y ago

The idea is that you follow this with a math Linear Algebra textbook. There is a recommended textbook, but any will do. I am not a mathematician, and there is not enough space in a blog post do develop everything step by step anyway. This should be a math->programming link, not a self-contained book.

flavio81 9y ago

For the syntax, just take a little time to review the Clojure syntax. I guarantee you that the syntax is as simple as it gets for a programming language!! You might happen to like it. Or you might happen to hate it, but, either way, I guarantee you that you will understand it quickly.

drostie 9y ago

So the transform is what we'd write as a matrix as: [-4 -6] [ 3 5] This matrix corresponds to the following linear transform: if you hand in the pair (x, y) it gives you the pair T(x, y) = (-4x - 6y, 3x + 5y). The word "linear" means that T(x1 + x2, y1 + y2) = T(x1, y1) + T(x2, y2) for all x1, x2, y1, y2 and that T(k x, k y) = k T(x, y) for all k. This has a nice interpretation in terms of the "vector space" underneath; a linear transform "distributes over vector addition" and "commutes with scalar multiplication." In fact vector spaces are super-general. The set of infinite sequences of real numbers `[a0, a1, a2, ...]` is a very nice vector space, and the Fibonacci recurrence F[n] = F[n - 1] + F[n - 2] is linear in such infinite sequences. It can be solved by F[n] = p^n for two bases p=b1, p=b2, and then you can see that any other sequence obeying that recurrence relation must have the form F[n] = A b1^n + B b2^n for some constants A, B. It's the same principles of linear algebra which get you there. (Exercise: solve the Fibonacci recurrence for b1, b2 and find A and B such that F[0] = 0, F[1] = 1, the normal Fibonacci numbers.) Anyway, back to the matrix. As you can see the trace of this matrix (sum of diagonal entries) is 1, and the determinant (for a 2x2 matrix, the product of the diagonal entries minus the product of the other two entries) is -20 + 18 = -2. It turns out that the trace is always the sum of the eigenvalues and the determinant is always the product of them, giving a nice way to understand this as the eigenvalues +2 and -1, the only two numbers that you can multiply together to get -2 and sum together to get +1. If we know that these are the eigenvalues then we would calculate the eigenvectors by looking for a non-trivial nullspace, T(x) = k x implying that T2(x) = T(x) - k x maps this nontrivial vector x to 0. Since the - k x is the diagonal matrix diag(-k, -k), we are looking at for k = +2 the matrix [-4 -6] + [-2 0] = [-6 -6] [ 3 5] [ 0 -2] [ 3 3] Now that looks like a very degenerate transform! T(x, y) = (-6 x - 6 y, 3 x + 3 y), what's going to map this to (0, 0)? Just x = -y will do perfectly nicely. So (1, -1) is one representative eigenvector for an entire eigendirection (t, -t) for all t. Plugging that into the original we also see T(1, -1) = (-4 + 6, 3 - 5) = (2, -2), proving that this is all 100% self-consistent. The other eigenvector comes from, [-4 -6] + [+1 0] = [-3 -6] [ 3 5] [ 0 +1] [ 3 6] This takes a little more thinking, the eigenvector is (2, -1) representing the eigendirection (2t, -t) for all t. Now what's the basic reason that you're doing all of this? Here's what: the eigenbasis. These vectors are not orthogonal, but they do span the space with a skewed coordinate system. Any vector (x, y) = a (2, -1) + b (1, -1) Call these new components {a, b} with curly braces. To solve for it explicitly, notice that {1, -1} = (1, 0) and {1, -2} = (0, 1). So x (1, 0) + y (0, 1) = x {1, -1} + y {1, -2} = {x + y, -x - 2y}, and we can find that a = x + y, b = -x -2y. Now if you pay the pain of using these skewed coordinates to begin with, then the matrix has a very nice representation in these coordinates: T{a, b} = {-a, 2b}. It just treats both of these coordinates independently, scaling them without mixing them. If you want to repeat it n times, it will just be T^n {a, b} = {(-1)^n a, 2^n b}. (Exercise: one of those roots b1, b2 for the Fibonaccis, let's say b2, has absolute magnitude less than 1, hence its exponentiations drift towards 0. Program an algorithm to calculate the Nth Fibonacci as `round(A*pow(b1, n))` and see how it does.) What complicates things a little is that usually your vector space is also an inner product space, and often that inner product has a nice structure (a, b) . (x, y) = a x + b y, in the orthogonal coordinates. It loses this structure in the skewed coordinates. Fortunately the physicists have a very nice notation for these cases coming from their work in relativity: it is to write vectors with both "upper indices" and "lower indices". The idea is that if we're using the basis (2, -1), (1, -1) then for each vector of the basis, we find a vector which has two properties: first, it's orthogonal to all of the other vectors of the basis; second, its dot product with the vector that it corresponds to is 1. These vectors form the "dual basis". So the vectors perpendicular to (1, -1) have the shape (t, t) for all t, we dot (2, -1) . (t, t) = 2t - t = t, so we choose t=1 and find that the dual vector to (2, -1) is (1, 1). Similarly the vectors perpendicular to (2, -1) have shape (t, 2t), dotting this with (1, -1) gives t - 2 t = -t, setting that to 1 says that t = -1, so the dual vector to (1, -1) is (-1, -2). [These mirror the expression {a, b} = {x + y, x - 2 y} above, and for good reason.] So the idea is that we represent every vector in two ways, with its "contravariant components" v^1, v^2 such that v^1 (2, -1) + v^2 (1, -1) is our vector, and its "covariant components" v_1, v_2 such that v_1 (1, 1) + v_2 (-1, -2) is also our vector. When we do this we discover that actually we get dot products back to a nice diagonal form even in a skewed coordinate system, that form is u_1 v^1 + u_2 v^2 + ... = u^1 v_1 + u^2 v_2 + ... . If you've got a nice crystal structure in physics, you might have, say, that the electrical conductivity really "wants" to be expressed in these skewed coordinates, where if you go down any of the natural directions of the crystal the material responds via Ohm's law. If it has slightly different resistances in slightly different crystal directions, say, then because the crystal is a skewed coordinate system, if you apply an electric field in an arbitrary physical direction you will in general create a current in a slightly different physical direction. But in the skewed coordinates it just looks like `J = {s1 E1, s2 E2, s3 E3}` corresponding to a diagonal conductivity tensor `diag(s1, s2, s3)` ... it's just that when you're not in the crystal structure you can't quite see that this material wants to flow in a couple of skewed directions preferentially.

deft 9y ago
Wow, thank you for this! I appreciate it and am going through it now :)