In linear algebra, an n-by-n (square) matrix A is called invertible or non-singular if there exists an n-by-n matrix B such that Linear algebra is the branch of mathematics concerned with the study of vectors, vector spaces (also called linear spaces), linear maps (also called linear transformations), and systems of linear equations. ... In mathematics, a matrix (plural matrices) is a rectangular table of elements (or entries), which may be numbers or, more generally, any abstract quantities that can be added and multiplied. ...

where I_n denotes the n-by-n identity matrix and the multiplication used is ordinary matrix multiplication. If this is the case, then the matrix B is uniquely determined by A and is called the inverse of A, denoted by A^-1. It follows from the theory of matrices that if In linear algebra, the identity matrix of size n is the n-by-n square matrix with ones on the main diagonal and zeros elsewhere. ... This article gives an overview of the various ways to perform matrix multiplication. ...

for square matrices A and B, then also

While the most common case is that of matrices over the real or complex numbers, all these definitions can be given for matrices over any ring. In mathematics, the real numbers may be described informally as numbers that can be given by an infinite decimal representation, such as 2. ... In mathematics, a complex number is a number of the form where a and b are real numbers, and i is the imaginary unit, with the property i 2 = −1. ... In mathematics, a ring is an algebraic structure in which addition and multiplication are defined and have properties listed below. ...

A square matrix that is not invertible is called singular or degenerate. A square matrix is singular if and only if its determinant is 0. In algebra, a determinant is a function depending on n that associates a scalar, det(A), to every n×n square matrix A. The fundamental geometric meaning of a determinant is as the scale factor for volume when A is regarded as a linear transformation. ...

Over the field of real numbers, the set of singular n-by-n matrices, considered as a subset of , is a null set, i.e., has Lebesgue measure zero. (This is true because singular matrices can be thought of as the roots of the polynomial function given by the determinant.) This can be interpreted as saying that almost all n-by-n matrices are invertible. Intuitively, this means that if you pick a random square matrix over the reals, the probability that it will be singular is zero. In practice however, one may encounter non-invertible matrices. And in numerical calculations, matrices which are invertible, but close to a non-invertible matrix, can still be problematic; such matrices are said to be ill conditioned. In measure theory, a null set is a set that is negligible for the purposes of the measure in question. ... In mathematics, the Lebesgue measure is the standard way of assigning a length, area or volume to subsets of Euclidean space. ... Let μ be a measure on a sigma algebra Σ of subsets of a set X. An element A in Σ is said to have measure zero if μ(A)=0. ... In algebra, a determinant is a function depending on n that associates a scalar, det(A), to every n×n square matrix A. The fundamental geometric meaning of a determinant is as the scale factor for volume when A is regarded as a linear transformation. ... Probability is the likelihood that something is the case or will happen. ... Numerical analysis is the study of approximate methods for the problems of continuous mathematics (as distinguished from discrete mathematics). ... In numerical analysis, the condition number associated with a numerical problem is a measure of that quantitys amenability to digital computation, that is, how well-posed the problem is. ...

Matrix inversion is the process of finding the matrix B that satisfies the prior equation for a given invertible matrix A.

Properties of invertible matrices

Let A be a square n by n matrix over a field K (for example the field R of real numbers). Then the following statements are equivalent: In abstract algebra, a field is an algebraic structure in which the operations of addition, subtraction, multiplication and division (except division by zero) may be performed, and the same rules hold which are familiar from the arithmetic of ordinary numbers. ...

• A is invertible.
• A is row-equivalent to the n-by-n identity matrix I_n.
• A is column-equivalent to the n-by-n identity matrix I_n.
• A has n pivot positions.
• det A ≠ 0.
• rank A = n.
• The equation Ax = 0 has only the trivial solution x = 0 (i.e., Null A = {0})
• The equation Ax = b has exactly one solution for each b in Kⁿ.
• The columns of A are linearly independent.
• The columns of A span Kⁿ (i.e. Col A = Kⁿ).
• The columns of A form a basis of Kⁿ.
• The linear transformation mapping x to Ax is a bijection from Kⁿ to Kⁿ.
• There is an n by n matrix B such that AB = I_n.
• The transpose A^T is an invertible matrix.
• The matrix times its transpose, A^T × A is an invertible matrix.
• The number 0 is not an eigenvalue of A.

