6 Matrix Algebra and Matrix Multiplication

6.1 Opening question

In the first three chapters, matrices appeared as containers for linear systems. But matrices are much more than storage devices.

A matrix can also represent a process:

\[ x \longmapsto Ax. \]

If one matrix represents one process and another matrix represents another process, then matrix multiplication represents doing one process after another.

This chapter develops the algebra of matrices:

matrix-vector multiplication,
matrix-matrix multiplication,
row-column computation,
column interpretation,
block interpretation,
matrix powers,
diagonal and triangular matrices,
and the noncommutative nature of matrix multiplication.

The key idea is:

Matrix multiplication is the algebra of composition.

6.2 Learning goals

After studying this chapter, you should be able to:

Determine when a matrix product is defined.
Compute matrix-vector and matrix-matrix products.
Interpret matrix multiplication by rows, columns, and transformations.
Understand why matrix multiplication is usually not commutative.
Use identity and zero matrices correctly.
Compute powers of square matrices.
Work with diagonal, upper triangular, and lower triangular matrices.
Use block matrix multiplication in simple cases.
Understand matrix multiplication as composition of linear processes.
Use Python to compute and experiment with matrix products.

6.3 4.1 Matrix-vector multiplication revisited

Let

\[ A= \begin{bmatrix} 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{bmatrix} \]

and

\[ x= \begin{bmatrix} x_1\\ x_2\\ \vdots\\ x_n \end{bmatrix}. \]

Then

\[ Ax= \begin{bmatrix} a_{11}x_1+a_{12}x_2+\cdots+a_{1n}x_n\\ a_{21}x_1+a_{22}x_2+\cdots+a_{2n}x_n\\ \vdots\\ a_{m1}x_1+a_{m2}x_2+\cdots+a_{mn}x_n \end{bmatrix}. \]

If \(A\) is \(m\times n\) and \(x\) is \(n\times 1\), then

\[ Ax \]

is an \(m\times 1\) vector.

In dimensions,

\[ \underbrace{A}_{m\times n} \underbrace{x}_{n\times 1} = \underbrace{Ax}_{m\times 1}. \]

6.4 4.2 Matrix multiplication by columns

Suppose \(B\) has columns

\[ B= \begin{bmatrix} |&|&&|\\ b_1&b_2&\cdots&b_p\\ |&|&&| \end{bmatrix}. \]

Then the product \(AB\) is defined by multiplying \(A\) by each column of \(B\):

\[ AB= \begin{bmatrix} |&|&&|\\ Ab_1&Ab_2&\cdots&Ab_p\\ |&|&&| \end{bmatrix}. \]

This is often the cleanest way to understand matrix multiplication.

If \(A\) is \(m\times n\) and \(B\) is \(n\times p\), then every column \(b_j\) of \(B\) is in \(\mathbb{R}^n\), so \(Ab_j\) is in \(\mathbb{R}^m\). Therefore \(AB\) is \(m\times p\).

In dimensions,

\[ \underbrace{A}_{m\times n} \underbrace{B}_{n\times p} = \underbrace{AB}_{m\times p}. \]

Dimension rule

The product \(AB\) is defined exactly when the number of columns of \(A\) equals the number of rows of \(B\).

6.5 4.3 Row-column formula

The entry in row \(i\), column \(j\) of \(AB\) is the dot product of row \(i\) of \(A\) with column \(j\) of \(B\).

\[ C=AB, \]

then

\[ c_{ij}=a_{i1}b_{1j}+a_{i2}b_{2j}+\cdots+a_{in}b_{nj}. \]

Equivalently,

\[ c_{ij}=\sum_{k=1}^n a_{ik}b_{kj}. \]

This formula is important, but do not memorize it without meaning. It says:

row of \(A\) times column of \(B\) gives one entry of \(AB\).

6.6 4.4 First example

Let

\[ A= \begin{bmatrix} 1&2\\ 3&4 \end{bmatrix}, \qquad B= \begin{bmatrix} 2&1\\ 0&-1 \end{bmatrix}. \]

