In

^{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.

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

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

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 ...

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 ...

, 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 ...

, 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 ...

, 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 ...

.
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, :$\backslash mathbf=\backslash begin\; a\_\; \&\; a\_\; \&\; \backslash cdots\; \&\; a\_\; \backslash \backslash \; a\_\; \&\; a\_\; \&\; \backslash cdots\; \&\; a\_\; \backslash \backslash \; \backslash vdots\; \&\; \backslash vdots\; \&\; \backslash ddots\; \&\; \backslash vdots\; \backslash \backslash \; a\_\; \&\; a\_\; \&\; \backslash cdots\; \&\; a\_\; \backslash \backslash \; \backslash end,\backslash quad\backslash mathbf=\backslash begin\; b\_\; \&\; b\_\; \&\; \backslash cdots\; \&\; b\_\; \backslash \backslash \; b\_\; \&\; b\_\; \&\; \backslash cdots\; \&\; b\_\; \backslash \backslash \; \backslash vdots\; \&\; \backslash vdots\; \&\; \backslash ddots\; \&\; \backslash vdots\; \backslash \backslash \; b\_\; \&\; b\_\; \&\; \backslash cdots\; \&\; b\_\; \backslash \backslash \; \backslash end$ the ''matrix product'' (denoted without multiplication signs or dots) is defined to be the matrix :$\backslash mathbf=\backslash begin\; c\_\; \&\; c\_\; \&\; \backslash cdots\; \&\; c\_\; \backslash \backslash \; c\_\; \&\; c\_\; \&\; \backslash cdots\; \&\; c\_\; \backslash \backslash \; \backslash vdots\; \&\; \backslash vdots\; \&\; \backslash ddots\; \&\; \backslash vdots\; \backslash \backslash \; c\_\; \&\; c\_\; \&\; \backslash cdots\; \&\; c\_\; \backslash \backslash \; \backslash end$ such that :$c\_\; =\; a\_b\_\; +\; a\_b\_\; +\backslash cdots\; +\; a\_b\_=\; \backslash 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 thedot 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
:$\backslash mathbf=\backslash begin\; a\_b\_\; +\backslash cdots\; +\; a\_b\_\; \&\; a\_b\_\; +\backslash cdots\; +\; a\_b\_\; \&\; \backslash cdots\; \&\; a\_b\_\; +\backslash cdots\; +\; a\_b\_\; \backslash \backslash \; a\_b\_\; +\backslash cdots\; +\; a\_b\_\; \&\; a\_b\_\; +\backslash cdots\; +\; a\_b\_\; \&\; \backslash cdots\; \&\; a\_b\_\; +\backslash cdots\; +\; a\_b\_\; \backslash \backslash \; \backslash vdots\; \&\; \backslash vdots\; \&\; \backslash ddots\; \&\; \backslash vdots\; \backslash \backslash \; a\_b\_\; +\backslash cdots\; +\; a\_b\_\; \&\; a\_b\_\; +\backslash cdots\; +\; a\_b\_\; \&\; \backslash cdots\; \&\; a\_b\_\; +\backslash cdots\; +\; a\_b\_\; \backslash \backslash \; \backslash 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 . :$\backslash overset\; \backslash overset\; =\; \backslash overset$ The values at the intersections marked with circles are: :$\backslash begin\; c\_\; \&\; =\; +\; \backslash \backslash \; c\_\; \&\; =\; +\; \backslash end$Fundamental applications

Historically, matrix multiplication has been introduced for facilitating and clarifying computations inlinear 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 ...

, 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 .
...

, 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 ...

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 avector 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 ...

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 ...

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 ...

from a vector space of dimension into a vector space of dimension maps a column vector
:$\backslash mathbf\; x=\backslash beginx\_1\; \backslash \backslash \; x\_2\; \backslash \backslash \; \backslash vdots\; \backslash \backslash \; x\_n\backslash end$
onto the column vector
:$\backslash mathbf\; y=\; A(\backslash mathbf\; x)=\; \backslash begina\_x\_1+\backslash cdots\; +\; a\_x\_n\backslash \backslash \; a\_x\_1+\backslash cdots\; +\; a\_x\_n\; \backslash \backslash \; \backslash vdots\; \backslash \backslash \; a\_x\_1+\backslash cdots\; +\; a\_x\_n\backslash end.$
The linear map is thus defined by the matrix
::$\backslash mathbf=\backslash begin\; a\_\; \&\; a\_\; \&\; \backslash cdots\; \&\; a\_\; \backslash \backslash \; a\_\; \&\; a\_\; \&\; \backslash cdots\; \&\; a\_\; \backslash \backslash \; \backslash vdots\; \&\; \backslash vdots\; \&\; \backslash ddots\; \&\; \backslash vdots\; \backslash \backslash \; a\_\; \&\; a\_\; \&\; \backslash cdots\; \&\; a\_\; \backslash \backslash \; \backslash end,$
and maps the column vector $\backslash mathbf\; x$ to the matrix product
:$\backslash mathbf\; y\; =\; \backslash 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 $\backslash mathbf\; B.$ A straightforward computation shows that the matrix of the composite map is the matrix product $\backslash mathbf\; .$ The general formula ) that defines the function composition is instanced here as a specific case of associativity of matrix product (see below):
:$(\backslash mathbf)\backslash mathbf\; x\; =\; \backslash mathbf(\backslash mathbf\; )\; =\; \backslash mathbf.$
System of linear equations

