Matrix multiplication

We know how to add vectors and how to multiply them by scalars. Together, these operations give us the possibility of making linear combinations. Similarly, we know how to add matrices and how to multiply matrices by scalars. In this section we mix all these ideas together and produce an operation known as matrix multiplication. This will lead to some results that are both surprising and central. We begin with a definition of how to multiply a vector by a matrix.

1. \begin{bmatrix} 2 & 3 & -1 & 0\\ 1 & -2 & 7 & 3\\ 1 & 5 & 3 & 2\\ \end{bmatrix} &&\text{with}&& \colvector{2\\-3\\0\\5}
2. \begin{bmatrix} 2 & 3 & -1 & 0\\ 1 & -2 & 7 & 3\\ 1 & 5 & 3 & 2\\ \end{bmatrix} && \begin{bmatrix} 2 & 6\\ -3 & -4\\ 0 & 2\\ 3 & -1\\ \end{bmatrix}
3. 2x_1 + 3x_2 - x_3 &= 0\\ x_1 + 2x_2 + x_3 &= 3\\ x_1 + 3x_2 + 3x_3 &= 7

We have repeatedly seen the importance of forming linear combinations of the columns of a matrix. As one example of this, the oft-used , said that every solution to a system of linear equations gives rise to a linear combination of the column vectors of the coefficient matrix that equals the vector of constants. This theorem, and others, motivate the following central definition.

So, the matrix-vector product is yet another version of multiplication, at least in the sense that we have yet again overloaded juxtaposition of two symbols as our notation. Remember your objects, an $m\times n$ matrix times a vector of size $n$ will create a vector of size $m$. So if $A$ is rectangular, then the size of the vector changes. With all the linear combinations we have performed so far, this computation should now seem second nature.

We can now represent systems of linear equations compactly with a matrix-vector product () and column vector equality (). This finally yields a very popular alternative to our unconventional $\linearsystem{A}{\vect{b}}$ notation.

Condensed: the full section is in Beezer, A First Course in Linear Algebra.

We now define how to multiply two matrices together. Stop for a minute and think about how you might define this new operation.

Many books would present this definition much earlier in the course. However, we have taken great care to delay it as long as possible and to present as many ideas as practical based mostly on the notion of linear combinations. Towards the conclusion of the course, or when you perhaps take a second course in linear algebra, you may be in a position to appreciate the reasons for this. For now, understand that matrix multiplication is a central definition and perhaps you will appreciate its importance more by having saved it for later.

Is this the definition of matrix multiplication you expected? Perhaps our previous operations for matrices caused you to think that we might multiply two matrices of the same size, entry-by-entry? Notice that our current definition uses matrices of different sizes (though the number of columns in the first must equal the number of rows in the second), and the result is of a third size. Notice too in the previous example that we cannot even consider the product $BA$, since the sizes of the two matrices in this order are not right.

But it gets weirder than that. Many of your old ideas about multiplication will not apply to matrix multiplication, but some still will. So make no assumptions, and do not do anything until you have a theorem that says you can. Even if the sizes are right, matrix multiplication is not commutative order matters.

Condensed: the full section is in Beezer, A First Course in Linear Algebra.

While certain natural properties of multiplication do not hold, many more do. In the next subsection, we will state and prove the relevant theorems. But first, we need a theorem that provides an alternate means of multiplying two matrices. In many texts, this would be given as the definition of matrix multiplication. We prefer to turn it around and have the following formula as a consequence of our definition. It will prove useful for proofs of matrix equality, where we need to examine products of matrices, entry-by-entry.

is the way many people compute matrix products by hand. It will also be very useful for the theorems we are going to prove shortly. However, the definition () is frequently the most useful for its connections with deeper ideas like the null space and the upcoming column space.

Condensed: the full section is in Beezer, A First Course in Linear Algebra.

