Matrix Addition and Scalar Multiplication

Matrices play a central role in linear algebra. We can add matrices to each other, multiply a matrix by a scalar, and multiply matrices. Some matrices have inverses; square matrices have eigenvalues and eigenvectors. Many of these matters lie ahead of us in the unfolding of linear algebra.

The word matrix now has many commercial and linguistic spinoffs for movies, computer games, computer memory, and medical search engines. There is even a matrix market, which is a repository for matrix test data that can be used in comparative studies of linear algebra algorithms.

It is customary to write A = (a_ij) to signify that the generic elements in A are named a_ij. Sometimes it is more convenient to write the generic elements of A as A_ij or (A)_ij. If A is m × n, then 1 ≤ i ≤ m and 1 ≤ j ≤ n in this discussion. The notation denotes the set of all m × n matrices. For a fixed pair (m, n), the set becomes a vector space if we agree to use the ordinary definitions of adding matrices and multiplying matrices by scalars. Thus, if A and B are in , then the definitions of matrix addition and multiplication by a scalar are

The zero element in this space is designated 0, and defined by 0_ij = 0. Notice that is a doubly indexed infinite sequence of distinct vector spaces. In fact, the parameters n and m range independently over the set of all positive integers.

SOLUTION

SOLUTION

In summary, the following are the salient properties of the vector space :

Here we take all values such that 1 ≤ i ≤ m and 1 ≤ j ≤ n. Once these definitions have been made, it is an easy matter to prove all the vector–space properties in Section 2.4. For example, A + 0 = A, and so forth. Thus, is a vector space.

We have already gone far beyond this stage in matrix algebra. Recall that the products Ax and AB have been defined in Sections 1.2 and 1.3. Specifically, if A is m × n and x is n × 1, then

Notice that the product in this case is an m × 1 matrix, or in other words a column vector containing m components.

SOLUTION This is an example of a matrix–vector product, obeying the preceding rule. The calculation produces

Matrix–Matrix Multiplication

The matrix–matrix product was defined in Section 1.3, and goes like this: The general matrix–matrix product AB exists whenever the number of columns in A matches the number of rows in B. Let the columns in B be denoted by b₁, b₂, …, b_k. Then AB is the matrix whose columns are Ab₁, Ab₂, …, Ab_k. Notice that the matrix–vector product is a special case of the matrix–matrix product, since a column vector is an n × 1 matrix.

If A is m × n and if B is n × k, then AB will have k columns, each being a vector in . In short, AB is m × k. The pattern of dimensions here should be remembered like this:

The common index n is necessitated by the fact that we must multiply each column b_j in B by the matrix A, and Ab_j makes sense only when the number of columns in A matches the number of components in each column vector b_j.

EXAMPLE 4

What is the product

SOLUTION We denote the columns of B by the notation b₁, b₂, b₃ and obtain

There are several ways to interpret matrix multiplication.¹ We have just seen the first way, which is taken as the definition. If it is desired to know the (i, j)-element in the product AB, we must first concentrate on the jth column of the product, which is Ab_j. Here (as previously) we use b_j to denote the jth column in B. Now, what is this vector Ab_j? It is a linear combination of the columns of A with coefficients taken from the vector b_j. (This was the matrix-product definition given in Section 1.3.) Suppose A is an m × n matrix and B is an n × k matrix. Note the critical entry of n in this calculation. Thus, using a_r for column r in A, we have

Here, the entries a₁, a₂, …, a_n are the columns of A. Because we asked for the ith element in this vector, we have

We prefer to write this as

Here, 1 ≤ i ≤ m and 1 ≤ j ≤ k. This formula provides a second way of interpreting the product AB.

Each summation in computing the product AB contains n multiplications, and there are mk of them because we need all values of (i, j). Consequently, matrix–matrix multiplication can be a computationally expensive operation, involving nmk scalar multiplications. If the matrices are square, say n × n, then the number of multiplications is n³. (This does not include the additions involved.) Of course, these considerations come into play only when the matrices are enormous, as occurs in many practical problems. Think of n = 10⁸, for which we obtain n³ = 10²⁴.

Pre-multiplication and Post-multiplication

Another example is given here to illustrate in complete detail that we can carry out a matrix–matrix product as either a post-multiplication by columns or a pre-multiplication by rows. First, let us use post-multiplication of the columns b_i of the matrix B into the matrix A. In this example, A is 3 × 2 and B is 2 × 2.

Next, we illustrate pre-multiplication by the rows r_i of matrix A with the same matrices B.

Of course, the two procedures lead to identical results!

Dot Product

The dot product between two vectors u = (u₁, u₂, u₃, …, u_n) and v = (v₁, v₂, v₃, …, v_n) is

which is the standard inner product in the Euclidean vector space . In matrix notation, the dot product can also be written as

If we use this notation, then we can say that (AB)_ij is the dot product of row i in A with column j in B. This is a third way of interpreting AB. Let us use r_i to designate row i in A. Then we have the formula

(Here we continue to denote column j in B by b_j.) This formula enables us to compute any element in the product AB with one simple dot product.

THEOREM 1

The (i, j)-element in the product of two matrices A and B can be written in summation notation or as the dot product of row i in A with column j in B.

EXAMPLE 5

What is the (2, 4)-element in this product? That is, what is (AB)_2,4?

SOLUTION We need not compute the entire product AB to answer this question. We simply compute the dot product of row 2 in A with column 4 in B, which is

Special Matrices

