33.2: Decompositions

Image from: Wikipedia

In numerical linear algebra, we factorize matrices to facilitate efficient and/or accurate computations (they are also helpful in proofs). There are many possible matrix decompositions. Some, e.g., the eigendecomposition, require the matrix to be square, while others, e.g., the \(QR\) factorization, exist for arbitrary matrices. Among all possible decompositions (also called factorizations), some common examples include:

• QR Factorization from Gram-Schmidt orthogonization:
  • \(A = QR\)
  • \(Q\) has orthonormal columns and \(R\) is a upper-triangular matrix
  • If there are zero rows in \(R\), we can reduce the number of columns in \(Q\)
  • Exists for arbitrary matrices

• LU / LDU Decomposition from Gauss Elimination:
  • \(A=LU\) or \(A=LDU\)
  • \(L\) is lower-triangular, \(U\) is upper-triangular, and \(D\) is diagonal
  • Exists for all square matrices
  • Is related to Gaussian Elimination
• Cholesky Decomposition:
  • \(A=R^{T}R \quad (=LDL^{T})\)
  • \(R\) is upper-triangular
  • Factorization of \(A\) into \(R^{T}R\) requires \(A\) be symmetric and positive-definite. The latter simply requires \(x^{T}Ax>0\) for every \(x \in \mathbb{R}^n\). Note that \(x^{T}Ax\) is always a scalar value (e.g., note that \(x^TA = y^T\) for some vector \(y\in\mathbb{R}^n\), and \(y^Tx\) is the dot product between \(x\) and \(y\) and, hence, a real scalar).
• Schur Decomposition:
  • \(A = UTU^{T}\)
  • \(U\) is orthogonal and \(T\) is upper-triangular
  • Exists for every square matrix and says every such matrix, \(A\), is unitarily equivalent to an upper-triangular matrix, \(T\) (i.e., there exists an orthonomal basis with respect to which \(A\) is upper-triangular)
  • Eigenvalues on diagonal of \(T\)
• Singular Value Decomposition:
  • \(A = U\Sigma V^{T}\)
  • \(U\) is orthogonal, \(V\) is orthogonal, and \(\Sigma\) is diagonal
  • Exists for arbitrary matrices
• Eigenvalue Decomposition:
  • \(A = X\Lambda X^{-1}\)
  • \(X\) is invertible and \(\Lambda\) is diagonal
  • Exists for square matrices with linearly independent columns (e.g., full rank)
  • Also called the eigendecomposition

Question

What decompositions have we covered in the class so far and how did we use them?