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 : V \to 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}^{n} x_{i} a_{i}

Note that if $A$ is $m \times n$ , then $\vec{x}$ must be $n \times 1$ .

Transpose

(A^{T})_{i j} = A_{j i}

Inner product (over $R$ )

{\vec{x}}^{T} \vec{y} \to α

$x$ and $y$ must be $n \times 1$ .

Outer product

\vec{x} {\vec{y}}^{T} \to A

Matrix-matrix multiplication

A B \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}^{k} a_{i r} b_{r j}

💡 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 (α_{1} B_{1} + α_{2} B_{2}) = α_{1} A B_{1} + α_{2} A B_{2} .

Blocked operations

A matrix can be thought of a combination of smaller matrices. Let $A_{i j}$ denote a block.

[\begin{matrix} A_{11} & A_{12} \\ A_{21} & A_{22} \end{matrix}] [\begin{matrix} x_{1} \\ x_{2} \end{matrix}] = [\begin{matrix} y_{1} \\ y_{2} \end{matrix}]

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

range (A) = "Col space of A" = {A x ∣ 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 ∣ A z = 0$ .

Rank-nullity theorem

rank(A) + dim(null(A)) = n .

Example. Suppose $A$ is equal to the outer product $u v^{T}$ . The range of $A$ is

{(u v^{T}) x ∣ x \in R^{n}} .

Since $v^{T} x$ 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} | A x - b |_{2}^{2}$
Eigenvalue problems. $A x = λ x$
Numerical optimization. $y_{i} \approx c^{T} σ (W_{2} σ (W_{1} x_{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.

They guarantee solutions (in exact arithmetic), or approximate answers
Stable w/r/t perturbations
Efficiency / computational complexity

Theme: Factorization $A = P L U$ , $A = Q R$ , $A = Q T Q^{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