A number of special categories of matrices will be enumerated here. A matrix is square if it has the same number of rows as columns. The diagonal of a square matrix A is the sequence of elements A_ii. The other elements are called off-diagonal elements. If all off-diagonal elements are 0, we say that A is a diagonal matrix. Among the diagonal matrices, the identity matrix is especially important: it has 1’s on the diagonal, and 0’s elsewhere. Here are examples of a square matrix, a diagonal matrix, and an identity matrix:

The n × n identity matrix is denoted by I_n or by I, if its size is clear from the context. We often denote the elements of an identity matrix by δ_ij. This is called the Kronecker delta.² The formal definition is

SOLUTION Here is a case in point:

PROOF We compute the (i, j)-element in the product AI_n using methods discussed previously:

Note that in the summation, the term δ_rj will be zero except when r = j. Then its value is 1. Hence, only one term in the sum survives, namely the one where r = j. The other equation is proved in the same manner.

Matrices with special structure occur in many applications. A square matrix A is said to be upper triangular if a_ij = 0 when i > j. Similarly, we have a concept of lower triangular: a_ij = 0 when i < j. (These definitions are also meaningful for nonsquare matrices.) See Figure 3.1 for illustrations of some matrices with special structure.

FIGURE 3.1 Matrices with special structure.

SOLUTION Here is a numerical case:

Subspaces are taken up systematically in Section 5.1.

SOLUTION Here is a simple case to guide us:

PROOF Let A and B be n × n upper triangular matrices. Let 1 ≤ j < i ≤ n. It is to be proved that (AB)_ij = 0. We have

In this calculation, use first the fact that a_ir = 0 if r < i. Then only terms having r ≥ i enter the sum. Next, use the fact that b_rj = 0 when r > j. The restriction on r is then i ≤ r ≤ j, which is impossible, because we assumed j < i.

A similar result is true for lower triangular matrices, and is left as General Exercise 62.

Matrix Transpose

When we exchange the rows and columns of a matrix, we obtain the transpose of the matrix, which is of particular importance.

SOLUTION

PROOF We use the subscript notation for elements of matrices and (not unexpectedly) the definition of a matrix product:

There is another way to describe what is happening in the preceding proof: To determine the (i, j)-element in B^TA^T, we should take the dot product of row i in B^T with column j in A^T. But this is the same as the dot product of column i in B with row j in A. That is the same as the dot product of row j in A with column i in B. Finally, this is the (j, i)-element in AB or the (i, j)-element in (AB)^T.

Here are four computational rules involving the matrix transpose:

Symmetric Matrices

A matrix A such that A = A^T is said to be symmetric. Here is a symmetric matrix whose elements are random numbers from the interval [0, 1], generated by mathematical software:

The symmetric property here depends upon three equations being true: a₂₁ = a₁₂, a₃₁ = a₁₃, and a₃₂ = a₂₃.

Skew–Symmetric Matrices

While a symmetric matrix A has the property A^T = A, a skew–symmetric matrix has the property A^T = −A, and this contains a minus sign! If a matrix is simultaneously symmetric and skew–symmetric, then it must be the zero matrix. (If A^T = A = −A^T, then A = 0.) Moreover, there is a representation of a square matrix as the sum of a symmetric matrix and a skew–symmetric matrix. The equation that proves this is

The first matrix on the right is symmetric and the second matrix is skew– symmetric.

The unicity of the splitting of A into symmetric and skew–symmetric parts can be easily established. Suppose that

where B is symmetric and C is skew–symmetric. We shall prove first that . By the first hypothesis, we obtain

Because C is skew–symmetric by hypotheses, . Using the symmetry of B, we see that

Then C is determined by the equation

EXAMPLE 10

Express this matrix as the sum of a symmetric matrix and a skew–symmetric matrix:

SOLUTION We let the symmetric part be

and let the skew–symmetric part be

Verifying, we find .

Non-commutativity of Matrix Multiplication

Now we come to the question of commutativity of matrix multiplication. Let us choose at random several square matrices A and B and see whether AB = BA.

Because these matrices seem typical, can we not assume that, in general, AB = BA? Most emphatically, the answer is no! In the real world, Baconian inductive reasoning is often used. It does proceed by looking at many examples, from which some tentative conclusion can be drawn. But this can be used in mathematics only to suggest something that may be true. In the present case, the suspected theorem is false, and generally AB ≠ BA. For example, we have

Of course, one example is sufficient to demolish the conjecture that matrix multiplication is commutative. The apparently random integer matrices displayed at the beginning of this section show that sometimes a pair of matrices will commute with each other. But those matrices are not actually random; they were carefully constructed to illustrate the existence of commuting pairs. Maybe you can find others.

CAUTION

Matrix multiplication is not commutative; that is, in general, one must expect that

Associativity Law for Matrix Multiplication

What can be said about associativity of matrix multiplication? Here the result is simple (and very useful).

THEOREM 6

Matrix multiplication is associative. Thus, if the products exist, we have

PROOF We calculate (and get practice in handling summations):

An example of the associative law for matrix multiplication is given here:

Calculating the product in a different order, we have

Linear Transformations

The next theorem shows why matrix multiplication is defined in the manner explained in Section 1.3.

PROOF We use the associativity of matrix multiplication in this quick calculation:

Another interpretation of this proof is as follows. Column i of matrix A, say a_i, is the image of the ith standard unit vector e_i = (0, …, 1, 0, …, 0) under the linear transformation S; namely, S(e_i) = a_i. We obtain similar results for matrix B and linear transformation T; that is, T(e_i) = b_i, where b_i is the ith column of matrix B. Consequently, we obtain

which is the ith column of matrix AB. Now associativity of matrix multiplication is a corollary of associativity of functional composition.

Elementary Matrices

