Introduction to Linear Algebra
Systems of Linear Equations
- Introduction
- Linear systems
- Vectors
- Linear combinations
- Matrices
- Planes in ℝ³
- Equation A x = b
- Sensitivity of solutions
- Linear independence
- Plane transformations
- Space transformations
- Linear transformations
- Affine maps
- Exercises
- Answers
Matrix Algebra
- Introduction
- Manipulation of matrices
- Partitioned matrices
- Block matrices
- Matrix operators
- Determinants
- Cofactors
- Cramer's rule
- Chiò's method
- Equivalent matrices
- Elimination: A = L U
- PLU factorization
- Reflection
- Givens rotation
- Special matrices
- Exercises
- Answers
Vector Spaces
- Introduction
- Motivation
- Vector spaces
- Bases
- Dimension
- Coordinate systems
- Linear transformations
- Change of basis
- Matrix transformations
- Compositions
- Isomorphisms
- Dual transformations
- Quotient spaces
- Rank
- Solving A x = b
- Exercises
- Answers
Eigenvalues, Eigenvectors
- Introduction
- Characteristic polynomials
- Companion matrix
- Algebraic and geometric multiplicities
- Minimal polynomials
- Eigenspaces
- Where are eigenvalues?
- Eigenvalues of A B and B A
- Generalized eigenvectors
- Similarity
- Diagonalizability
- Self-adjoint operators
- Exercises
- Answers
Euclidean Spaces
- Introduction
- Euclidean space
- Bilinear transformations
- Norm and distance
- Matrix norms
- Dual norms
- Dual transformations
- Examples of transformations
- Orthogonality
- Gram--Schmidt Process
- Orthogonal matrices
- Self-adjoint matrices
- Unitary matrices
- Projection operators
- QR-decomposition
- Least Square Approximation
- Quadratic forms
- Exercises
- Answers
Canonical forms
- Introduction
- 2D decomposition
- 3D decomposition
- Projectors
- Direct-sum decompositions
- Cyclic decompositions
- Symmetric matrices
- Pseudoinverse
- URV-decomposition
- LU-decomposition
- QR-decomposition
- Cholesky decomposition
- Schur decomposition
- Positive matrices
- Roots
- Polar factorization
- Spectral decomposition
- CUR decomposition
- Exercises
- Answers
Applications
- Introduction
- Circles along curves
- TNB frames
- GPS problem
- Coriolis acceleration
- Poisson equation
- Graph theory
- Error correcting codes
- Electric circuits
- FSA
- Markov chains
- Cryptography
- Wave-length transfer matrix
- Computer graphics
- Linear Programming
- Hill's determinant
- Fibonacci matrices
- Discrete dynamic systems
- Discrete Fourier transform
- Fast Fourier transform
- Curve fitting
- Answers
Miscellany
- Introduction
- Circles along curves
- TNB frames
- Differential forms
- Calculus
- Vector representations
- Matrix representations
- Change of basis
- Orthonormal Diagonalization
- Generalized inverse
- Differential forms
Preliminaries
- Complex Number Operations
- Sets
- Polynomials
- Polynomials and Matrices
- Computer solves Systems of Linear Equations
- Location of Eigenvalues
- Power Method
- Iterative Method
- Similarity and Diagonalization
Glossary
Reference
This Book is licensed under Creative Commons Attribution-NonCommercial-NoDerivs 3.0 Unported License
To enhance pedagogical effectiveness, the treatment of the dot product is presented in several distinct sections
Metric
Metric via Dot Product
In mathematics, a metric space is a set where a notion of distance between any two elements (usually called points) is defined, satisfying specific axioms: non-negativity, identity of indiscernibles, symmetry, and the triangle inequality. Essentially, it's a set with a defined distance function that allows us to measure how "far apart" any two elements are.
A vector space, by definition, has no metric inside it, which is very desirable property. It turns out that the scalar product can be used to define length or distance between vectors transferring ℝn into a metric space, known as the Euclidean space. In order to distinguish metric space from vector space with metric, mathematicians call the magnitude or length of vector v by norm and denote it as ∥v∥.
A first relation between the angles α and β is found if we project the sides AC and BC onto AB \[ c = b\,\cos\alpha + a\,\cos\beta . \] Projecting similarly onto the other sides, we are led to two further equations (which can be obtained from the first one by the use of circular permutations). Here is the system \[ \begin{cases} b\,\cos\alpha + a\,\cos\beta \phantom{+b\,\cos\gamma} &= c , \\ \phantom{b\,\cos\alpha} c \,\cos\beta + b\,\cos\gamma &= a , \\ c\,\cos\alpha + \phantom{c\.\cos\beta} + a\,\cos\gamma &= b . \end{cases} \] It is linear in the three variables x₁ = cosα, x₂ = cosβ, x₃ = cosγ. Let us solve this system by Gaussian elimination: \begin{align*} \left( \begin{array}{ccc|l} b&a&0&c \\ 0&c&b&a \\ c&0&a&b \end{array} \right) &\sim \left( \begin{array}{ccc|l} b&a&0&c \\ 0&c&b&a \\ 0& -\frac{c}{b}\,a & a& b - \frac{c}{b}\,c \end{array} \right) \\ &\sim \left( \begin{array}{ccc|l} b&a&0&c \\ 0&c&b&a \\ 0&0& 2a & b - \frac{c^2}{b} + \frac{a^2}{b} \end{array} \right) \end{align*} This yields
With standard basis in ℝn
We summarize properties of Euclidean norm in the following assesment.
- ∥v∥ > 0 for v ≠ 0 (positivity).
- ∥λv∥ = |λ| ∥v∥ (scaling).
- ∥v + u∥ ≤ ∥v∥ + ∥u∥ (triangle inequality).
- | ∥v∥ − ∥u∥ | ≤ ∥v − u∥ ≤ ∥v∥ + ∥u∥.
- This property follows immediately from the definition \[ \mathbf{v} \bullet \mathbf{v} = v_1^2 + v_2^2 + \cdots + v_n^2 . \] A sum of positive entries cannot be negative, and it is zero only when every term is zero.
- It has been shown previously.
- By definition, \begin{align*} \| \mathbf{v} - \mathbf{u} \|^2 &= \left( \mathbf{v} - \mathbf{u} \right) \bullet \left( \mathbf{v} - \mathbf{u} \right) \\ &= \mathbf{v} \bullet \mathbf{v} + \mathbf{v} \bullet \mathbf{u} + \mathbf{u} \bullet \mathbf{v} + \mathbf{u} \bullet \mathbf{u} = \| \mathbf{v} \|^2 + \| \mathbf{u} \|^2 + 2\,\mathbf{v} \bullet \mathbf{u} . \end{align*} Using Cauchy's inequality, we get \[ \left\vert \mathbf{v} \bullet \mathbf{u} \right\vert \le \| \mathbf{v} \| \cdot \| \mathbf{u} \| . \] This yields \[ \| \mathbf{v} - \mathbf{u} \|^2 \le \| \mathbf{v} \|^2 + \| \mathbf{u} \|^2 + 2\,\| \mathbf{v} \| \cdot \| \mathbf{u} \| = \left( \| \mathbf{v} \| + \| \mathbf{u} \| \right)^2 . \]
- Similarly to the previous proof, \[ \| \mathbf{v} - \mathbf{u} \|^2 = \left( \mathbf{v} - \mathbf{u} \right) \bullet \left( \mathbf{v} - \mathbf{u} \right) = \| \mathbf{v} \|^2 + \| \mathbf{u} \|^2 - 2\left( \mathbf{v} \bullet \mathbf{u} \right) \] Again from Cauchy's inequality, \[ - 2\left( \mathbf{v} \bullet \mathbf{u} \right) \ge 2\,\| \mathbf{v} \| \cdot \| \mathbf{u} \| , \] which leads to \[ \| \mathbf{v} - \mathbf{u} \|^2 \ge \| \mathbf{v} \|^2 + \| \mathbf{u} \|^2 - 2\, \| \mathbf{v} \| \cdot \| \mathbf{u} \| = \left( \| \mathbf{v} \| - \| \mathbf{u} \| \right)^2 . \] The next inequality \( \displaystyle \quad \| \mathbf{v} - \mathbf{u} \| \le \| \mathbf{v} \| + \| \mathbf{u} \| \quad \) follows from the triangle inequality (property 3).
Using Mathematica, we verify properties included in Theorem 6 with the following examples.
- This formulas follows from the identity: \[ \mathbf{v} \bullet \mathbf{v} = v_1^2 + v_2^2 + \cdots + v_n^2 . \] which is zero only when all components of vector v are zeroes.
-
We generate a vector of size five:
v = Flatten[RandomReal[{-1, 1}, {1, 5}]]{0.371645, -0.811594, 0.591386, -0.037053, 0.758338}Upon choosing a real scalar λ = 2.71, we multiply2.71*v{1.00716, -2.19942, 1.60266, -0.100414, 2.0551}Its norm isNorm[2.71*v]3.55722Now we calculate the norm of v and multiply the result by λ = 2.71,2.71*Norm[v]3.55722
-
We generate two vectors of length five:
v = RandomInteger[{-8, 8}, {1, 5}]{{-1, -7, 0, 6, 1}}u = RandomInteger[{-7, 8}, {1, 5}]{{-1, 3, -2, 2, 3}}In order to verify the triangle inequality, we evaluate both sides:N[Norm[u] + Norm[v]]14.5235N[Norm[u + v]]10.198\[ 10.198 \approx \| \mathbf{v} + \mathbf{u} \| < \| \mathbf{v} \| + \| \mathbf{u} \| \approx 14.5235 . \]
-
We choose randomly two vectors
v = Flatten[RandomInteger[{-7, 9}, {1, 6}]]
u = Flatten[RandomInteger[{-7, 9}, {1, 6}]]{5, 9, -5, 1, 2, -2}Their norms are
{-1, -6, 3, -5, -3, -1}Norm[v]2 Sqrt[35]Norm[u]9The difference of norms isN[Norm[v] - Norm[u]]2.83216The norm of their difference isN[Norm[v - u]]19.6723The sum of norms isN[Norm[v] + Norm[u]]20.8322These numbers confirm inequalities in part 4.
Scalar multiplication property allows us to define, for any non-zero vector v ∈ ℝn, an associated normalized vector n with unit length given by
Upon introducing the norm (meaning length or magnitude) of a vector, \( \displaystyle \quad \| {\bf v} \| = +\sqrt{{\bf v} \bullet {\bf v}} , \quad \) Cauchy's inequality can be written as
Using points A(0, 0, c), B(𝑎, 0, 0), and C(0, b, 0), we find vectors \[ \mathbf{u} = \vec{BA} = (-a, 0, c) \qquad\mbox{and} \qquad \mathbf{v} = \vec{BC} = (-a, b, 0) . \] Their norms \[ \| \mathbf{u} \| = \sqrt{a^2 + c^2} , \qquad \|\mathbf{v} \| = \sqrt{a^2 + b^2} \] and dot product \[ \mathbf{u} \bullet \mathbf{v} = a^2 \] show that formula (8) can be written as \[ \frac{\mathbf{u} \bullet \mathbf{v}}{\| \mathbf{u} \| \cdot \| \mathbf{v} \|} = \frac{a^2}{\sqrt{a^2 + c^2}\cdot\sqrt{a^2 + b^2}} = \cos\theta \] because the ratio is definitely less than 1. For instance, if 𝑎 =1, b = 2, and c = 3, we get \[ \cos\theta = \frac{1}{\sqrt{5}\cdot \sqrt{10}} \qquad \Longrightarrow \qquad \theta = \mbox{arctan}\left( \frac{1}{5\sqrt{2}} \right) \approx 0.14049 . \]
Another angle problem: We consider the same cuboid, but now we are going to determine the angle between a diagonal on a face and a diagonal of the cuboid. Upon plotting Figure 16.2, we are after the angle ∠ABD.
Since point D has coordinates (0, b, c), we find vector \( \displaystyle \quad \mathbf{v} = \vec{BD} = \left( -a, b, c \right) . \quad \) Then the dot product of vectors u and v becomes \[ \mathbf{u} \bullet \mathbf{v} = \left( -a, 0, c \right) \bullet \left( -a, b, c \right) = a^2 + c^2 . \] Then formula (8) yields \[ \cos\theta = \frac{\mathbf{u} \bullet \mathbf{v}}{\| \mathbf{u} \| \, \| \mathbf{v} \|} = \frac{a^2 + c^2}{\sqrt{a^2 + c^2}\,\sqrt{a^2 + b^2 + c^2}} . \] Taking inverse cosine function, we find the angle to be \[ \theta = \mbox{arccos} \left( \frac{\sqrt{a^2 + c^2}}{\sqrt{a^2 + b^2 + c^2}} \right) . \] For 𝑎 =1, b = 2, c = 3, we get \[ \theta = \mbox{arccos} \left( \frac{\sqrt{10}}{\sqrt{14}} \right) \approx 0.563943 = 32.3115^{\circ} . \]
Dot product in not standard bases
When ordered basis [e₁, e₂, … , en] in ℝn is not a standard one, the dot product must be modified in order to maintain regular (Euclidean) distance between points or vectors:
If [e¹, e², … , en] is the dual basis, then the inverse of gi,j is the raised-indices metric tensor for the covector space:
Another basis: \[ \beta = \left[ \mathbf{b}_1 , \mathbf{b}_2 \right] = \left[ \mathbf{i} , \mathbf{i} + \mathbf{j} \right] . \] The vector v = (−3, 4) has the following coordinates in basis β: \[ \mathbf{v} = \left( -3, 4 \right) \qquad \Longrightarrow \qquad \left[\!\left[ \mathbf{v} \right]\!\right]_{\beta} = \left( v^1 , v^2 \right) = \left( -7 , 4 \right) \] because \[ \mathbf{v} = -3\mathbf{i} + 4\mathbf{j} = -3\mathbf{i} + 4 \left( \mathbf{i} + \mathbf{j} - \mathbf{i} \right) = -3\mathbf{i} + 4 \left( \mathbf{i} + \mathbf{j} \right) - 4\mathbf{i} . \] Here we used a mathematical trick: add and subtruct the same value. The second component j is replaced by j + i − i = b₂ − i. The dot product in basis β becomes \begin{align*} \mathbf{v} \bullet \mathbf{v} &= g_{1,1} v^1 v^1 + g_{1,2} v^1 v^2 + g_{2,1} v^2 v^1 + g_{2,2} v^2 v^2 \\ &= g_{1,1} \left( -7 \right)^2 + g_{1,2} \left( -7 \right) \left( 4 \right) + g_{2,1} \left( 4 \right) \left( -7 \right) + g_{2,2} \left( 4 \right)^2 \\ &= g_{1,1} 49 - g_{1,2} 28 - g_{2,1} 28 + g_{2,2} 16 . \end{align*} The components of the metric tensor are \begin{align*} g_{1,1} &= \mathbf{b}^1 \bullet \mathbf{b}^1 = \mathbf{i} \bullet \mathbf{i} = 1 , \\ g_{1,2} &= \mathbf{b}^1 \bullet \mathbf{b}^2 = \mathbf{i} \bullet \left( \mathbf{i} + \mathbf{j} \right) = \mathbf{i} \bullet \mathbf{i} + \mathbf{i} \bullet \mathbf{j} = 1 + 0 = 1 , \\ g_{2,1} &= \mathbf{b}^2 \bullet \mathbf{b}^1 = \mathbf{i} \bullet \left( \mathbf{i} + \mathbf{j} \right) = \mathbf{i} \bullet \mathbf{i} + \mathbf{i} \bullet \mathbf{j} = 1 + 0 = 1 , \\ g_{2,2} &= \mathbf{b}^2 \bullet \mathbf{b}^2 = \left( \mathbf{i} + \mathbf{j} \right) \bullet \left( \mathbf{i} + \mathbf{j} \right) = \mathbf{i} \bullet \mathbf{i} + \mathbf{j} \bullet \mathbf{j} = 2 . \end{align*} Using these values, we calculate the dot product \begin{align*} \mathbf{v} \bullet \mathbf{v} &= 49 - 28 - 26 + 2\cdot 16 = 25 . \end{align*}