Then

\[ AB= \begin{bmatrix} 1(2)+2(0)&1(1)+2(-1)\\ 3(2)+4(0)&3(1)+4(-1) \end{bmatrix} = \begin{bmatrix} 2&-1\\ 6&-1 \end{bmatrix}. \]

Now compute \(BA\):

\[ BA= \begin{bmatrix} 2&1\\ 0&-1 \end{bmatrix} \begin{bmatrix} 1&2\\ 3&4 \end{bmatrix} = \begin{bmatrix} 2(1)+1(3)&2(2)+1(4)\\ 0(1)+(-1)(3)&0(2)+(-1)(4) \end{bmatrix} = \begin{bmatrix} 5&8\\ -3&-4 \end{bmatrix}. \]

\[ AB\ne BA. \]

This is one of the most important differences between matrix algebra and ordinary number algebra.

6.7 4.5 Matrix multiplication is not commutative

For real numbers,

\[ ab=ba. \]

For matrices, usually

\[ AB\ne BA. \]

Sometimes \(AB\) and \(BA\) are both defined but unequal.

Sometimes \(AB\) is defined but \(BA\) is not.

6.7.1 Example where one product is defined but the other is not

Let

\[ A= \begin{bmatrix} 1&2&3\\ 4&5&6 \end{bmatrix} \]

and

\[ B= \begin{bmatrix} 1\\ 0\\ -1 \end{bmatrix}. \]

Then \(A\) is \(2\times 3\) and \(B\) is \(3\times 1\), so

\[ AB \]

is defined and has size \(2\times 1\).

But

\[ BA \]

would require multiplying a \(3\times 1\) matrix by a \(2\times 3\) matrix. The inner dimensions \(1\) and \(2\) do not match, so \(BA\) is not defined.

Common mistake

Do not write \(AB=BA\) unless you have checked it. Matrix multiplication is not usually commutative.

6.8 4.6 Identity matrices

The identity matrix acts like the number \(1\).

If \(A\) is \(m\times n\), then

\[ I_mA=A \]

and

\[ AI_n=A. \]

The sizes matter:

\(I_m\) goes on the left of \(A\),
\(I_n\) goes on the right of \(A\).

Example:

\[ I_2 \begin{bmatrix} 1&2&3\\ 4&5&6 \end{bmatrix} = \begin{bmatrix} 1&2&3\\ 4&5&6 \end{bmatrix}, \]

and

\[ \begin{bmatrix} 1&2&3\\ 4&5&6 \end{bmatrix} I_3 = \begin{bmatrix} 1&2&3\\ 4&5&6 \end{bmatrix}. \]

6.9 4.7 Zero matrices

If sizes are compatible, multiplying by a zero matrix gives a zero matrix:

\[ A0=0, \]

\[ 0A=0. \]

Again, the sizes must match.

For example, if \(A\) is \(2\times 3\), then

\[ A0_{3\times 4}=0_{2\times 4}. \]

The output size is determined by the outside dimensions.

6.10 4.8 Algebraic rules for matrix products

When the dimensions are compatible, matrix multiplication satisfies:

6.10.1 Associativity

\[ (AB)C=A(BC). \]

This is very important. It means we may write

\[ ABC \]

without ambiguity.

6.10.2 Distributivity

\[ A(B+C)=AB+AC, \]

and

\[ (A+B)C=AC+BC. \]

6.10.3 Scalar compatibility

For a scalar \(c\),

\[ c(AB)=(cA)B=A(cB). \]

6.10.4 Not usually commutative

Usually,

\[ AB\ne BA. \]

6.11 4.9 Matrix powers

If \(A\) is square, then powers of \(A\) are defined:

\[ A^2=AA, \]

\[ A^3=AAA, \]

and in general,

\[ A^k=\underbrace{AA\cdots A}_{k\text{ times}}. \]

Matrix powers represent repeated application of the same linear process.

For example, if

