Showing posts with label linear algebra. Show all posts
Showing posts with label linear algebra. Show all posts

Monday, 17 November 2025

Modeling simple quantum systems

Figure 1: A two-state system (qubit)
In this post I'll model some simple systems using the equations of quantum mechanics, culminating in the qubit (illustrated in Figure 1) - the building-block of quantum computing.[1]

The time evolution of a quantum system, where the unitary operator \(U\) transforms the state of the system at time \(0\) to time \(t\), is defined as:

\[\psi(t) = U(t)\psi(0) \tag{1} \]

Operator \(U\), where the Hamiltonian \(H\) encodes the system's energy levels (spectrum), is defined as:[2]

\[U(t) = e^{−iHt} \tag{2} \]

Time evolution intuition: Time evolution is phase accumulation: in the energy basis, each component of \(\psi\) picks up a phase \(e^{-iE_k t}\). For each component, visualize a clock hand (or arrow) that spins at a rate set by its energy.

Differentiating and using \(\frac{d}{dt}U(t) = -iHU(t)\) gives the Schrödinger equation:[3]

\[i \frac{d}{dt}\psi(t) = H \psi(t) \tag{3} \]

Schrödinger equation intuition: Visualize each energy component of \(\psi(t)\) as a clock hand rotating on the complex plane. Its time derivative is the tangent to that rotating clock hand (i.e., the clock hand rotated 90° clockwise and scaled by its energy). Multiplying by \(i\) rotates that tangent back to the radial direction. In the energy basis, applying \(H\) to \(\psi(t)\) simply scales each energy component by its corresponding energy level. Thus \(i \frac{d}{dt}\psi(t)\) (tangent rotated back) and \(H \psi(t)\) (component-wise scaling) are the same vector, giving the Schrödinger equation.

A trivial one-state system (no phase change)


Consider a particle with a frequency of 0Hz. Set \(H=0\) and \(\psi(0)=1\). Then

\[\psi(t)=e^{-i\cdot 0\cdot t}\cdot 1 = 1 \]

for all \(t\) (as illustrated in Figure 2). For a one-state system, there is only one possible measurement outcome, namely, that single state.

Figure 2: \(\psi(t) = 1\) (0Hz)
horizontal-axis: time | lateral axes: complex amplitude

0Hz system intuition: We are, in effect, modeling a clock whose hand does not rotate (0Hz). Hence the graph shows the amplitude fixed in its initial phase over time. Note, however, that we cannot subsequently measure the angle (phase) of the clock hand, or even its frequency (more on this below).

A one-state system with a 1Hz phase (global phase change only)


Now consider a particle with a frequency of 1Hz. Set \(H = \theta\) and \(\psi(0)=1\). Then

\[\psi(t)=e^{-i\cdot \theta \cdot t} \cdot 1 = e^{-i\cdot \theta \cdot t} \]

where \(\theta\) is a scalar.

Figure 3: \(\psi(t) = e^{-i\cdot\tau\cdot t}\) (1Hz)

The amplitudes at selected times per Figure 3 for \(\theta = \tau\) (where \(\theta\) is the energy eigenvalue and \(\tau \equiv 2\pi\), representing the radians in one cycle):

\[t=0,1: 1, \quad t=0.25: -i,\]
\[t=0.5: -1, \quad t=0.75: i.\]


As noted before: for a one-state system, there is only one possible measurement outcome, namely, that single state. Since the global phase (including both the degree of rotation around the complex plane and its rate of change) is unobservable in quantum systems, this system is indistinguishable from the earlier 0Hz system. The different oscillations become relevant for multi-state systems which we will consider next.

1Hz system intuition: Now we're modeling a clock whose hand rotates once per second (1Hz). Hence the graph shows the amplitude rotating in a unit circle from 1 through -i, -1 and i back to 1. This is visualized as a corkscrew along the time axis. As noted earlier, we cannot measure the angle of the clock hand or its frequency. Only relative phase (between two or more clocks) can be measured. Each clock is, in effect, enclosed in its own black box with no way to experimentally distinguish them.

A superposed two-state system (qubit)


Now consider a two-dimensional Hilbert space comprising a ground state (with \(0\) energy) and an excited state (with \(\tau\) energy) in equal superposition.[4][5] For example, a spin-½ particle with up (0Hz ground) and down (1Hz excited) states.