When a single row operation is applied to the identity matrix, the result is called an elementary matrix. Thus, if denotes any row operation, we can set and get an elementary matrix, E. It is easy to recognize an elementary matrix because it differs very little from an identity matrix. Here, we interpret a row operation as a function that applies to a matrix and produces another matrix. Examples of elementary matrices are

Why are elementary matrices useful? They enable us to interpret row operations on a matrix as multiplication on the left by one or more elementary matrices. For example, using E₁, E₂, and E₃ as in the preceding display, we have

Now we have a more sophisticated way of thinking about row equivalence. If A ~ B, then a sequence of row operations can be applied to A, producing B. Hence, there will exist elementary matrices E_i such that

PROOF We give the proof for one type of row operation—namely, the addition of a scalar multiple of one row onto another row. (This is the most tiresome of the three cases.) Suppose specifically that is the operation of adding c times row s in A onto row r. (Of course, s ≠ r.) The action of on the n × n identity matrix produces the elementary matrix E with these entries:

(To verify this, begin by noticing that E and I differ only in row r because of the factor δ_ir.) The matrix à that results from applying to A has this definition:

Next, we compute EA, element-by-element:

More on the Matrix–Matrix Product

We have been using the product Ax in many situations involving systems of equations. This product exists if A is, say, m × n and x is n × 1. An analogous product y^TA exists when y^T is 1 × m. This will certainly arise naturally if we find it necessary to proceed from Ax = b to (Ax)^T = b^T, because this is the same as x^TA^T = b^T. (Remember that taking the transpose of a product requires the order of the factors to be reversed.) We can prove theorems about this product y^TA that are logically parallel to the results about the product Ax. We have

where the column vector b is m × 1 and the row vector c^T is 1 × n.

Recall, from Section 1.2, that the product Ax was defined to be

where a_j denotes the jth column of A. The vector x is a column vector, and n is the number of components in x as well as the number of columns in A. This definition of a matrix multiplying a vector led us to the appropriate definition of AB. Namely, if the matrix B has columns b_j, then

SOLUTION The desired entry is in column j of AB, and this column is Ab_j, by the definition of the product AB (as quoted previously). The ith component in this vector is the desired entry in AB. Thus, it is

Just as we expect, it is the dot product of row i of matrix A (denoted here by r_i) and column j of matrix B (written here as b_j).

Vector–Matrix Product

Suppose that we have the m × n matrix A, the 1 × n row vector c, and the 1 × m row vector y^T. Formulas similar to those obtained previously can be given for products

when y^T is a row vector. Namely, we write

In this equation, the rows of A are the vectors r_i. The matrix A is m × n. We can verify the correctness of the displayed formula by computing the jth component of the vectors on the right and on the left. The one on the left is

The one on the right is

Consequently, we have the following two important theorems.

THEOREM 9

If y^T is a row vector, then y^TA is a linear combination of the rows of A, with coefficients taken to be the components of the row vector y^T.

where r_i are the rows of A.

THEOREM 10

If the rows of A are denoted by r₁, r₂, …, r_m, then

PROOF The (i, j)-element in AB is .

The (i, j)-element in B is (r_iB)_j = r_ib_j, where b_j is column j in B.

This is just the dot-product formula for any entry in the product AB.

SOLUTION As an example to exhibit this phenomenon in matrix theory, we offer

Thus, one must resist the temptation in matrix algebra to go from the equation AB = AC to the equation B = C, solely on the strength of the fact that A ≠ 0. See General Exercises 3, 12, 34, and 44.

Application: Diet Problems

Linear algebra can play a role in dietetics, whether for humans, animals, or bacteria, among others. The objective might be to achieve some nutritional goal through a suitably compounded mixture of foods and dietary supplements. These problems often lead to systems of linear inequalities, a topic treated briefly here.

We assume that there are foods labeled f₁, f₂, …, f_n, and that the nutritional content of each is known. There are m different nutrients being considered, and they are labeled v₁, v₂, …, v_m. (Think of these as vitamins in a typical case.) The nutritional values are displayed in a table.

The entries a_ij signify the amounts of nutrients in each gram of each food. Specifically, a_ij is the amount of nutrient v_i in food f_j. (Standard units must have been established.) In a given row, the units should be the same, as they pertain to a single nutrient. Units (for example, grams) would be assigned to each food, f_j.

Looking down a column, say column j, we see the amounts of each nutrient contained in one unit of food f_j. Looking across a row, say row i, we see what foods contain nutrient v_i and in what quantities. For example, if f_j is orange juice and v_i is vitamin C, then a_ij might indicate how many milligrams of vitamin C are contained in each gram of orange juice.

A diet will be a vector x = (x₁, x₂, …, x_n). If each day a patient ingests x₁ units of food f₁, x₂ units of food f₂, and so on, then he or she will get units of nutrient v_i. The problem is to formulate a diet that provides on a daily basis certain prescribed amounts of each nutrient. We can define a vector b containing these minimum daily requirements and ask for a diet, x, such that

For example, suppose that we are considering a diet that involves three nutrients and four foods. The matrix of nutritional values is known, and we have a target for minimal nutrition. The table of nutrients is the following matrix:

A diet is a vector x in whose components indicate the number of units of each food to be made available to the patient or animal, as the case may be. The product Ax is a vector of three components, and we want these components to be at least 84, 43, 68. We can start by solving the system

In the usual way, we have

We find the general solution to be

Here we have one free variable, x₄. We do not want any component of the vector x to be negative, and this restricts x₄ to the interval 0 ≤ x₄ ≤ . The resulting extreme cases are x = (5, 8, 10, 0) and (0, 17/4, 15/2, ). Different choices of pivot rows lead to different extreme solutions.

