Linear Algebra

Linear algebra is the backbone of deep learning. As Andrew Ng famously said,

“Linear algebra is the language of deep learning”.

Vectors and Matrices

Several types of mathmatical objects are important in discussing linear algebra study:

Scalars: single number, in contrst with the array, matrix … which are the series of numbers.

Vector: An ordered list of numbers (scalars) often represented as a column.

e.g., a vector in $\mathbb{R}^n$ can be written as $\mathbf{v} = \begin{bmatrix} v_1 \\ v_2 \\ \vdots \\ v_n \end{bmatrix}$

Matrix (Matrices): A rectangular array of numbers with size

m \times n

(

m

rows,

n

columns), or 2-D array. We often denote a matrix as

A = [a_{ij}]

where

a_{ij}

is the entry in the

i

th row and

j

th column.

e.g. $2\times 3$ matrix: $A = \begin{bmatrix} a_{11} & a_{12} & a_{13} \\ a_{21} & a_{22} & a_{23} \end{bmatrix}$ . A column vector is a special case of a matrix (size $n \times 1$ ).

Tensors are generalizations of matrices to higher dimensions (used to store multi-dimensional data in deep learning).

Matrix Operations

Transpose: mirror image of the matrix acress the main diagonal line.

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

. e.g.,

A = \begin{bmatrix} \boldsymbol{a_{11}} & a_{12} \\ a_{21} & \boldsymbol{a_{22}} \\ a_{31} & a_{32} \end{bmatrix} \Rightarrow A^T = \begin{bmatrix} \boldsymbol{a_{11}} & a_{21} & a_{31} \\ a_{12} & \boldsymbol{a_{22}} & a_{32} \end{bmatrix}

Addition: for matrices

A

and

B

of the same size, e.g.

m\times n

(A + B)_{ij} = A_{ij} + B_{ij}

(add corresponding entries).

Scalar Multiplication: for scalar

c

(cA)_{ij} = c \cdot A_{ij}

Matrix Multiplication:

A

m\times n

and

B

n\times p

, their product

C = AB

is an

m\times p

matrix with entries:

C_{ij} = \sum_{k=1}^{n} A_{ik}\, B_{kj}

(sum of row

i

A

times column

j

B

). Matrix multiplication is associative and distributes over addition (but not commutative in general).

Multiplication (dot product) operation is both distributive, $A(B+C)=AB+AC$ , and associative, $A(BC) = (AB)C$ . But it’s NOT commutative, $AB \neq BA$ .

BUT, the dot product of vectors is commutative, $x^Ty = y^Tx$ :

\text{Since, }(AB)^T = B^T A^T\,,\,(A^T)^T = A\\ \text{Hence, }x^Ty = (x^Ty)^T = y^Tx

Untile now, we can introduce the system of linear algebra, which is the main problems notation that we are goning to solve. $Ax=b$ , where $\boldsymbol{A}\in\mathbb{R}^{m\times n}$ is a matrix, $\boldsymbol{b}\in\mathbb{R}^{m}$ is a vector, $\boldsymbol{x}\in\mathbb{R}^{n}$ is a vector of unknown.

Additionals

Identity Matrix

I

: Mathmatically:

I_n \in \mathbb{R}^{n\times n}\text{, and, }\forall x \in \mathbb{R}^{n}, I_{n}x = x

. It acts as the multiplicative identity:

AI = A

and

IA = A

. Simply,

I = \operatorname{diag}(1,1,\dots,1)

, or

I = \begin{bmatrix} 1 & 0 & 0 & \cdots & 0 \\ 0 & 1 & 0 & \cdots & 0 \\ 0 & 0 & \ddots & \ddots & \vdots \\ \vdots & \vdots & \ddots & \ddots & 0 \\ 0 & 0 & \cdots & 0 & 1 \end{bmatrix}

Inverse: For a square matrix

A

, the inverse

A^{-1}

satisfies

AA^{-1} = A^{-1}A = I

. Only invertible (non-singular) matrices have inverses, which requires full rank (no zero eigenvalues, see rank below). e.g. For a

2\times2

A=\begin{pmatrix}a & b\\ c & d\end{pmatrix}

A^{-1} = \displaystyle\frac{1}{ad - bc}\begin{pmatrix} d & -b\\ -c & a \end{pmatrix}

(provided

ad - bc \neq 0

). And we do can solve

x

from

Ax=b

Ax = b\\ A^{-1}Ax = A^{-1}b\\ I_nx = A^{-1}b\\ x = A^{-1}b

Determinant (

\det A

|A|

): A scalar value defined for square matrices that encodes volume scaling factor of the linear transformation and whether it flips orientation.

e.g. For $2\times2$ as above, $\det(A) = ad - bc$ . For larger matrices, it’s computed via a recursive formula or row reduction.

$\det(AB) = \det(A)\det(B)$ ,

$\det(A)\neq 0 \iff A\ \text{is invertible}$ .

Trace: The trace of a square matrix is the sum of its diagonal entries:

\mathrm{tr}(A) = \sum_{i=1}^n a_{ii}

. Notable property: the trace equals the sum of eigenvalues of

A

(counting multiplicity), and it is invariant under change of basis.

Rank: The rank of a matrix is the number of linearly independent rows (which equals the number of independent columns). It indicates the dimension of the subspace spanned by its columns (column space). Full rank means rank =

\min(m,n)

; for a square

n\times n

matrix, full rank (rank

=n

) means the matrix is invertible. Low rank means the matrix’s rows/columns are linearly dependent (some redundancy in information).