The general form of asystem 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
:$\backslash begina\_x\_1+\backslash cdots\; +\; a\_x\_n=b\_1\; \backslash \backslash \; a\_x\_1+\backslash cdots\; +\; a\_x\_n\; =b\_2\; \backslash \backslash \; \backslash vdots\; \backslash \backslash \; a\_x\_1+\backslash cdots\; +\; a\_x\_n\; =b\_m\backslash 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 ...

:$\backslash mathbf=\backslash mathbf\; b.$
Dot product, bilinear form and inner product

Thedot 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
:$\backslash mathbf\; x^\backslash mathsf\; T\; \backslash mathbf\; y,$
where $\backslash mathbf\; x^\backslash 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 $\backslash 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
:$\backslash mathbf\; x^\backslash mathsf\; T\; \backslash 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
:$\backslash mathbf\; x^\backslash dagger\; \backslash mathbf\; ,$
where $\backslash mathbf\; x^\backslash 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 $\backslash mathbf\; x$ (conjugate of the transpose, or equivalently transpose of the conjugate).
General properties

Matrix multiplication shares some properties with usualmultiplication
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 ...

. 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 iscommutative
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 $\backslash mathbf\backslash mathbf$ is defined, then $\backslash mathbf\backslash mathbf$ is also defined, and $\backslash mathbf\backslash mathbf=\backslash mathbf\backslash mathbf.$
If and are matrices of respective sizes and , then $\backslash mathbf\backslash mathbf$ is defined if , and $\backslash mathbf\backslash 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
:$\backslash mathbf\backslash mathbf\; \backslash neq\; \backslash mathbf\backslash mathbf.$
For example
:$\backslash begin\; 0\; \&\; 1\; \backslash \backslash \; 0\; \&\; 0\; \backslash end\backslash begin\; 0\; \&\; 0\; \backslash \backslash \; 1\; \&\; 0\; \backslash end=\backslash begin\; 1\; \&\; 0\; \backslash \backslash \; 0\; \&\; 0\; \backslash end,$
but
:$\backslash begin\; 0\; \&\; 0\; \backslash \backslash \; 1\; \&\; 0\; \backslash end\backslash begin\; 0\; \&\; 1\; \backslash \backslash \; 0\; \&\; 0\; \backslash end\; =\; \backslash begin\; 0\; \&\; 0\; \backslash \backslash \; 0\; \&\; 1\; \backslash 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 $\backslash mathbf\backslash mathbf\; =\; \backslash mathbf\backslash 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 ...

$\backslash mathbf=c\backslash ,\backslash 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 ...

. 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 tomatrix 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)
:$\backslash mathbf(\backslash mathbf\; +\; \backslash mathbf)\; =\; \backslash mathbf\; +\; \backslash mathbf,$
and (right distributivity)
:$(\backslash mathbf\; +\; \backslash mathbf\; )\backslash mathbf\; =\; \backslash mathbf\; +\; \backslash mathbf.$
This results from the distributivity for coefficients by
:$\backslash sum\_k\; a\_(b\_\; +\; c\_)\; =\; \backslash sum\_k\; a\_b\_\; +\; \backslash sum\_k\; a\_c\_$
:$\backslash sum\_k\; (b\_\; +\; c\_)\; d\_\; =\; \backslash sum\_k\; b\_d\_\; +\; \backslash sum\_k\; c\_d\_.$
Product with a scalar