This is probably a good opportunity to raise the issue of systems of linear inequalities. We might relax the requirement Ax = b to be

(For two vectors u and v in , we write u ≥ v when u_i ≥ v_i for 1 ≤ i ≤ n.) That would certainly be better if there exists no solution to the first problem, Ax = b.

In the diet problems, it can often happen that the system of linear equations is inconsistent. (Remember that a system of equations in which the equations outnumber the variables is likely to be inconsistent.) Conversely, it may not be necessary to meet the requirements exactly because overnourishment is usually not serious—it is merely wasteful. What is the right formulation of the problem if it is inconsistent as it originally stands? Obviously we can require simply Ax ≥ b, as explained previously. Is this a numerical problem that we can easily solve with our trustworthy row-reduction algorithm? Here, we tread on dangerous ground. Consider a very simple case

Yielding to the temptation of using row operations, we proceed to

This is wrong! For example, it seems to say that x₂ < 0. Where is the error? The manipulation on the inequalities is completely unjustified. A better approach is to turn the inequalities into equations by inserting positive parameters p₁, p₂ like this:

One step of the standard row-reduction leads to

Notice that the term −2p₁ + p₂ can be either positive or negative. In order that x₂ ≥ 0, we must have 2 − 2p₁ + p₂ ≤ 0. For example, we could let p₁ = 1, p₂ = 0, x₂ = 0, and . In problems of this type, there can be many solutions, and usually there is a cost function involved. In that case, the variables should have low values, in general. This leads to a type of problem called linear programming, in which we seek to minimize a linear objective function c₁x₁ + ··· + c_nx_n subject to constraints of the form x ≥ 0 and Ax ≥ 0. Special codes are available for this type of problem. Row-reduction techniques by themselves are virtually useless in these optimization problems.

EXAMPLE 13

A diet problem leads to this system of linear inequalities:

Find one or more good solutions.

SOLUTION We change from a system of inequalities to a system of equations Ax ≥ b by introducing a vector p whose coordinates are to be nonnegative: Ax = b + p. There are now five unknowns: the two components of x and the three components of p. Here is the augmented matrix for the problem:

The reduced echelon form of this matrix is

We obtain the genral solution

From the third equation we see that the smallest possible value for p₁ is 7.5, obtained by selecting p₂ = p₃ = 0. With these values of p, we compute an acceptible solution (x₁, x₂) = (, 4). Hence, we obtain (15.5, 5, 12) ≥ (8, 5, 12) on the righthand side of the preceding inequality.

Dangerous Pitfalls

We end this section with some words of caution.

1. Usually AB ≠ BA. For example, we see that

Thus, the factors in matrix multiplication do not commute, in general.

2. If AB = AC, we cannot infer that B = C. For example, we have

where cancellation of the matrix factor A is not correct!

3. If AB = 0, we cannot conclude that A = 0 or B = 0. For example,

but neither factor A nor B is the zero matrix!

4. If a practical problem results in a system of linear inequalities, say Ax ≤ b, do not expect the row-reduction techniques to work. See the discussion in the subtopic of diets, in this section, for one way of proceeding.

SUMMARY 3.1

KEY CONCEPTS 3.1

The space of all m × n matrices, addition and multiplication of matrices, dot product of two vectors, multiplication of a vector by a matrix, diagonal matrices, identity matrices, transpose of a matrix, symmetric matrices, skew–symmetric matrices, elementary matrix, triangular matrices, associativity, commutativity, upper triangular, lower triangular, Kronecker delta, outer products, diet problems

GENERAL EXERCISES 3.1

1. Refer to Example 4. Explain why BA cannot be computed.

2. If A is a square matrix, the product AA exists, and is denoted by A². Compute the square of the matrix

3. For real numbers r, we know that if r² = 0, then r = 0. Is this true also for square matrices? A theorem or example is required.

4. Is this the correct definition of upper triangular, for a matrix A: A_ij ≠ 0 when j ≥ i.

5. Find all the 2 × 2 matrices that commute with the matrix

6. Explain why, in defining row operations, we must insist on i ≠ j in the operation r_i ← r_i + αr_j.

7. Which of these matrices is not an elementary matrix?

8. Define

Verify that BA = I. Then solve the system Ax = c by multiplying both sides of this equation by B. This produces BAx = Bc or x = Bc. Verify by an independent calculation that Ax = c.

9. Let . What is A^T? What is Ax if ?

10. Let ,

C = AB

Compute these: C₂₃, A^T, A + B, and B².

11. Find all the matrices that commute with

12. Certainly we can find n × n matrices that are nonzero, yet satisfy the equation AB = 0. Is this possible with B = A? Is it possible with B = A^T?

13. Explain why this diet problem leads to an inconsistent system of linear equations:

14. (Continuation.) Find a good solution of the inequality Ax ≥ b, using A and b from the preceding exercise. Ideally, there will exist a vector x such that if the vector y satisfies b ≤ Ay ≤ Ax, then x = y. Try to find such an x.

15. Solve this diet problem:

As usual, there may be some solutions that are better than others. Try to find an optimal solution, using the least quantities of foodstuffs to accomplish the nutritional objective.

16. Criticize this solution to a diet problem: Ax ≥ b where and

We find .

Thus, we have x₁ = 1 and x₂ is either 1 or .

17. Show in detail the operations for the matrix–matrix multiplication AB^T with

23. Explain why, for any square matrix A, A + A^T and AA^T are symmetric. Explain why A must be square in these assertions.

24. (Continuation.) Explain why every square matrix is the sum of a symmetric matrix and a skew–symmetric matrix. General Exercise 3 may be helpful.

