# 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

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