Linear algebraic equations have numerous applications virtually everywhere. One of the efficient ways to solve a system of linear equations Ax=b (where A is a matrix, x is the solution (column), b is the right-hand-side (also a column)) is to transform it into a triangular system, Ty=c, where T is a triangular matrix. A triangular system can be easily solved by backsubstitution.

Back-substitution is a method to solve an upper-triangular linear system Ty=c with one run:

for(i = n; i>=1; i--) { yi = (ci - ∑k=i+1,m Ti,k yk)/Ti,i }

LU decomposition is a decomposition, of a matrix A into a product of a lower triangular matrix L and an upper triangular matrix U, A = LU. The equation Ax=b, ie LUx=b, can then be solved by first solving for Ly=b and then for Ux=y by two runs of backward and forward substitutions.

QR decomposition. A rectangular n-by-m matrix A has a QR decomposition, A = Q R, into the product of an orthogonal n-by-m matrix Q, Q^TQ = 1, and an m-by-m right-triangular matrix R. This decomposition can be used to convert the linear system A x = b into the triangular system R x = Q^T b, which can be solved by back-substitution. QR decomposition can be also used for for linear least-squares fits and diagonalization of matrices.

Gram-Schmidt orthogonalization is a method to perform QR decomposition of a matrix A by orthogonalization of its column-vectors a⁽ⁱ⁾:

do i=1:m
	Ri,i=√[a(i)⋅a(i)]; q(i)=a(i)/Ri,i  //normalization
	do j=i+1:m 
		Ri,j=q(i)⋅a(j); a(j)=a(j)-q(i)Ri,j  //orthogonalization

Determinant of a triangular matrix is a product of its diagonal elements.

Matrix inverse can be calculated by solving n linear equations Axⁱ=bⁱ, i=1..n, where bⁱ is a column with all elements equal zero except for the element number i which is equal one. The matrix made of columns xⁱ is apparently the inverse of A.

Problems

1. QR decomposition by a modified Gram-Schmidt method.
2. QR back-substitution.
3. Matrix inverse.
4. Non-obligatory: LU decomposition.