Hilbert space intuition: Consider the familiar 2D Euclidean plane that represent lengths in an x and y direction, and also angles and magnitude. A 2D Hilbert space allows the x and y coordinates to be complex numbers. This retains the familiar geometry but adds structure for phases and interference. A vector in a 2D Hilbert space (i.e., a qubit) can be visualized as a point on the surface of a Bloch sphere where the latitude represents proximity to the poles (0 and 1) and the longitude represents the relative phase between them.

Energy basis \(\{|E_0\rangle,|E_1\rangle\}\) with

\[H_{energy} = \begin{bmatrix}0 & 0\\0 & \tau\end{bmatrix}, \quad \psi_{energy}(0) = \dfrac{1}{\sqrt2} \begin{bmatrix}1\\1\end{bmatrix} \]

Time evolution:

\[\begin{align}\psi_{energy}(t) &= U_{energy}(t)\psi_{energy}(0) \\ &= e^{−iH_{energy}t} \frac{1}{\sqrt2} \begin{bmatrix}1\\1\end{bmatrix} \\ &= \begin{bmatrix} 1 & 0 \\ 0 & e^{−i \tau t}\end{bmatrix} \frac{1}{\sqrt2} \begin{bmatrix}1\\1\end{bmatrix} \\ &= \frac{1}{\sqrt2} \begin{bmatrix}1 \\ e^{−i \tau t}\end{bmatrix} \end{align} \]

Figure 4: \(|\psi_{energy}(t)⟩ = \frac{1}{\sqrt2}(|E_0⟩ + e^{-i \tau t}|E_1⟩)\) (0Hz+1Hz)

The (superposed) amplitudes at selected times per Figure 4:

\[t=0,1: \dfrac{1}{\sqrt2}\begin{bmatrix}1\\1\end{bmatrix}, \quad t=0.25: \dfrac{1}{\sqrt2}\begin{bmatrix}1\\-i\end{bmatrix},\]
\[t=0.5: \dfrac{1}{\sqrt2}\begin{bmatrix}1\\-1\end{bmatrix}, \quad t=0.75: \dfrac{1}{\sqrt2}\begin{bmatrix}1\\i\end{bmatrix}.\]

These amplitudes are the linear combination of the amplitudes for the one-state systems in Figures 2 and 3 (normalized such that the square of the magnitudes equals 1). 

Vector intuition: The vectors have two elements, associated with the two component states. Reading 

Since the magnitude of the individual amplitudes for each state are \(\tfrac{1}{\sqrt2}\) at all points, the probability of measuring a particular state is \(\tfrac{1}{2}\) (per the Born rule, \((\tfrac{1}{\sqrt2})^2\)).

Born rule intuition: The two states can be represented as the adjacent and opposite sides of a right-angled triangle, with the hypotenuse of unit length \(1\). Per the Pythagorean Theorem, if the magnitudes of the two states are \(0.6\) and \(0.8\), then the probability of measuring those states per the Born rule is \(0.6^2  = 0.36\) and \(0.8^2 = 0.64\) respectively (with \(0.36 + 0.64  = 1\)). In the main qubit example, the triangle side lengths are each \(\tfrac{1}{\sqrt2}\) whose squares are each \(\tfrac{1}{2}\) (summing to 1). A measurement is a projection onto one of the sides per the Born probabilities. Thus, in the main qubit example, there is an equal probability of measuring either state (i.e., 0Hz or 1Hz, ground or excited, 0 or 1).

Time (Hadamard/DFT-2) basis. Define \(|T_0\rangle, |T_1\rangle\) via the Hadamard:

\[\begin{align}\psi_{time}(t) &= \mathcal{F}^{-1} \psi_{energy}(t) \\ &= \frac{1}{\sqrt2} \begin{bmatrix}1 & 1\\1 & -1\end{bmatrix} \frac{1}{\sqrt2}\begin{bmatrix} 1 \\ e^{−i \tau t} \end{bmatrix} \\ &= \frac{1}{2}\begin{bmatrix}1 + e^{−i \tau t} \\ 1 - e^{−i \tau t}\end{bmatrix} \end{align} \]


Figure 5: \(|\psi_{time}(t)⟩ = \frac{1}{2}(1 + e^{-i \tau t})|T_0⟩ + \frac{1}{2}(1 - e^{-i \tau t})|T_1⟩ \)

The (superposed) amplitudes at selected times per Figure 5:[6]

\[t=0,1: \begin{bmatrix}1\\0\end{bmatrix}, \quad t=0.25: \dfrac{1}{2} \begin{bmatrix}1 - i\\1 + i\end{bmatrix},\]
\[t=0.5: \begin{bmatrix}0\\1\end{bmatrix}, \quad t=0.75: \dfrac{1}{2} \begin{bmatrix}1 + i\\1 - i\end{bmatrix}.\]