\[ x_{t+1}=Ax_t, \]

then

\[ x_1=Ax_0, \]

\[ x_2=Ax_1=A^2x_0, \]

and

\[ x_k=A^kx_0. \]

This idea will return in the chapters on eigenvalues, diagonalization, Markov chains, and dynamical systems.

6.12 4.10 Example: powers of a diagonal matrix

Let

\[ D= \begin{bmatrix} 2&0\\ 0&3 \end{bmatrix}. \]

Then

\[ D^2= \begin{bmatrix} 4&0\\ 0&9 \end{bmatrix}, \]

and

\[ D^3= \begin{bmatrix} 8&0\\ 0&27 \end{bmatrix}. \]

In general,

\[ D^k= \begin{bmatrix} 2^k&0\\ 0&3^k \end{bmatrix}. \]

Diagonal matrices are easy to power because each coordinate is scaled independently.

6.13 4.11 Diagonal matrices

A diagonal matrix has the form

\[ D= \begin{bmatrix} d_1&0&\cdots&0\\ 0&d_2&\cdots&0\\ \vdots&\vdots&\ddots&\vdots\\ 0&0&\cdots&d_n \end{bmatrix}. \]

Multiplying by \(D\) scales the coordinates:

\[ D \begin{bmatrix} x_1\\ x_2\\ \vdots\\ x_n \end{bmatrix} = \begin{bmatrix} d_1x_1\\ d_2x_2\\ \vdots\\ d_nx_n \end{bmatrix}. \]

Thus diagonal matrices are computationally simple and geometrically meaningful.

They stretch or shrink along coordinate axes.

6.14 4.12 Upper and lower triangular matrices

An \(n\times n\) matrix is upper triangular if all entries below the main diagonal are zero.

Example:

\[ U= \begin{bmatrix} 2&1&4\\ 0&3&-1\\ 0&0&5 \end{bmatrix}. \]

An \(n\times n\) matrix is lower triangular if all entries above the main diagonal are zero.

Example:

\[ L= \begin{bmatrix} 2&0&0\\ 1&3&0\\ 4&-1&5 \end{bmatrix}. \]

Triangular matrices are important because triangular systems are easy to solve.

For an upper triangular system, we use back substitution.

For a lower triangular system, we use forward substitution.

6.15 4.13 Example: upper triangular system

Solve

\[ \begin{cases} x_1+2x_2-x_3=4,\\ x_2+3x_3=5,\\ x_3=1. \end{cases} \]

Start from the bottom:

\[ x_3=1. \]

Then

\[ x_2+3(1)=5, \]

\[ x_2=2. \]

Finally,

\[ x_1+2(2)-1=4, \]

\[ x_1=1. \]

Thus

\[ (x_1,x_2,x_3)=(1,2,1). \]

Triangular structure makes the solution straightforward.

6.16 4.14 Matrix multiplication as composition

Suppose

\[ T(x)=Bx \]

and

\[ S(y)=Ay. \]

If we first apply \(T\) and then apply \(S\), we get

\[ S(T(x))=A(Bx). \]

By associativity,

\[ A(Bx)=(AB)x. \]

Therefore the matrix of the combined transformation is

\[ AB. \]

This explains the order of multiplication:

\(AB\) means first apply \(B\), then apply \(A\).

Order matters

In the product \(ABx\), the vector \(x\) is first multiplied by \(B\), then the result is multiplied by \(A\).

6.17 4.15 Geometric example: reflection and projection

Let

\[ P= \begin{bmatrix} 1&0\\ 0&0 \end{bmatrix} \]

be projection onto the \(x\)-axis, and let

\[ R= \begin{bmatrix} 1&0\\ 0&-1 \end{bmatrix} \]

be reflection across the \(x\)-axis.

Then

\[ PR= \begin{bmatrix} 1&0\\ 0&0 \end{bmatrix} \begin{bmatrix} 1&0\\ 0&-1 \end{bmatrix} = \begin{bmatrix} 1&0\\ 0&0 \end{bmatrix} =P. \]

