Linear Algebra
Introduction
Let $\R$ denote the set of real numbers. Its elements are called scalars. If $n$ is a positive integer, then the $\R^n$ is defined to be the set of all sequences $\mathbf{x}$ of $n$ real numbers $\mathbf{x} = (x_1, x_2, \dots, x_n)$. This is referred to as a Cartesian product.
The elements of $\R^n$ are called points or vectors. We follow the convention of indicating vectors in boldface and scalars in plainface. For a vector $\mathbf{x} \in \R^n$, the individual scalar entries $x_i$ for $i = 1, 2, \dots, n$ are called coordinates or components.
Linear algebra extends elementary algebra by viewing linear systems of equations as linear transformations of vectors from $\R^n$ to $\R^m$ (through the matrix equation $A\mathbf{x} = \mathbf{b}$), as opposed to a collection of unrelated equations. This concept is then generalized to apply to transformations between abstract vector spaces.
Vectors and Orthogonality
Vectors are the fundamental objects of study in linear algebra. In contrast to physics or computer science, which define vectors as an arrow in space or a tuple of $n$ numbers, pure mathematics defines a vector by a set of axioms.
More specifically, if we take vectors and add them together or multiply them by a scalar, the result remains within the same vector space. This makes the idea of linear combinations useful, because any linear combination of some vectors is still a vector. We formalize this in the definitions below:
There is also vector subspaces, which are subsets of a vector space (containing the zero vector) that is closed under addition and multiplication. They can always be defined by a set of basis vectors.
Inner product is an operation on two vectors in an inner product space that returns a scalar. Inner products is perhaps one of the most important vector operations, because it reveals information on both the magnitude and angle between of the two vectors. The most common inner product space is the real Euclidian space $\R^n$, where the inner product is defined as the dot product.
The operation defined as the inner product must satisfy the following properties:
| Inner product definition | |
|---|---|
| $\langle \mathbf{u}, \mathbf{v} \rangle = \langle \mathbf{v}, \mathbf{u} \rangle$ | $\langle \alpha \mathbf{u}, \mathbf{v} \rangle = \alpha \langle \mathbf{u}, \mathbf{v} \rangle$ |
| $\langle \mathbf{u} + \mathbf{w}, \mathbf{v} \rangle = \langle \mathbf{u}, \mathbf{v} \rangle + \langle \mathbf{w}, \mathbf{v} \rangle$ | $\langle \mathbf{v}, \mathbf{v} \rangle \geq 0$, with equality if and only if $\mathbf{v} = \mathbf{0}$ |
Commonly defined inner-product spaces:
- The set of real numbers $\R$, with $\langle u, v\rangle = uv$ ($u,v$ in $\R$).
- The set of real coordinate space $\R^{n}$, with $\langle \mathbf{u},\mathbf{v}\rangle = \mathbf{u}^{T}\mathbf{v}$ (the dot product).
- The set $C[a,b]$ of continuous functions on $[a,b]$, with $\langle f,g\rangle = \int_{a}^{b} f(x) g(x)\ \dd{x}$.
We can now define the angle between two vectors; two vectors $\mathbf{u}, \mathbf{v}$ are orthogonal when their inner product satisfy $\langle \mathbf{u}, \mathbf{v} \rangle = 0$. Two vectors $\mathbf{u}, \mathbf{v}$ are orthonormal when they are orthogonal and both have norm of $1$.
An orthogonal projection of $\mathbf{v}$ onto the subspace $W$ is defined as the vector,
$$proj_{W}(\mathbf{v}) = \hat{\mathbf{v}}$$
where $\hat{\mathbf{v}}$ in the span of $W$ such that $\mathbf{v} = \hat{\mathbf{v}} + \mathbf{u}$, where $\mathbf{u}$ is in $W^{\perp}$ (the orthogonal complement of $W$).
Orthogonal projections’ geometric interpretation is the “shadow” cast on $W$ by $\mathbf{v}$. They are used frequently to solve the least squares problems.
The orthogonal projection of $\mathbf{v}$ onto subspace $W$ can be calculated as follows:
- $proj_{\mathbf{S}}(\mathbf{v}) = \frac{\langle \mathbf{v}, \mathbf{u}_{1} \rangle}{\langle \mathbf{u}_{1}, \mathbf{u}_{1} \rangle}\mathbf{u}_{1} + \cdots + \frac{\langle \mathbf{v}, \mathbf{u}_{n} \rangle}{\langle \mathbf{u}_{n}, \mathbf{u}_{n} \rangle}\mathbf{u}_{n}$, where $\mathbf{u}_{i}$ are the orthogonal basis for $S$.
- $proj_{\mathbf{S}}(\mathbf{v}) = A(A^{T} A)^{-1} A^{T}\mathbf{v}$, where the column vectors of $A$ are any basis for $S$.
The Gram-Schmidt process is the process of transforming a set of basis into an orthogonal basis. It repeatedly applies the equations above to adjust each basis to be orthogonal to each other, one by one.
Matrices and Linear Transformations
We now turn to functions on vector spaces. The particular type of function that we are interested in the most are functions that are linear. We define linearity below:
Linear transformations, denoted by $T: V \to W$, is a function from abstract vector spaces $V$ to $W$ that preserves addition and scalar multiplication. Technically, $T$ is linear if and only if
- $T(\mathbf{u} + \mathbf{v}) = T(\mathbf{u}) + T(\mathbf{v})$
- $T(\alpha \cdot \mathbf{u}) = \alpha \cdot T(\mathbf{u})$
for all $\mathbf{u}, \mathbf{v} \in V$ and for all $\alpha \in \R$.
In addition, we define the following properties for any linear transformation $T: V \to W$ to better characterize their behavior:
- The kernel of $T$, denoted by $\text{Ker}(T)$, is defined to be $\{\mathbf{x} \in V\ |\ T(\mathbf{x}) = \mathbf{0}\}$.
- The image of $T$, denoted by $\text{Im}(T)$, is defined to be $\{T(\mathbf{x}) \in W\ |\ \mathbf{x} \in \mathbf{V}\} = T(\mathbf{V})$.
- An eigenvector of $T$ is defined as $\mathbf{x}$ such that $T(\mathbf{x}) = \lambda \mathbf{x}$, where $\lambda$ is its eigenvalue.
- An eigenspace of $T$, is defined as the span of all eigenvectors with some eigenvalue $\lambda$.
The number of dimensions of the image of $T$ is called the rank of $T$. The number of dimensions of the kernel of $T$ is called the nullity of $T$. We have the following relationship:
Let $T: V \to W$ be an arbitrary linear transformation. Let $p$ and $q$ be the rank and nullity of $T$, respectively. Then, the following equality holds:
$$p + q = \text{dim}(V)$$
Although a linear transformation can map from any abstract vector space to another, one can always choose a set of basis vectors to describe the linear transformation with one that maps from $\R^n$ to $\R^m$. Not only that, one can further describe any transformation from $\R^n$ to $\R^m$ by its effect on the standard basis of $\R^n$ ($\mathbf{e}_1, \mathbf{e}_2, \dots, \mathbf{e}_n$). This is illustrated below:
First, note that every $\mathbf{x}$ in $\R^n$ can be expressed in terms of the standard basis vectors: $\mathbf{x} = x_1 \mathbf{e}_1 + x_2 \mathbf{e}_2 + \cdots + x_n \mathbf{e}_n$. Thus, by the definition of the linear transformation:
$$ \begin{align*} T(\mathbf{x}) &= T(x_1 \mathbf{e}_1 + x_2 \mathbf{e}_2 + \cdots + x_n \mathbf{e}_n) \\ &= T(x_1 \mathbf{e}_1) + T(x_2 \mathbf{e}_2) + \cdots + T(x_n \mathbf{e}_n) \\ &= x_1 T(\mathbf{e}_1) + x_2 T(\mathbf{e}_2) + \cdots + x_n T(\mathbf{e}_n) \\ &= x_1 \mathbf{a}_1 + x_2 \mathbf{a}_2 + \cdots + x_n \mathbf{a}_3 \\ \end{align*} $$
where each $\mathbf{a}_i = T(\mathbf{e}_i)$. Thus, a linear transformation is completely determined by its effects on the basis vectors. We record this intuition via matrices.
A matrix is a rectangular array of numbers. In linear algebra, both systems of linear equations and linear transformations $T: \R^{n} \to \R^{m}$ can be represented by an $m \times n$ matrix $A$, where $T(\mathbf{x}) = A\mathbf{x}$. In this case:
- The image is referred to as the column space: $\text{Col}(A) = \text{Span} \{\mathbf{a}_{1}, \dotsc, \mathbf{a}_{n}\}$
- The kernel is referred to as the null space: $\text{Null}(A) = \text{Span} \{\mathbf{x} \ |\ A \mathbf{x} = \mathbf{0}\}$.
Matrices can be added entry by entry and multiplied row by column, as well as transposed or inverted. Matrix multiplication is geometrically a composition of two linear transformations. It is not commutative, because the composite function $(T \circ S)(\mathbf{x})$ is not equivalent to $(S \circ T)(\mathbf{x})$.
| Properties of matrices | |
|---|---|
| $AB \neq BA$ (multiplication) | $A^{n} = AA \cdots A$ (power) |
| $A(B + C) = AB + AC$ (left distribution) | $(B + C)A = BA + CA$ (right distribution) |
| $(AB)^{T} = B^{T} A^{T}$ (transposition of products) | $(AB)^{-1} = B^{-1} A^{-1}$ (inverse of products) |
| $(A^{-1})^{T} = (A^{T})^{-1}$ (transposition of inverse) | $(A^{-1})^{-1} = A$ (inverse of inverse) |
In addition to these properties, one can apply three types of elementary row operations on matrices, which has a number of uses such as computing row echelon form, computing determinants, and finding inverse matrices.
Elementary row operations are also represented as elementary matrices, denoted by $E$. They are matrices obtained by one elementary row operation on the identity matrix $I$. It can be proven that left multiplying some matrix $A$ with an elementary matrix obtained by an row operation is the same as applying that row operation on $A$ directly. In other words, if $f$ is a function that applies an row operation on some matrix $A$, then $f(A) = f(I) \cdot A$.
Using row reduction to solve $A\mathbf{x} = \mathbf{b}$ can be viewed as left multiplying a bunch of elementary matrices:
$$(E_k \cdots E_3E_2E_1)A\mathbf{x} = (E_k \cdots E_3E_2E_1)\mathbf{b}$$
If after $k$ multiplications, the left hand side reduces to the identity matrix, we can conclude that $E_k \cdots E_3E_2E_1 = A^{-1}$. Because each elementary matrix corresponds to a row operation, we can perform the same sequence of row operation on an identity matrix to compute the inverse $A^{-1}$. Thus, we find $T^{-1}(\mathbf{x}) = A^{-1} \mathbf{x}$.
Determinants and Diagonalization
Determinants are a number associated with a square matrix. Historically, they were developed to solve $n \times n$ systems of equations (Cramer’s Rule), but now primarily serve as a geometric interpretation of linear maps.
Determinants represent how the linear transformation scales space itself. For example, if a determinant of a $2 \times 2$ matrix is $5$, then the linear transformation the matrix represents scales area by a factor of $5$. If a determinant of a $3 \times 3$ matrix is $1/4$, then the linear transformation scales volume by a quarter.
| Properties of determinants | |
|---|---|
| $\det(AB) = \det(A) \cdot \det(B)$ | $\det(A^{-1}) = 1 /\det(A)$ |
| $\det(A) = \det(A^{T})$ | $\det(c \cdot A) = c^{n} \cdot \det(A)$ |
| $\begin{vmatrix} a & b \\ c & d \end{vmatrix} = ad - bc$ | $\begin{vmatrix} a & b & c \\ d & e & f \\ g & h & u \end{vmatrix} = a \begin{vmatrix} e & f \\ h & u \end{vmatrix} - b \begin{vmatrix} d & f \\ g & u \end{vmatrix} + c \begin{vmatrix} d & e \\ g & h \end{vmatrix}$ |
The most straightforward method of computing determinants is to use Laplace expansion by computing its minors and cofactors. However, it may be worthwhile to use row or column operations (since $\det A = \det A^T$) to simplify the matrix beforehand.
Since performing an elementary row operation on $A$ is equivalent to left multiplying an elementary matrix $E$, and $\det EA = \det E \cdot \det A$, one can recover $\det A = \det EA / \det E$ after performing a row or column operation on $A$. In particular, the following row operations necessitate the following changes on the determinant:
- Swapping two rows: $\det (A)$ changes sign
- Multiply a row by scalar $k$: $\det (A)$ is multiplied by $k$
- Add one row to another row: $\det (A)$ does not change.
If the $\det A = 0$, then the transformation $T(\mathbf{x}) = A\mathbf{x}$ compresses dimensions. This means that $A$ is not full-rank and has a nonzero null space, and $A$ is not invertible.
The inverse of an $n \times n$ matrix $A$ exists if
- $A$ has a non-zero determinant.
- $A$ is row equivalent to the identity matrix $I$.
- $A$ is a one-to-one and onto map (bijective).
- $A$ is full-rank (the dimensions of its column space is $n$).
- $A$’s nullity (dimension of its null space) equals zero.
- $A$ is the product of two invertible matrices.
- The transpose of $A$ is also invertible.
- The eigenvalue of $A$ does not contain $0$.
To better manipulate, solve, and characterize matrices and their underlying linear map, we can factor a matrix. Some common factorizations include the $LU$ and the $QR$ factorization. In particular, the factorization of a matrix into a diagonal matrix is called diagonalization or eigendecomposition.
An $n \times n$ matrix $A$ is diagonalizable if it is similar to a diagonal matrix.
- If $A$ is diagonalizable, then $A = PDP^{-1}$. Note that we can calculate $A^n$ easily here.
- The $i$-th diagonal entry of matrix $D$, $d_{ii}$, is a unique eigenvalue of matrix $A$.
- The $i$-th column vector of matrix $P$, $\mathbf{p}_{i}$ is a linearly independent eigenvector of matrix $A$.
- The matrix $A$ can be diagonalized if there are enough linearly independent eigenvectors.
- Geometrically, diagonalizations and similar matrices are a change of basis.