Linear Algebra, Mechanics of Matrix Multiplication

In this subsection we consider matrix multiplication as a mechanical process,
putting aside for the moment any implications about the underlying maps.
As described earlier,
the striking thing about matrix multiplication is the
way rows and columns combine.
The i , j entry of the matrix product is the dot product of
row i of the left matrix with column j
of the right one.
For instance,
here a second row and a third column combine to make a {}2 , 3 entry.

( \begin{matrix}1 & 1 \\ 0 & 1 \\ 1 & 0\end{matrix} ) ( \begin{matrix}4 & 6 & 8 & 2 \\ 5 & 7 & 9 & 3\end{matrix} ) = ( \begin{matrix}9 & 13 & 17 & 5 \\ 5 & 7 & 9 & 3 \\ 4 & 6 & 8 & 2\end{matrix} )

We can view this as the left matrix acting
by multiplying its rows, one at a time, into the columns of the right matrix.
Of course, another perspective
is that the right matrix uses its columns to
act on the left matrix's rows.
Below, we will examine actions from the left and from the right for some
simple matrices.

The first case, the action of a zero matrix, is very easy.

Example 3.1

Multiplying by an appropriately-sized zero matrix
from the left or from the right

( \begin{matrix}0 & 0 \\ 0 & 0\end{matrix} ) ( \begin{matrix}1 & 3 & 2 \\ − 1 & 1 & − 1\end{matrix} ) = ( \begin{matrix}0 & 0 & 0 \\ 0 & 0 & 0\end{matrix} ) \ ( \begin{matrix}2 & 3 \\ 1 & 4\end{matrix} ) ( \begin{matrix}0 & 0 \\ 0 & 0\end{matrix} ) = ( \begin{matrix}0 & 0 \\ 0 & 0\end{matrix} )

results in a zero matrix.

After zero matrices, the matrices whose actions are easiest to understand
are the ones with a single nonzero entry.

Definition 3.2

A matrix with all zeroes except for a one in the i , j entry
is an i , j unit matrix.

Example 3.3

This is the ${}1 , 2 $ unit matrix with three rows and two columns,
multiplying from the left.

( \begin{matrix}0 & 1 \\ 0 & 0 \\ 0 & 0\end{matrix} ) ( \begin{matrix}5 & 6 \\ 7 & 8\end{matrix} ) = ( \begin{matrix}7 & 8 \\ 0 & 0 \\ 0 & 0\end{matrix} )

Acting
from the left, an i , j unit matrix copies row j of
the multiplicand into row i of the result.
From the right an i , j unit matrix copies column i of
the multiplicand into column j of the result.

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

Example 3.4

Rescaling these matrices simply rescales the result.
This is the action from the left of the matrix that is twice the one in the
prior example.

( \begin{matrix}0 & 2 \\ 0 & 0 \\ 0 & 0\end{matrix} ) ( \begin{matrix}5 & 6 \\ 7 & 8\end{matrix} ) = ( \begin{matrix}14 & 16 \\ 0 & 0 \\ 0 & 0\end{matrix} )

And this is the action of the matrix that is minus three times the one
from the prior example.

( \begin{matrix}1 & 2 & 3 \\ 4 & 5 & 6 \\ 7 & 8 & 9\end{matrix} ) ( \begin{matrix}0 & − 3 \\ 0 & 0 \\ 0 & 0\end{matrix} ) = ( \begin{matrix}0 & − 3 \\ 0 & − 12 \\ 0 & − 21\end{matrix} )

Next in complication are matrices with two nonzero entries.
There are two cases.
If a left-multiplier has entries in different rows then their actions
don't interact.

Example 3.5

\begin{matrix}( \begin{matrix}1 & 0 & 0 \\ 0 & 0 & 2 \\ 0 & 0 & 0\end{matrix} ) ( \begin{matrix}1 & 2 & 3 \\ 4 & 5 & 6 \\ 7 & 8 & 9\end{matrix} ) & = ( ( \begin{matrix}1 & 0 & 0 \\ 0 & 0 & 0 \\ 0 & 0 & 0\end{matrix} ) + ( \begin{matrix}0 & 0 & 0 \\ 0 & 0 & 2 \\ 0 & 0 & 0\end{matrix} ) ) ( \begin{matrix}1 & 2 & 3 \\ 4 & 5 & 6 \\ 7 & 8 & 9\end{matrix} ) \\ & = ( \begin{matrix}1 & 2 & 3 \\ 0 & 0 & 0 \\ 0 & 0 & 0\end{matrix} ) + ( \begin{matrix}0 & 0 & 0 \\ 14 & 16 & 18 \\ 0 & 0 & 0\end{matrix} ) \\ & = ( \begin{matrix}1 & 2 & 3 \\ 14 & 16 & 18 \\ 0 & 0 & 0\end{matrix} )\end{matrix}