Also,

\[ RP= \begin{bmatrix} 1&0\\ 0&-1 \end{bmatrix} \begin{bmatrix} 1&0\\ 0&0 \end{bmatrix} = \begin{bmatrix} 1&0\\ 0&0 \end{bmatrix} =P. \]

In this special case,

\[ PR=RP. \]

Why? Projecting onto the \(x\)-axis removes the \(y\)-component, and reflecting across the \(x\)-axis only changes the \(y\)-component. Once the \(y\)-component is gone, reflection has no visible effect.

Not all geometric transformations commute.

6.18 4.16 Geometric example: rotation and projection do not commute

Let

\[ P= \begin{bmatrix} 1&0\\ 0&0 \end{bmatrix} \]

be projection onto the \(x\)-axis, and let

\[ Q= \begin{bmatrix} 0&-1\\ 1&0 \end{bmatrix} \]

be counterclockwise rotation by \(90^\circ\).

Compute

\[ PQ= \begin{bmatrix} 1&0\\ 0&0 \end{bmatrix} \begin{bmatrix} 0&-1\\ 1&0 \end{bmatrix} = \begin{bmatrix} 0&-1\\ 0&0 \end{bmatrix}. \]

But

\[ QP= \begin{bmatrix} 0&-1\\ 1&0 \end{bmatrix} \begin{bmatrix} 1&0\\ 0&0 \end{bmatrix} = \begin{bmatrix} 0&0\\ 1&0 \end{bmatrix}. \]

Thus

\[ PQ\ne QP. \]

The order of operations matters:

\(PQ\) means rotate first, then project.
\(QP\) means project first, then rotate.

These produce different results.

6.19 4.17 Block matrix multiplication

Sometimes a large matrix can be divided into smaller blocks.

For example,

\[ A= \begin{bmatrix} A_{11}&A_{12}\\ A_{21}&A_{22} \end{bmatrix}, \qquad B= \begin{bmatrix} B_{11}&B_{12}\\ B_{21}&B_{22} \end{bmatrix}. \]

If the block sizes are compatible, then

\[ AB= \begin{bmatrix} A_{11}B_{11}+A_{12}B_{21}&A_{11}B_{12}+A_{12}B_{22}\\ A_{21}B_{11}+A_{22}B_{21}&A_{21}B_{12}+A_{22}B_{22} \end{bmatrix}. \]

This looks like ordinary \(2\times 2\) multiplication, but each entry is a block.

Block multiplication is useful in computation because large matrices are often processed in pieces.

6.20 4.18 Computational cost

If \(A\) is \(m\times n\) and \(B\) is \(n\times p\), then computing \(AB\) directly requires many multiplications and additions.

There are \(mp\) entries in \(AB\). Each entry requires about \(n\) multiplications and additions.

So the direct cost is approximately proportional to

\[ mnp. \]

For large matrices, matrix multiplication can be expensive. Modern numerical linear algebra studies how to perform these computations accurately and efficiently.

In AI and data science, large matrix multiplications are everywhere. They are the basic computational operation behind neural network layers, linear regression, PCA, attention mechanisms, and many optimization algorithms.

6.21 4.19 Python: matrix multiplication

import numpy as np

A = np.array([
    [1, 2],
    [3, 4]
], dtype=float)

B = np.array([
    [2, 1],
    [0, -1]
], dtype=float)

A @ B

array([[ 2., -1.],
       [ 6., -1.]])

The symbol @ is Python’s matrix multiplication operator.

Now compare with \(BA\):

B @ A

array([[ 5.,  8.],
       [-3., -4.]])

Usually the results are different.

6.22 4.20 Python: dimension compatibility

A = np.array([
    [1, 2, 3],
    [4, 5, 6]
], dtype=float)

x = np.array([1, 0, -1], dtype=float)

A @ x

array([-2., -2.])

This works because \(A\) is \(2\times 3\) and \(x\) has \(3\) entries.

Now try a vector with the wrong size:

