Matrix multiplication

Matrix multiplication has multiple different motivations. The one presented here is fairly elementary and allows us to use a more concise representation of subsequent ideas.

Recall

S : {\begin{matrix} x_{1} & + 3 x_{2} & + 3 x_{3} & + 2 x_{4} & + x_{5} & = & 7 \\ 3 x_{1} & + 9 x_{2} & - 6 x_{3} & + 4 x_{4} & + 3 x_{5} & = & -7 \\ 2 x_{1} & + 6 x_{2} & - 4 x_{3} & + 2 x_{4} & + 2 x_{5} & = & -4 \end{matrix}

If we add negative three times the first equation to the third equation we obtain:

-3 ρ_{1} + ρ_{2} \overset{S}{\to} \begin{matrix} -15 x_{3} & - 2 x_{4} & = & -28 \end{matrix}

We will be explicit by including the fact that above we added zero times the third row.

-3 ρ_{1} + 1 ρ_{2} + 0 ρ_{3} \overset{S}{\to} \begin{matrix} -15 x_{3} & - 2 x_{4} & = & -28 \end{matrix}

Here are a few more such combinations

Negative three times equation one plus equation three

-3 ρ_{1} + 0 ρ_{2} + 1 ρ_{3} \overset{S}{\to} \begin{matrix} - x_{1} & - 3 x_{2} & - 13 x_{3} & - 4 x_{4} & - x_{1} & = & -25 \end{matrix}

Negative three times equation two plus equation three

0 ρ_{1} - 3 ρ_{2} + 1 ρ_{3} \overset{S}{\to} \begin{matrix} -7 x_{1} & - 23 x_{2} & + 14 x_{3} & - 10 x_{4} & - 7 x_{1} & = & 17 \end{matrix}

Equation two only

0 ρ_{1} + 1 ρ_{2} + 0 ρ_{3} \overset{S}{\to} \begin{matrix} 3 x_{1} & + 9 x_{2} & - 6 x_{3} & + 4 x_{4} & + 3 x_{5} & = & -7 \end{matrix}

Sum of all three equations

1 ρ_{1} + 1 ρ_{2} + 1 ρ_{3} \overset{S}{\to} \begin{matrix} 6 x_{1} & + 18 x_{2} & - 7 x_{3} & + 8 x_{4} & + 6 x_{5} & = & -4 \end{matrix}

Collecting all resulting equations we obtain

S^{'} : {\begin{matrix} -15 x_{3} & - 2 x_{4} & = & -28 \\ - x_{1} & - 3 x_{2} & - 13 x_{3} & - 4 x_{4} & - x_{5} & = & -25 \\ -7 x_{1} & - 23 x_{2} & + 14 x_{3} & - 10 x_{4} & - 7 x_{5} & = & 17 \\ 3 x_{1} & + 9 x_{2} & - 6 x_{3} & + 4 x_{4} & + 3 x_{5} & = & -7 \\ 6 x_{1} & + 18 x_{2} & - 7 x_{3} & + 8 x_{4} & + 6 x_{5} & = & -4 \end{matrix}

We want to encode such transformation so that there is an easy and convenient way to work just with the (augmented) matrices of the system of linear equation. The constants $-3$ and $1$ are the same when:

adding negative three times Equation 1 to Equation 2,
adding negative three times Equation 1 to Equation 3 and
adding negative three times Equation 2 to Equation 3.

However by being explicit we distinguish between $(-3, 1, 0)$ , $(-3, 0, 1)$ and $(0, -3, 1)$ allowing us to encode the above transform of row combinations in a matrix $rowcomb = (\begin{matrix} -3 & 1 & 0 \\ -3 & 0 & 1 \\ 0 & -3 & 1 \\ 0 & 1 & 0 \\ 1 & 1 & 1 \end{matrix})$

When $rowcomb$ is applied to $S$ the result is $S^{'}$ , or $rowcomb S = S^{'}$ which written as (augmented) matrices is

(\begin{matrix} -3 & 1 & 0 \\ -3 & 0 & 1 \\ 0 & -3 & 1 \\ 0 & 1 & 0 \\ 1 & 1 & 1 \end{matrix}) (\begin{matrix} 1 & 3 & 3 & 2 & 1 & 7 \\ 3 & 9 & -6 & 4 & 3 & -7 \\ 2 & 6 & -4 & 2 & 2 & -4 \end{matrix}) = (\begin{matrix} 0 & 0 & -15 & -2 & 0 & -28 \\ -1 & -3 & -13 & -4 & -1 & -25 \\ -7 & -23 & 14 & -10 & -7 & 17 \\ 1 & 3 & 3 & 2 & 1 & 7 \\ 6 & 18 & -7 & 8 & 6 & -4 \end{matrix})

Above we performed matrix-matrix multiplication or matrix multiplication for short. In that matrix the $r$ th row of the result is the $r$ th combination of equations that is taken. For example the second equation that was obtained was

-3 ρ_{1} + 0 ρ_{2} + 1 ρ_{3} \overset{S}{\to} \begin{matrix} - x_{3} & - 3 x_{3} & - 13 x_{3} & - 4 x_{4} & - x_{4} & = & -25 \end{matrix}

the same operation (highlighted) in the matrix multiplication below

(\begin{matrix} -3 & 1 & 0 \\ -3 & 0 & 1 \\ 0 & -3 & 1 \\ 0 & 1 & 0 \\ 1 & 1 & 1 \end{matrix}) (\begin{matrix} 1 & 3 & 3 & 2 & 1 & 7 \\ 3 & 9 & -6 & 4 & 3 & -7 \\ 2 & 6 & -4 & 2 & 2 & -4 \end{matrix}) = (\begin{matrix} 0 & 0 & -15 & -2 & 0 & -28 \\ -1 & -3 & -13 & -4 & -1 & -25 \\ -7 & -23 & 14 & -10 & -7 & 17 \\ 1 & 3 & 3 & 2 & 1 & 7 \\ 6 & 18 & -7 & 8 & 6 & -4 \end{matrix})

reflects that for the result

- x_{1} - 3 x_{2} - 13 x_{3} - 4 x_{4} - x_{5} = -25

the right side is

-3 \times 7 + 0 \times -7 + 1 \times -4 = -25

and the left side is

\begin{matrix} -3 (x_{1} + 3 x_{2} + 3 x_{3} + 2 x_{4} + 1 x_{5}) \\ + 0 (3 x_{1} + 9 x_{2} - 6 x_{3} + 4 x_{4} + 3 x_{5}) \\ + 1 (2 x_{1} + 6 x_{2} - 4 x_{3} + 2 x_{4} + 2 x_{5}) \\ = \underset{\underset{= -1}{⏟}}{(-3 \times 1 + 0 \times 3 + 1 \times 2)} x_{1} \\ + \underset{\underset{= -3}{⏟}}{(-3 \times 3 + 0 \times 9 + 1 \times 6)} x_{2} \\ + \underset{\underset{= -13}{⏟}}{(-3 \times 3 + 0 \times -6 + 1 \times -4)} x_{3} \\ + \underset{\underset{= -4}{⏟}}{(-3 \times 2 + 0 \times 4 + 1 \times 2)} x_{4} \\ + \underset{\underset{= -1}{⏟}}{(-3 \times 1 + 0 \times 3 + 1 \times 2)} x_{5} & = & - x_{1} - 3 x_{2} - 13 x_{3} - 4 x_{4} - x_{5} \end{matrix}

In the matrix multiplication

(\begin{matrix} -3 & 1 & 0 \\ -3 & 0 & 1 \\ 0 & -3 & 1 \\ 0 & 1 & 0 \\ 1 & 1 & 1 \end{matrix}) (\begin{matrix} 1 & 3 & 3 & 2 & 1 & 7 \\ 3 & 9 & -6 & 4 & 3 & -7 \\ 2 & 6 & -4 & 2 & 2 & -4 \end{matrix}) = (\begin{matrix} 0 & 0 & -15 & -2 & 0 & -28 \\ -1 & -3 & -13 & -4 & -1 & -25 \\ -7 & -23 & 14 & -10 & -7 & 17 \\ 1 & 3 & 3 & 2 & 1 & 7 \\ 6 & 18 & -7 & 8 & 6 & -4 \end{matrix})

to obtain the entry in the first row sixth (last) column of the matrix on the right hand side of the equation we compute:

-28 = -3 \times 7 + 1 \times -7 + 0 \times -4

to obtain the entry in the first row third column we compute:

-15 = -3 \times 3 + 1 \times -6 + 0 \times -4

to obtain the entry in the third row second column we compute:

-23 = 0 \times 3 - 3 \times 9 + 1 \times 6

To summarize: when multiplying matrices $A B = C$

each row of matrix $A$ contributes a row in the resulting matrix $C$ , that is each combination of equations results in exactly one equation;
each column of matrix $B$ contributes a column in the resulting matrix $C$ , that is the set of variables is unchanged;
the number of columns in matrix $A$ equals the number of rows in matrix $B$ , that is we are explicit expressing the combination of equations.

In the above matrix multiplication we multiplied a $5 \times 3$ matrix by a $3 \times 6$ to obtain a $5 \times 6$ .

We are ready to define matrix multiplication

Let $A = {α_{i j}}$ be an $m \times k$ matrix and $B = {β_{i j}}$ be an $k \times n$ matrix. The matrix multiplication of matrix $A$ with matrix $B$ denoted by $A B$ is an $m \times n$ matrix $C$

C = {ζ_{r c}}_{1 \leq r \leq m, 1 \leq c \leq n}

where

ζ_{r c} = \sum_{i = 1}^{k} α_{r i} β_{i c}

Here is another example including a corresponding systems of linear equations:

Let

{\begin{matrix} x_{3} & + 2 x_{4} & = & 3 \\ x_{1} & + 3 x_{2} & + 3 x_{3} & + 2 x_{4} & = & 1 \\ 2 x_{1} & + 6 x_{2} & + 5 x_{3} & + 2 x_{4} & = & 0 \end{matrix}

then

\begin{matrix} 1 ρ_{1} + 0 ρ_{2} + 0 ρ_{3} \\ 1 ρ_{1} - 2 ρ_{2} + 1 ρ_{3} \end{matrix} \overset{S}{\to} {\begin{matrix} 0 x_{1} & + 0 x_{2} & + 1 x_{3} & + 2 x_{4} & = & 3 \\ 0 x_{1} & + 0 x_{2} & + 0 x_{3} & + 0 x_{4} & = & 0 \end{matrix}

or as matrix multiplication

(\begin{matrix} 1 & 0 & 0 \\ 1 & -2 & 1 \end{matrix}) (\begin{matrix} 0 & 0 & 1 & 2 & 3 \\ 1 & 3 & 3 & 2 & 1 \\ 2 & 6 & 5 & 2 & 0 \end{matrix}) = (\begin{matrix} 0 & 0 & 1 & 2 & 3 \\ 0 & 0 & 0 & 0 & 1 \end{matrix})

Matrix multipcation is independent from the underlying system of linear equations but some of the earlier notation we introduced is motivated by matrix multiplication.

Verify

(\begin{matrix} 1 & 3 & 3 & 2 & 1 \\ 3 & 9 & -6 & 4 & 3 \\ 2 & 6 & -4 & 2 & 2 \end{matrix}) (\begin{matrix} 3 \\ 0 \\ 2 \\ -1 \\ 0 \end{matrix}) = (\begin{matrix} 7 \\ -7 \\ -4 \end{matrix})

Compare the above result with the matrix form

(\begin{matrix} 1 & 3 & 3 & 2 & 1 \\ 3 & 9 & -6 & 4 & 3 \\ 2 & 6 & -4 & 2 & 2 \end{matrix}) (\begin{matrix} x_{1} \\ x_{2} \\ x_{3} \\ x_{4} \\ x_{5} \end{matrix}) = (\begin{matrix} 7 \\ -7 \\ -4 \end{matrix})

of the system of linear equations

S : {\begin{matrix} x_{1} & + 3 x_{2} & + 3 x_{3} & + 2 x_{4} & + x_{5} & = & 7 \\ 3 x_{1} & + 9 x_{2} & - 6 x_{3} & + 4 x_{4} & + 3 x_{5} & = & -7 \\ 2 x_{1} & + 6 x_{2} & - 4 x_{3} & + 2 x_{4} & + 2 x_{5} & = & -4 \end{matrix}

A word of caution: not all pair of matrices can be multiplied!

While the multiplications

(\begin{matrix} 3 \\ 5 \\ -7 \\ 8 \end{matrix}) (\begin{matrix} 1 \\ -1 \\ 2 \end{matrix})

and

(\begin{matrix} 3 & 5 & -7 & 8 \end{matrix}) (\begin{matrix} 1 \\ -1 \\ 2 \end{matrix})

cannot be performed, one can verify

(\begin{matrix} 1 \\ -1 \\ 2 \end{matrix}) (\begin{matrix} 3 & 5 & -7 & 8 \end{matrix}) = (\begin{matrix} 3 & 5 & -7 & 8 \\ -3 & -5 & 7 & -8 \\ 6 & 10 & -14 & 16 \end{matrix})

The above example illustrates that matrix multiplication is not commutative that is

A B \neq B A

In fact the existence of $A B$ does not imply the existence of $B A$ . Here is an example where both multiplications exist but are not equal to each other.

Verify

(\begin{matrix} 1 \\ -1 \\ 2 \end{matrix}) (\begin{matrix} 3 & 5 & -7 \end{matrix}) = (\begin{matrix} 3 & 5 & -7 \\ -3 & -5 & 7 \\ 6 & 10 & -14 \end{matrix})

and

(\begin{matrix} 1 & -1 & 2 \end{matrix}) (\begin{matrix} 3 \\ 5 \\ -7 \end{matrix}) = (\begin{matrix} -16 \end{matrix})

Bear in mind that the last multiplication results in a one by one matrix not the number sixteen.

Let us consider the multiplication of three matrices.

Let

\begin{matrix} A & = & (\begin{matrix} 1 & -1 & 2 \\ 4 & 1 & 5 \\ -3 & -4 & 0 \\ 9 & -6 & 7 \end{matrix}) \\ B & = & (\begin{matrix} 3 & 5 & -7 & 4 & 1 \\ 0 & 3 & 4 & 0 & -1 \\ 5 & 0 & 1 & -1 & 2 \end{matrix}) \\ C & = & (\begin{matrix} 0 & 1 \\ 2 & -1 \\ 3 & 0 \\ -1 & 1 \\ 1 & -2 \end{matrix}) \end{matrix}

Then

\begin{matrix} A B & = & (\begin{matrix} 1 & -1 & 2 \\ 4 & 1 & 5 \\ -3 & -4 & 0 \\ 9 & -6 & 7 \end{matrix}) (\begin{matrix} 3 & 5 & -7 & 4 & 1 \\ 0 & 3 & 4 & 0 & -1 \\ 5 & 0 & 1 & -1 & 2 \end{matrix}) = (\begin{matrix} 13 & 2 & -9 & 2 & 6 \\ 37 & 23 & -19 & 11 & 13 \\ -9 & -27 & 5 & -12 & 1 \\ 62 & 27 & -80 & 29 & 29 \end{matrix}) \\ B C & = & (\begin{matrix} 3 & 5 & -7 & 4 & 1 \\ 0 & 3 & 4 & 0 & -1 \\ 5 & 0 & 1 & -1 & 2 \end{matrix}) (\begin{matrix} 0 & 1 \\ 2 & -1 \\ 3 & 0 \\ -1 & 1 \\ 1 & -2 \end{matrix}) = (\begin{matrix} -14 & 0 \\ 17 & -1 \\ 6 & 0 \end{matrix}) \end{matrix}

And furthermore

\begin{matrix} (A B) C & = & (\begin{matrix} 13 & 2 & -9 & 2 & 6 \\ 37 & 23 & -19 & 11 & 13 \\ -9 & -27 & 5 & -12 & 1 \\ 62 & 27 & -80 & 29 & 29 \end{matrix}) (\begin{matrix} 0 & 1 \\ 2 & -1 \\ 3 & 0 \\ -1 & 1 \\ 1 & -2 \end{matrix}) = (\begin{matrix} -19 & 1 \\ -9 & -1 \\ -26 & 4 \\ -186 & 6 \end{matrix}) \\ A (B C) & = & (\begin{matrix} 1 & -1 & 2 \\ 4 & 1 & 5 \\ -3 & -4 & 0 \\ 9 & -6 & 7 \end{matrix}) (\begin{matrix} -14 & 0 \\ 17 & -1 \\ 6 & 0 \end{matrix}) = (\begin{matrix} -19 & 1 \\ -9 & -1 \\ -26 & 4 \\ -186 & 6 \end{matrix}) \end{matrix}

Matrix multiplication is not commutative operation but the above example suggests that it is an associative operation!

Matrix multiplication is associative

A (B C) = (A B) C

Show proof:

Let $A = {α_{i j}}$ be an $m \times k$ matrix, $B = {β_{i j}}$ be an $k \times p$ matrix and $C = {ζ_{i j}}$ be an $p \times n$ matrix. Then

D = B C = {d_{i c}}

is a $k \times n$ matrix where

d_{i c} = \sum_{j = 1}^{p} β_{i j} ζ_{j c}

and

E = A B = {e_{r j}}

is an $m \times p$ matrix where

e_{r j} = \sum_{i = 1}^{k} α_{r i} β_{i j}

Consider $X = A D = {χ_{r c}}$ . It is an $m \times n$ matrix where

χ_{r c} = \sum_{i = 1}^{k} α_{r i} d_{i c} = \sum_{i = 1}^{k} α_{r i} (\sum_{j = 1}^{p} β_{i j} ζ_{j c}) = \sum_{i = 1}^{k} \sum_{j = 1}^{p} (α_{r i} β_{i j} ζ_{j c})

Consider $Y = E C = {γ_{r c}}$ . It is an $m \times n$ matrix where

γ_{r c} = \sum_{j = 1}^{p} e_{r j} ζ_{j c} = \sum_{j = 1}^{p} (\sum_{i = 1}^{k} α_{r i} β_{i j}) ζ_{j c} = \sum_{j = 1}^{p} \sum_{i = 1}^{k} (α_{r i} β_{i j} ζ_{j c})

Matrices $X$ and $Y$ have the same number of rows and columns and

χ_{r c} = \sum_{i = 1}^{k} \sum_{j = 1}^{p} (α_{r i} β_{i j} ζ_{j c}) = \sum_{j = 1}^{p} \sum_{i = 1}^{k} (α_{r i} β_{i j} ζ_{j c}) = γ_{r c}

hence $X = Y$ , which concludes the argument.