Partitioned matrices

For many problems in applied linear algebra, it is useful to adopt the perspective of a matrix as being a concatenation of column vectors. For example, when solving the linear system ${\displaystyle x=A^{-1}b}$, rather than understanding x as the product of ${\displaystyle A^{-1}}$ with b, it is helpful to think of x as the vector of coefficients in the linear expansion of b in the basis formed by the columns of A.^[1]: 8 Thinking of matrices as a concatenation of columns is also a practical approach for the purposes of matrix algorithms. This is because matrix algorithms frequently contain two nested loops: one over the columns of a matrix A, and another over the rows of A. For example, for matrices ${\displaystyle A^{m\times n}}$ and vectors ${\displaystyle x^{n\times 1}}$ and ${\displaystyle y^{m\times 1}}$, we could use the column partitioning perspective to compute y := Ax + y as

for q = 1:n
  for p = 1:m
    y(p) = A(p,q)*x(q) + y(p)
  end
end

Singular value decomposition

The singular value decomposition of a matrix ${\displaystyle A^{m\times n}}$ is ${\displaystyle A=U\Sigma V^{\ast }}$ where U and V are unitary, and ${\displaystyle \Sigma }$ is diagonal. The diagonal entries of ${\displaystyle \Sigma }$ are called the singular values of A. Because singular values are the square roots of the eigenvalues of ${\displaystyle AA^{\ast }}$, there is a tight connection between the singular value decomposition and eigenvalue decompositions. This means that most methods for computing the singular value decomposition are similar to eigenvalue methods;^[1]: 36 perhaps the most common method involves Householder procedures.^[1]: 253

QR factorization

The QR factorization of a matrix ${\displaystyle A^{m\times n}}$ is a matrix ${\displaystyle Q^{m\times m}}$ and a matrix ${\displaystyle R^{m\times n}}$ so that A = QR, where Q is orthogonal and R is upper triangular.^{[1]: 50 [4]: 223} The two main algorithms for computing QR factorizations are the Gram–Schmidt process and the Householder transformation. The QR factorization is often used to solve linear least-squares problems, and eigenvalue problems (by way of the iterative QR algorithm).

LU factorization

An LU factorization of a matrix A consists of a lower triangular matrix L and an upper triangular matrix U so that A = LU. The matrix U is found by an upper triangularization procedure which involves left-multiplying A by a series of matrices ${\displaystyle M_{1},\ldots ,M_{n-1}}$ to form the product ${\displaystyle M_{n-1}\cdots M_{1}A=U}$, so that equivalently ${\displaystyle L=M_{1}^{-1}\cdots M_{n-1}^{-1}}$.^{[1]: 147 [4]: 96}

Eigenvalue decomposition

The eigenvalue decomposition of a matrix ${\displaystyle A^{m\times m}}$ is ${\displaystyle A=X\Lambda X^{-1}}$, where the columns of X are the eigenvectors of A, and ${\displaystyle \Lambda }$ is a diagonal matrix the diagonal entries of which are the corresponding eigenvalues of A.^[1]: 33 There is no direct method for finding the eigenvalue decomposition of an arbitrary matrix. Because it is not possible to write a program that finds the exact roots of an arbitrary polynomial in finite time, any general eigenvalue solver must necessarily be iterative.^[1]: 192

Gaussian elimination

From the numerical linear algebra perspective, Gaussian elimination is a procedure for factoring a matrix A into its LU factorization, which Gaussian elimination accomplishes by left-multiplying A by a succession of matrices ${\displaystyle L_{m-1}\cdots L_{2}L_{1}A=U}$ until U is upper triangular and L is lower triangular, where ${\displaystyle L\equiv L_{1}^{-1}L_{2}^{-1}\cdots L_{m-1}^{-1}}$.^[1]: 148 Naive programs for Gaussian elimination are notoriously highly unstable, and produce huge errors when applied to matrices with many significant digits.^[2] The simplest solution is to introduce pivoting, which produces a modified Gaussian elimination algorithm that is stable.^[1]: 151

Solutions of linear systems

Numerical linear algebra characteristically approaches matrices as a concatenation of columns vectors. In order to solve the linear system ${\displaystyle x=A^{-1}b}$, the traditional algebraic approach is to understand x as the product of ${\displaystyle A^{-1}}$ with b. Numerical linear algebra instead interprets x as the vector of coefficients of the linear expansion of b in the basis formed by the columns of A.^[1]: 8

Many different decompositions can be used to solve the linear problem, depending on the characteristics of the matrix A and the vectors x and b, which may make one factorization much easier to obtain than others. If A = QR is a QR factorization of A, then equivalently ${\displaystyle Rx=Q^{\ast }b}$. This is as easy to compute as a matrix factorization.^[1]: 54 If ${\displaystyle A=X\Lambda X^{-1}}$ is an eigendecomposition A, and we seek to find b so that b = Ax, with ${\displaystyle b'=X^{-1}b}$ and ${\displaystyle x'=X^{-1}x}$, then we have ${\displaystyle b'=\Lambda x'}$.^[1]: 33 This is closely related to the solution to the linear system using the singular value decomposition, because singular values of a matrix are the absolute values of its eigenvalues, which are also equivalent to the square roots of the absolute values of the eigenvalues of the Gram matrix ${\displaystyle X^{*}X}$. And if A = LU is an LU factorization of A, then Ax = b can be solved using the triangular matrices Ly = b and Ux = y.^{[1]: 147 [4]: 99}

Least squares optimisation

Matrix decompositions suggest a number of ways to solve the linear system r = b − Ax where we seek to minimize r, as in the regression problem. The QR algorithm solves this problem by computing the reduced QR factorization of A and rearranging to obtain ${\displaystyle {\widehat {R}}x={\widehat {Q}}^{\ast }b}$. This upper triangular system can then be solved for x. The SVD also suggests an algorithm for obtaining linear least squares. By computing the reduced SVD decomposition ${\displaystyle A={\widehat {U}}{\widehat {\Sigma }}V^{\ast }}$ and then computing the vector ${\displaystyle {\widehat {U}}^{\ast }b}$, we reduce the least squares problem to a simple diagonal system.^[1]: 84 The fact that least squares solutions can be produced by the QR and SVD factorizations means that, in addition to the classical normal equations method for solving least squares problems, these problems can also be solved by methods that include the Gram-Schmidt algorithm and Householder methods.