In general, a square matrix over a commutative ring is invertible if and only if its determinant is a unit in that ring. In mathematics, Gaussian elimination or Gauss-Jordan elimination, named after Carl Friedrich Gauss and Wilhelm Jordan, is an algorithm in linear algebra for determining the solutions of a system of linear equations, for determining the rank of a matrix, and for calculating the inverse of an invertible square matrix. ... In linear algebra, the identity matrix of size n is the n-by-n square matrix with ones on the main diagonal and zeros elsewhere. ... In mathematics, Gaussian elimination or Gauss-Jordan elimination, named after Carl Friedrich Gauss and Wilhelm Jordan, is an algorithm in linear algebra for determining the solutions of a system of linear equations, for determining the rank of a matrix, and for calculating the inverse of an invertible square matrix. ... In linear algebra, the identity matrix of size n is the n-by-n square matrix with ones on the main diagonal and zeros elsewhere. ... In algebra, a determinant is a function depending on n that associates a scalar, det(A), to every n×n square matrix A. The fundamental geometric meaning of a determinant is as the scale factor for volume when A is regarded as a linear transformation. ... In linear algebra, the column rank (row rank respectively) of a matrix A with entries in some field is defined to be the maximal number of columns (rows respectively) of A which are linearly independent. ... In mathematics, the null space (also nullspace) of an operator A is the set of all operands v which solve the equation Av = 0. ... In linear algebra, a family of vectors is linearly independent if none of them can be written as a linear combination of finitely many other vectors in the collection. ... In mathematics, a subset B of a vector space V is said to be a basis of V if it satisfies one of the four equivalent conditions: B is both a set of linearly independent vectors and a generating set of V. B is a minimal generating set of V... A bijective function. ... In linear algebra, the transpose of a matrix A is another matrix AT (also written Atr, tA, or A′) created by any one of the following equivalent actions: write the rows of A as the columns of AT write the columns of A as the rows of AT reflect A... In mathematics, a number is called an eigenvalue of a matrix if there exists a nonzero vector such that the matrix times the vector is equal to the same vector multiplied by the eigenvalue. ... In ring theory, a branch of abstract algebra, a commutative ring is a ring in which the multiplication operation obeys the commutative law. ... In algebra, a determinant is a function depending on n that associates a scalar, det(A), to every n×n square matrix A. The fundamental geometric meaning of a determinant is as the scale factor for volume when A is regarded as a linear transformation. ... In mathematics, a unit in a ring R is an element u such that there is v in R with uv = vu = 1R. That is, u is an invertible element of the multiplicative monoid of R. The units of R form a group U(R) under multiplication, the group of...

The inverse of an invertible matrix A is itself invertible, with

.

The inverse of an invertible matrix A multiplied by a non-zero scalar k yields the product of the inverse of both the matrix and the scalar

.

For an invertible matrix A, the transpose of the inverse is the inverse of the transpose:

The product of two invertible matrices A and B of the same size is again invertible, with the inverse given by

(note that the order of the factors is reversed.) As a consequence, the set of invertible n-by-n matrices forms a group, known as the general linear group Gl(n). This picture illustrates how the hours on a clock form a group under modular addition. ... In mathematics, the general linear group of degree n is the set of n×n invertible matrices, together with the operation of ordinary matrix multiplication. ...

Proof for matrix product rule

If A₁, A₂, ..., A_n are nonsingular square matrices over a field, then

It becomes evident why this is the case if one attempts to find an inverse for the product of the A_is from first principles, that is, that we wish to determine B such that

where B is the inverse matrix of the product. To remove A₁ from the product, we can then write

which would reduce the equation to

Likewise, then, from

which simplifies to

If one repeat the process up to A_n, the equation becomes

but B is the inverse matrix, i.e. so the property is established.

Methods of matrix inversion

Gaussian elimination

