- Elementary Row Operations
- Elementary Matrix
There are three types of elementary matrices, which correspond to three types of row operations (respectively, column operations):
- Row Switching
- Row Multiplication
- Row Addition
An square matrix is called an elementary matrix if it can be obtained from an identity matrix of the same size by performing a single elementary row operation.
If E is an elementary matrix, to apply the elementary row operation to a matrix A, one multiplies A by the elementary matrix on the left (right for column operations). The elementary matrix for any row operation is obtained by executing the operation on the identity matrix.
import numpy as np
- How to tell if a matrix is invertible
- How to find the inverse
For any square matrix A, if there exist a matrix B of the same size such that
$$ AB = BA = I $$
then A is said to be invertible and B is called an inverse of A.
If no such B can be found, then A is said to be singular.
Note: all elementary matrices are invertible
A matrix A is invertible if and only if A can be expressed as the product of elementary matrices.
Or, refering to Elementary Linear Algebra with Applications by Howard Anton
, if A is an n by n matrix, then the following statements are equivalent, that is, all true or all false:
- A is invertible
- Ax=0 has only the trivial solution
- The reduced row echelon form of A is an identity matrix
- A is expressible as a product of elementary matrices
In practice, we decides the invertibility of a square matrix by computing its determinant, i.e.,
A square matrix A is invertible if and only if $ det(A) != 0$
Over the year, many methods have been develop to find the inverse of a square matrix. Here I only list a few. For more information, see the wikipage
- Gaussian elimination
- Analytic solution
Finds the inverse of a matrix by decomposing a matix into products of elementary matrices. See here for details.
The computational complexity of the method is $ O(n^3) $. See here for details.