A measurement in the time basis (with eigenstates \(|T_0\rangle, |T_1\rangle\)) at physical time \(t=0\) would return the eigenstate \(|T_0\rangle\) (i.e., the spin-½ particle ground state in the time basis) with certainty and at physical time \(t=0.25\) would return either eigenstate with equal probability.

Qubit intuition: The two independent clocks discussed earlier can be superposed in a single two-state system (a qubit). A measurement projects onto just one of the clocks (0Hz or 1Hz, ground or excited, 0 or 1). In the standard (energy) basis, the two clocks are modeled per Figure 4, with the measurement of either 0Hz or 1Hz being equally likely at any point in time. In the Fourier (time) basis, the relative phase between the two clocks are modeled per Figure 5, with the probability of measuring either T0 or T1 (which is + or -, in-phase or out-of-phase, 0 or 1) being dependent on the time of measurement.

Relative phase intuition: In Figure 4, the straight bright purple line models the 0Hz stopped clock hand whereas the curved dim purple line models the 1Hz moving clock hand. In Figure 5, the bright green line models how correlated the two clock hands are (how in-phase they are, i.e., the phase difference) while the dim green line models how anti-correlated the two clock hands are (how out-of-phase they are). So at t=0, the two hands point in the same direction, while at t=0.5, the two hands point in the opposite direction. Note that the purple lines don't exhibit interference since just the stopped clock or the moving clock state is measured (but, to reiterate, not its phase). This is analogous to measuring a particle at just one of the slits in the double-slit experiment. However the green lines are each interference patterns since they represent the phase between both clock hands. Remove one of the clocks and the interference pattern disappears.

Wrapping up


We started with the basic rule for how quantum systems change over time and built up from the simplest case: a system that never changes to one that oscillates and then to a two-state system (a qubit). An energy level is analogous to a tiny clock hand spinning at its own speed. With just one clock, nothing interesting happens, but with two clocks spinning at different rates, their positions combine to create interference patterns. These two-clock systems, or qubits, are the building blocks of quantum computing.


Related posts







Footnotes


[1] Units, \(\tau\), and representations


Using Planck units with \(\hbar=1\) and representing the radians in one cycle with \(\tau\equiv 2\pi\), then

\[h=\tau,\qquad E=hf=\tau f = \omega,\]

referencing Planck's constant (\(h\)), energy (\(E\)), frequency (\(f\)) and angular frequency (\(\omega\)).

A quantum state is a complex wavefunction written here either in the energy basis or in a convenient “time (Fourier)” basis. In a one-state system these coincide (so any Heisenberg trade-off is vacuous). In finite-dimensional quantum systems, a “time basis” is not the eigenbasis of a fundamental time operator. It is a complementary basis obtained by a unitary transformation (Hadamard/DFT in 2D). Such systems satisfy SU(2) (spin-½) commutation relations, e.g.  \([Sx​,Sy​]=iSz\), but not canonical commutation, such as \([E,T]=iI\). Here, \(Sx\) corresponds to energy, \(Sy\) to time and \(Sz\) to the relative phase between energy and time.


[2] Exponentiating the Hamiltonian


The Hamiltonian \(H\) is a diagonal matrix that encodes the system's energy levels \(E_k\) along the diagonal. For a one-state system, it reduces to a scalar.

One-state system. With \(E_f=\tau f\) (the energy at a specific frequency),

\[H=E_f,\qquad U(t)=e^{-iHt}=e^{-iE_f t}.\]

Two-state system. With energy basis \(\{|E_0\rangle,|E_1\rangle\}\)),

\[H=\begin{bmatrix}E_0&0\\[2pt]0&E_1\end{bmatrix},\qquad U(t)=e^{-iHt}=\begin{bmatrix}e^{-iE_0 t}&0\\[2pt]0&e^{-iE_1 t}\end{bmatrix}.\]

Eigen/evolution relations (operator form):

\[H|E_n\rangle=E_n|E_n\rangle,\qquad U(t)|E_n\rangle=e^{-iE_n t}|E_n\rangle\quad(n=0,1).\]

[3] Deriving the Schrödinger equation


Starting from \(\psi(t)=U(t)\psi(0)\) with \(U(t)=e^{-iHt}\) and time-independent \(H\),

\[\begin{align}i \frac{d}{dt}\psi(t) &= i \frac{d}{dt}e^{−iHt}\psi(0) \\ &= i \cdot -iH e^{−iHt}\psi(0) \\ &= H \psi(t). \end{align} \]