In this subsection, we collect properties of matrix multiplication and its interaction with the zero matrix (), the identity matrix (), matrix addition (), scalar matrix multiplication (), the inner product (), conjugation (), and the transpose (). Whew! Here we go. These are great proofs to practice with, so try to concoct the proofs before reading them, they will get progressively more complicated as we go.

It is this theorem that gives the identity matrix its name. It is a matrix that behaves with matrix multiplication like the scalar 1 does with scalar multiplication. To multiply by the identity matrix is to have no effect on the other matrix.

Since says matrix multipication is associative, it means we do not have to be careful about the order in which we perform matrix multiplication, nor how we parenthesize an expression with just several matrices multiplied togther. So this is where we draw the line on explaining every last detail in a proof. We will frequently add, remove, or rearrange parentheses with no comment. Indeed, I only see about a dozen places where is cited in a proof. You could try to count how many times we avoid making a reference to this theorem.

Condensed: the full section is in Beezer, A First Course in Linear Algebra.

The adjoint of a matrix has a basic property when employed in a matrix-vector product as part of an inner product. At this point, you could even use the following result as a motivation for the definition of an adjoint.

Sometimes a matrix is equal to its adjoint (), and these matrices have interesting properties. One of the most common situations where this occurs is when a matrix has only real number entries. Then we are simply talking about symmetric matrices (), so you can view this as a generalization of a symmetric matrix.

Again, the set of real matrices that are Hermitian is exactly the set of symmetric matrices. In we will uncover some amazing properties of Hermitian matrices, so when you get there, run back here to remind yourself of this definition. Further properties will also appear in . Right now we prove a fundamental result about Hermitian matrices, matrix vector products and inner products. As a characterization, this could be employed as a definition of a Hermitian matrix and some authors take this approach.

So, informally, Hermitian matrices are those that can be tossed around from one side of an inner product to the other with reckless abandon. We will see later what this buys us.

Condensed: the full section is in Beezer, A First Course in Linear Algebra.

In mathematics, specifically in linear algebra, matrix multiplication is a binary operation that produces a matrix 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 A and B is denoted as AB.

Matrix multiplication was first described by the French mathematician Jacques Philippe Marie Binet in 1812, to represent the composition of linear maps that are represented by matrices. Matrix multiplication is thus a basic tool of linear algebra, and as such has numerous applications in many areas of mathematics, as well as in applied mathematics, statistics, physics, economics, and engineering. Computing matrix products is a central operation in all computational applications of linear algebra.

This article will use the following notational conventions: matrices are represented by capital letters in bold, e.g. A; vectors in lowercase bold, e.g. a; and entries of vectors and matrices are italic (they are numbers from a field), e.g. A and a. Index notation is often the clearest way to express definitions, and is used as standard in the literature. The entry in row i, column j of matrix A is indicated by (A)_ij, A_ij or a_ij. In contrast, a single subscript, e.g. A₁, A₂, is used to select a matrix (not a matrix entry) from a collection of matrices.

If A is an m × n matrix and B is an n × p matrix, \[\mathbf{A}=\begin{pmatrix} a_{11} & a_{12} & \cdots & a_{1n} \\ a_{21} & a_{22} & \cdots & a_{2n} \\ \vdots & \vdots & \ddots & \vdots \\ a_{m1} & a_{m2} & \cdots & a_{mn} \\ \end{pmatrix},\quad\mathbf{B}=\begin{pmatrix} b_{11} & b_{12} & \cdots & b_{1p} \\ b_{21} & b_{22} & \cdots & b_{2p} \\ \vdots & \vdots & \ddots & \vdots \\ b_{n1} & b_{n2} & \cdots & b_{np} \\ \end{pmatrix}\] the matrix product C = AB (denoted without multiplication signs or dots) is defined to be the m × p matrix \[\mathbf{C} = \begin{pmatrix} c_{11} & c_{12} & \cdots & c_{1p} \\ c_{21} & c_{22} & \cdots & c_{2p} \\ \vdots & \vdots & \ddots & \vdots \\ c_{m1} & c_{m2} & \cdots & c_{mp} \\ \end{pmatrix}\] such that \[c_{ij} = a_{i1} b_{1j} + a_{i2} b_{2j} + \cdots + a_{in} b_{nj} = \sum_{k=1}^n a_{ik} b_{kj},\] for i = 1, ..., m and j = 1, ..., p.

