Linear Algebra/Mechanics of Matrix Multiplication/Solutions
Solutions[edit]
 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.
 Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "/mathoid/local/v1/":): {\displaystyle \begin{pmatrix} 3 &0 \\ 0 &0 \end{pmatrix} \begin{pmatrix} 1 &2 \\ 3 &4 \end{pmatrix} }
 Answer
 The second matrix has its first row multiplied by and its second row multiplied by .
 Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "/mathoid/local/v1/":): {\displaystyle \begin{pmatrix} 3 &6 \\ 0 &0 \end{pmatrix} }
 The second matrix has its first row multiplied by Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "/mathoid/local/v1/":): {\displaystyle 4 }
and its second row multiplied by .
 The second matrix undergoes the pivot operation of replacing the second row with times the first row added to the second.
 The first matrix undergoes the column operation of: the second column is replaced by times the first column plus the second.
 The first matrix has its columns swapped.
 Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "/mathoid/local/v1/":): {\displaystyle \begin{pmatrix} 2 &1 \\ 4 &3 \end{pmatrix} }
 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 Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "/mathoid/local/v1/":): i,j entry is the number of roads from city to city . 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 twoway streets. Vermont doesn't have many oneway streets.)
 What is the significance of the square of the incidence matrix? The cube?
 Answer
 The incidence matrix is this (e.g, the first row shows that there is only one connection including Burlington, the road to Winooski).
 Because these are twoway roads, any road connecting city to city gives a connection between city Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "/mathoid/local/v1/":): j and city Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "/mathoid/local/v1/":): i .
 The square of the incidence matrix tells how cities are connected by trips involving two roads.
 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.)
 Answer
The pay due each person appears in the matrix product of the two arrays.
 Problem 4
Find the product of this matrix with its transpose.
 Answer
The product is the identity matrix (recall that ). An explanation is that the given matrix represents, with respect to the standard bases, a rotation in of radians while the transpose represents a rotation of radians. The two cancel.
 This exercise is recommended for all readers.
 Problem 5
Prove that the diagonal matrices form a subspace of . What is its dimension?
 Answer
The set of diagonal matrices is nonempty as the zero matrix is diagonal. Clearly it is closed under scalar multiples and sums. Therefore it is a subspace. The dimension is Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "/mathoid/local/v1/":): n ; here is a basis.
 Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "/mathoid/local/v1/":): {\displaystyle \{\begin{pmatrix} 1 &0 &\ldots \\ 0 &0 \\ & &\ddots \\ 0 &0 & &0 \end{pmatrix},\ldots, \begin{pmatrix} 0 &0 &\ldots \\ 0 &0 \\ & &\ddots \\ 0 &0 & &1 \end{pmatrix} \} }
 Problem 6
Does the identity matrix represent the identity map if the bases are unequal?
 Answer
No. In , with respect to the unequal bases and , the identity transformation is represented by by this matrix.
 Problem 7
Show that every multiple of the identity commutes with every square matrix. Are there other matrices that commute with all square matrices?
 Answer
For any scalar and square matrix we have .
There are no other such matrices; here is an argument for matrices that is easily extended to . If a matrix commutes with all others then it commutes with this unit matrix.
From this we first conclude that the upper left entry must equal its lower right entry . We also conclude that the lower left entry is zero. The argument for the upper right entry is similar.
 Problem 8
Prove or disprove: nonsingular matrices commute.
 Answer
It is false; these two don't 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.
 Answer
A permutation matrix has a single one in each row and column, and all its other entries are zeroes. Fix such a matrix. Suppose that the th row has its one in its th column. Then no other row has its one in the th column; every other row has a zero in the th column. Thus the dot product of the th row and any other row is zero.
The th row of the product is made up of the dot products of the th row of the matrix and the columns of the transpose. By the last paragraph, all such dot products are zero except for the th one, which is one.
 Problem 10
Show that if the first and second rows of are equal then so are the first and second rows of . Generalize.
 Answer
The generalization is to go from the first and second rows to the th and th rows. Row of is made up of the dot products of row of and the columns of . Thus if rows and of are equal then so are rows and of .
 Problem 11