But if the left-multiplier's nonzero entries are in the same row
then that row of the result is a combination.

Example 3.6

\begin{matrix}( \begin{matrix}1 & 0 & 2 \\ 0 & 0 & 0 \\ 0 & 0 & 0\end{matrix} ) ( \begin{matrix}1 & 2 & 3 \\ 4 & 5 & 6 \\ 7 & 8 & 9\end{matrix} ) & = ( ( \begin{matrix}1 & 0 & 0 \\ 0 & 0 & 0 \\ 0 & 0 & 0\end{matrix} ) + ( \begin{matrix}0 & 0 & 2 \\ 0 & 0 & 0 \\ 0 & 0 & 0\end{matrix} ) ) ( \begin{matrix}1 & 2 & 3 \\ 4 & 5 & 6 \\ 7 & 8 & 9\end{matrix} ) \\ & = ( \begin{matrix}1 & 2 & 3 \\ 0 & 0 & 0 \\ 0 & 0 & 0\end{matrix} ) + ( \begin{matrix}14 & 16 & 18 \\ 0 & 0 & 0 \\ 0 & 0 & 0\end{matrix} ) \\ & = ( \begin{matrix}15 & 18 & 21 \\ 0 & 0 & 0 \\ 0 & 0 & 0\end{matrix} )\end{matrix}

Right-multiplication acts in the same way, with columns.

These observations about matrices that are mostly zeroes
extend to arbitrary matrices.

Lemma 3.7

In a product of two matrices G and H,
the columns of G H are formed by taking G times the columns of H

G ⋅ ( \begin{matrix}⋮ & & ⋮ \\ {\overset{→}{h}}_{1} & ⋯ & {\overset{→}{h}}_{n} \\ ⋮ & & ⋮\end{matrix} ) = ( \begin{matrix}⋮ & & ⋮ \\ G ⋅ {\overset{→}{h}}_{1} & ⋯ & G ⋅ {\overset{→}{h}}_{n} \\ ⋮ & & ⋮\end{matrix} )

and the rows of G H are formed by taking the rows of G times H

( \begin{matrix}⋯ \ {\overset{→}{g}}_{1} \ ⋯ \\ ⋮ \\ ⋯ \ {\overset{→}{g}}_{r} \ ⋯\end{matrix} ) ⋅ H = ( \begin{matrix}⋯ \ {\overset{→}{g}}_{1} ⋅ H \ ⋯ \\ ⋮ \\ ⋯ \ {\overset{→}{g}}_{r} ⋅ H \ ⋯\end{matrix} )

(ignoring the extra parentheses).

Proof

We will show the {}2 \ × \ 2 case and leave the general case as
an exercise.

G H = ( \begin{matrix}{g}_{1 , 1} & {g}_{1 , 2} \\ {g}_{2 , 1} & {g}_{2 , 2}\end{matrix} ) ( \begin{matrix}{h}_{1 , 1} & {h}_{1 , 2} \\ {h}_{2 , 1} & {h}_{2 , 2}\end{matrix} ) = ( \begin{matrix}{g}_{1 , 1} {h}_{1 , 1} + {g}_{1 , 2} {h}_{2 , 1} & {g}_{1 , 1} {h}_{1 , 2} + {g}_{1 , 2} {h}_{2 , 2} \\ {g}_{2 , 1} {h}_{1 , 1} + {g}_{2 , 2} {h}_{2 , 1} & {g}_{2 , 1} {h}_{1 , 2} + {g}_{2 , 2} {h}_{2 , 2}\end{matrix} )

The right side of the first equation in the result

( \begin{matrix}G ( \begin{matrix}{h}_{1 , 1} \\ {h}_{2 , 1}\end{matrix} ) & G ( \begin{matrix}{h}_{1 , 2} \\ {h}_{2 , 2}\end{matrix} )\end{matrix} ) = ( \begin{matrix}( \begin{matrix}{g}_{1 , 1} {h}_{1 , 1} + {g}_{1 , 2} {h}_{2 , 1} \\ {g}_{2 , 1} {h}_{1 , 1} + {g}_{2 , 2} {h}_{2 , 1}\end{matrix} ) & ( \begin{matrix}{g}_{1 , 1} {h}_{1 , 2} + {g}_{1 , 2} {h}_{2 , 2} \\ {g}_{2 , 1} {h}_{1 , 2} + {g}_{2 , 2} {h}_{2 , 2}\end{matrix} )\end{matrix} )