That is, the entry ⁠\(c_{ij}\)⁠ of the product is obtained by multiplying term-by-term the entries of the ith row of A and the jth column of B, and summing these n products. In other words, ⁠\(c_{ij}\)⁠ is the dot product of the ith row of A and the jth column of B.

Therefore, AB can also be written as \[\mathbf{C} = \begin{pmatrix} a_{11}b_{11} +\cdots + a_{1n}b_{n1} & a_{11}b_{12} +\cdots + a_{1n}b_{n2} & \cdots & a_{11}b_{1p} +\cdots + a_{1n}b_{np} \\ a_{21}b_{11} +\cdots + a_{2n}b_{n1} & a_{21}b_{12} +\cdots + a_{2n}b_{n2} & \cdots & a_{21}b_{1p} +\cdots + a_{2n}b_{np} \\ \vdots & \vdots & \ddots & \vdots \\ a_{m1}b_{11} +\cdots + a_{mn}b_{n1} & a_{m1}b_{12} +\cdots + a_{mn}b_{n2} & \cdots & a_{m1}b_{1p} +\cdots + a_{mn}b_{np} \\ \end{pmatrix}\]

Thus the product AB is defined if and only if the number of columns in A equals the number of rows in B, in this case n.

In most scenarios, the entries are numbers, but they may be any kind of mathematical objects for which an addition and a multiplication are defined, that are associative, and such that the addition is commutative, and the multiplication is distributive with respect to the addition. In particular, the entries may be matrices themselves (see block matrix).

A vector \(\mathbf x\) of length \(n\) can be viewed as a column vector, corresponding to an \(n\times1\) matrix \(\mathbf X\) whose entries are given by \(\mathbf X_{i1}=\mathbf x_i.\) If \(\mathbf A\) is an \(m\times n\) matrix, the matrix-times-vector product denoted by \(\mathbf {Ax}\) is then the vector \(\mathbf y\) that, viewed as a column vector, is equal to the \(m\times1\) matrix \(\mathbf{AX}.\) In index notation, this amounts to:

\(y_i=\sum_{j=1}^n a_{ij}x_j.\)

One way of looking at this is that the changes from "plain" vector to column vector and back are assumed and left implicit.

Similarly, a vector \(\mathbf x\) of length \(n\) can be viewed as a row vector, corresponding to a \(1\times n\) matrix. To make it clear that a row vector is meant, it is customary in this context to represent it as the transpose of a column vector; thus, one will see notations such as \(\mathbf{x}^\mathrm{T}\mathbf{A}.\) The identity \(\mathbf{x}^\mathrm{T}\mathbf{A}=(\mathbf{A}^\mathrm{T}\mathbf{x})^\mathrm{T}\) holds. In index notation, if \(\mathbf A\) is an \(n\times p\) matrix, \(\mathbf{x}^\mathrm{T}\mathbf{A}=\mathbf{y}^\mathrm{T}\) amounts to: \(y_k=\sum_{j=1}^n x_j a_{jk}.\)

A vector with n components can be represented as a 1 × n matrix (a row-vector) or as a n × 1 matrix (a column-vector). Assuming that \(\mathbf a\) and \(\mathbf b\) are both column-vectors the dot product (or inner product) \(\mathbf a\cdot\mathbf b\) is equal to the single entry of the \(1\times 1\) matrix resulting from the matrix multiplication of the row-vector \(\mathbf{a}^\mathrm{T}\) with the column-vector \(\mathbf{b}\), i.e. \(\mathbf{a}^\mathrm{T}\mathbf{b}\).