Describe the product of two diagonal matrices.
 Answer
If the product of two diagonal matrices is defined— if both are — then the product of the diagonals is the diagonal of the products: where are equalsized diagonal matrices, is all zeros except each that entry is .
 Problem 12
Write
as the product of two elementary reduction matrices.
 Answer
One way to produce this matrix from the identity is to use the column operations of first multiplying the second column by three, and then adding the negative of the resulting second column to the first.
Column operations, in contrast with row operations) are written from left to right, so doing the above two operations is expressed with this matrix product.
Remark. Alternatively, we could get the required matrix with row operations. Starting with the identity, first adding the negative of the first row to the second, and then multiplying the second row by three will work. Because successive row operations are written as matrix products from right to left, doing these two row operations is expressed with: the same matrix product.
 This exercise is recommended for all readers.
 Problem 13
Show that if has a row of zeros then (if defined) has a row of zeros. Does that work for columns?
 Answer
The th row of Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "/mathoid/local/v1/":): GH is made up of the dot products of the Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "/mathoid/local/v1/":): i th row of with the columns of . The dot product of a zero row with a column is zero.
It works for columns if stated correctly: if has a column of zeros then (if defined) has a column of zeros. The proof is easy.
 Problem 14
Show that the set of unit matrices forms a basis for .
 Answer
Perhaps the easiest way is to show that each matrix is a linear combination of unit matrices in one and only one way:
 Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "/mathoid/local/v1/":): {\displaystyle c_1\begin{pmatrix} 1 &0 &\ldots \\ 0 &0 \\ \vdots \end{pmatrix} +\dots+ c_{n,m}\begin{pmatrix} 0 &0 &\ldots \\ \vdots \\ 0 &\ldots & &1 \end{pmatrix} =\begin{pmatrix} a_{1,1} &a_{1,2} &\ldots \\ \vdots \\ a_{n,1} &\ldots & &a_{n,m} \end{pmatrix} }
has the unique solution Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "/mathoid/local/v1/":): {\displaystyle c_1=a_{1,1} } , , etc.
 Problem 15
Find the formula for the th power of this matrix.
 Answer
Call that matrix . We have
 Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "/mathoid/local/v1/":): {\displaystyle F^2=\begin{pmatrix} 2 &1 \\ 1 &1 \end{pmatrix} \quad F^3=\begin{pmatrix} 3 &2 \\ 2 &1 \end{pmatrix} \quad F^4=\begin{pmatrix} 5 &3 \\ 3 &2 \end{pmatrix} }
In general,
where is the th Fibonacci number and , Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "/mathoid/local/v1/":): {\displaystyle f_1=1 } , which is verified by induction, based on this equation.
 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 .
 Answer
Chapter Five gives a less computational reason— the trace of a matrix is the second coefficient in its characteristic polynomial— but for now we can use indices. We have
while
and the two are equal.
 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?
 Answer
A matrix is upper triangular if and only if its Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "/mathoid/local/v1/":): {\displaystyle i,j} entry is zero whenever Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "/mathoid/local/v1/":): i>j . Thus, if are upper triangular then and are zero when Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "/mathoid/local/v1/":): i>j . An entry in the product Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "/mathoid/local/v1/":): {\displaystyle p_{i,j}=g_{i,1}h_{1,j}+\dots+g_{i,n}h_{n,j} } is zero unless at least some of the terms are nonzero, that is, unless for at least some of the summands both and . Of course, if this cannot happen and so the product of two upper triangular matrices is upper triangular. (A similar argument works for lower triangular matrices.)
 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.
 Answer
The sum along the Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "/mathoid/local/v1/":): i th row of the product is this.
 This exercise is recommended for all readers.
 Problem 19
Give an example of two matrices of the same rank with squares of differing rank.
 Answer
Matrices representing (say, with respect to ) the maps that send
and
will do.
 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?
 Answer