25. Explain why every square matrix is the sum of a lower and an upper triangular matrix.

26. Establish that the diagonal matrices, the upper triangular matrices, and the symmetric matrices form three subspaces in .

27. Explain why, for any matrix A, this equation holds: (A^T)^T = A.

28. Establish that if (m, n) ≠ (α, β), then .

29. Explain why or find a counterexample: The product of two symmetric n × n matrices is symmetric.

30. Let A be a fixed matrix in . Consider the set of all matrices that commute with A. Is this set a subspace of ?

31. Let A be an n × n matrix. Establish that A commutes with every polynomial in A. (That terminology means a matrix of the form α₀I + α₁A + α₂A² + ··· + α_mA^m.)

32. Is it possible for a 2 × 2 matrix to have the property that its powers (including A⁰ = I) span ?

33. Explain why, for 2 × 2 matrices, A² is a linear combination of I and A.

34. Find a 2 × 2 matrix, none of whose entries is zero, such that its square is zero.

35. Is there a 7 × 7 matrix of rank 7 all of whose entries are either 5 or 8?

36. Establish that (A + B)^T = A^T + B^T.

37. Explain why or find a counterexample: The product of two skew–symmetric matrices is skew–symmetric.

38. Give an example of two matrices, A and B, that are not row equivalent to each other, but their transposes are row equivalent to each other.

39. Give an argument why every 2 × 2 matrix A satisfies the equation

A² − (A₁₁ + A₂₂)A + (A₁₁A₂₂ − A₁₂A₂₁)I = 0 (This is one case of the Cayley–Hamilton Theorem. See Section 8.1.)

40. Establish the remaining case of Theorem 8. (Recall that the interchange of two rows can be executed by row operations of the other two types.)

41. If x and y are two vectors in , their outer product is

Here we assume that x and y are column vectors. The outer product then is an n × n matrix A, specified by the equation A_ij = x_iy_j. Explain why the rows of this matrix are scalar multiples of each other. What is the rank of the matrix xy^T? (The rank of a matrix is defined on p. 63.)

42. Is every square matrix the product of a lower triangular matrix and an upper triangular matrix?

43. Explain why the dot product has this property: x • y = y • x.

44. Find all the 2 × 2 matrices A such that A² = 0.

45. If A is an m × n matrix, what can be said of AI_n, AI_m, I_mA, and I_nA?

46. If A is a 2 × 2 upper triangular matrix and B is a 2 × 2 lower triangular matrix, what special properties does the product AB have? Is it possible to factor any 2 × 2 matrix into the product of an upper and a lower triangular matrix?

47. Explain this apparent contradiction: For some pair of matrices A and B we can have AB ≠ BA, yet in this calculation we have reversed the terms A_ikB_kj:

48. Find two different 2 × 2 matrices (other than ±I) such that AA^T = I.

49. Define A ⊕ B = AB + BA. Is this operation commutative? Is it associative? Answer the same questions for the operation A B = AB − BA.

50. Establish Theorem 9 by using transposes in the equation .

51. Let A be a square matrix. Assume that the homogeneous system of equations A²x = 0 has a nontrivial solution. Establish that the system Ay = 0 has a nontrivial solution.

52. Let A, B, and P be n × n matrices. If A = PBP^T, does it follow that A is symmetric?

53. Establish that if A ~ B, then there is a nonsingular matrix C such that A = CB.

54. Suppose that the column sums of a square matrix A are all equal to 1. Does it follow that the same property is true for A^k for all integers 2, 3, and so on?

55. (Continuation.) Repeat the argument in the preceding exercise when the column sums are all equal but not necessarily 1.

56. Establish the statements that are true and give counterexamples for the others. In each case we are dealing with n × n matrices.

57. Suppose that A and B are n × n symmetric matrices. Does it follow that (AB)^T = BA? Is the converse true?

58. Establish that for any matrix A (not necessarily square), AA^T is symmetric.

59. Explain why the hypothesis “A is square” leads to the conclusion “A + A^T is symmetric.”

60. Refer to the elements in the matrices A = (a_ij) and B = (b_ij). Compute these quantities: , , , . Recall the Kronecker delta: δ_ij is 1 when i = j; otherwise it is 0.

61. Suppose that a matrix A has the property A^TA = AA^T. Does it follow that A is square? Is the converse true? That is, if A is square, does it follow that A^TA = AA^T?

62. Establish that the product of two n × n lower triangular matrices is lower triangular.

63. For a vector x, we write x ≥ 0 if all components of x are nonnegative. Suppose that A is an m × n matrix such that Ax ≥ 0 whenever x ≥ 0. Does it follow that all entries in A are nonnegative?

64. Let A be an m × n matrix in which each entry is positive (i.e., greater than zero). Establish that, for any b in , the inequality Ax ≥ b has a solution. Also, show that if we drop the assumption on A that each entry be positive, the result is not true.

65. Let

What can be done with this diet problem? (We want Ax ≥ b.)

66. If x and y are vectors, does it follow from x > y that Ax > Ay? What hypothesis on A would be useful here? Establish a theorem of your own devising, and give examples.

67. Find the necessary and sufficient conditions on two symmetric 2 × 2 matrices so that their product is symmetric.

68. (Continuation.) Find the most general pair of symmetric 2 × 2 matrices whose product is not symmetric.

69. Let Ω be the operator that produces from A its reduced row echelon form Ω(A). Explain why Ω(AB) = Ω(A)B.

70. In , suppose addition is defined by the equation (A B)_ij = A_ij + B_ji. Would be a vector space? (A simple yes or no is not sufficient.)

71. Establish that the operation A → A^T is linear.

