# Matrix Factorization

## Gaussian Elimination

• 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.

## LU Decomposition

• #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.

## Cholesky Decomposition

• #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$.

## QR Decomposition

• #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.

## Eigen Decomposition

• #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.

## Singular Value Decomposition

• #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.

## Polar Decomposition

• #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.

## Comparison in Eigen library

DecompositionRequirementsSpeed (small-to-medium)Speed (large)Accuracy

Positive definite

+++

+++

+

Positive or negative semidefinite

+++

+

++

Invertible

++

++

+

None

-

- -

+++

None

++

++

+

None

+

-

+++

None

-

- -

+++

None

+

-

+++

None

-

-

+++

None

-

- - -

+++

## References

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

Last updated