e.g., $\begin{bmatrix} 1 & 0 & 1\\ 0 & 1 & 1\\ 0 & 1 & 1\\ \end{bmatrix}$ has rank 2: the first two columns are linearly independent, so the rank is at least 2, but since the third is a linear combination of the first two, the three columns are linearly dependent so the rank must be less than 3.

How to compute rank of matrix:

\text{Given a mtrix}\,A = \begin{bmatrix} 1 & 2 & 1 & 1 \\ -2 & -3 & 1 & 1 \\ 3 & 5 & 0 & 0 \end{bmatrix} \xrightarrow{2R_1 + R_2 \to R_2} \begin{bmatrix} 1 & 2 & 1 & 1 \\ 0 & 1 & 3 & 3 \\ 3 & 5 & 0 & 0 \end{bmatrix} \xrightarrow{-3R_1 + R_3 \to R_3} \begin{bmatrix} 1 & 2 & 1 & 1 \\ 0 & 1 & 3 & 3 \\ 0 & -1 & -3 & -3 \end{bmatrix} \xrightarrow{R_2 + R_3 \to R_3} \begin{bmatrix} 1 & 2 & 1 & 1 \\ 0 & 1 & 3 & 3 \\ 0 & 0 & 0 & 0 \end{bmatrix} \xrightarrow{-2R_2 + R_1 \to R_1} \begin{bmatrix} 1 & 0 & -5 & -5 \\ 0 & 1 & 3 & 3 \\ 0 & 0 & 0 & 0 \end{bmatrix}

The final matrix (in reduced row echelon form) has two non-zero rows and thus the rank of matrix $A$ is 2.

Norm is used to measure the size of matrix.

L^p

norm:

\left\|x\right\|_p = (\sum_i |x_i|^p)^{\frac{1}{p}}

, for

p \in \mathbb{R}, p\geq 1

. There are some usual used norms:

Euclidean Norm (

L^2

\left\|x\right\|_2

or simply denote as

\left\|x\right\|

, genrally known as default ‘distance’ in geometry.

L^1

norm:

\left\|x\right\|_1 = \sum_i |x_i|

. commonly used in machine learning.

Max Norm (

L^\infin

\left\|x\right\|_\infin = \max_i |x_i|

Special matrices

Symmetric matrix:

A = A^T

Unit Vector is the vector with unit norm:

\left\|x\right\|_2 = 1

Orthogonal:

x^Ty = 0

x

and

y

are orthogonal vectors;

AA^T = A^TA = I

, the

A

is an orthogonal matrix, also

\Rightarrow A^{-1} = A^T

. Their inverse is very cheap & easy to compute.

e.g., $A = \displaystyle\frac{1}{7}\begin{bmatrix} 3 & 2 & 6 \\ -6 & 3 & 2 \\ 2 & 6 & -3 \end{bmatrix} \Rightarrow A^T = \displaystyle\frac{1}{7}\begin{bmatrix} 3 & -6 & 2 \\ 2 & 3 & 6 \\ 6 & 2 & -3 \end{bmatrix} \Rightarrow AA^T = \displaystyle\frac{1}{49}\begin{bmatrix} 49 & 0 & 0 \\ 0 & 49 & 0 \\ 0 & 0 & 49 \end{bmatrix} = \begin{bmatrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \end{bmatrix} = I \Rightarrow A \text{ is an Orthogonal matrix.}$

Decompositions

Both Eigendecomposition and Singular Value Deconposition are used in Principal Component Analysis (PCA) algorithm.

Eigenvalues and Eigenvectors

For a square matrix

A \in \mathbb{R}^{n\times n}

, a non-zero vector

v

is an Eigenvector if

Av = \lambda v

for some scalar

\lambda

. Here

\lambda

is called the eigenvalue corresponding to

v

To determine the eigenvalues of $A$ , solve the characteristic equation: $det(A−λI)=0$ , and eugenvector by solving $(A - \lambda I)v = 0$ .

Eigendecomposition

Assuming $A$ has $n$ linearly independent eigenvectors $\left\{v^{(1)}, \dots,v^{(n)} \right\}$ with correspounding eigenvalues $\left\{\lambda^{(1)}, \dots,\lambda^{(n)} \right\}$ , given $V = [v^{(1)}, \dots,v^{(n)} ]$ and $\lambda = [\lambda^{(1)}, \dots,\lambda^{(n)}]^T$ , the eigendecomposition of $A$ is then:

A = V \operatorname{diag}(\lambda) V^{-1}

For Symmetric Matrices,

A = Q\Lambda Q^T

where $Q$ is an Orthogonal matrix composed of eigenvector of A and $\Lambda$ is a diagonal matrix of eigenvalues. Geometrically, scaling space $A$ can be decomposit as $\lambda_i \in \Lambda$ (length) in direction $v^{(i)} \in Q$ .

🤖: The technic can be used in 🧠 PCA by Correlated matrix Eigendecomposition

Singular Value Decomposition (SVD)

Singular value decomposition is a fundamental matrix factorization. It states that any real $m\times n$ matrix $A$ can be factored as:

A = U\,\Sigma\,V^T

V

is an

n\times n

orthogonal matrix, rotation or reflection;

\Sigma

is an

m\times n

diagonal matrix (nonnegative), scales the axes by the singular values;

U

is an

m\times m

orthogonal matrix, second rotation or reflection.

The diagonal entries $\sigma_1,\sigma_2,\dots$ of $\Sigma$ are the singular values of $A$ . They are conventionally ordered $\sigma_1 \ge \sigma_2 \ge \cdots \ge 0$ .

SVD says that $A$ = (orthogonal rotation/reflection) $\times$ (scaling) $\times$ (orthogonal rotation/reflection).

🧠 How to compute SVD:

The folowing algorithm is mathematically valid, but in practice, this simple method can lead to numerical instability and increased computational complexity.