jsEval "curl_module('Matrix.ob')"
Orthogonality
Humans have an innate sense of three dimensions of space, so the concepts of length and angle are obvious to us. But how do we generalize lengths and angles to higher dimensions?
One approach is the dot product. For up to three dimensions of space, we can visualize that:
\[ \newcommand{\u}{\mathbf{u}} \newcommand{\v}{\mathbf{v}} \newcommand{\w}{\mathbf{w}} \newcommand{\vv}[1]{\mathbf{#1}} \newcommand{\R}{\mathbb{R}} \v \cdot \w = |\v| |\w| \cos \theta \]
Since the dot product works in any finite-dimensional vector space, we can use it to discuss lengths and angles in higher dimensions, and replace geometric intuition with pure algebra.
We can generalize further, and do without coordinates completely. Define an inner product on a real vector space \(V\) to be a function \( ( \cdot ) : V \times V → \mathbb{R} \) satisfying:
-
Symmetry: \[ \v \cdot \w = \w \cdot \v \]
-
Linearity in first argument: \[ (a_1 \v_1 + a_2 \v_2) \cdot \w = a_1 (\v_1 \cdot \w) + a_2 (\v_2 \cdot \w) \]
-
Positive definiteness: \[ \v \ne 0 \implies \v \cdot \v \gt 0 \]
Experience has shown that these are the only properties that matter. A symmetric, bilinear, positive-definite function is enough to derive results that capture our understanding of three-dimensional space. This is miraculous, as inner products are so general that they allow us to talk about lengths and angles in some infinite-dimensional vector spaces.
The norm or length of a vector \(\v\) is:
\[ \lVert \v \rVert = \sqrt{\v \cdot \v} \]
Two vectors \(\v, \w\) are orthogonal if \(\v \cdot \w = 0\). An orthogonal set is a set of vectors such that any two are orthogonal. An orthonormal set is an orthogonal set where each vector has unit length.
Intuitively, in any space, any orthogonal set of nonzero vectors must be linearly independent, and if is not a basis, then we can add more vectors so it is an orthogonal basis of our space. However, since we have committed to an algebraic definition of orthogonality, we must prove these seemingly basic facts with algebra alone.
Let \( \{\v_1,…,.\v_n \} \) be an orthogonal set of nonzero vectors. The equations are nicer if we normalize, so let:
\[ \u_i = \frac{\v_i}{\lVert \v_i \rVert} \]
These vectors span the same space, but are now orthonormal. Let \( \v \) be some vector in their span of either set, so \(\v = \sum_{i=1}^n a_i \u_i, \) where each \(a_i\) is some scalar.
Then by linearity, and because the \(\u_i\)'s are orthonormal, we find for all \(k\):
\[ \u_k \cdot \v = \u_k \cdot \left( \sum_{i=0}^n a_i \u_i \right) = \sum_{i=0}^n a_i \u_k \cdot \u_i = a_k \]
Thus each \(a_k\) is uniquely determined, implying that orthogonal sets are linearly independent, and the inner product \(\u_i \cdot \v\) can be thought of as returning a coordinate of a point with respect to the \(\u_i\):
\[ \v = \sum_{i=1}^n (\u_i \cdot \v) \u_i \]
Now let \(\v\) be a vector outside the span of the \(\u_i\), so that the above equality fails, and consider the difference:
\[ \w = \v - \sum_{i=1}^n (\u_i \cdot \v) \u_i \]
The vector \( (\u_1 \cdot \v) \u_1 \) is sometimes called the vector projection of \(\v\) on \( \u_1, \) and \( \v - (\u_1 \cdot \v) \u_1 \) the vector rejection of \(\v\) from \( \u_1. \)
More generally, we can call \( \sum_{i=1}^n (\u_i \cdot \v) \u_i \) the vector projection of \(\v\) on the subspace generated by the \(\u_i\) and \(\w\) the vector rejection of \(\v\) from the subspace generated by the \(\u_i\).
Later, we’ll need this equation written only with inner products, and without the convenience of norms and normal vectors. This looks like:
\[ \w = \v - \sum_{i=1}^n \frac{\v_i \cdot \v}{\v_i \cdot \v_i} \v_i \]
Anyway, as before, for any \(k\):
\[ \u_k \cdot \w = \u_k \cdot \v - \u_k \cdot \left(\sum_{i=1}^n (\u_i \cdot \v) \u_i\right) = \u_k \cdot \v - \u_k \cdot \v = 0 \]
Thus \(\w\) is orthogonal to \(\u_1,…,\u_n\), and by construction, the span of \( \{\w, \u_1,…, \u_n \} \) is the same as the span of \( \{\v, \u_1,…, \u_n \} \).
This yields a non-constructive inductive proof that any \(n\)-dimensional vector space has an orthgonal basis. We start from the empty set \(B_0\). For \(k \ge 0 \), if \(B_k\) does not span the entire space, let \(\v\) be some vector lying outside the span, and use the above equation to compute a vector \(\w\) orthogonal to each vector of \(B_k\), and define \(B_{k+1} = B_k \cup \{ \w \}. \) This process must terminate in exactly \(n\) steps; the set \(B_n\) is an orthgonal basis of the entire space.
We can normalize each vector of such a basis to obtain an orthonormal basis, and it’s deja vu all over again: in a finite-dimensional space, any inner product is in fact just the standard dot product with respect to a certain basis. This is a sign that we have chosen our definitions wisely.
Change of basis is especially simple when the target basis is orthonormal. Let \(\{\u_1,…,\u_n\}\) be an orthonormal basis. From above:
\[ \v = \sum_{i=1}^n (\u_i \cdot \v) \u_i \]
Hence to write \(\v\) with respect to \(B\) we simply multiply \(\v\) by the matrix:
\[ \begin{bmatrix} \u_1 \\ \vdots \\ \u_n \end{bmatrix} = \begin{bmatrix} u_{11} & … & u_{1n} \\ \vdots & \ddots & \vdots \\ u_{n1} & … & u_{nn} \end{bmatrix} \]
To change back, we multiply by the transpose of this matrix; recall that for this matrix we simply write the basis vectors in columns. For this reason, we say \(M\) is an orthogonal matrix or an orthonormal matrix if \(M^T = M^{-1};\) one can check this equality implies the rows or columns of \(M\) are an orthonormal basis. (The term "orthogonal matrix" is mildly misleading, as it sounds like it ought to apply even when its vectors are not normal.)
Gram-Schmidt
Did you spot the non-constructive step in the above proof? It was when we magically plucked some vector \(\v\) not contained in the span. We shall see that a constructive version of the proof is invaluable, for both theory and practice.
To this end, suppose we’re given some basis of the space. We can then explicitly construct a orthogonal basis, simply by picking successive basis vectors for the \(\v\) in the above proof. We describe the details of this important algorithm, known as Gram-Schmidt orthogonalization.
Let \(\v_1, …, \v_n\) be a basis of a vector space \(V\). Define \(\w_1 = \v_1\), and for \(k \gt 1\) define:
\[ \w_{k+1} = \v_{k+1} - \sum_{i=1}^k \frac{\w_i \cdot \v_{k+1}}{\w_i \cdot \w_i} \v_{k+1} \]
Then \(\w_1,…,\w_n\) is the Gram-Schmidt orthogonalization of \(\v_1,…,\v_n,\) that is, the \(\w_i\) are an orthogonal set of nonzero vectors that span \(V\).
import Matrix
gramSchmidt = go [] where
go acc = \case
[] -> reverse acc
v:vt -> go (foldr (zipWith (+)) v (muMul v <$> acc):acc) vt
muMul v w = (-(mu v w) *) <$> w
mu v w = dot v w / dot w w
For example:
rice = [ [3, 2, 1] , [2, 3, 1] , [1, 2, 3] ] gramSchmidt rice
Let’s perform some sanity checks. The first vectors of the input and output should match:
g = gramSchmidt rice head g == head rice
The output vectors should be pairwise orthogonal:
[dot (g!!i) (g!!j) | let n = length g, i <- [0..n-1], j <- [i+1..n-1]]
Multiplying by its transpose should result in a diagonal matrix:
g `matrixMul` transpose g
Let \(G\) be the matrix of the Gram-Schmidt orthogonalization of \(\v_1, …, \v_n\), written as column vectors. The following computes the matrix \(H\) satisfying \(G H = A\), where the columns of \(A\) are \(\v_1, …, \v_n\).
unGramSchimidt vs = transpose $ go <$> vs where go v = mu v <$> ws ws = gramSchmidt vs h = unGramSchimidt rice
By convention, we tend to write vectors as column vectors, which explains
the transpose in the above code.
Let’s check it works as advertised:
matrixMul (transpose g) h == transpose rice
Next, we check by eye that every diagonal entry of \(H\) is 1, and that it is upper triangular:
Matrix h
This implies that the \(k\)th column vector of \(G\) can be written in terms of the first \(k\) columns of \(A\), and furthermore the \(k\)th coefficient is 1, thus each step really did take \(\v_k\) and subtract some linear combination of the previous entries. In particular the first vector is preserved.
Normalizing an orthogonal basis produces an orthonormal basis, which requires taking square roots.
normalize v = (recip (sqrt $ dot v v) *) <$> v orthonorm = map normalize . gramSchmidt orthonorm rice
An orthonormal basis can be viewed as an orthogonal matrix, so its inverse is its transpose:
orthonorm rice `matrixMul` transpose (orthonorm rice)
Let \(Q\) be the matrix resulting from normalizing each column vector of \(G\), that is, we compute the Gram-Schmidt orthogonalization of \(\v_1, …, \v_n\) and normalize each vector.
Like before, we can find an upper triangular matrix \(R\) such that \(QR = A\), where the columns of \(A\) are \(\v_1, …, \v_n\).
qr vs = (transpose g, matrixMul g vs) where g = orthonorm $ transpose vs (q, r) = qr rice Matrix $ q `matrixMul` r Matrix q Matrix r
This is known as the QR decomposition of a matrix.
Complex Inner Product Spaces
Generalizing the underlying field to the complex numbers runs into a hiccup. Consider one-dimensional space, that is just \(\mathbb{C}\). We want:
\[ |z|^2 = z \cdot z \]
and we want our definition to work for the classic norm we first learned in school, that is, there should be some choice of (\(\cdot\)) so that:
\[ |a + bi|^2 = (a + bi) \cdot (a + bi) = a^2 + b^2 \]
If we say (\(\cdot\)) is ordinary multiplication (which works fine for the reals), we run into \( |i|^2 = i \cdot i = i \times i = -1 \).
We can get rid of the pesky minus sign by conjugating the second argument before multiplication:
\[ |i|^2 = i \cdot i = i \times \bar{i} = i \times -i = 1 \]
and this fix works for all complex numbers since \(|z|^2 = z \bar{z}\).
But this implies (\(\cdot\)) is no longer necessarily symmetric. There’s nothing we can do about this. We must accept complex numbers are more complex, and slightly loosen our first requirement.
Define an inner product on a complex vector space \(V\) to be a function \( ( \cdot ) : V \times V → \mathbb{C} \) satisfying:
-
Conjugate symmetry: \[ \v \cdot \w = \overline{\w \cdot \v} \]
-
Linearity in the first argument: \[ (a_1 \v_1 + a_2 \v_2) \cdot \w = a_1 (\v_1 \cdot \w) + a_2 (\v_2 \cdot \w) \]
-
Positive definiteness: \[ \v \ne 0 \implies \v \cdot \v \ge 0 \]
It might seem the only use for these definitions are mathematical fun and games, because we typically model the space around us with \(\mathbb{R}^3\), with imaginary numbers left to the imagination. But it turns out physicists describe reality with complex inner product spaces.