[4] Transforming between the time and energy representations


The time and energy representations of a quantum system are related via a unitary Fourier transform:

\[\psi_{energy} = \mathcal{F} \psi_{time} , \quad \psi_{time} = \mathcal{F}^{-1} \psi_{energy} .\]

One-state system: the Identity matrix,

\[\mathcal{F}_1 = \mathcal{F}_1^{-1} = \begin{bmatrix}1\end{bmatrix} . \]

Two-state system: the Hadamard/DFT-2,

\[\mathcal{F}_2 = \mathcal{F}_2^{-1} = \frac{1}{\sqrt2} \begin{bmatrix}1 & 1\\1 & -1\end{bmatrix} . \]

[5] Energy and time bases


In the two-state system with \(\hbar=1\) and \(\tau\equiv 2\pi\) we set

\[ H_{\text{energy}}=\begin{bmatrix}0&0\\[2pt]0&\tau\end{bmatrix}.\]

So \(|E_0\rangle, |E_1\rangle\) satisfy

\[H_{\text{energy}}|E_0\rangle=0\,|E_0\rangle,\qquad H_{\text{energy}}|E_1\rangle=\tau\,|E_1\rangle,\]

and, in the energy basis coordinates,

\[|E_0\rangle = \begin{bmatrix}1\\0\end{bmatrix},\qquad |E_1\rangle = \begin{bmatrix}0\\1\end{bmatrix}.\]

We also define the time (Hadamard/DFT-2) basis by
\[|T_0\rangle=\frac{1}{\sqrt2}(|E_0\rangle+|E_1\rangle)=\frac{1}{\sqrt2}\begin{bmatrix}1\\[2pt]1\end{bmatrix},\qquad |T_1\rangle=\frac{1}{\sqrt2}(|E_0\rangle-|E_1\rangle)=\frac{1}{\sqrt2}\begin{bmatrix}1\\[2pt]-1\end{bmatrix}.\]

[6] Transform-then-evolve (and other alternatives)


A second method for calculating \( \psi_{time}(t) \) is to transform \(H_{energy} \) and \(\psi_{energy}(0)\) to the time basis first and then evolve the state.

\[\begin{align}H_{time} &= \mathcal{F}^{-1} H_{energy} \mathcal{F} \\ &= \frac{1}{\sqrt2} \begin{bmatrix}1 & 1\\1 & -1\end{bmatrix} \begin{bmatrix}0 & 0\\0 & \tau\end{bmatrix} \frac{1}{\sqrt2} \begin{bmatrix}1 & 1\\1 & -1\end{bmatrix} \\ &= \begin{bmatrix}\pi & -\pi\\-\pi & \pi\end{bmatrix} \end{align} \]

\[\begin{align}\psi_{time}(0) &= \mathcal{F}^{-1} \psi_{energy}(0) \\ &= \frac{1}{\sqrt2} \begin{bmatrix}1 & 1\\1 & -1\end{bmatrix} \frac{1}{\sqrt2} \begin{bmatrix}1\\1\end{bmatrix} \\ &= \begin{bmatrix}1\\0\end{bmatrix} \end{align} \]

\[\begin{align}\psi_{time}(t) &= U_{time}(t)\psi_{time}(0) \\ &= e^{−iH_{time}t} \begin{bmatrix}1\\0\end{bmatrix} \\ &= \frac{1}{2} \begin{bmatrix}1 + e^{−i \tau t} & 1 - e^{−i \tau t} \\ 1 - e^{−i \tau t} & 1 + e^{−i \tau t}\end{bmatrix} \begin{bmatrix}1\\0\end{bmatrix} \\ &= \frac{1}{2} \begin{bmatrix}1 + e^{−i \tau t} \\ 1 - e^{−i \tau t}\end{bmatrix} \end{align} \]

A third method for calculating \( \psi_{time}(t) \) is via the Schrödinger equation.

\[i \frac{d}{dt}\psi(t) = H \psi(t), \quad H_{energy} = \begin{bmatrix}0 & 0\\0 & \tau\end{bmatrix}, \quad \psi_{energy}(0) = \dfrac{1}{\sqrt2} \begin{bmatrix}1\\1\end{bmatrix}.\]

Because the Hamiltonian is diagonal, the Schrödinger equation decouples into independent equations for each component. For the first component:

\[ i \frac{d}{dt}\psi_0(t) = 0 \cdot \psi_0(t) = 0 \]