The combination is to have all entries of the matrix be zero except for one (possibly) nonzero entry in each row and column. Such a matrix can be written as the product of a permutation matrix and a diagonal matrix, e.g.,
 Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "/mathoid/local/v1/":): {\displaystyle \begin{pmatrix} 0 &4 &0 \\ 2 &0 &0 \\ 0 &0 &5 \end{pmatrix} =\begin{pmatrix} 0 &1 &0 \\ 1 &0 &0 \\ 0 &0 &1 \end{pmatrix} \begin{pmatrix} 4 &0 &0 \\ 0 &2 &0 \\ 0 &0 &5 \end{pmatrix} }
and its action is thus to rescale the rows and permute them.
 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 matrix and a 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 matrix, a Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "/mathoid/local/v1/":): {\displaystyle 10 \! \times \! 20 } matrix, a matrix, and a matrix.
 (Very hard.) Find a way to multiply two matrices using only seven multiplications instead of the eight suggested by the naive approach.
 Answer
 Each entry takes Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "/mathoid/local/v1/":): r multiplications and there are entries. Thus there are multiplications.
 Let be Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "/mathoid/local/v1/":): {\displaystyle 5 \! \times \! 10 }
, let be , let be , let Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "/mathoid/local/v1/":): {\displaystyle H_4 }
be . Then, using the formula from the prior part,
Failed to parse (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle {\begin{array}{ll}{\textit {this\ association}}&{\textit {uses\ this\ many\ multiplications}}\\\hline ((H_{1}H_{2})H_{3})H_{4}&1000+500+25=1525\\(H_{1}(H_{2}H_{3}))H_{4}&1000+250+25=1275\\(H_{1}H_{2})(H_{3}H_{4})&1000+100+100=1200\\H_{1}(H_{2}(H_{3}H_{4}))&100+200+50=350\\H_{1}((H_{2}H_{3})H_{4})&1000+50+50=1100\end{array}}}
shows which is cheapest.
 This is reported by Knuth as an improvement by S. Winograd of a formula due to V. Strassen: where ,
 Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "/mathoid/local/v1/":): {\displaystyle \begin{pmatrix} a &b \\ c &d \end{pmatrix} \begin{pmatrix} A &B \\ C &D \end{pmatrix} }
 Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "/mathoid/local/v1/":): {\displaystyle \begin{pmatrix} a &b \\ c &d \end{pmatrix} \begin{pmatrix} A &B \\ C &D \end{pmatrix} }
 ? Problem 22
If and are square matrices of the same size such that , does it follow that Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "/mathoid/local/v1/":): {\displaystyle BABA=0 } ? (Putnam Exam 1990)
 Answer
This is how the answer was given in the cited source.
No, it does not. Let and represent, with respect to the standard bases, these transformations of .
Observe that
 Problem 23
Demonstrate these four assertions to get an alternate proof that column rank equals row rank. (Liebeck 1966)
 iff .
 iff .
 .
 .
 Answer
This is how the answer was given in the cited source.
 Obvious.
 If then where . Hence by (a). The converse is obvious.
 By (b), , ... , are linearly independent iff , ... , are linearly independent.
 We have . Thus also and so we have .
 Problem 24
Prove (where is an matrix and so defines a transformation of any dimensional space with respect to where is a basis) that . Conclude
 iff ;
 iff ;
 iff and ;
 iff ;
 (Requires the Direct Sum subsection, which is optional.) iff .
 Answer
This is how the answer was given in the cited source.
Let be a basis for ( might be ). Let be such that . Note is linearly independent, and extend to a basis for : where .
Now take . Write
and so
But , so and we now know
spans .
To see is linearly independent, write
and, since we get a contradiction unless it is (clearly it is in , but is a basis for ).
Hence .
References[edit]
 Ackerson, R. H. (Dec. 1955), "A Note on Vector Spaces", American Mathematical Monthly (American Mathematical Society) 62 (10): 721.
 Liebeck, Hans. (Dec. 1966), "A Proof of the Equality of Column Rank and Row Rank of a Matrix", American Mathematical Monthly (American Mathematical Society) 73 (10): 1114.
 William Lowell Putnam Mathematical Competition, Problem A5, 1990.