72. In Example 12, we found that if A and B have no zero entries, then it can happen that AB = 0. For 2 × 2 matrices, find general conditions for this to be true and give another simple example.

Solving Systems with a Left Inverse

Suppose it is known that a given system, Ax = b, has a solution. Instead of treating x as an unknown, we can let x denote one such concrete solution. Then Ax really is b. Suppose also that we are in possession of a matrix B such that BA = I. Then we can multiply both sides of the equation Ax = b by B and arrive at BAx = Bb, or Ix = Bb, or x = Bb. We have concluded that if x is a solution of the equation, then x must equal Bb.

Because this statement is often misinterpreted, we state it again as a theorem.

EXAMPLE 1

Consider the system Ax = b, in which

Fortune has smiled upon us and given us a matrix B such that BA = I, namely . The verification is

How can we use this information to solve the given system?

SOLUTION If the system of equations has a solution, it must be Bb. So we compute and then test it by substitution:

Notice that we do not talk about verifying the solution; we test it to see whether it is a solution. (There is a subtle difference.) Our work prior to the testing does not prove that the given x is a solution. Remember that we started by assuming that x was a solution! That assumption could have been false. A false assumption can get you in trouble!

EXAMPLE 2

Here we illustrate an incorrect use of Theorem 1. Consider this system of equations:

The coefficient matrix is . Let .

Then DC = I, as we quickly verify:

How can we use this information to solve the given system?

SOLUTION The original system of equations is Cy = g, where . Multiply both sides of this equation by D, getting DCy = Dg.

(There is no question that this is legitimate.) The equation reduces to y = Dg, so the solution must be

Just to be sure, we verify the solution by substitution and get a surprise:

Where is the error?

The procedure used depends for its validity on the consistency of the system of equations. That is, we must know in advance that there exists at least one solution. In this example, such knowledge is not present, and in fact the given system is inconsistent. This is revealed by the row-reduction process of the augmented matrix:

Similar fallacies can arise outside of linear algebra. (For example, see General Exercise 27.)

Solving Systems with a Right Inverse

To pursue these ideas further, suppose that again we want to solve a system of linear equations, Ax = b. Assume now that we have another matrix, B, such that AB = I. Then we can write A(Bb) = (AB)b = Ib = b; whence Bb solves the equation Ax = b. This conclusion did not require an a priori assumption that a solution exist; we have produced a solution. The argument does not reveal whether Bb is the only solution. There may be others.

EXAMPLE 3

Consider another system of linear equations:

How can we solve this system using information from Example 2?

SOLUTION The coefficient matrix here is the matrix D from Example 2.

Hence, the problem to be solved is Dx = f, where . We know that DC = I, where C is as in Example 2. Hence, by Theorem 2, one solution is x = Cf = [−3, 6, −12]^T. To check these results, we find that

Analysis

There are two phenomena here, illustrated by Examples 1 and 3. In the first case, if we know from some external information that the system Ax = b has a solution, then it must be Bb. That is not the same as saying flatly that Bb is a solution, because there may be no solution. There is that annoying additional hypothesis that there must exist a solution. In the second case, we are more fortunate, as the calculation shows that Cb is a solution, without further hypotheses. However, we do not know whether, in fact, it is the only solution.

EXAMPLE 4

Are these matrices related with regard to left and right inverses?

SOLUTION In Example 2, we had DC = I. Therefore, D is a left inverse of C and C is a right inverse of D.

SOLUTION We carry out a row reduction, getting

As usual, we write this in a form with the free variable on the right:

The problem has infinitely many solutions. The solution of the equation obtained in Example 3 arises by taking x₃ = −4.

To summarize in slightly different language, suppose that we wish to solve the system of linear equations Ax = b, and have a right inverse of A, say AB = I. Then Bb is a solution, as is verified by noting A(Bb) = (AB)b = Ib = b. Conversely, if we have a left inverse of A, say CA = I, then we can only conclude that Cb is the sole candidate for a solution; however, it must be checked by substitution to determine whether, in fact, it is a solution.

Square Matrices

The situation for square matrices is much simpler, and we turn to it next with a theorem of great importance. For example, in Section 7.1, we shall use the following theorem to deduce that if the rows of a square matrix form an orthonormal set, then the same is true of its columns.

PROOF Step 1. Let A and B be n × n matrices, and assume that BA = I. The equation Ax = 0 has only the trivial solution because if Ax = 0, then BAx = 0 and x = 0. (Use the equation BA = I.)

Step 2. The reduced echelon form of A must have n pivots, for if there were fewer there would exist free variables and there would exist nontrivial solutions to the homogeneous equation Ax = 0, contrary to the conclusion in Step 1.

Step 3. Because the matrix is square, each row has a pivot, and the reduced echelon form of A is I_n.

Step 4. We can solve any equation Ax = b by the row-reduction process, because A reduces to I in this process.We can also solve the equation AX = I, where I is the identity matrix and X is an n × n matrix. (This calculation can be done using one column at a time from the matrix I. It is more efficient to use the technique explained in Example 8 in Section 1.3.)

Step 5. AB = (AB)I = (AB) (AX) = A(BA) X = AIX = AX = I.

PROOF By Theorem 4, BA = I. Multiply each side of the equation in the hypothesis on the left by B, getting BAB = BAC. This reduces to B = C.

Invertible Matrices

Theorem 5 asserts that if a matrix has an inverse, then it has only one. We need this fact to justify the following definition.

An invertible matrix is also said to be nonsingular. If a matrix has no inverse, it is said to be singular or noninvertible.

EXAMPLE 6

Here are two matrices

Is one of these the inverse of the other? If so, which is which?