Gaussian elimination is an algorithm that can be used to determine whether a given matrix is invertible and to find the inverse. An alternative is the LU decomposition which generates an upper and a lower triangular matrices which are easier to invert. For special purposes, it may be convenient to invert matrices by treating mn-by-mn matrices as m-by-m matrices of n-by-n matrices, and applying one or another formula recursively (other sized matrices can be padded out with dummy rows and columns). For other purposes, a variant of Newton's method may be convenient (particularly when dealing with families of related matrices, so inverses of earlier matrices can be used to seed generating inverses of later matrices). In mathematics, Gaussian elimination (not to be confused with Gauss–Jordan elimination), named after Carl Friedrich Gauss, is an algorithm in linear algebra for determining the solutions of a system of linear equations, for determining the rank of a matrix, and for calculating the inverse of an invertible square matrix. ... In mathematics, computing, linguistics, and related disciplines, an algorithm is a finite list of well-defined instructions for accomplishing some task that, given an initial state, will terminate in a defined end-state. ... In linear algebra, the LU decomposition is a matrix decomposition which writes a matrix as the product of a lower and upper triangular matrix. ... In numerical analysis, Newtons method (also known as the Newton–Raphson method or the Newton–Fourier method) is an efficient algorithm for finding approximations to the zeros (or roots) of a real-valued function. ...

Analytic solution

Writing another special matrix of cofactors, known as an adjugate matrix, can also be an efficient way to calculate the inverse of small matrices, but this recursive method is inefficient for large matrices. To determine the inverse, we calculate a matrix of cofactors: In linear algebra, a minor of a matrix is the determinant of a certain smaller matrix. ... In linear algebra, the adjugate or classical adjoint of a square matrix is a matrix which plays a role similar to the inverse of a matrix; it can however be defined for any square matrix without the need to perform any divisions. ...

where |A| is the determinant of A, C_ij is the matrix cofactor, and A^T represents the matrix transpose. In algebra, a determinant is a function depending on n that associates a scalar, det(A), to every n×n square matrix A. The fundamental geometric meaning of a determinant is as the scale factor for volume when A is regarded as a linear transformation. ... In linear algebra, a minor of a matrix is the determinant of a certain smaller matrix. ... In linear algebra, the transpose of a matrix A is another matrix AT (also written Atr, tA, or A′) created by any one of the following equivalent actions: write the rows of A as the columns of AT write the columns of A as the rows of AT reflect A...

For most practical applications, it is not necessary to invert a matrix to solve a system of linear equations; however, for a unique solution, it is necessary that the matrix involved be invertible. In mathematics and linear algebra, a system of linear equations is a set of linear equations such as A standard problem is to decide if any assignment of values for the unknowns can satisfy all three equations simultaneously, and to find such an assignment if it exists. ...

Decomposition techniques like LU decomposition, are much faster than inversion, and various fast algorithms for special classes of linear systems have also been developed. In linear algebra, the LU decomposition is a matrix decomposition which writes a matrix as the product of a lower and upper triangular matrix. ...

Inversion of 2×2 matrices

The cofactor equation listed above yields the following result for 2×2 matrices. Inversion of these matrices can be done easily as follows: ^[1]

Blockwise inversion

Matrices can also be inverted blockwise by using the following analytic inversion formula:

where A, B, C and D are matrix sub-blocks of arbitrary size. This strategy is particularly advantageous if A is diagonal and D−CA^-1B (the Schur complement of A) is a small matrix, since they are the only matrices requiring inversion. This technique was invented by Volker Strassen, who also invented the Strassen algorithm for fast(er) matrix multiplication. In the mathematical discipline of matrix theory, a block matrix or a partitioned matrix is a partition of a matrix into rectangular smaller matrices called blocks. ... In linear algebra and the theory of matrices, the Schur complement (named after Issai Schur) of a block of a matrix within the larger matrix is defined as follows. ... Volker Strassen is a German mathematician. ... In the mathematical discipline of linear algebra, the Strassen algorithm, named after Volker Strassen, is an algorithm used for matrix multiplication. ... This article gives an overview of the various ways to perform matrix multiplication. ...

The inversion procedure that led to Equation (1) performed matrix block operations that operated on C and D first. Instead, if A and B are operated on first, the result is

Equating Equations (1) and (2) leads to

where Equation (3) is the matrix inversion lemma, which is equivalent to the binomial inverse theorem. In mathematics (specifically linear algebra), the Woodbury matrix identity says that the inverse of a rank-k correction of some matrix can be computed by doing a rank-k correction to the inverse of the original matrix. ... In mathematics, the binomial inverse theorem is useful for expressing matrix inverses in different ways. ...