The matrix multiplication between the column-vector \(\mathbf{a}\) and the row-vector \(\mathbf{b}^\mathrm{T}\), also known as outer-product \(\mathbf{a}\mathbf{b}^\mathrm{T}\), will, instead, give a n × n matrix.

The figure to the right illustrates diagrammatically the product of two matrices A and B, showing how each intersection in the product matrix corresponds to a row of A and a column of B. \[\overset{4\times 2 \text{ matrix}}{\begin{bmatrix} a_{11} & a_{12} \\ \cdot & \cdot \\ a_{31} & a_{32} \\ \cdot & \cdot \\ \end{bmatrix}} \overset{2\times 3\text{ matrix}}{\begin{bmatrix} \cdot & b_{12} & b_{13} \\ \cdot & b_{22} & b_{23} \\ \end{bmatrix}} = \overset{4\times 3\text{ matrix}}{\begin{bmatrix} \cdot & c_{12} & \cdot \\ \cdot & \cdot & \cdot \\ \cdot & \cdot & c_{33} \\ \cdot & \cdot & \cdot \\ \end{bmatrix}}\]

The values at the intersections, marked with circles in figure to the right, are: \[\begin{aligned} c_{12} & = a_{11} b_{12} + a_{12} b_{22} \\ c_{33} & = a_{31} b_{13} + a_{32} b_{23} . \end{aligned}\]

Historically, matrix multiplication has been introduced for facilitating and clarifying computations in linear algebra. This strong relationship between matrix multiplication and linear algebra remains fundamental in all mathematics, as well as in physics, chemistry, engineering and computer science.

If a vector space has a finite basis, its vectors are each uniquely represented by a finite sequence of scalars, called a coordinate vector, whose elements are the coordinates of the vector on the basis. These coordinate vectors form another vector space, which is isomorphic to the original vector space. A coordinate vector is commonly organized as a column matrix (also called a 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 A from a vector space of dimension n into a vector space of dimension m maps a column vector

\(\mathbf x=\begin{pmatrix}x_1 \\ x_2 \\ \vdots \\ x_n\end{pmatrix}\)

onto the column vector

\(\mathbf y= A(\mathbf x)= \begin{pmatrix}a_{11}x_1+\cdots + a_{1n}x_n\\ a_{21}x_1+\cdots + a_{2n}x_n \\ \vdots \\ a_{m1}x_1+\cdots + a_{mn}x_n\end{pmatrix}.\)

The linear map A is thus defined by the matrix

\(\mathbf{A}=\begin{pmatrix} a_{11} & a_{12} & \cdots & a_{1n} \\ a_{21} & a_{22} & \cdots & a_{2n} \\ \vdots & \vdots & \ddots & \vdots \\ a_{m1} & a_{m2} & \cdots & a_{mn} \\ \end{pmatrix},\)

and maps the column vector \(\mathbf x\) to the matrix product

\(\mathbf y = \mathbf {Ax}.\)

If B is another linear map from the preceding vector space of dimension m, into a vector space of dimension p, it is represented by a ⁠\(p\times m\)⁠ matrix \(\mathbf B.\) A straightforward computation shows that the matrix of the composite map ⁠\(B\circ A\)⁠ is the matrix product \(\mathbf {BA}.\) The general formula ⁠\((B\circ A)(\mathbf x) = B(A(\mathbf x))\)⁠) that defines the function composition is instanced here as a specific case of associativity of matrix product (see § Associativity below):

\((\mathbf{BA})\mathbf x = \mathbf{B}(\mathbf {Ax}) = \mathbf{BAx}.\)

The general form of a system of linear equations is

\(\begin{matrix}a_{11}x_1+\cdots + a_{1n}x_n=b_1, \\ a_{21}x_1+\cdots + a_{2n}x_n =b_2, \\ \vdots \\ a_{m1}x_1+\cdots + a_{mn}x_n =b_m. \end{matrix}\)

Using same notation as above, such a system is equivalent with the single matrix equation

\(\mathbf{Ax}=\mathbf b.\)