is indeed the same as the right side of GH, except for the extra parentheses (the ones marking the columns as column vectors). The other equation is similarly easy to recognize.

An application of those observations is that there is a matrix
that just copies out the rows and columns.

Definition 3.8

The main diagonal (or principal diagonal or diagonal) of a square matrix goes from the upper left to the lower right.

Definition 3.9

An identity matrix is square and has with all entries zero
except for ones in the main diagonal.

{I}_{n \ × \ n} = ( \begin{matrix}1 & 0 & … & 0 \\ 0 & 1 & … & 0 \\ & ⋮ \\ 0 & 0 & … & 1\end{matrix} )

Example 3.10

The {}3 \ × \ 3 identity
leaves its multiplicand unchanged both from the left

( \begin{matrix}1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1\end{matrix} ) ( \begin{matrix}2 & 3 & 6 \\ 1 & 3 & 8 \\ − 7 & 1 & 0\end{matrix} ) = ( \begin{matrix}2 & 3 & 6 \\ 1 & 3 & 8 \\ − 7 & 1 & 0\end{matrix} )

and from the right.

( \begin{matrix}2 & 3 & 6 \\ 1 & 3 & 8 \\ − 7 & 1 & 0\end{matrix} ) ( \begin{matrix}1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1\end{matrix} ) = ( \begin{matrix}2 & 3 & 6 \\ 1 & 3 & 8 \\ − 7 & 1 & 0\end{matrix} )

Example 3.11

So does the {}2 \ × \ 2 identity matrix.

( \begin{matrix}1 & − 2 \\ 0 & − 2 \\ 1 & − 1 \\ 4 & 3\end{matrix} ) ( \begin{matrix}1 & 0 \\ 0 & 1\end{matrix} ) = ( \begin{matrix}1 & − 2 \\ 0 & − 2 \\ 1 & − 1 \\ 4 & 3\end{matrix} )

In short, an identity matrix is the identity element
of the set of n \ × \ n matrices with
respect to the operation of matrix multiplication.

We next see two ways to generalize the identity matrix.

The first is that if the ones are relaxed to arbitrary reals,
the resulting matrix will rescale whole rows or columns.

Definition 3.12

A diagonal matrix is square and has zeros off the main
diagonal.

( \begin{matrix}{a}_{1 , 1} & 0 & … & 0 \\ 0 & {a}_{2 , 2} & … & 0 \\ & ⋮ \\ 0 & 0 & … & {a}_{n , n}\end{matrix} )

Example 3.13

From the left,
the action of multiplication by a diagonal matrix is to
rescales the rows.

( \begin{matrix}2 & 0 \\ 0 & − 1\end{matrix} ) ( \begin{matrix}2 & 1 & 4 & − 1 \\ − 1 & 3 & 4 & 4\end{matrix} ) = ( \begin{matrix}4 & 2 & 8 & − 2 \\ 1 & − 3 & − 4 & − 4\end{matrix} )

From the right such a matrix rescales the columns.

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

The second generalization of identity matrices is that
we can put a single one in each row and column
in ways other than putting them down the diagonal.

Definition 3.14

A permutation matrix is square and is all zeros except for a
single one in each row and column.

Example 3.15

From the left these matrices permute rows.

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

From the right they permute columns.

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

We finish this subsection by applying these observations to get matrices
that perform Gauss' method and Gauss-Jordan reduction.

Example 3.16

We have seen how to produce a matrix that will rescale rows.
Multiplying by this diagonal matrix rescales the second row of
the other by a factor of three.

( \begin{matrix}1 & 0 & 0 \\ 0 & 3 & 0 \\ 0 & 0 & 1\end{matrix} ) ( \begin{matrix}0 & 2 & 1 & 1 \\ 0 & 1 / 3 & 1 & − 1 \\ 1 & 0 & 2 & 0\end{matrix} ) = ( \begin{matrix}0 & 2 & 1 & 1 \\ 0 & 1 & 3 & − 3 \\ 1 & 0 & 2 & 0\end{matrix} )