Proof (slightly different than the binomial inverse theorem proof, but more intuitive) In mathematics, the binomial inverse theorem is useful for expressing matrix inverses in different ways. ...

First, multiply the RHS of (3) by the inverse of the LHS to get

Note that

If we can show that P=D^-1, then the BD^-1CA^-1 terms would be cancelled out. This is accomplished by noting

Hence we have shown that P is indeed equal to D^-1. After the cancellation of the BD^-1CA^-1 term, all there is left is the identity matrix; and the proof is completed.

The derivative of the matrix inverse

Suppose that the matrix A depends on a parameter t. Then the derivative of the inverse of A with respect to t is given by

This formula can be found by differentiating the identity

The Moore-Penrose pseudoinverse

Some of the properties of inverse matrices are shared by (Moore-Penrose) pseudoinverses, which can be defined for any m-by-n matrix. In mathematics, and in particular linear algebra, the pseudoinverse of an matrix is a generalization of the inverse matrix. ...

Matrix inverses in real-time simulations

Matrix inversion plays a significant role in computer graphics, particularly in 3D graphics rendering and 3D simulations. Examples include screen-to-world ray casting, world-to-subspace-to-world object transformations, and physical simulations. The problem is usually the numerical complexity of calculating the inverses of 3×3 and 4×4 matrices. Compared to matrix multiplication or creation of rotation matrices, matrix inversion is several orders of magnitude slower. There are existing solutions which use hand-crafted assembly language routines and SIMD processor extensions (SSE, SSE2, Altivec) that address this problem and which achieve a performance improvement of as much as five times. This article is about the scientific discipline of computer graphics. ... The rewrite of this article is being devised at Talk:3D computer graphics/Temp. ... See the terminology section, below, regarding inconsistent use of the terms assembly and assembler. ... -1...

See also

• Matrix decomposition
• Binomial inverse theorem
• Singular value decomposition
• LU decomposition
• Pseudoinverse (Moore-Penrose inverse)

In the mathematical discipline of linear algebra, a matrix decomposition is a factorization of a matrix into some canonical form. ... In mathematics, the binomial inverse theorem is useful for expressing matrix inverses in different ways. ... In linear algebra, the singular value decomposition (SVD) is an important factorization of a rectangular real or complex matrix, with several applications in signal processing and statistics. ... In linear algebra, the LU decomposition is a matrix decomposition which writes a matrix as the product of a lower and upper triangular matrix. ... In mathematics, and in particular linear algebra, the pseudoinverse of an matrix is a generalization of the inverse matrix. ...

References

• Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms, Second Edition. MIT Press and McGraw-Hill, 2001. ISBN 0-262-03293-7. Section 28.4: Inverting matrices, pp.755–760.

1. ^ Strang, Gilbert (2006). Linear Algebra and Its Applications. Thomson Brooks/Cole, p. 46. ISBN 0-03-010567-6. 

Thomas H. Cormen is the co-author of Introduction to Algorithms, along with Charles Leiserson, Ron Rivest, and Cliff Stein. ... Charles E. Leiserson is a computer scientist, specializing in the theory of parallel computing and distributed computing, and particularly practical applications thereof; as part of this effort, he developed the Cilk multithreaded language. ... Professor Ron Rivest Professor Ronald Linn Rivest (born 1947, Schenectady, New York) is a cryptographer, and is the Viterbi Professor of Computer Science at MITs Department of Electrical Engineering and Computer Science. ... Clifford Stein is a computer scientist, currently working as a professor at Columbia University in New York, NY. He earned his BSE from Princeton University in 1987, a MS from Massachusetts Institute of Technology in 1989, and a PhD from Massachusetts Institute of Technology in 1992. ... Cover of the second edition Introduction to Algorithms is a book by Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. ...

External links

• MIT Linear Algebra Lecture on Inverse Matrices at Google Video, from MIT OpenCourseWare
• LAPACK is a collection of FORTRAN subroutines for solving dense linear algebra problems
• ALGLIB includes a partial port of the LAPACK to C++, C#, Delphi, etc.
• Online Inverse Matrix Calculator using AJAX
• Inverse Matrix Calculator
• Moore Penrose Pseudoinverse
• Inverse of a Matrix Notes
• Module for the Matrix Inverse
• Derivative of inverse matrix on PlanetMath