\[ \frac{d}{dt}\psi_0(t) = 0 \implies \psi_0(t) = \psi_0(0) = \frac{1}{\sqrt2} \]

For the second component:

\[ i \frac{d}{dt}\psi_1(t) = \tau \cdot \psi_1(t) \]

\[\psi_1(t) = \psi_1(0) e^{−i \tau t} = \frac{1}{\sqrt2} e^{−i \tau t}\]

Therefore, the solution in the energy basis is:

\[\psi_{energy}(t) = \frac{1}{\sqrt2} \begin{bmatrix}\psi_0(t) \\ \psi_1(t) \end{bmatrix} = \frac{1}{\sqrt2} \begin{bmatrix}1 \\ e^{−i \tau t}\end{bmatrix}\]

Finally, transform \(\psi_{energy}(t)\) to the time basis:

\[\begin{align}\psi_{time}(t) &= \mathcal{F}^{-1} \psi_{energy}(t) \\ &= \frac{1}{\sqrt2} \begin{bmatrix}1 & 1\\1 & -1\end{bmatrix} \frac{1}{\sqrt2}\begin{bmatrix} 1 \\ e^{−i \tau t} \end{bmatrix} \\ &= \frac{1}{2}\begin{bmatrix}1 + e^{−i \tau t} \\ 1 - e^{−i \tau t}\end{bmatrix} \end{align} \]

Friday, 17 May 2019

Visualizing linear algebra: Introduction

The purpose of this series is to explain the core concepts of linear algebra in a concrete and visual way and is based on the Essence of Linear Algebra series by 3Blue1Brown.

Part 1: Vectors
Part 2: Matrices
Part 3: Determinant
Part 4: Matrix inverse
Part 5: Dot product
Part 6: Cross product
Part 7: Change of basis
Part 8: Eigenvectors
Part 9: Vector spaces

Visualizing linear algebra: Vector spaces

Figure 1: Functions, like vectors, can be added
This is Part 9 in a series on linear algebra [1].

A vector can be represented numerically as a list of numbers or geometrically as an arrow. But is one representation more fundamental than the other or are they both manifestations of something deeper?

A list of numbers seems clear cut and unambiguous when dealing with different dimensions, whether a 2D vector or a 100D vector. Whereas a 4D or higher space can be difficult to describe geometrically. On the other hand, the vector space exists independently of the coordinates that you give it and those coordinates can seem somewhat arbitrary since they depend on your choice of basis vectors. For example, determinants and eigenvectors are inherently spatial (the determinant tells you how much a transformation scales areas and eigenvectors stay on their own span during a transformation) and you can freely change your coordinate system without changing the underlying values of either one.

So if vectors are not fundamentally lists of numbers and their underlying essence is more spatial, then that raises the question of what mathematicians mean when they use a word like space or spatial.

Figure 2: The sum of two functions
It turns out that there is something which is neither an arrow nor a list of numbers but is also a type of vector: functions. In the same way that you can add two vectors together, there is also a sensible notion for adding two functions f and g to get a new function (f + g). That is, the value of the sum function at any given input x is the sum of the values of f(x) + g(x). See Figure 1 which shows two functions and Figure 2 which shows their sum. This is represented as:

(f + g)(x) = f(x) + g(x)

Figure 3: Functions, like vectors, can be scaled
This is similar to adding vectors coordinate by coordinate except that there is, in a sense, infinitely many coordinates to deal with. Similarly, there is a sensible notion for scaling a function by a real number. Just scale all of the outputs by that number For example, as illustrated in Figure 3:

(2f)(x) = 2f(x)

Again, this is analogous to scaling a vector coordinate by coordinate but with infinitely many coordinates.

Now, given that the only thing vectors can really do is get added together or scaled, it seems like we should be able to take the same useful constructs and problem solving techniques of linear algebra (linear transformations, null space, dot products, eigen-everything) that were originally thought about in the context of arrows in space and apply them to functions as well. Such as, for example, the derivative that transforms one function into another function:

ddx(3x3 - x) = 9x2 - 1

These are sometimes called operators instead of transformations, but the meaning is the same.

Figure 4: Additivity
A transformation is linear if it satisfies two properties, commonly called additivity (see Figure 4) and scaling (see Figure 5).

Additivity means that if you add two vectors, v and w, then apply a transformation to their sum, you get the same result as if you added the transformed versions of v and w. That is:

L(v + w) = L(v) + L(w)

Figure 5: Scaling
The scaling property is that when you scale a vector v by some number, then apply the transformation, you get the same ultimate vector as if you scale the transformed version of v by that same amount. That is:

L(c.v) = c.L(v)

So linear transformations preserve the operations of vector addition and scalar multiplication. These properties also apply to functions such as the derivative. For example:

ddx(x3 + x2) = ddx(x3) + ddx(x2)

ddx(4x3) = 4 ddx(x3)

Consider the vector space for polynomials. Coordinates are needed for this space which requires choosing a basis. Since polynomials are already written down as the sum of scaled powers of the variable x, it's natural to just choose pure powers of x as the basis function. The first basis function will be the constant function b0(x)=1, the second basis function will be b1(x)=x, then b2(x)=x2, then b3(x)=x3, and so on. The role that these basis functions serve will be similar to the roles of i-hat, j-hat and k-hat in the world of vectors as arrows. For example, the vector [5;3;1;0;0...] (with an infinite tail of zeroes) would be expressed in terms of the basis functions as:

5*1 + 3x + 1x2

Most of the concepts that apply to arrows in space such as linear transformations, the dot product and eigenvectors have direct analogues in the world of functions but with different names such as linear operators, the inner product and eigenfunctions.

Figure 6: Vector spaces
There are lots of vector-like things in math. As long as you're dealing with a set of objects where there's a reasonable notion of scaling and adding, whether that's a set of arrows in space, lists of numbers, functions or whatever else you choose to define, all of the tools developed in linear algebra regarding vectors, linear transformations and so on should be able to apply.

A mathematician need not think about all the different kinds of vector spaces that people might come up with. Instead there are eight axioms that any vector space must satisfy if all the theory and constructs that have been discovered are going to apply. These axioms are not so much fundamental rules of nature as they are an interface between the mathematician who is discovering results and other people who might want to apply those results to new sorts of vector spaces. The axioms serve as a checklist for verifying one's definitions before applying the results of linear algebra. Whereas mathematicians express their results abstractly and only in terms of these axioms. Thus the mathematician's answer to "What are vectors?" is to just ignore the question since the form that vectors take doesn't really matter as long as those rules are followed. Similarly, textbooks and lectures tend to be phrased abstractly to describe the most general case.

And this wraps up the series on visualizing linear algebra!

--

[1] The figures and examples of the posts in this series are based on the Essence of Linear Algebra series by 3Blue1Brown.

Visualizing linear algebra: Eigenvectors

Figure 1: Before transformation
This is Part 8 in a series on linear algebra [1].

A vector that remains on its span [2] when a linear transformation is applied to it is termed an eigenvector of that transformation. The amount that it is scaled is called an eigenvalue.

For example, Figure 1 shows a yellow arrow that will be transformed by the indicated matrix. The purple line is the span of the yellow arrow.

Figure 2: After transformation
Figure 2 shows the yellow arrow after the transformation. Note that the yellow arrow has remained on its span, so it is an eigenvector of the transformation. It has been scaled by a factor of 2, so 2 is the eigenvalue. The eigenvalue is shown as the coefficient of the original vector.

Notice that i-hat is also an eigenvector and its eigenvalue is 3 (i.e., it is scaled by 3). However j-hat has not remained on its span, so it is not an eigenvector of the transformation.

Any vector that lies on the span of either the yellow arrow or the green arrow is an eigenvector and it will also have the eigenvalues 2 and 3 respectively. Any vector, such as the red arrow, that does not lie on either of those spans will be rotated off the line that it spans.

Figure 3: 3D rotation around an axis
Eigenvalues can be negative which means that after the transformation the arrow will point in the opposite direction along its span.

For one example of where finding an eigenvector is useful, consider a 3D dimensional rotation as in Figure 3. If you can find an eigenvector for that transformation, a vector that remains on its own span, then you have found the axis of rotation. For rotations the eigenvalue is always 1 since the length of the vector remains the same.

Note that the columns of a matrix describe the landing spots for the basis vectors. However, as illustrated by the 3D rotation, finding the eigenvectors and eigenvalues describes what the transformation does independent of the particular basis vectors used.

An eigenvector equation can be represented as:

Av = λv

where A is the matrix representing a transformation, v is the eigenvector and λ (lambda) is the corresponding eigenvalue (a number). This expression says that the matrix-vector product (A times v) gives the same result as just scaling the eigenvector v by some value λ. So finding the eigenvectors and their eigenvalues of a matrix A comes down to finding the values of v and λ that make this expression true.

The first step is to convert the right-hand-side of the equation so that it represents a matrix-vector product like the left-hand-side of the equation. This is done by multiplying λ by the identity matrix I, as follows:

Av = (λI)v

Now subtracting the right-hand-side and factoring out v:

Av - λIv = 0
(A - λI)v = 0

We're now looking for a non-zero vector v such that this new matrix times v gives the zero vector. The only way it is possible for the product of a matrix with a non-zero vector to become zero is if the transformation associated with that matrix reduces space to a lower dimension, say, from a plane to a line. In that case, the matrix has a determinant of zero. That is:

det(A - λI) = 0

For example, consider the matrix from Figures 1 and 2:

[3 1]
[0 2]

Now think about subtracting a variable amount λ from each diagonal entry:

[3 1] - λ[1 0] = [3-λ   1]
[0 2]    [0 1]   [  0 2-λ]

The goal is to find any values of λ that will make the determinant of the matrix zero. That is:

det([3-λ   1]) = ad - bc = (3-λ)(2-λ) - 1*0(3-λ)(2-λ) = 0
    [  0 2-λ]

Solving this equation, the only possible eigenvalues are λ = 2 and λ = 3.

So when λ equals 2 or 3, the matrix (A - λI) transforms space onto a line. That means there are non-zero vectors v such that (A - λI) times v equals the zero vector. Recall the reason we care about that is because it means Av = λv. That is, the vector v is an eigenvector of A.

To figure out the eigenvectors that have one of these eigenvalues, plug that value of λ into the matrix and then solve for which vectors this diagonally-altered matrix sends to zero. Solving with λ = 2:

[3-2   1][x] = [1 1][x] = x[1] + y[1] = [x+y] = [0]
 0 2-2][y]   [0 0][y]    [0]    [0]   [  0]   [0]

Since the determinant is zero, there is no unique solution. The solutions are all the vectors on the line described by y = -x which is the diagonal line spanned by [-1;1] or the yellow arrow in Figure 1. Similarly, solving with λ = 3:

[3-3   1][x] = [0  1][x] = x[0] + y[ 1] = [ y] = [0]
 0 2-3][y]   [0 -1][y]    [0]    [-1]   [-y]   [0]

In this case, the solutions are all the vectors on the line described by y = 0 which is the horizontal line spanned by [1;0] or i-hat in Figure 1.

Figure 4: 90° rotation
Not all transformations have eigenvectors. One example is a 2D 90° counterclockwise rotation which rotates all vectors off their spans as shown in Figure 4. Consider computing the eigenvalues of this rotation. Subtract λ from the diagonal elements and look for when the determinant is zero.

det([-λ -1]) = (-λ)(-λ) - -1*10
    [ 1 -λ]
             = λ2 + 1 = 0

∴ λ = i or λ = -i

The only roots of that polynomial are the imaginary numbers i and -i. Assuming we are only looking for real number solutions, there are no eigenvectors for that transformation. However note that eigenvalues that are complex numbers generally correspond to some kind of rotation in the transformation.

Whenever a matrix has zeroes everywhere other than the diagonal, it is called a diagonal matrix. The way to interpret this is that all the basis vectors are eigenvectors with the diagonal entries of the matrix being their eigenvalues. That is, a diagonal matrix simply scales the basis vectors. A diagonal matrix can be represented as a vector times the identity matrix I. For example:

Figure 5: Change of basis
[-1 0] = [1 0][-1]
0 2]   [0 1][ 2]

Therefore, whenever we want to apply a matrix multiplication to a diagonal matrix, it is the same as applying a matrix-vector multiplication, converting an O(N2) operation into O(N).

If a transformation has enough eigenvectors such that you can choose a set that spans the full space, then you can change your coordinate system so that these eigenvectors are your basis vectors. For example, using the eigenvectors for the matrix from Figure 1 as the change of basis matrix (the green and yellow arrows):

[1 -1]-1[3 1][1 -1] = [3 0]
[ 1]  [0 2][ 1]   [0 2]

This new matrix is guaranteed to be diagonal with its corresponding eigenvalues down that diagonal. The new basis is called an eigenbasis with Figure 5 showing the change of basis. Applying the transformation will scale the new basis vectors by those eigenvalues, that is, the green arrow by 3 and the yellow arrow by 2.

Next up: vector spaces

--

[1] The figures and examples of the posts in this series are based on the Essence of Linear Algebra series by 3Blue1Brown.

[2] A vector that remains on its span either points in the same direction or points in the opposite direction (the negative direction).

Wednesday, 15 May 2019

Visualizing linear algebra: Change of basis

Figure 1: Alternative basis vectors
This is Part 7 in a series on linear algebra [1].