We have seen how to produce a matrix that will swap rows.
Multiplying by this permutation matrix swaps the
first and third rows.

( \begin{matrix}0 & 0 & 1 \\ 0 & 1 & 0 \\ 1 & 0 & 0\end{matrix} ) ( \begin{matrix}0 & 2 & 1 & 1 \\ 0 & 1 & 3 & − 3 \\ 1 & 0 & 2 & 0\end{matrix} ) = ( \begin{matrix}1 & 0 & 2 & 0 \\ 0 & 1 & 3 & − 3 \\ 0 & 2 & 1 & 1\end{matrix} )

To see how to perform a pivot,
we observe something about those two examples.
The matrix that rescales the second row by a factor of three arises in this
way from the identity.

( \begin{matrix}1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1\end{matrix} ) {→}_{ \ }^{3 {ρ}_{2}} ( \begin{matrix}1 & 0 & 0 \\ 0 & 3 & 0 \\ 0 & 0 & 1\end{matrix} )

Similarly, the matrix that swaps first and third rows arises in this way.

( \begin{matrix}1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1\end{matrix} ) {→}_{ \ }^{{ρ}_{1} ↔ {ρ}_{3}} ( \begin{matrix}0 & 0 & 1 \\ 0 & 1 & 0 \\ 1 & 0 & 0\end{matrix} )

Example 3.17

The {}3 \ × \ 3 matrix that arises as

( \begin{matrix}1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1\end{matrix} ) {→}_{ \ }^{− 2 {ρ}_{2} + {ρ}_{3}} ( \begin{matrix}1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & − 2 & 1\end{matrix} )

will, when it acts from the left,
perform the pivot operation − 2 {ρ}_{2} + {ρ}_{3}.

( \begin{matrix}1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & − 2 & 1\end{matrix} ) ( \begin{matrix}1 & 0 & 2 & 0 \\ 0 & 1 & 3 & − 3 \\ 0 & 2 & 1 & 1\end{matrix} ) = ( \begin{matrix}1 & 0 & 2 & 0 \\ 0 & 1 & 3 & − 3 \\ 0 & 0 & − 5 & 7\end{matrix} )

Definition 3.18

The elementary reduction matrices are obtained from identity
matrices with one Gaussian operation. We denote them:

• I {→}_{ \ }^{k {ρ}_{i}} {M}_{i} ( k ) for k ≠ 0;
• I {→}_{ \ }^{{ρ}_{i} ↔ {ρ}_{j}} {P}_{i , j} for

i ≠ j;

• I {→}_{ \ }^{k {ρ}_{i} + {ρ}_{j}} {C}_{i , j} ( k ) for i ≠ j.

Lemma 3.19

Gaussian reduction can be done through matrix multiplication.

• If H {→}_{ \ }^{k {ρ}_{i}} G then {M}_{i} ( k ) H = G.
• If H {→}_{ \ }^{{ρ}_{i} ↔ {ρ}_{j}} G

then {P}_{i , j} H = G.

• If H {→}_{ \ }^{k {ρ}_{i} + {ρ}_{j}} G then {C}_{i , j} ( k ) H = G.

Proof

Clear.

Example 3.20

This is the first system, from the first chapter, on which we
performed Gauss' method.

\begin{matrix} & & & & 3 {x}_{3} & = & 9 \\ {x}_{1} & + & 5 {x}_{2} & − & 2 {x}_{3} & = & 2 \\ ( 1 / 3 ) {x}_{1} & + & 2 {x}_{2} & & & = & 3\end{matrix}

It can be reduced with matrix multiplication.
Swap the first and third rows,

( \begin{matrix}0 & 0 & 1 \\ 0 & 1 & 0 \\ 1 & 0 & 0\end{matrix} ) ( \begin{matrix}0 & 0 & 3 & 9 \\ 1 & 5 & − 2 & 2 \\ 1 / 3 & 2 & 0 & 3\end{matrix} ) = ( \begin{matrix}1 / 3 & 2 & 0 & 3 \\ 1 & 5 & − 2 & 2 \\ 0 & 0 & 3 & 9\end{matrix} )

triple the first row,

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

and then add − 1 times the first row to the second.

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

Now back substitution will give the solution.

Example 3.21

Gauss-Jordan reduction works the same way.
For the matrix ending the prior example, first adjust the leading entries

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

and to finish, clear the third column and then the second column.

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

We have observed the following result,
which we shall use in the next subsection.

Corollary 3.22