SOLUTION Do not make the mistake of thinking that it is necessary to compute the inverse of one of these two matrices. It is much easier to compute one of the products AB or BA. It turns out that AB = I. Several conclusions can be drawn, namely, BA = I, A⁻¹ = B, and B⁻¹ = A. Thus, each matrix is the inverse of the other. Theorem 4 applies here. If you compute the products to see whether they equal the identity matrix, the work will be quite different for AB and BA. But Theorem 4 asserts that both of the products will be I₃.

PROOF B = BI = B(AC) = (BA) C = IC = C

SOLUTION It is verified by multiplying the matrices, in either order, to get I₂. Recall Theorem 4, which asserts that in verifying that a square matrix B is the inverse of a square matrix A, we need check only one of the two equations AB = I or BA = I.

Do not be misled by this example into thinking that the inverse of an integer matrix is always an integer matrix, because it rarely is! For a 2 × 2 matrix, the inverse is

where ad − bc ≠ 0.

EXAMPLE 8

Solve this equation using an inverse matrix:

SOLUTION This equation has the form Ax = b, where A is the matrix in Example 7. To solve it, multiply both sides of the equation by A⁻¹, getting x = A⁻¹b. Thus, we find the solution

We can check our result by substitution into the original equation.

PROOF We wish to know that B⁻¹ A⁻¹ is the inverse of AB. It only requires direct verification, and this gives us a chance to use our new knowledge that matrix multiplication is associative (Theorem 7 in Section 3.1):

Elementary Matrices and LU Factorization

Some matrices have inverses that are easy to find. For example, the inverse of the diagonal matrix D = Diag(d_i) is clearly D⁻¹ = Diag(d_i⁻¹). Here Diag(α_i) is notation for a square diagonal matrix with diagonal elements α₁, α₂, …, α_n. Also, the inverse matrix of an elementary matrix that corresponds to a replacement operation such as

is found by simply changing the sign of the multiplier c in the matrix:

Inverses of elementary matrices arise naturally when we recall that elementary row operations on a matrix can be interpreted as pre-multiplication of A by elementary matrices. (Each elementary matrix carries out one row operation, as explained in Section 3.1, Theorem 8). Thus, the row-reduction process ending at U can be expressed like this:

This equation shows immediately that

where

By Theorem 8, any product of elementary matrices is invertible.

EXAMPLE 9

Suppose we have a reduction process that uses only replacement operations such as this one:

Establish the LU factorization of A.

SOLUTION By writing down the elementary matrices

we obtain

where

Notice that the multiplication of these elementary matrices is particularly easy! We multiply the elementary matrices together to form E = E₃E₂E₁ rather than finding the inverse of E, which would be more difficult. Finally, we obtain

The row-reduction process can include swapping and scaling of rows to avoid small pivots, which brings in pivoting and a permutation matrix. We explore matrix factorizations further in Section 8.2.

Computing an Inverse

We turn now to an algorithm for finding the inverse of a square matrix, if it has one. From Theorem 2, we know that if AX = I then the equation XA = I follows, it being assumed that all three matrices involved are square and of the same size. Thus, if the equation AX = I has a solution X, then X is the inverse of A.

In Section 1.3, systems of equations of this sort were discussed. One simply forms an augmented matrix and carries out the row-reduction process. If all goes well, the result will be . In other words, the result will be .

EXAMPLE 10

Compute an inverse of

SOLUTION We consider the augmented matrix

We remind the reader that this calculation is not dispositive, by, itself, in concluding that we have the inverse. As established by the calculation, we know that AX = I and X is a left inverse. An appeal to Theorem 4 is needed so that we can also infer XA = I and X is a right inverse.

More on Left and Right Inverses of Non-square Matrices

The method suggested for computing an inverse can be modified for finding right inverses or left inverses, as shown in the next examples.

EXAMPLE 11

Find all the right inverses of the matrix

SOLUTION To do this, we solve AX = I₂, where A is 2 × 3, X is 3 × 2, and I₂ is 2 × 2. The augmented matrix for this problem and its reduced row echelon form are

Because of column 3, we have one free variable for each of the two subproblems, and thus there are many solutions. Setting the free variables equal to zero, we get—as one possible right inverse—the 3 × 2 matrix

Because there are two columns and ultimately two free variables, there is a two-parameter family of solutions. Concentrating on the first column of X, we find that

We can treat the second column of X in the same way and obtain the general form of the right inverse:

We have left to General Exercise 50 a verification of this result.

SOLUTION To execute the search, we begin by setting up the equation to be solved: YA = I₃, where A is 2 × 3 and Y must be 3 × 2, since I₃ is 3 × 3. To make this into a familiar sort of problem, take transposes, getting A^TY^T = I₃. Here is the result of the row-reduction process:

Clearly, this system is inconsistent and A has no left inverse!

Invertible Matrix Theorem

The set of all n × n matrices is divided into two classes: the invertible matrices and the noninvertible matrices. The latter are also called singular, and we have noted previously that the word nonsingular is synonymous with ‘‘invertible.’’ The favorable and useful properties of an invertible matrix are many in number. Let us contemplate a few of them here, with proofs. Later in this section, a more comprehensive list of equivalent conditions is stated (Theorem 10).

PROOF The efficient way to prove such a theorem is to establish the circle of implications 1 2 3 4 5 1.

For 1 2, note that invertibility implies that an inverse exists, A⁻¹. Because AA⁻¹b = b, the system Ax = b has a solution. To see that it is unique, suppose that Ax = b. Multiply on the left by A⁻¹ to get x = A⁻¹b.