The dot product of two column vectors is the unique entry of the matrix product

\(\mathbf x^\mathsf T \mathbf y,\)

where \(\mathbf x^\mathsf T\) is the row vector obtained by transposing \(\mathbf x\). (As usual, a 1×1 matrix is identified with its unique entry.)

More generally, any bilinear form over a vector space of finite dimension may be expressed as a matrix product

\(\mathbf x^\mathsf T \mathbf {Ay},\)

and any sesquilinear form may be expressed as

\(\mathbf x^\dagger \mathbf {Ay},\)

where \(\mathbf x^\dagger\) denotes the conjugate transpose of \(\mathbf x\) (conjugate of the transpose, or equivalently transpose of the conjugate).

Matrix multiplication shares some properties with usual 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, even when the product remains defined after changing the order of the factors.

An operation is commutative if, given two elements A and B such that the product \(\mathbf{A}\mathbf{B}\) is defined, then \(\mathbf{B}\mathbf{A}\) is also defined, and \(\mathbf{A}\mathbf{B}=\mathbf{B}\mathbf{A}.\)

If A and B are matrices of respective sizes ⁠\(m\times n\)⁠ and ⁠\(p\times q\)⁠, then \(\mathbf{A}\mathbf{B}\) is defined if ⁠\(n=p\)⁠, and \(\mathbf{B}\mathbf{A}\) is defined if ⁠\(m=q\)⁠. Therefore, if one of the products is defined, the other one need not be defined. If ⁠\(m=q\neq n=p\)⁠, the two products are defined, but have different sizes; thus they cannot be equal. Only if ⁠\(m=q= n=p\)⁠, that is, if A and B are square matrices of the same size, are both products defined and of the same size. Even in this case, one has in general

\(\mathbf{A}\mathbf{B} \neq \mathbf{B}\mathbf{A}.\)

For example

\(\begin{pmatrix} 0 & 1 \\ 0 & 0 \end{pmatrix}\begin{pmatrix} 0 & 0 \\ 1 & 0 \end{pmatrix}=\begin{pmatrix} 1 & 0 \\ 0 & 0 \end{pmatrix},\)

but

\(\begin{pmatrix} 0 & 0 \\ 1 & 0 \end{pmatrix}\begin{pmatrix} 0 & 1 \\ 0 & 0 \end{pmatrix} = \begin{pmatrix} 0 & 0 \\ 0 & 1 \end{pmatrix}.\)

This example may be expanded for showing that, if A is a ⁠\(n\times n\)⁠ matrix with entries in a field F, then \(\mathbf{A}\mathbf{B} = \mathbf{B}\mathbf{A}\) for every ⁠\(n\times n\)⁠ matrix B with entries in F, if and only if \(\mathbf{A}=c\,\mathbf{I}\) where ⁠\(c\in F\)⁠, and I is the ⁠\(n\times n\)⁠ identity matrix. If, instead of a field, the entries are supposed to belong to a ring, then one must add the condition that c belongs to the center of the ring.

One special case where commutativity does occur is when D and E are two (square) diagonal matrices (of the same size); then DE = ED. 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.

The matrix product is distributive with respect to matrix addition. That is, if A, B, C, D are matrices of respective sizes m × n, n × p, n × p, and p × q, respectively, one has (left distributivity)

\(\mathbf{A}(\mathbf{B} + \mathbf{C}) = \mathbf{AB} + \mathbf{AC},\)

and (right distributivity)

\((\mathbf{B} + \mathbf{C} )\mathbf{D} = \mathbf{BD} + \mathbf{CD}.\)

This results from the distributivity for coefficients by

\(\sum_k a_{ik}(b_{kj} + c_{kj}) = \sum_k a_{ik}b_{kj} + \sum_k a_{ik}c_{kj}\)

\(\sum_k (b_{ik} + c_{ik}) d_{kj} = \sum_k b_{ik}d_{kj} + \sum_k c_{ik}d_{kj}.\)