1. Basic Linear Algebra Review
Feb 8, 2021
What is a matrix?
A matrix is a 2D array of numbers. A $m\times n$ matrix has $m$ rows and $n$ columns. It is a linear map between vector spaces. $L: \mathcal{V} \to \mathcal{W}$.
- Any vector in the span of a basis can be written as a linear combination of the basis vectors.
- A vector can be thought as a $n\times 1$ matrix.
- A scalar can be thought of as a $1\times 1$ matrix.
Common operations on matrices
Matrix vector products
\[A\vec x = \vec y.\]If we denote $A$ as the set of vectors $[a_1, \dots, a_n]$,
\[y = \sum_{i=1}^nx_ia_i\]Note that if $A$ is $m\times n$, then $\vec x$ must be $n\times 1$.
Transpose
\[(A^T)_{ij} = A_{ji}\]Inner product (over $\R$)
\[\vec x^T\vec y \to \alpha\]$x$ and $y$ must be $n\times 1$.
Outer product
\[\vec x \vec y^T\to A\]Matrix-matrix multiplication
\[AB \to C\]This can be thought of a sum between a $m\times k$ matrix and $k\times n$ matrix.
\[C = \sum_{i=1}^m\sum_{r=1}^ka_{ir}b_{rj}\]💡 Matrix-vector, inner product, and the outer product are all special cases of matrix-matrix multiplication!
Remember that matrix multiplication is linear and associative.
\[A(\alpha_1B_1 + \alpha_2B_2) = \alpha_1AB_1+\alpha_2AB_2.\]Blocked operations
A matrix can be thought of a combination of smaller matrices. Let $A_{ij}$ denote a block.
\[\begin{bmatrix} A_{11}& A_{12}\\ A_{21} & A_{22} \end{bmatrix}\begin{bmatrix}x_1\\x_2\end{bmatrix} = \begin{bmatrix}y_1\\y_2\end{bmatrix}\]The solutions to this equation are
\[y_1 = A_{11}x_1 + A_{12}x_2\\ y_2 = A_{21}x_1 + A_{22}x_2.\]Linear Algebra Concepts
\[\text{range}(A) = \text{"Col space of A"}\\ = \{Ax\mid x\in \R^n\}.\]From the range, we get the rank, which is the dimension of the image of $A$.
The null space (the kernel), is the set ${z\mid Az=0}$.
Rank-nullity theorem
\[\text{rank(A)} + \text{dim(null(A))} = n.\]Example. Suppose $A$ is equal to the outer product $uv^T$. The range of $A$ is
\[\{(uv^T)x\mid x\in \R^n\}.\]Since $v^Tx$ is a scalar, the rank of $A$ is 1. By the rank nullity theorem, the dimension of the null space is $n-1$.
Proposition. If for a matrix $m=n$ and is full rank, then by the rank nullity theorem, the dimension of the null space is 0. The matrix is called nonsingular (has an inverse).
Major Course Topics
- Solving linear systems. $x = A^{-1}b$.
- Least squares problems. $\min_x |Ax-b|^2_2$
- Eigenvalue problems. $Ax = \lambda x$
- Numerical optimization. $y_i \approx c^T \sigma(W_2\sigma (W_1x_i+b_1)+b_2)$
- What types of solutions?
- Efficiency
- Trade off with speed and quality
This course will involve developing algorithms.
- They guarantee solutions (in exact arithmetic), or approximate answers
- Stable w/r/t perturbations
- Efficiency / computational complexity
Theme: Factorization $A = PLU$, $A = QR$, $A = QTQ^T$
Goals
- Literate and comfortable with matrix comps + basic operations
- Know general building blocks and ideas
- Confidence to find a good solution for your problem