y = np.array([1, 0], dtype=float)

# Uncomment the next line to see the dimension mismatch error.
# A @ y

The product is not defined because the inner dimensions do not match.

6.23 4.21 Python: powers of a matrix

A = np.array([
    [1, 1],
    [1, 0]
], dtype=float)

A2 = A @ A
A3 = A @ A @ A

A2, A3

(array([[2., 1.],
        [1., 1.]]),
 array([[3., 2.],
        [2., 1.]]))

For repeated powers, NumPy provides:

np.linalg.matrix_power(A, 5)

array([[8., 5.],
       [5., 3.]])

This is useful for repeated processes.

6.24 4.22 Python: repeated dynamics

Consider the recurrence

\[ x_{t+1}=Ax_t, \]

where

\[ A= \begin{bmatrix} 0.8&0.3\\ 0.2&0.7 \end{bmatrix}. \]

Start with

\[ x_0= \begin{bmatrix} 100\\ 0 \end{bmatrix}. \]

A = np.array([
    [0.8, 0.3],
    [0.2, 0.7]
], dtype=float)

x = np.array([100, 0], dtype=float)

history = [x]

for k in range(10):
    x = A @ x
    history.append(x)

np.array(history)

array([[100.       ,   0.       ],
       [ 80.       ,  20.       ],
       [ 70.       ,  30.       ],
       [ 65.       ,  35.       ],
       [ 62.5      ,  37.5      ],
       [ 61.25     ,  38.75     ],
       [ 60.625    ,  39.375    ],
       [ 60.3125   ,  39.6875   ],
       [ 60.15625  ,  39.84375  ],
       [ 60.078125 ,  39.921875 ],
       [ 60.0390625,  39.9609375]])

This kind of model appears in population movement, Markov chains, ranking algorithms, and dynamical systems. We will return to it later with eigenvalues.

6.25 4.23 Common mistakes

6.25.1 Mistake 1: multiplying entry by entry

Matrix multiplication is not entrywise multiplication.

In general,

\[ AB \]

is not obtained by multiplying corresponding entries.

6.25.2 Mistake 2: ignoring dimensions

Always check the inner dimensions:

\[ (m\times n)(n\times p)=(m\times p). \]

6.25.3 Mistake 3: assuming \(AB=BA\)

Matrix multiplication is usually not commutative.

6.25.4 Mistake 4: reversing composition order

The product \(ABx\) means \(B\) acts first, then \(A\) acts.

6.25.5 Mistake 5: using powers for nonsquare matrices

The power \(A^2\) is defined only when \(A\) is square.

6.25.6 Mistake 6: using the wrong identity size

If \(A\) is \(m\times n\), then

\[ I_mA=A \]

and

\[ AI_n=A. \]

The identity sizes are different unless \(m=n\).

6.26 4.24 Chapter summary

Matrix multiplication is defined when inner dimensions match:

\[ (m\times n)(n\times p)=(m\times p). \]

The entry formula is

\[ (AB)_{ij}=\sum_{k=1}^n a_{ik}b_{kj}. \]

The column interpretation is

\[ AB= \begin{bmatrix} Ab_1&Ab_2&\cdots&Ab_p \end{bmatrix}. \]

Matrix multiplication is associative and distributive, but not usually commutative.

The identity matrix acts like \(1\):

\[ I_mA=A,\qquad AI_n=A. \]

Matrix powers represent repeated application of a square matrix.

Matrix multiplication represents composition:

\[ A(Bx)=(AB)x. \]

The order matters: in \(ABx\), \(B\) acts first and \(A\) acts second.

6.27 Exercises

6.27.1 A. Dimension compatibility

For each product, determine whether it is defined. If it is defined, give the size of the result.

\((2\times 3)(3\times 4)\)
\((3\times 2)(3\times 4)\)
\((5\times 1)(1\times 7)\)
\((1\times 5)(5\times 1)\)
\((4\times 4)(4\times 2)\)
\((2\times 3)(2\times 3)\)

