Comment on page

# Matrix Factorization

- Gaussian elimination involves three types of elementary row operations:
- Swapping two rows (also known as a row exchange),
- Multiplying a row by a nonzero number,
- Adding a multiple of one row to another row.

- Gaussian elimination reduces A to
**row echelon form**in general, whereas #4 reduces A to the**reduced row echelon form (rref)**, which further requires 1) the leading entry (pivot) in each nonzero row is 1, and 2) each column containing a pivot has all other entries equal to zero.

- #1, #2 and #3 are three variants of LU decomposition.
- #1 and #2 are the simple/basic forms of LU decomposition, which use only the second and third types of row operations in Gaussian elimination. No row exchanges.
- #3 is known as the LU decomposition
**with partial pivoting**(or PLU decomposition), where row exchanges are necessary and represented by a permutation matrix P. - There exists the fourth variant of LU decomposition, where column permutations are also necessary and represented by a permutation matrix Q. The decomposition becomes PAQ = LU, and is known as LU factorization
**with full pivoting**. - It is typically required that A be a square matrix, but it is possible to generalize LU decomposition to rectangular matrices.
- LU decomposition can be viewed as the matrix form of Gaussian elimination. It is often used to solve square systems of linear equations, and serves as a key step when inverting a matrix or computing the determinant of a matrix.

- #5 is the standard form of Cholesky decomposition, which is a special case of LU decomposition where matrices are symmetric and positive-definite.
- This is also known as
**LLT decomposition**, since we can replace the notation C with L and denote$A = LL^{\text{T}}$. This expression is not recommended as it can confuse the reader on the meaning of notation L.

- In practice, we often perform$A = LDL^{\text{T}}$(as mentioned in #2) to avoid extracting square roots as required in$C = L\sqrt{D}$. This is often known as
**LDL decomposition**,**LDLT decomposition**, or square-root-free Cholesky decomposition. - If matrices are not positive-definite, LDLT decomposition can still be performed, but requires
**pivoting**(as discussed previously in LU decomposition) to ensure numerical stability. The decomposition becomes$A = P^{\text{T}}LDL^{\text{T}}P$.

- #6 is the standard form of QR decomposition. The only requirement is that A has independent columns.
- There are three implementations of QR decomposition: Gram–Schmidt process, Givens rotation matrices, Householder transformation (reflection operation).
- If pivoting is necessary (for numerical stability), the decomposition becomes$PAP'=QR$, where P and P' are permutation matrices for row and column, respectively.
- QR decomposition is often used to solve the linear least squares problem and is the basis for a particular eigenvalue algorithm, the QR algorithm.

- #7 is the standard form of Eigendecomposition. The requirement is that A is
**diagonalizable**or**non-defective**, or equivalently A is a square matrix with n linearly independent eigenvectors.- Diagonalizability of A depends on
**enough eigenvectors**, whereas the invertibility of A depends on**nonzero eigenvalues**. There is no connection between the two. - Diagonalization can fail only if there are repeated eigenvalues. In this case, some of the eigenvectors may be linearly dependent on others.

- #8 is a special case of Eigendecomposition, where A is a real symmetric matrix.
- When the matrix being factorized is a normal or real symmetric matrix, the decomposition is also known as
**spectral decomposition**, derived from the spectral theorem. - Every real symmetric matrix is a normal matrix.

- Useful facts:
- The product of the eigenvalues is equal to the determinant of A.
- The sum of the eigenvalues is equal to the trace of A.
- The eigenvectors of A^-1 are the same as the eigenvectors of A.
- The statement "A can be eigendecomposed" does not imply that A has an inverse. A can be inverted if and only if all eigenvalues are nonzero.
- The statement "A has an inverse" does not imply that A can be eigendecomposed. The counterexample is [1 1; 0 1], which is an invertible defective matrix.

- #10 is the standard form of Singular Value Decomposition (SVD), which generalizes the eigendecomposition of a square matrix to any m-by-n matrix.
- Intuitively, the SVD decomposition breaks down a linear transformation of R^n into a composition of three geometrical transformations: a rotation or reflection (V), followed by a coordinate-by-coordinate scaling (Sigma), followed by another rotation or reflection (U).
- Examples on the relation between SVD and eigendecomposition.
- For a real symmetric square matrix, the singular values are the absolute values of the eigenvalues.
- For matrix A = [1 0 1; 0 1 1; 0 0 0], the eigenvalues of A are 1, 1, 0, whereas the singular values of A are sqrt(3), 1, 0.
- For matrix A = [1 1; 0 0], the eigenvalues are 1 and 0; the singular values are sqrt(2) and 0.

- #12 is the standard form of Polar decomposition.
- In general, the polar decomposition of a square matrix A always exists. If A is invertible, the decomposition is unique, and the factor H will be positive-definite.
- Intuitively, if a real n-by-n matrix A is interpreted as a linear transformation of n-dimensional space R^n, the polar decomposition separates it into a rotation or reflection U of R^n, and a scaling of the space along a set of n orthogonal axes.
- This decomposition is useful in computing the fundamental group of (matrix) Lie groups.

Decomposition | Requirements | Speed (small-to-medium) | Speed (large) | Accuracy |
---|---|---|---|---|

Positive definite | +++ | +++ | + | |

Positive or negative
semidefinite | +++ | + | ++ | |

Invertible | ++ | ++ | + | |

None | - | - - | +++ | |

None | ++ | ++ | + | |

None | + | - | +++ | |

None | - | - - | +++ | |

None | + | - | +++ | |

None | - | - | +++ | |

None | - | - - - | +++ |

- Appendix C in the textbook "Linear algebra and its applications", Gilbert Strang

Last modified 5mo ago