If is a matrix and a scalar, then the matrices $c\backslash mathbf$ and $\backslash mathbfc$ are obtained by left or right multiplying all entries of by . If the scalars have thecommutative 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\backslash mathbf\; =\; \backslash mathbfc.$
If the product $\backslash mathbf$ is defined (that is, the number of columns of equals the number of rows of ), then
:$c(\backslash mathbf)\; =\; (c\; \backslash mathbf)\backslash mathbf$ and $(\backslash mathbf\; \backslash mathbf)c=\backslash mathbf(\backslash 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\; \backslash left(\backslash sum\_k\; a\_b\_\backslash right)\; =\; \backslash sum\_k\; (c\; a\_\; )\; b\_$
:$\backslash left(\backslash sum\_k\; a\_b\_\backslash right)\; c\; =\; \backslash sum\_k\; a\_\; (\; b\_c).$
Transpose

If the scalars have thecommutative 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 ...

of a product of matrices is the product, in the reverse order, of the transposes of the factors. That is
:$(\backslash mathbf)^\backslash mathsf\; =\; \backslash mathbf^\backslash mathsf\backslash mathbf^\backslash mathsf$
where Complex conjugate

If and havecomplex
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 ...

entries, then
:$(\backslash mathbf)^*\; =\; \backslash mathbf^*\backslash 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
:$(\backslash mathbf)^\backslash dagger\; =\; \backslash mathbf^\backslash dagger\backslash mathbf^\backslash 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 theassociative 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). ...

:$(\backslash mathbf)\backslash mathbf=\backslash mathbf(\backslash 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
:$\backslash prod\_^n\; \backslash mathbf\_i\; =\; \backslash mathbf\_1\backslash mathbf\_2\backslash cdots\backslash 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 ...

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 ...

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, seeMatrix 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\; \backslash log\; n).$
Application to similarity

Anyinvertible 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 ...

$\backslash mathbf$ defines a similarity transformation (on square matrices of the same size as $\backslash mathbf$)
:$S\_\backslash mathbf(\backslash mathbf)\; =\; \backslash mathbf^\; \backslash mathbf\; \backslash mathbf.$
Similarity transformations map product to products, that is
:$S\_\backslash mathbf(\backslash mathbf)\; =\; S\_\backslash mathbf(\backslash mathbf)S\_\backslash mathbf(\backslash mathbf).$
In fact, one has
:$\backslash mathbf^\; (\backslash mathbf)\; \backslash mathbf\; =\; \backslash mathbf^\; \backslash mathbf(\backslash mathbf\backslash mathbf^)\backslash mathbf\; \backslash mathbf\; =(\backslash mathbf^\; \backslash mathbf\backslash mathbf)(\backslash mathbf^\backslash mathbf\; \backslash mathbf).$
Square matrices

Let us denote $\backslash mathcal\; M\_n(R)$ the set ofsquare 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 $\backslash mathcal\; M\_n(R)$, the product is defined for every pair of matrices. This makes $\backslash 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 ...

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 ...

. 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
:$\backslash mathbf\backslash mathbf^\; =\; \backslash mathbf^\backslash mathbf\; =\; \backslash 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
:$(\backslash mathbf\backslash mathbf)^\; =\; \backslash mathbf^\backslash 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 ...

of a product is the product of the determinants. As determinants are scalars, and scalars commute, one has thus
:$\backslash det(\backslash mathbf)\; =\; \backslash det(\backslash mathbf)\; =\backslash det(\backslash mathbf)\backslash det(\backslash 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 ...

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, :$\backslash mathbf^0\; =\; \backslash mathbf,$ :$\backslash mathbf^1\; =\; \backslash mathbf,$ :$\backslash mathbf^k\; =\; \backslash 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 usingexponentiation 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 :
:$\backslash begin\; a\_\; \&\; 0\; \&\; \backslash cdots\; \&\; 0\; \backslash \backslash \; 0\; \&\; a\_\; \&\; \backslash cdots\; \&\; 0\; \backslash \backslash \; \backslash vdots\; \&\; \backslash vdots\; \&\; \backslash ddots\; \&\; \backslash vdots\; \backslash \backslash \; 0\; \&\; 0\; \&\; \backslash cdots\; \&\; a\_\; \backslash end^k\; =\; \backslash begin\; a\_^k\; \&\; 0\; \&\; \backslash cdots\; \&\; 0\; \backslash \backslash \; 0\; \&\; a\_^k\; \&\; \backslash cdots\; \&\; 0\; \backslash \backslash \; \backslash vdots\; \&\; \backslash vdots\; \&\; \backslash ddots\; \&\; \backslash vdots\; \backslash \backslash \; 0\; \&\; 0\; \&\; \backslash cdots\; \&\; a\_^k\; \backslash 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 betropical 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 ...

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 ...

, 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 ...

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 multiplicationalgorithm
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 ...

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^)\; \backslash 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 ...

.
Generalizations

Other types of products of matrices include: * * Cracovian product, defined as *Frobenius inner product, thedot 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 $\backslash mathbf\backslash mathbf^\backslash mathsf$
*Scalar multiplication
See also

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

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* Strassen, Volker, ''Gaussian Elimination is not Optimal'', Numer. Math. 13, p. 354-356, 1969. * * {{Linear algebra Matrix theory Bilinear operators Multiplication Numerical linear algebra