6.27.2 B. Matrix products

Compute each product if it is defined.

\[ \begin{bmatrix} 1&2\\ 3&4 \end{bmatrix} \begin{bmatrix} 2&1\\ 0&-1 \end{bmatrix} \]

\[ \begin{bmatrix} 2&1\\ 0&-1 \end{bmatrix} \begin{bmatrix} 1&2\\ 3&4 \end{bmatrix} \]

\[ \begin{bmatrix} 1&2&3\\ 4&5&6 \end{bmatrix} \begin{bmatrix} 1\\ 0\\ -1 \end{bmatrix} \]

\[ \begin{bmatrix} 1&2\\ 3&4 \end{bmatrix} \begin{bmatrix} 1&0&2\\ 0&1&3 \end{bmatrix} \]

6.27.3 C. Noncommutativity

Find \(AB\) and \(BA\).

\[ A= \begin{bmatrix} 1&1\\ 0&1 \end{bmatrix}, \qquad B= \begin{bmatrix} 1&0\\ 1&1 \end{bmatrix}. \]

\[ A= \begin{bmatrix} 0&-1\\ 1&0 \end{bmatrix}, \qquad B= \begin{bmatrix} 1&0\\ 0&0 \end{bmatrix}. \]

Give a geometric interpretation of the second example.

6.27.4 D. Identity and zero matrices

Let

\[ A= \begin{bmatrix} 1&2&3\\ 4&5&6 \end{bmatrix}. \]

Compute:

\(I_2A\)
\(AI_3\)
\(A0_{3\times 2}\)
\(0_{4\times 2}A\)

6.27.5 E. Matrix powers

Compute \(A^2\) and \(A^3\).

\[ A= \begin{bmatrix} 2&0\\ 0&3 \end{bmatrix} \]

\[ A= \begin{bmatrix} 1&1\\ 0&1 \end{bmatrix} \]

\[ A= \begin{bmatrix} 0&1\\ 1&0 \end{bmatrix} \]

Describe geometrically what the matrix in part 3 does. What is \(A^2\)?

6.27.6 F. Triangular systems

Solve by substitution.

\[ \begin{cases} x_1+2x_2-x_3=4,\\ x_2+3x_3=5,\\ x_3=1. \end{cases} \]

\[ \begin{cases} 2x_1=6,\\ x_1+3x_2=8,\\ 4x_1-x_2+x_3=10. \end{cases} \]

Explain the difference between forward substitution and back substitution.

6.27.7 G. Composition

Let

\[ P= \begin{bmatrix} 1&0\\ 0&0 \end{bmatrix} \]

and

\[ Q= \begin{bmatrix} 0&-1\\ 1&0 \end{bmatrix}. \]

Compute \(PQ\).
Compute \(QP\).
Apply both products to

\[ x= \begin{bmatrix} 1\\ 2 \end{bmatrix}. \]

Explain why the two answers are different.

6.27.8 H. Python exercises

Create two \(2\times 2\) matrices \(A\) and \(B\) in NumPy. Compute \(AB\) and \(BA\).
Find an example where \(AB=BA\).
Find an example where \(AB\) is defined but \(BA\) is not defined.
Use np.linalg.matrix_power to compute \(A^{10}\) for

\[ A= \begin{bmatrix} 1&1\\ 1&0 \end{bmatrix}. \]

Simulate \(x_{t+1}=Ax_t\) for

\[ A= \begin{bmatrix} 0.8&0.3\\ 0.2&0.7 \end{bmatrix} \]

and several different initial vectors \(x_0\).

Write a short paragraph explaining what you observe.

6.28 AI-age connection

Matrix multiplication is one of the central operations of modern computation. A neural network layer multiplies an input vector by a weight matrix. A data transformation multiplies a data matrix by another matrix. A recommendation system, a graph algorithm, or a dimensionality reduction method may require many large matrix products. Understanding matrix multiplication as both computation and composition is essential for understanding linear algebra in the age of AI.