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}$.

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$.


\[(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

  1. Solving linear systems. $x = A^{-1}b$.
  2. Least squares problems. $\min_x |Ax-b|^2_2$
  3. Eigenvalue problems. $Ax = \lambda x$
  4. Numerical optimization. $y_i \approx c^T \sigma(W_2\sigma (W_1x_i+b_1)+b_2)$
    1. What types of solutions?
    2. Efficiency
    3. Trade off with speed and quality

This course will involve developing algorithms.

Theme: Factorization $A = PLU$, $A = QR$, $A = QTQ^T$