Matrix Decompositions

Diagonalizable Matrices

$A$ is diagonalizable if and only if it has linearly independent eigenvectors, or equivalently, if the geometric multiplicity and the algebraic multiplicity of all the eigenvalues agree. A special case of this is if $A$ has $n$ distinct eigenvalues. Suppose we have eigenvalues $\lambda_1, \dots, \lambda_n$ and corresponding eigenvectors $v_1, \dots, v_n$ . Then

A = XDX^{-1}, \quad X = \begin{bmatrix} v_1 & \dots & v_n \end{bmatrix}, \quad D = \begin{bmatrix} \lambda_1 & & 0 \\ & \ddots & \\ 0 & & \lambda_n \end{bmatrix}

Intuitively, this says that we can find a basis consisting of the eigenvectors of $A$ . Useful for computing large powers of $A$ , as $A^n = XD^n X^{-1}$ . An important example is $A$ being real and symmetric implies $A$ is diagonalizable.

Singular Value Decomposition

SVD is powerful in low-rank approximations of matrices. Unlike eigenvalue decomposition, SVD uses two unique bases (left/right singular vectors). For orthogonal matrices $U (m \times m), V (n \times n)$ and diagonal matrix $\Sigma (m \times n)$ with nonnegative diagonal entries in nonincreasing order, we can write any $m \times n$ matrix $A$ as:

A = U\Sigma V^\intercal

Intuitively, this says that we can express $A$ as a diagonal matrix with suitable choices of (orthogonal) bases.

QR Decomposition

For nonsingular $A$ , we can write $A = QR$ , where $Q$ is orthogonal and $R$ is an upper triangular matrix with positive diagonal elements. QR decomposition assists in increasing the efficiency of solving $Ax = b$ for nonsingular $A$ :

Ax = b \implies QRx = b \implies Rx = Q^{-1}b = Q^\intercal b

QR decomposition is very useful in efficiently solving large numerical systems and inversion of matrices. Furthermore, it is also used in least-squares when our data is not full rank.

LU and Cholesky Decompositions

For nonsingular $A$ , we can write $A = LU$ , where $L$ is a lower and $U$ is an upper triangular matrix. This decomposition assists in solving $Ax = b$ as well as computing the determinant:

\det(A) = \det(L)\det(U) = \prod_{i=1}^n L_{ii} \prod_{j=1}^n U_{jj}

If $A$ is symmetric positive definite, then $A$ can be expressed as $A = R^\intercal R$ via Cholesky decomposition, where $R$ is an upper triangular matrix with positive diagonal entries. Cholesky decomposition is essentially LU decomposition with $L = U^\intercal$ . These decompositions are both useful for solving large linear systems.

Projections

Fix a vector $v \in \mathbb{R}^n$ . The projection of $x \in \mathbb{R}^n$ onto $v$ is given by

\text{proj}_v(x) = P_v x = \frac{vv^\intercal}{\|v\|^2}x = \frac{x \cdot v}{\|v\|^2}v

More generally, if $S = \text{Span}\{v_1, \dots, v_k\} \subseteq \mathbb{R}^n$ has orthogonal basis $\{v_1, \dots, v_k\}$ , then the projection of $x \in \mathbb{R}^n$ onto $S$ is given by

\text{proj}_S(x) = \sum_{i=1}^k \frac{x \cdot v_i}{\|v_i\|^2}v_i