HOME

TheInfoList




In
mathematics Mathematics (from Greek: ) includes the study of such topics as numbers (arithmetic and number theory), formulas and related structures (algebra), shapes and spaces in which they are contained (geometry), and quantities and their changes (cal ...
, particularly in
linear algebra Linear algebra is the branch of mathematics concerning linear equations such as: :a_1x_1+\cdots +a_nx_n=b, linear maps such as: :(x_1, \ldots, x_n) \mapsto a_1x_1+\cdots +a_nx_n, and their representations in vector spaces and through matrix (mat ...
, matrix multiplication is a
binary operation In mathematics Mathematics (from Ancient Greek, Greek: ) includes the study of such topics as quantity (number theory), mathematical structure, structure (algebra), space (geometry), and calculus, change (mathematical analysis, analysis). I ...
that produces a
matrix Matrix or MATRIX may refer to: Science and mathematics * Matrix (mathematics), a rectangular array of numbers, symbols, or expressions * Matrix (logic), part of a formula in prenex normal form * Matrix (biology), the material in between a eukaryoti ...
from two matrices. For matrix multiplication, the number of columns in the first matrix must be equal to the number of rows in the second matrix. The resulting matrix, known as the matrix product, has the number of rows of the first and the number of columns of the second matrix. The product of matrices and is denoted as . Matrix multiplication was first described by the French mathematician
Jacques Philippe Marie Binet Jacques Philippe Marie Binet (; 2 February 1786 – 12 May 1856) was a French mathematician A mathematician is someone who uses an extensive knowledge of mathematics Mathematics (from Ancient Greek, Greek: ) includes the study of such topi ...
in 1812, to represent the
composition Composition or Compositions may refer to: Arts * Composition (dance), practice and teaching of choreography * Composition (music), an original piece of music and its creation *Composition (visual arts) The term composition means "putting togethe ...
of
linear map In mathematics Mathematics (from Ancient Greek, Greek: ) includes the study of such topics as quantity (number theory), mathematical structure, structure (algebra), space (geometry), and calculus, change (mathematical analysis, analysis). I ...

linear map
s that are represented by matrices. Matrix multiplication is thus a basic tool of
linear algebra Linear algebra is the branch of mathematics concerning linear equations such as: :a_1x_1+\cdots +a_nx_n=b, linear maps such as: :(x_1, \ldots, x_n) \mapsto a_1x_1+\cdots +a_nx_n, and their representations in vector spaces and through matrix (mat ...
, and as such has numerous applications in many areas of mathematics, as well as in
applied mathematics Applied mathematics is the application of mathematical methods by different fields such as physics Physics is the natural science that studies matter, its Elementary particle, fundamental constituents, its Motion (physics), motion and be ...
,
statistics Statistics is the discipline that concerns the collection, organization, analysis, interpretation, and presentation of data Data (; ) are individual facts, statistics, or items of information, often numeric. In a more technical sens ...

statistics
,
physics Physics is the that studies , its , its and behavior through , and the related entities of and . "Physical science is that department of knowledge which relates to the order of nature, or, in other words, to the regular succession of eve ...

physics
,
economics Economics () is a social science Social science is the branch A branch ( or , ) or tree branch (sometimes referred to in botany Botany, also called , plant biology or phytology, is the science of plant life and a bran ...

economics
, and
engineering Engineering is the use of scientific principles to design and build machines, structures, and other items, including bridges, tunnels, roads, vehicles, and buildings. The discipline of engineering encompasses a broad range of more specializ ...

engineering
. Computing matrix products is a central operation in all computational applications of linear algebra.


Notation

This article will use the following notational conventions: matrices are represented by capital letters in bold, e.g. ;
vectors Vector may refer to: Biology *Vector (epidemiology), an agent that carries and transmits an infectious pathogen into another living organism; a disease vector *Vector (molecular biology), a DNA molecule used as a vehicle to artificially carr ...
in lowercase bold, e.g. ; and entries of vectors and matrices are italic (since they are numbers from a field), e.g. and .
Index notation In mathematics Mathematics (from Ancient Greek, Greek: ) includes the study of such topics as quantity (number theory), mathematical structure, structure (algebra), space (geometry), and calculus, change (mathematical analysis, analysis). It h ...
is often the clearest way to express definitions, and is used as standard in the literature. The entry of matrix is indicated by , or , whereas a numerical label (not matrix entries) on a collection of matrices is subscripted only, e.g. , etc.


Definition

If is an matrix and is an matrix, :\mathbf=\begin a_ & a_ & \cdots & a_ \\ a_ & a_ & \cdots & a_ \\ \vdots & \vdots & \ddots & \vdots \\ a_ & a_ & \cdots & a_ \\ \end,\quad\mathbf=\begin b_ & b_ & \cdots & b_ \\ b_ & b_ & \cdots & b_ \\ \vdots & \vdots & \ddots & \vdots \\ b_ & b_ & \cdots & b_ \\ \end the ''matrix product'' (denoted without multiplication signs or dots) is defined to be the matrix :\mathbf=\begin c_ & c_ & \cdots & c_ \\ c_ & c_ & \cdots & c_ \\ \vdots & \vdots & \ddots & \vdots \\ c_ & c_ & \cdots & c_ \\ \end such that : c_ = a_b_ + a_b_ +\cdots + a_b_= \sum_^n a_b_, for and . That is, the entry of the product is obtained by multiplying term-by-term the entries of the th row of and the th column of , and summing these products. In other words, is the
dot product In mathematics, the dot product or scalar productThe term ''scalar product'' is often also used more generally to mean a symmetric bilinear form, for example for a pseudo-Euclidean space. is an algebraic operation that takes two equal-length seque ...
of the th row of and the th column of . Therefore, can also be written as :\mathbf=\begin a_b_ +\cdots + a_b_ & a_b_ +\cdots + a_b_ & \cdots & a_b_ +\cdots + a_b_ \\ a_b_ +\cdots + a_b_ & a_b_ +\cdots + a_b_ & \cdots & a_b_ +\cdots + a_b_ \\ \vdots & \vdots & \ddots & \vdots \\ a_b_ +\cdots + a_b_ & a_b_ +\cdots + a_b_ & \cdots & a_b_ +\cdots + a_b_ \\ \end Thus the product is defined if and only if the number of columns in equals the number of rows in , in this case . Many scientific calculator manuals do not mention this condition correctly. In most scenarios, the entries are numbers, but they may be any kind of
mathematical object A mathematical object is an abstract concept arising in mathematics. In the usual language of mathematics, an ''object'' is anything that has been (or could be) formally defined, and with which one may do deductive reasoning and mathematical proofs ...
s for which an addition and a multiplication are defined, that are
associative In mathematics Mathematics (from Ancient Greek, Greek: ) includes the study of such topics as quantity (number theory), mathematical structure, structure (algebra), space (geometry), and calculus, change (mathematical analysis, analysis). ...
, and such that the addition is
commutative In mathematics Mathematics (from Greek: ) includes the study of such topics as numbers ( and ), formulas and related structures (), shapes and spaces in which they are contained (), and quantities and their changes ( and ). There is no ge ...
, and the multiplication is distributive with respect to the addition. In particular, the entries may be matrices themselves (see
block matrix In mathematics Mathematics (from Ancient Greek, Greek: ) includes the study of such topics as quantity (number theory), mathematical structure, structure (algebra), space (geometry), and calculus, change (mathematical analysis, analysis). It h ...
).


Illustration

The figure to the right illustrates diagrammatically the product of two matrices and , showing how each intersection in the product matrix corresponds to a row of and a column of . : \overset \overset = \overset The values at the intersections marked with circles are: :\begin c_ & = + \\ c_ & = + \end


Fundamental applications

Historically, matrix multiplication has been introduced for facilitating and clarifying computations in
linear algebra Linear algebra is the branch of mathematics concerning linear equations such as: :a_1x_1+\cdots +a_nx_n=b, linear maps such as: :(x_1, \ldots, x_n) \mapsto a_1x_1+\cdots +a_nx_n, and their representations in vector spaces and through matrix (mat ...
. This strong relationship between matrix multiplication and linear algebra remains fundamental in all mathematics, as well as in
physics Physics is the that studies , its , its and behavior through , and the related entities of and . "Physical science is that department of knowledge which relates to the order of nature, or, in other words, to the regular succession of eve ...

physics
,
chemistry Chemistry is the study of the properties and behavior of . It is a that covers the that make up matter to the composed of s, s and s: their composition, structure, properties, behavior and the changes they undergo during a with other . ...

chemistry
,
engineering Engineering is the use of scientific principles to design and build machines, structures, and other items, including bridges, tunnels, roads, vehicles, and buildings. The discipline of engineering encompasses a broad range of more specializ ...

engineering
and
computer science Computer science deals with the theoretical foundations of information, algorithms and the architectures of its computation as well as practical techniques for their application. Computer science is the study of , , and . Computer science ...
.


Linear maps

If a
vector space In mathematics Mathematics (from Ancient Greek, Greek: ) includes the study of such topics as quantity (number theory), mathematical structure, structure (algebra), space (geometry), and calculus, change (mathematical analysis, analysis). ...
has a finite
basis Basis may refer to: Finance and accounting *Adjusted basisIn tax accounting, adjusted basis is the net cost of an asset after adjusting for various tax-related items. Adjusted Basis or Adjusted Tax Basis refers to the original cost or other ba ...
, its vectors are each uniquely represented by a finite
sequence In mathematics Mathematics (from Greek: ) includes the study of such topics as numbers (arithmetic and number theory), formulas and related structures (algebra), shapes and spaces in which they are contained (geometry), and quantities and t ...
of scalars, called a
coordinate vector In linear algebra, a coordinate vector is a representation of a vector as an ordered list of numbers that describes the vector in terms of a particular ordered basis. Coordinates are always specified relative to an ordered basis. Bases and their a ...
, whose elements are the
coordinates In geometry Geometry (from the grc, γεωμετρία; ''wikt:γῆ, geo-'' "earth", ''wikt:μέτρον, -metron'' "measurement") is, with arithmetic, one of the oldest branches of mathematics. It is concerned with properties of space t ...

coordinates
of the vector on the basis. These coordinate vectors form another vector space, which is
isomorphic In mathematics Mathematics (from Ancient Greek, Greek: ) includes the study of such topics as quantity (number theory), mathematical structure, structure (algebra), space (geometry), and calculus, change (mathematical analysis, analysis). I ...

isomorphic
to the original vector space. A coordinate vector is commonly organized as a
column matrixIn linear algebra, a column vector is a column of entries, for example, :\boldsymbol = \begin x_1 \\ x_2 \\ \vdots \\ x_m \end \,. Similarly, a row vector is a row of entries, p. 8 :\boldsymbol a = \begin a_1 & a_2 & \dots & a_n \end \,. Throu ...
(also called ''column vector''), which is a matrix with only one column. So, a column vector represents both a coordinate vector, and a vector of the original vector space. A
linear map In mathematics Mathematics (from Ancient Greek, Greek: ) includes the study of such topics as quantity (number theory), mathematical structure, structure (algebra), space (geometry), and calculus, change (mathematical analysis, analysis). I ...

linear map
from a vector space of dimension into a vector space of dimension maps a column vector :\mathbf x=\beginx_1 \\ x_2 \\ \vdots \\ x_n\end onto the column vector :\mathbf y= A(\mathbf x)= \begina_x_1+\cdots + a_x_n\\ a_x_1+\cdots + a_x_n \\ \vdots \\ a_x_1+\cdots + a_x_n\end. The linear map is thus defined by the matrix ::\mathbf=\begin a_ & a_ & \cdots & a_ \\ a_ & a_ & \cdots & a_ \\ \vdots & \vdots & \ddots & \vdots \\ a_ & a_ & \cdots & a_ \\ \end, and maps the column vector \mathbf x to the matrix product :\mathbf y = \mathbf . If is another linear map from the preceding vector space of dimension , into a vector space of dimension , it is represented by a matrix \mathbf B. A straightforward computation shows that the matrix of the composite map is the matrix product \mathbf . The general formula ) that defines the function composition is instanced here as a specific case of associativity of matrix product (see below): :(\mathbf)\mathbf x = \mathbf(\mathbf ) = \mathbf.


System of linear equations

The general form of a
system of linear equations In mathematics Mathematics (from Ancient Greek, Greek: ) includes the study of such topics as quantity (number theory), mathematical structure, structure (algebra), space (geometry), and calculus, change (mathematical analysis, analysis). It ...
is :\begina_x_1+\cdots + a_x_n=b_1 \\ a_x_1+\cdots + a_x_n =b_2 \\ \vdots \\ a_x_1+\cdots + a_x_n =b_m\end. Using same notation as above, such a system is equivalent with the single matrix
equation In mathematics Mathematics (from Ancient Greek, Greek: ) includes the study of such topics as quantity (number theory), mathematical structure, structure (algebra), space (geometry), and calculus, change (mathematical analysis, analysis). I ...

equation
:\mathbf=\mathbf b.


Dot product, bilinear form and inner product

The
dot product In mathematics, the dot product or scalar productThe term ''scalar product'' is often also used more generally to mean a symmetric bilinear form, for example for a pseudo-Euclidean space. is an algebraic operation that takes two equal-length seque ...
of two column vectors is the matrix product :\mathbf x^\mathsf T \mathbf y, where \mathbf x^\mathsf T is the
row vector In linear algebra Linear algebra is the branch of mathematics concerning linear equations such as: :a_1x_1+\cdots +a_nx_n=b, linear maps such as: :(x_1, \ldots, x_n) \mapsto a_1x_1+\cdots +a_nx_n, and their representations in vector spaces and th ...
obtained by \mathbf x and the resulting 1×1 matrix is identified with its unique entry. More generally, any
bilinear form In mathematics Mathematics (from Ancient Greek, Greek: ) includes the study of such topics as quantity (number theory), mathematical structure, structure (algebra), space (geometry), and calculus, change (mathematical analysis, analysis). It h ...
over a vector space of finite dimension may be expressed as a matrix product :\mathbf x^\mathsf T \mathbf , and any
inner product In mathematics, an inner product space or a Hausdorff space, Hausdorff pre-Hilbert space is a vector space with a binary operation called an inner product. This operation associates each pair of vectors in the space with a Scalar (mathematics), ...
may be expressed as :\mathbf x^\dagger \mathbf , where \mathbf x^\dagger denotes the
conjugate transpose In mathematics, the conjugate transpose (or Hermitian transpose) of an ''m''-by-''n'' matrix (mathematics), matrix \boldsymbol with complex number, complex entries is the ''n''-by-''m'' matrix obtained from \boldsymbol by taking the transpose and ...
of \mathbf x (conjugate of the transpose, or equivalently transpose of the conjugate).


General properties

Matrix multiplication shares some properties with usual
multiplication Multiplication (often denoted by the cross symbol , by the mid-line dot operator , by juxtaposition Juxtaposition is an act or instance of placing two elements close together or side by side. This is often done in order to compare/contr ...

multiplication
. However, matrix multiplication is not defined if the number of columns of the first factor differs from the number of rows of the second factor, and it is
non-commutative In mathematics Mathematics (from Ancient Greek, Greek: ) includes the study of such topics as quantity (number theory), mathematical structure, structure (algebra), space (geometry), and calculus, change (mathematical analysis, analysis). I ...
, even when the product remains definite after changing the order of the factors.


Non-commutativity

An operation is
commutative In mathematics Mathematics (from Greek: ) includes the study of such topics as numbers ( and ), formulas and related structures (), shapes and spaces in which they are contained (), and quantities and their changes ( and ). There is no ge ...
if, given two elements and such that the product \mathbf\mathbf is defined, then \mathbf\mathbf is also defined, and \mathbf\mathbf=\mathbf\mathbf. If and are matrices of respective sizes and , then \mathbf\mathbf is defined if , and \mathbf\mathbf is defined if . Therefore, if one of the products is defined, the other is not defined in general. If , the two products are defined, but have different sizes; thus they cannot be equal. Only if , that is, if and are
square matrices In mathematics Mathematics (from Ancient Greek, Greek: ) includes the study of such topics as quantity (number theory), mathematical structure, structure (algebra), space (geometry), and calculus, change (mathematical analysis, analysis). It ...
of the same size, are both products defined and of the same size. Even in this case, one has in general :\mathbf\mathbf \neq \mathbf\mathbf. For example :\begin 0 & 1 \\ 0 & 0 \end\begin 0 & 0 \\ 1 & 0 \end=\begin 1 & 0 \\ 0 & 0 \end, but :\begin 0 & 0 \\ 1 & 0 \end\begin 0 & 1 \\ 0 & 0 \end = \begin 0 & 0 \\ 0 & 1 \end. This example may be expanded for showing that, if is a matrix with entries in a
field Field may refer to: Expanses of open ground * Field (agriculture), an area of land used for agricultural purposes * Airfield, an aerodrome that lacks the infrastructure of an airport * Battlefield * Lawn, an area of mowed grass * Meadow, a grassl ...
, then \mathbf\mathbf = \mathbf\mathbf for every matrix with entries in ,
if and only if In logic Logic is an interdisciplinary field which studies truth and reasoning Reason is the capacity of consciously making sense of things, applying logic Logic (from Ancient Greek, Greek: grc, wikt:λογική, λογική, l ...
\mathbf=c\,\mathbf where , and is the
identity matrix In linear algebra, the identity matrix of size ''n'' is the ''n'' × ''n'' square matrix In mathematics Mathematics (from Ancient Greek, Greek: ) includes the study of such topics as quantity (number theory), mathematical structure, structu ...

identity matrix
. If, instead of a field, the entries are supposed to belong to a ring, then one must add the condition that belongs to the
center Center or centre may refer to: Mathematics *Center (geometry) In geometry, a centre (or center) (from Ancient Greek language, Greek ''κέντρον'') of an object is a point in some sense in the middle of the object. According to the speci ...
of the ring. One special case where commutativity does occur is when and are two (square)
diagonal matrices In linear algebra, a diagonal matrix is a matrix in which the entries outside the main diagonal are all zero; the term usually refers to square matrices. An example of a 2×2 diagonal matrix is \left begin 3 & 0 \\ 0 & 2 \end\right/math>, while ...
(of the same size); then . Again, if the matrices are over a general ring rather than a field, the corresponding entries in each must also commute with each other for this to hold.


Distributivity

The matrix product is distributive with respect to
matrix addition In mathematics Mathematics (from Ancient Greek, Greek: ) includes the study of such topics as quantity (number theory), mathematical structure, structure (algebra), space (geometry), and calculus, change (mathematical analysis, analysis). It ...
. That is, if are matrices of respective sizes , , , and , one has (left distributivity) :\mathbf(\mathbf + \mathbf) = \mathbf + \mathbf, and (right distributivity) :(\mathbf + \mathbf )\mathbf = \mathbf + \mathbf. This results from the distributivity for coefficients by :\sum_k a_(b_ + c_) = \sum_k a_b_ + \sum_k a_c_ :\sum_k (b_ + c_) d_ = \sum_k b_d_ + \sum_k c_d_.


Product with a scalar

If is a matrix and a scalar, then the matrices c\mathbf and \mathbfc are obtained by left or right multiplying all entries of by . If the scalars have the
commutative property In mathematics Mathematics (from Ancient Greek, Greek: ) includes the study of such topics as quantity (number theory), mathematical structure, structure (algebra), space (geometry), and calculus, change (mathematical analysis, analysis). I ...
, then c\mathbf = \mathbfc. If the product \mathbf is defined (that is, the number of columns of equals the number of rows of ), then : c(\mathbf) = (c \mathbf)\mathbf and (\mathbf \mathbf)c=\mathbf(\mathbfc). If the scalars have the commutative property, then all four matrices are equal. More generally, all four are equal if belongs to the
center Center or centre may refer to: Mathematics *Center (geometry) In geometry, a centre (or center) (from Ancient Greek language, Greek ''κέντρον'') of an object is a point in some sense in the middle of the object. According to the speci ...
of a ring containing the entries of the matrices, because in this case, for all matrices . These properties result from the
bilinearity In mathematics Mathematics (from Greek: ) includes the study of such topics as numbers ( and ), formulas and related structures (), shapes and spaces in which they are contained (), and quantities and their changes ( and ). There is no gene ...
of the product of scalars: :c \left(\sum_k a_b_\right) = \sum_k (c a_ ) b_ :\left(\sum_k a_b_\right) c = \sum_k a_ ( b_c).


Transpose

If the scalars have the
commutative property In mathematics Mathematics (from Ancient Greek, Greek: ) includes the study of such topics as quantity (number theory), mathematical structure, structure (algebra), space (geometry), and calculus, change (mathematical analysis, analysis). I ...
, the
transpose In linear algebra Linear algebra is the branch of mathematics concerning linear equations such as: :a_1x_1+\cdots +a_nx_n=b, linear maps such as: :(x_1, \ldots, x_n) \mapsto a_1x_1+\cdots +a_nx_n, and their representations in vector spaces an ...

transpose
of a product of matrices is the product, in the reverse order, of the transposes of the factors. That is : (\mathbf)^\mathsf = \mathbf^\mathsf\mathbf^\mathsf where T denotes the transpose, that is the interchange of rows and columns. This identity does not hold for noncommutative entries, since the order between the entries of and is reversed, when one expands the definition of the matrix product.


Complex conjugate

If and have
complex The UCL Faculty of Mathematical and Physical Sciences is one of the 11 constituent faculties of University College London , mottoeng = Let all come who by merit deserve the most reward , established = , type = Public university, Public rese ...

complex
entries, then : (\mathbf)^* = \mathbf^*\mathbf^* where denotes the entry-wise
complex conjugate In mathematics Mathematics (from Greek: ) includes the study of such topics as numbers ( and ), formulas and related structures (), shapes and spaces in which they are contained (), and quantities and their changes ( and ). There is no gen ...
of a matrix. This results from applying to the definition of matrix product the fact that the conjugate of a sum is the sum of the conjugates of the summands and the conjugate of a product is the product of the conjugates of the factors. Transposition acts on the indices of the entries, while conjugation acts independently on the entries themselves. It results that, if and have complex entries, one has : (\mathbf)^\dagger = \mathbf^\dagger\mathbf^\dagger , where denotes the
conjugate transpose In mathematics, the conjugate transpose (or Hermitian transpose) of an ''m''-by-''n'' matrix (mathematics), matrix \boldsymbol with complex number, complex entries is the ''n''-by-''m'' matrix obtained from \boldsymbol by taking the transpose and ...
(conjugate of the transpose, or equivalently transpose of the conjugate).


Associativity

Given three matrices and , the products and are defined if and only if the number of columns of equals the number of rows of , and the number of columns of equals the number of rows of (in particular, if one of the products is defined, then the other is also defined). In this case, one has the
associative property In mathematics Mathematics (from Ancient Greek, Greek: ) includes the study of such topics as quantity (number theory), mathematical structure, structure (algebra), space (geometry), and calculus, change (mathematical analysis, analysis). ...
:(\mathbf)\mathbf=\mathbf(\mathbf). As for any associative operation, this allows omitting parentheses, and writing the above products as This extends naturally to the product of any number of matrices provided that the dimensions match. That is, if are matrices such that the number of columns of equals the number of rows of for , then the product : \prod_^n \mathbf_i = \mathbf_1\mathbf_2\cdots\mathbf_n is defined and does not depend on the , if the order of the matrices is kept fixed. These properties may be proved by straightforward but complicated
summation In mathematics, summation is the addition of a sequence of any kind of numbers, called ''addends'' or ''summands''; the result is their ''sum'' or ''total''. Beside numbers, other types of values can be summed as well: function (mathematics), fun ...

summation
manipulations. This result also follows from the fact that matrices represent
linear map In mathematics Mathematics (from Ancient Greek, Greek: ) includes the study of such topics as quantity (number theory), mathematical structure, structure (algebra), space (geometry), and calculus, change (mathematical analysis, analysis). I ...

linear map
s. Therefore, the associative property of matrices is simply a specific case of the associative property of
function composition In mathematics Mathematics (from Ancient Greek, Greek: ) includes the study of such topics as quantity (number theory), mathematical structure, structure (algebra), space (geometry), and calculus, change (mathematical analysis, analysis). ...
.


Complexity is not associative

Although the result of a sequence of matrix products does not depend on the order of operation (provided that the order of the matrices is not changed), the computational complexity may depend dramatically on this order. For example, if and are matrices of respective sizes , computing needs multiplications, while computing needs multiplications. Algorithms have been designed for choosing the best order of products, see
Matrix chain multiplication Matrix chain multiplication (or the matrix chain ordering problem) is an optimization problem In mathematics Mathematics (from Ancient Greek, Greek: ) includes the study of such topics as quantity (number theory), mathematical structure, stru ...
. When the number of matrices increases, it has been shown that the choice of the best order has a complexity of O(n \log n).


Application to similarity

Any
invertible matrixIn linear algebra, an ''n''-by-''n'' square matrix is called invertible (also nonsingular or nondegenerate), if there exists an ''n''-by-''n'' square matrix such that :\mathbf = \mathbf = \mathbf_n \ where denotes the ''n''-by-''n'' identit ...
\mathbf defines a similarity transformation (on square matrices of the same size as \mathbf) :S_\mathbf(\mathbf) = \mathbf^ \mathbf \mathbf. Similarity transformations map product to products, that is :S_\mathbf(\mathbf) = S_\mathbf(\mathbf)S_\mathbf(\mathbf). In fact, one has :\mathbf^ (\mathbf) \mathbf = \mathbf^ \mathbf(\mathbf\mathbf^)\mathbf \mathbf =(\mathbf^ \mathbf\mathbf)(\mathbf^\mathbf \mathbf).


Square matrices

Let us denote \mathcal M_n(R) the set of
square matrices In mathematics Mathematics (from Ancient Greek, Greek: ) includes the study of such topics as quantity (number theory), mathematical structure, structure (algebra), space (geometry), and calculus, change (mathematical analysis, analysis). It ...
with entries in a ring , which, in practice, is often a
field Field may refer to: Expanses of open ground * Field (agriculture), an area of land used for agricultural purposes * Airfield, an aerodrome that lacks the infrastructure of an airport * Battlefield * Lawn, an area of mowed grass * Meadow, a grassl ...
. In \mathcal M_n(R), the product is defined for every pair of matrices. This makes \mathcal M_n(R) a ring, which has the
identity matrix In linear algebra, the identity matrix of size ''n'' is the ''n'' × ''n'' square matrix In mathematics Mathematics (from Ancient Greek, Greek: ) includes the study of such topics as quantity (number theory), mathematical structure, structu ...

identity matrix
as
identity element In mathematics Mathematics (from Greek: ) includes the study of such topics as numbers (arithmetic and number theory), formulas and related structures (algebra), shapes and spaces in which they are contained (geometry), and quantities and th ...
(the matrix whose diagonal entries are equal to 1 and all other entries are 0). This ring is also an associative -algebra. If , many matrices do not have a
multiplicative inverse Image:Hyperbola one over x.svg, thumbnail, 300px, alt=Graph showing the diagrammatic representation of limits approaching infinity, The reciprocal function: . For every ''x'' except 0, ''y'' represents its multiplicative inverse. The graph forms a r ...

multiplicative inverse
. For example, a matrix such that all entries of a row (or a column) are 0 does not have an inverse. If it exists, the inverse of a matrix is denoted , and, thus verifies : \mathbf\mathbf^ = \mathbf^\mathbf = \mathbf. A matrix that has an inverse is an
invertible matrixIn linear algebra, an ''n''-by-''n'' square matrix is called invertible (also nonsingular or nondegenerate), if there exists an ''n''-by-''n'' square matrix such that :\mathbf = \mathbf = \mathbf_n \ where denotes the ''n''-by-''n'' identit ...
. Otherwise, it is a
singular matrixIn linear algebra, an ''n''-by-''n'' square matrix In mathematics Mathematics (from Ancient Greek, Greek: ) includes the study of such topics as quantity (number theory), mathematical structure, structure (algebra), space (geometry), and calc ...
. A product of matrices is invertible if and only if each factor is invertible. In this case, one has :(\mathbf\mathbf)^ = \mathbf^\mathbf^. When is
commutative In mathematics Mathematics (from Greek: ) includes the study of such topics as numbers ( and ), formulas and related structures (), shapes and spaces in which they are contained (), and quantities and their changes ( and ). There is no ge ...
, and, in particular, when it is a field, the
determinant In mathematics Mathematics (from Greek: ) includes the study of such topics as numbers (arithmetic and number theory), formulas and related structures (algebra), shapes and spaces in which they are contained (geometry), and quantities and t ...

determinant
of a product is the product of the determinants. As determinants are scalars, and scalars commute, one has thus : \det(\mathbf) = \det(\mathbf) =\det(\mathbf)\det(\mathbf). The other matrix invariants do not behave as well with products. Nevertheless, if is commutative, and have the same
trace Trace may refer to: Arts and entertainment Music * ''Trace'' (Son Volt album), 1995 * ''Trace'' (Died Pretty album), 1993 * Trace (band) Trace was a Netherlands, Dutch progressive rock trio founded by Rick van der Linden in 1974 after leavin ...
, the same
characteristic polynomial In linear algebra Linear algebra is the branch of mathematics concerning linear equations such as: :a_1x_1+\cdots +a_nx_n=b, linear maps such as: :(x_1, \ldots, x_n) \mapsto a_1x_1+\cdots +a_nx_n, and their representations in vector spaces a ...
, and the same
eigenvalues In linear algebra, an eigenvector () or characteristic vector of a Linear map, linear transformation is a nonzero Vector space, vector that changes at most by a Scalar (mathematics), scalar factor when that linear transformation is applied to it ...
with the same multiplicities. However, the
eigenvector In linear algebra Linear algebra is the branch of mathematics concerning linear equations such as: :a_1x_1+\cdots +a_nx_n=b, linear maps such as: :(x_1, \ldots, x_n) \mapsto a_1x_1+\cdots +a_nx_n, and their representations in vector spaces an ...

eigenvector
s are generally different if .


Powers of a matrix

One may raise a square matrix to any nonnegative integer power multiplying it by itself repeatedly in the same way as for ordinary numbers. That is, :\mathbf^0 = \mathbf, :\mathbf^1 = \mathbf, :\mathbf^k = \underbrace_. Computing the th power of a matrix needs times the time of a single matrix multiplication, if it is done with the trivial algorithm (repeated multiplication). As this may be very time consuming, one generally prefers using
exponentiation by squaring In mathematics Mathematics (from Ancient Greek, Greek: ) includes the study of such topics as quantity (number theory), mathematical structure, structure (algebra), space (geometry), and calculus, change (mathematical analysis, analysis). It ...
, which requires less than matrix multiplications, and is therefore much more efficient. An easy case for exponentiation is that of a
diagonal matrix In linear algebra Linear algebra is the branch of mathematics concerning linear equations such as: :a_1x_1+\cdots +a_nx_n=b, linear maps such as: :(x_1, \ldots, x_n) \mapsto a_1x_1+\cdots +a_nx_n, and their representations in vector spaces and ...
. Since the product of diagonal matrices amounts to simply multiplying corresponding diagonal elements together, the th power of a diagonal matrix is obtained by raising the entries to the power : : \begin a_ & 0 & \cdots & 0 \\ 0 & a_ & \cdots & 0 \\ \vdots & \vdots & \ddots & \vdots \\ 0 & 0 & \cdots & a_ \end^k = \begin a_^k & 0 & \cdots & 0 \\ 0 & a_^k & \cdots & 0 \\ \vdots & \vdots & \ddots & \vdots \\ 0 & 0 & \cdots & a_^k \end.


Abstract algebra

The definition of matrix product requires that the entries belong to a semiring, and does not require multiplication of elements of the semiring to be
commutative In mathematics Mathematics (from Greek: ) includes the study of such topics as numbers ( and ), formulas and related structures (), shapes and spaces in which they are contained (), and quantities and their changes ( and ). There is no ge ...
. In many applications, the matrix elements belong to a field, although the
tropical semiring In idempotent analysis, the tropical semiring is a semiring of extended real numbers with the operations of minimum (or maximum) and addition replacing the usual ("classical") operations of addition and multiplication, respectively. The tropical se ...
is also a common choice for graph
shortest path In graph theory In mathematics, graph theory is the study of ''graph (discrete mathematics), graphs'', which are mathematical structures used to model pairwise relations between objects. A graph in this context is made up of ''Vertex (graph the ...

shortest path
problems. Even in the case of matrices over fields, the product is not commutative in general, although it is
associative In mathematics Mathematics (from Ancient Greek, Greek: ) includes the study of such topics as quantity (number theory), mathematical structure, structure (algebra), space (geometry), and calculus, change (mathematical analysis, analysis). ...
and is distributive over
matrix addition In mathematics Mathematics (from Ancient Greek, Greek: ) includes the study of such topics as quantity (number theory), mathematical structure, structure (algebra), space (geometry), and calculus, change (mathematical analysis, analysis). It ...
. The identity matrices (which are the
square matrices In mathematics Mathematics (from Ancient Greek, Greek: ) includes the study of such topics as quantity (number theory), mathematical structure, structure (algebra), space (geometry), and calculus, change (mathematical analysis, analysis). It ...
whose entries are zero outside of the main diagonal and 1 on the main diagonal) are
identity element In mathematics Mathematics (from Greek: ) includes the study of such topics as numbers (arithmetic and number theory), formulas and related structures (algebra), shapes and spaces in which they are contained (geometry), and quantities and th ...
s of the matrix product. It follows that the matrices over a ring form a ring, which is noncommutative except if and the ground ring is commutative. A square matrix may have a
multiplicative inverse Image:Hyperbola one over x.svg, thumbnail, 300px, alt=Graph showing the diagrammatic representation of limits approaching infinity, The reciprocal function: . For every ''x'' except 0, ''y'' represents its multiplicative inverse. The graph forms a r ...

multiplicative inverse
, called an
inverse matrixIn linear algebra, an ''n''-by-''n'' square matrix is called invertible (also nonsingular or nondegenerate), if there exists an ''n''-by-''n'' square matrix such that :\mathbf = \mathbf = \mathbf_n \ where denotes the ''n''-by-''n'' identit ...
. In the common case where the entries belong to a
commutative ring In ring theory In algebra Algebra (from ar, الجبر, lit=reunion of broken parts, bonesetting, translit=al-jabr) is one of the areas of mathematics, broad areas of mathematics, together with number theory, geometry and mathematical ana ...
, a matrix has an inverse if and only if its
determinant In mathematics Mathematics (from Greek: ) includes the study of such topics as numbers (arithmetic and number theory), formulas and related structures (algebra), shapes and spaces in which they are contained (geometry), and quantities and t ...

determinant
has a multiplicative inverse in . The determinant of a product of square matrices is the product of the determinants of the factors. The matrices that have an inverse form a
group A group is a number A number is a mathematical object used to counting, count, measurement, measure, and nominal number, label. The original examples are the natural numbers 1, 2, 3, 4, and so forth. Numbers can be represented in language with ...
under matrix multiplication, the
subgroup In group theory, a branch of mathematics, given a group (mathematics), group ''G'' under a binary operation ∗, a subset ''H'' of ''G'' is called a subgroup of ''G'' if ''H'' also forms a group under the operation ∗. More precisely ...
s of which are called
matrix groupIn mathematics, a matrix group is a group (mathematics), group ''G'' consisting of invertible matrix, invertible matrix (mathematics), matrices over a specified field (mathematics), field ''K'', with the operation of matrix multiplication. A linear g ...
s. Many classical groups (including all
finite group In abstract algebra In algebra, which is a broad division of mathematics, abstract algebra (occasionally called modern algebra) is the study of algebraic structures. Algebraic structures include group (mathematics), groups, ring (mathematics), ...
s) are
isomorphic In mathematics Mathematics (from Ancient Greek, Greek: ) includes the study of such topics as quantity (number theory), mathematical structure, structure (algebra), space (geometry), and calculus, change (mathematical analysis, analysis). I ...
to matrix groups; this is the starting point of the theory of
group representation In the mathematical field of representation theory Representation theory is a branch of mathematics Mathematics (from Ancient Greek, Greek: ) includes the study of such topics as quantity (number theory), mathematical structure, struc ...
s.


Computational complexity

The matrix multiplication
algorithm In and , an algorithm () is a finite sequence of , computer-implementable instructions, typically to solve a class of problems or to perform a computation. Algorithms are always and are used as specifications for performing s, , , and other ...

algorithm
that results from the definition requires, in the
worst case In computer science Computer science deals with the theoretical foundations of information, algorithms and the architectures of its computation as well as practical techniques for their application. Computer science is the study of Algor ...
, multiplications and additions of scalars to compute the product of two square matrices. Its computational complexity is therefore , in a
model of computation A model is an informative representation of an object, person or system. The term originally denoted the Plan_(drawing), plans of a building in late 16th-century English, and derived via French and Italian ultimately from Latin ''modulus'', a meas ...
for which the scalar operations take constant time (in practice, this is the case for
floating point In computing Computing is any goal-oriented activity requiring, benefiting from, or creating computing machinery. It includes the study and experimentation of algorithmic processes and development of both computer hardware , hardware and soft ...
numbers, but not for integers). Rather surprisingly, this complexity is not optimal, as shown in 1969 by
Volker Strassen Volker Strassen (born April 29, 1936) is a German German(s) may refer to: Common uses * of or related to Germany * Germans, Germanic ethnic group, citizens of Germany or people of German ancestry * For citizens of Germany, see also German nat ...
, who provided an algorithm, now called Strassen's algorithm, with a complexity of O( n^) \approx O(n^). Strassen's algorithm can be parallelized to further improve the performance. , the best matrix multiplication algorithm is by Josh Alman and
Virginia Vassilevska Williams Virginia Vassilevska Williams (née Virginia Panayotova Vassilevska) is a theoretical computer scientist and mathematician known for her research on graph algorithms and Coppersmith–Winograd algorithm, fast matrix multiplication. She is Steven an ...
and has complexity . It is not known whether matrix multiplication can be performed in time. This would be optimal, since one must read the elements of a matrix in order to multiply it with another matrix. Since matrix multiplication forms the basis for many algorithms, and many operations on matrices even have the same complexity as matrix multiplication (up to a multiplicative constant), the computational complexity of matrix multiplication appears throughout
numerical linear algebra Numerical linear algebra, sometimes called applied linear algebra, is the study of how matrix operations can be used to create algorithms, computer algorithms which Algorithmic efficiency, efficiently and accurately provide approximate answers to q ...
and
theoretical computer science Theoretical computer science (TCS) is a subset of general computer science Computer science deals with the theoretical foundations of information, algorithms and the architectures of its computation as well as practical techniques for the ...

theoretical computer science
.


Generalizations

Other types of products of matrices include: * * Cracovian product, defined as *Frobenius inner product, the
dot product In mathematics, the dot product or scalar productThe term ''scalar product'' is often also used more generally to mean a symmetric bilinear form, for example for a pseudo-Euclidean space. is an algebraic operation that takes two equal-length seque ...
of matrices considered as vectors, or, equivalently the sum of the entries of the Hadamard product *Hadamard product (matrices), Hadamard product of two matrices of the same size, resulting in a matrix of the same size, which is the product entry-by-entry *Kronecker product or tensor product, the generalization to any size of the preceding *Khatri-Rao product and Face-splitting product *Outer product, also called dyadic product or tensor product of two column matrices, which is \mathbf\mathbf^\mathsf *Scalar multiplication


See also

*Matrix calculus, for the interaction of matrix multiplication with operations from calculus


Notes


References

* Henry Cohn, Robert Kleinberg, Balázs Szegedy, and Chris Umans. Group-theoretic Algorithms for Matrix Multiplication. . ''Proceedings of the 46th Annual Symposium on Foundations of Computer Science'', 23–25 October 2005, Pittsburgh, PA, IEEE Computer Society, pp. 379–388. * Henry Cohn, Chris Umans. A Group-theoretic Approach to Fast Matrix Multiplication. . ''Proceedings of the 44th Annual IEEE Symposium on Foundations of Computer Science'', 11–14 October 2003, Cambridge, MA, IEEE Computer Society, pp. 438–449. * * * Donald Knuth, Knuth, D.E., ''The Art of Computer Programming Volume 2: Seminumerical Algorithms''. Addison-Wesley Professional; 3 edition (November 14, 1997). . pp. 501. * . * Ran Raz. On the complexity of matrix product. In Proceedings of the thirty-fourth annual ACM symposium on Theory of computing. ACM Press, 2002. . * Robinson, Sara, ''Toward an Optimal Algorithm for Matrix Multiplication,'' SIAM News 38(9), November 2005
PDF
* Strassen, Volker, ''Gaussian Elimination is not Optimal'', Numer. Math. 13, p. 354-356, 1969. * * {{Linear algebra Matrix theory Bilinear operators Multiplication Numerical linear algebra