Any given vector can be understood as the scaling of the unit vectors i-hat and j-hat. These special vectors are the standard basis vectors in a coordinate system.

However it is also possible to use different basis vectors. In Figure 1, the basis vectors b1 and b2 point in different directions and have different lengths to i-hat and j-hat.

Figure 2: Alice and Bobs' coordinate systems
Suppose that Alice uses the standard basis vectors i-hat and j-hat while Bob uses the alternative basis vectors b1 and b2. While Alice and Bob are looking at the same vectors in space, they can be considered to be using different languages to refer to them.

In Figure 2, Alice would describe b1 with the vector coordinates [2;1] and b2 with the vector coordinates [-1;1].[2] Whereas from Bob's perspective, b1 and b2 have coordinates [1;0] and [0;1]. They are what define the meaning of the coordinates [1;0] and [0;1] in his system. To reiterate, both Alice and Bob are looking at the same vectors in space, but they use different words and numbers to describe them.

Figure 3: Vector [-1;2] in Bob's system
To translate between Alice and Bobs' coordinate systems, consider Figure 3. Suppose Bob describes a vector with coordinates [-1;2] in his system. That is, b1 is scaled by -1 and b2 is scaled by 2 as represented by the yellow arrow. From Alice's perspective, the coordinates for b1 and b2 in her system can be similarly scaled to describe the vector in her system. That is:

-1[2] + 2[-1] = [-4]
  [1]    [ 1]   [ 1]

Note that this is just matrix-vector multiplication with a matrix whose column vectors represent Bob's basis vectors in Alice's language. That is:

[2 -1][-1] = -1[2] + 2[-1] = [-4]
[1  1][ 2]     [1]    [ 1]   [ 1]

In effect, a matrix whose column vectors represent Bob's basis vectors can be thought of as a transformation that moves Alice's basis vectors, i-hat and j-hat, to Bob's basis vectors, b1 and b2. So the vector [-1;2] is a certain linear combination of Alice's basis vectors (-1î +  ). The resulting vector after the transformation will be that same linear combination but of the new basis vectors (-1b1 + 2b2). This transformation, in essence, enables Alice to describe vectors in Bob's language.

It is similarly possible for Bob to describe vectors in Alice's language. This requires taking the inverse of the matrix which corresponds to playing the transformation backwards. The inverse of the matrix is:

[2 -1]-1 = [ 1/3 1/3]
[1  1]     [-1/3 2/3]

Let's go in the other direction, taking the vector that Alice describes in her language above as [-4;1] and describe it in Bob's language:

[ 1/3 1/3][-4] = -4[ 1/3] + 1[1/3] = [-1]
[-1/3 2/3][ 1]     [-1/3]    [2/3]   [ 2]

The result is [-1;2] in Bob's language which is verified by the yellow arrow in Figure 3.

That is how to translate the descriptions of individual vectors back and forth between coordinate systems. The matrix whose columns represent Bob's basis vectors but written in Alice's coordinates translates vectors from Bob's language into Alice's. And the inverse matrix does the opposite.

Linear transformations involving matrices can also be described in different coordinate systems. For example, a 90° counterclockwise rotation can be described in Alice's system as:

[0 -1]
[1  0]

That is, i-hat ends up at coordinates [0;1] and j-hat ends up at coordinates [-1;0]. To translate this into Bob's system, first consider a vector in Bob's language, say, the vector [-1;2] from above. That vector needs to be translated to Alice's language using the change of basis matrix, then the rotation applied in Alice's language, then translated back to Bob's language using the inverse change of basis matrix. This can be represented, from right-to-left, as:

[2 -1]-1[0 -1][2 -1][-1]
[1  1]  [1  0][1  1][ 2]

This transformation sequence will work for any vector in Bob's language. The product of the three matrices is:

[2 -1]-1[0 -1][2 -1] = [1/3 -2/3]
[1  1]  [1  0][1  1]   [5/3 -1/3]

If Bob applies this composition matrix to a vector in his system, it will return the rotated version of that vector expressed in his coordinate system. For example:

[1/3 -2/3][1] = [-1]
[5/3 -1/3][2]   [ 1]

With an expression like A-1MA , the middle matrix represents a transformation M as one person sees it, the outer matrices indicate the shift in perspective, while the full matrix product represents a transformation M as someone else sees it.

Next up: eigenvectors

--

[1] The figures and examples of the posts in this series are based on the Essence of Linear Algebra series by 3Blue1Brown.

[2] The notation [x;y] using a semicolon indicates a column vector.