For 2 3, observe that 0 is the only solution of the equation Ax = 0. In other words, 0 is the only member of the kernel of A.

For 3 4, recall that if any column of A has no pivot position, then the homogeneous set of equations will have free variables and many solutions. By 3, this does not happen, and every column of A must have a pivot position.

For 4 5, observe that 4 forces there to be n pivot positions in A. Hence, each row must have a pivot.

For 5 1, recall that if each row of A has a pivot, then the row-reduction process applied to the augmented system , ends with , thereby establishing the invertibility of A. This argument gives us AX = I, and that suffices because of Theorem 4.

The following important theorem has many parts, each part asserting some property that an invertible matrix must possess. Each property in the theorem is equivalent logically to all the others. You can think of this as a list of important properties of any invertible matrix. But it is more than that, because a matrix that has any one of the listed properties must be invertible, without any further evidence. Caution: The theorem applies only to square matrices.

This theorem and other versions of it are collectively known as the Invertible Matrix Theorem. Some of the notation and terminology used in this theorem have not yet been dealt with in this text, but it is convenient to have all these properties listed together. For example, column spaces and row spaces arise in Section 5.1 and eigenvalues are covered in Section 6.1. To avoid almost doubling the number of equivalent statements in the Invertible Matrix Theorem, most statements involving A^T have been omitted. To help make the statement of this theorem more digestible for the reader, we intersperse it with some labels.

Application: Interpolation

One application of linear algebra that arises in many scientific enterprises involves the reconstruction of a function from knowledge of some of its values. For example, we might have empirical data that we wish to reproduce by means of a formula. Or, an experiment might lead to a table of data consisting of points in the plane (t_i, y_i) for i = 0, 1, 2, …, n. The variable t_i is thought of as the independent variable and y_i is the dependent variable. These data are discrete, meaning that we have no curve but only individual points. If a continuous function f is sought such that y_i = f(t_i) for all of the points in the given table, then this problem is called interpolation. Frequently we use polynomials for this task of interpolation. (Spline functions are usually better, but their theory is beyond the scope of this book.)

SOLUTION The polynomial will have these values: p(1) = 3, p(2) = 7, p(3) = 9. Thus, three conditions are placed on p. Degree 2 is chosen, because a polynomial of degree 2 has three available coefficients. Let p(t) = a + bt + ct². Then

The augmented matrix and its reduced echelon form are

The answer to the problem is then the polynomial p defined by p(t) = −3 + 7t − t². One verifies this result by evaluating the polynomial at the three given points and getting the values 3, 7, and 9.

The polynomial interpolation problem, if carefully stated, will always have a unique solution, as established in the next theorem.

PROOF We have seen in the preceding example that such a polynomial is governed by a system of equations. There will be n + 1 equations and n + 1 unknown coefficients in the general case considered here. The matrix that arises will be (n + 1) × (n + 1). Consider the homogeneous problem, in which all the values y_i are zero. The polynomial p must satisfy the equation p(t_i) = 0 for 0 ≤ i ≤ n. However, a nontrivial polynomial of degree n or less can have at most n zeros in the complex plane (see Fundamental Theorem of Algebra in Appendix B). Hence, we conclude that p = 0 and that the homogeneous problem has only the zero solution. The matrix mentioned previously is therefore invertible, and the system of equations in the nonhomogeneous problem will have a unique solution. (We are using one part of the Invertible Matrix Theorem: 5 4.)

EXAMPLE 14

Find a linear combination of these three functions

that takes values 4, 3, −4 at the points 0, 1, 2, respectively.

SOLUTION This is obviously impossible because each basic function takes the value zero at the point zero. This impossibility does not contradict the preceding theorem because that theorem does not apply in this situation. (It requires all the powers of the variable t, from 0 to n, inclusive.)

Interpolation by other functions is also possible, as illustrated in the next example.

EXAMPLE 15

Find a linear combination of these three functions

that takes values 1, 7/12, 13/30 at the points 4, 5, 6.

SOLUTION Let the unknown function be f = a₁h₁ + a₂h₂ + a₃h₃. When we impose the interpolation conditions, we obtain

We multiply each equation by a suitable factor to eliminate the fractions, thus arriving at the augmented matrix and its row reduced echelon form:

This work reveals that a₁ = 3, a₂ = −2, and a₃ = 1.

The preceding example has some interesting theoretical background. The relevant theorem is as follows.

(For a proof of this, see Cheney [1982, p. 195].)

Before leaving the subject of interpolation, we should point out that it is a topic in all elementary textbooks on numerical analysis. Interpolation by polynomials is emphasized, and efficient algorithms are developed for finding the polynomial that takes on prescribed values. The subject has a rich history, going back to Newton and some of his predecessors.

Mathematical Software

Mathematical software systems contain procedures useful in linear algebra such as computing the inverse of a given matrix. They are very easy to use in the following three well-known mathematical software packages, as will be shown here. We use a 3 × 3 matrix randomly generated by a MATLAB command.

MATLAB commands are given for these four tasks: (1) displaying numbers to full precision, (2) constructing a random matrix A, (3) invoking a program to compute the inverse of A, and (4) checking the results. This program and similar ones in Maple and Mathematica are shown in subsequent text. The programs may not automatically display numbers with the full precision in which they are computed and stored.

MATLAB 

Maple

format long 
A = -5.0+10*rand(3) 
inv(A) 
B*A 

with(LinearAlgebra):
A := RandomMatrix(3,3,
     generator=-5.0..5.0);
B := MatrixInverse(A);
B.A;

Mathematica

MatrixForm[A = Table[Random[Real,-5,5,15],3,3]]
MatrixForm[B = Inverse[A]]
B.A