For any matrix H there are elementary reduction matrices {R}_{1}, ..., {R}_{r} such that {R}_{r} ⋅ {R}_{r − 1} ⋯ {R}_{1} ⋅ H is in reduced echelon form.

Until now we have taken the point of view that our primary objects of study
are vector spaces and the maps between them, and
have adopted matrices only for computational convenience.
This subsection show that this point of view isn't the whole story.
Matrix theory is a fascinating and fruitful area.

In the rest of this book we shall continue to focus on maps as the primary
objects, but we will be pragmatic— if the matrix point of view gives some
clearer idea then we shall use it.

Exercises

This exercise is recommended for all readers.

Problem 1

Predict the result of each multiplication by an elementary
reduction matrix, and then check by multiplying it out.

• ( \begin{matrix}3 & 0 \\ 0 & 0\end{matrix} ) ( \begin{matrix}1 & 2 \\ 3 & 4\end{matrix} )
• ( \begin{matrix}4 & 0 \\ 0 & 2\end{matrix} ) ( \begin{matrix}1 & 2 \\ 3 & 4\end{matrix} )
• ( \begin{matrix}1 & 0 \\ − 2 & 1\end{matrix} ) ( \begin{matrix}1 & 2 \\ 3 & 4\end{matrix} )
• ( \begin{matrix}1 & 2 \\ 3 & 4\end{matrix} ) ( \begin{matrix}1 & − 1 \\ 0 & 1\end{matrix} )
• ( \begin{matrix}1 & 2 \\ 3 & 4\end{matrix} ) ( \begin{matrix}0 & 1 \\ 1 & 0\end{matrix} )

This exercise is recommended for all readers.

Problem 2

The need to take linear combinations of rows and columns in tables of
numbers arises often in practice.
For instance, this is a map of part of Vermont and New York.

• The incidence matrix
  of a map is the square matrix
  whose i , j entry is the number of roads from city i
  to city j.
  Produce the incidence matrix of this map (take the cities in
  alphabetical order).
• A matrix is symmetric if it equals its transpose.

Show that an incidence matrix is symmetric.
(These are all two-way streets.
Vermont doesn't have many one-way streets.)

• What is the significance of the square of the
  incidence matrix?
  The cube?

This exercise is recommended for all readers.

Problem 3

This table gives the number of hours of each
type done by each worker, and the associated pay rates.
Use matrices to compute the wages due.

(Remark.
This illustrates, as did the prior problem, that in practice
we often want to compute linear combinations of rows and
columns in a context where we really aren't interested in any
associated linear maps.)

Problem 4

Find the product of this matrix with its transpose.

( \begin{matrix}cos ⁡ θ & − sin ⁡ θ \\ sin ⁡ θ & cos ⁡ θ\end{matrix} )

This exercise is recommended for all readers.

Problem 5

Prove that the diagonal matrices form a subspace of
{ℳ}_{n \ × \ n}.
What is its dimension?

Problem 6

Does the identity matrix represent the identity map if the bases are
unequal?

Problem 7

Show that every multiple of the identity commutes with every
square matrix.
Are there other matrices that commute with all square matrices?

Problem 8

Prove or disprove: nonsingular matrices commute.

This exercise is recommended for all readers.

Problem 9

Show that the product of a permutation matrix and its transpose
is an identity matrix.

Problem 10

Show that if the first and second rows of G are equal then so
are the first and second rows of G H.
Generalize.

Problem 11

Describe the product of two diagonal matrices.

Problem 12

Write

( \begin{matrix}1 & 0 \\ − 3 & 3\end{matrix} )

as the product of two elementary reduction matrices.

This exercise is recommended for all readers.

Problem 13

Show that if G has a row of zeros then G H
(if defined) has a row of zeros.
Does that work for columns?

Problem 14

Show that the set of unit matrices forms a basis for
{ℳ}_{n \ × \ m}.

Problem 15

Find the formula for the n-th power of this matrix.

( \begin{matrix}1 & 1 \\ 1 & 0\end{matrix} )

This exercise is recommended for all readers.

Problem 16

The trace
of a square matrix is the sum of the
entries on its diagonal (its significance appears in
Chapter Five).
Show that \text{trace} \ ( G H ) = \text{trace} \ ( H G ).

This exercise is recommended for all readers.

Problem 17

A square matrix is
upper triangular
if its only nonzero
entries lie above, or on, the diagonal.
Show that the product of two upper triangular matrices is upper triangular.
Does this hold for lower triangular also?

Problem 18

A square matrix is a Markov matrix
if each entry is between zero
and one and the sum along each row is one.
Prove that a product of Markov matrices is Markov.

This exercise is recommended for all readers.

Problem 19

Give an example of two matrices of the same rank with squares of
differing rank.

Problem 20

Combine the two generalizations of the identity matrix,
the one allowing entires to be other than ones, and the one allowing the
single one in each row and column to be off the diagonal.
What is the action of this type of matrix?

Problem 21

On a computer multiplications are more costly than additions, so
people are interested in reducing the number of multiplications used to
compute a matrix product.

• How many real number multiplications are needed in formula
  we gave for the product of a
  m \ × \ r matrix and a r \ × \ n matrix?

Matrix multiplication is associative, so all associations yield
the same result.
The cost in number of multiplications, however, varies.
Find the association requiring the fewest real number multiplications
to compute the matrix product of
a {}5 \ × \ 10 matrix,
a {}10 \ × \ 20 matrix,
a {}20 \ × \ 5 matrix, and
a {}5 \ × \ 1 matrix.

• (Very hard.)
  Find a way to multiply two {}2 \ × \ 2 matrices using only seven
  multiplications instead of the eight suggested by the naive approach.

? Problem 22

If A and B are square matrices of the
same size such that A B A B = 0, does it follow that B A B A = 0?
(Putnam Exam 1990)

Problem 23

Demonstrate these four assertions to get an
alternate proof that column rank equals row rank. (Liebeck 1966)

• \overset{→}{y} ⋅ \overset{→}{y} = \overset{→}{0} iff \overset{→}{y} = \overset{→}{0}.
• A \overset{→}{x} = \overset{→}{0} iff {A}^{t r a n s} A \overset{→}{x} = \overset{→}{0}.
• dim ⁡ ( ℛ ( A ) ) = dim ⁡ ( ℛ ( {A}^{t r a n s} A ) ).
• \text{col rank} ( A ) = \text{col rank} ( {A}^{t r a n s} ) = \text{row rank} ( A ).

Problem 24

Prove
(where A is an n \ × \ n matrix and so defines
a transformation of any n-dimensional space V
with respect to B , B where B is a basis) that
dim ⁡ ( ℛ ( A ) ∩ 𝒩 ( A ) ) = dim ⁡ ( ℛ ( A ) ) − dim ⁡ ( ℛ ( {A}^{2} ) ).
Conclude

• 𝒩 ( A ) ⊂ ℛ ( A )

iff
dim ⁡ ( 𝒩 ( A ) ) = dim ⁡ ( ℛ ( A ) ) − dim ⁡ ( ℛ ( {A}^{2} ) );

• ℛ ( A ) ⊆ 𝒩 ( A )

iff
{A}^{2} = 0;

• ℛ ( A ) = 𝒩 ( A )

iff
{A}^{2} = 0
and dim ⁡ ( 𝒩 ( A ) ) = dim ⁡ ( ℛ ( A ) ) ;

• dim ⁡ ( ℛ ( A ) ∩ 𝒩 ( A ) ) = 0

iff
dim ⁡ ( ℛ ( A ) ) = dim ⁡ ( ℛ ( {A}^{2} ) ) ;

• (Requires the Direct Sum subsection, which is optional.)
  V = ℛ ( A ) ⊕ 𝒩 ( A )
  iff
  dim ⁡ ( ℛ ( A ) ) = dim ⁡ ( ℛ ( {A}^{2} ) ).

(Ackerson 1955)

Solutions

References

• Ackerson, R. H. (1955), "A Note on Vector Spaces", American Mathematical Monthly, 62 (10), American Mathematical Society: 721 {{citation}}: Unknown parameter |month= ignored (help).
• Liebeck, Hans. (1966), "A Proof of the Equality of Column Rank and Row Rank of a Matrix", American Mathematical Monthly, 73 (10), American Mathematical Society: 1114 {{citation}}: Unknown parameter |month= ignored (help).
• William Lowell Putnam Mathematical Competition, Problem A-5, 1990.

Where this page came from

This page was imported from Wikibooks. From “Linear Algebra” on Wikibooks, by its contributors, under CC BY-SA 4.0. Changed here: set as a page; navigation and edit links left out; each image under its own licence, credited in its caption.

Nobody has written it yet — it is the source material at a new address, which is why search engines are asked to skip it and why no one earns from it. It is up for grabs: take it on, and it is yours to rewrite and to earn from.