Matrix Multiplication

10 Key excerpts on "Matrix Multiplication"

• 

  eBook - PDF

  Linear Algebra

  Examples and Applications

  • Alain M Robert(Author)
  • 2005(Publication Date)
  • WSPC

    (Publisher)

  Chapter 3 Matrix Multiplication In typography, the word matrix refers to a lead rectangle on which the characters are placed in view of the printing process. By analogy, in mathematics the term matrix refers to any rectangular array containing mathematical entities. If it has m rows and n columns, it is a matrix of size m x n (read m by n). In Chapter 1, arrays were viewed as representations of linear systems. Here, we deal with matrices in a more general and abstract way: Matrices of the same size form a vector space. Two matrices of suitable size may even be multiplied together. 3.1 Row by Column Multiplication 3.1.1 Linear Fractional Transformations To guess how to define the multiplication of 2 x 2 matrices, let us consider the composition of linear fractional transformations. Such a function is defined by a x + b y = f ( x ) = - cx + d where ad # bc. The condition ad # bc implies that c and d are not both 0, hence the denom- inator is not identically 0. Moreover it also shows # f so that numerator and denominator are not proportional. The function f is not a constant, and is well-defined except where the denominator vanishes. When c # 0, the point x = -d/c is not in the domain off: This is a vertical asymptote for its graph. (For y = a/c, there is a horizontal asymptote; linear fractional transformations are bijective maps if we add a point “infinity” to the line, and extend in a natural way the definition of f .) If we make a change of variable x = g ( t ) = - at + @ where ad # @r, rt + 6 60 3.1. ROW BY COLUMN MULTIPLICATION 61 we find a composite in the form of another linear fractional transformation a s + b - (aa + by)t + (aP + bd) - = f ( g ( t ) ) = cQt+P + d (ca + dy)t + (cP + dd) * 7t+6 This suggests to define the product of 2 x 2 matrices by c a + d y cp+dd aa+by aP+M (: :) (; f) = ( 3.1.2 Linear Changes of Variables The multiplication law for matrices (to be introduced below) can be motivated more generally as follows.

  Sign up to read

  Learn more about book
• 

  eBook - PDF

  Invitation to Linear Programming and Game Theory

  • David C. Vella(Author)
  • 2021(Publication Date)
  • Cambridge University Press

    (Publisher)

  The definition of the matrix product is not as simple as that for the matrix sum. In order to understand how multiplication works, it is useful to consider first a special case – that of a row matrix times a column matrix. So suppose we have the following row matrix A and column matrix B : A =  a 1 a 2 a 3 . . . a n  B = ⎡ ⎢ ⎢ ⎢ ⎢ ⎢ ⎣ b 1 b 2 b 3 . . . b r ⎤ ⎥ ⎥ ⎥ ⎥ ⎥ ⎦ . The dot product A · B is defined by Definition 2.3. definition 2.4 A · B =  undefined if n = r c if n = r (2.3) where c = a 1 b 1 + a 2 b 2 + · · · + a n b n . You may regard the single number c as a 1 × 1 matrix or simply as a scalar. Here are examples:  2 5 3  · ⎡ ⎣ 4 −1 3 ⎤ ⎦ = 2(4) + 5(−1) + 3(3) = 12  2 5 3  ·  4 −1  = undefined, since n = r . So, in this special case, the dot product is the matrix product. Before we go on to look at the general case, it is worth presenting a couple of examples that illustrate how such a strange way of multiplying comes up naturally. We consider two examples. In our first example, suppose the Grand Flick Railroad movie theater sells four different types of tickets: children’s tickets sell for $5 each, student tickets sell for $7 each, adult tickets are $10 each, and senior citizens’ tickets are $8 each. We might conveniently arrange this information in a 1 × 4 matrix P (for “price matrix”) – we may even label the columns to help us keep track: P = C S A SC  5 7 10 8  . Now, on a given night, say Friday, the theater is showing the movie Closer to Home and will sell different amounts of each type of ticket. We might keep track of this information by listing it as a 4 × 1 matrix Q (for “quantity matrix”), with one row for each type of ticket: Q = C S A SC ⎡ ⎢ ⎢ ⎣ 40 50 80 10 ⎤ ⎥ ⎥ ⎦ , 2.2 Operations on Matrices I 69 meaning that they sold 40 children’s tickets, 50 student tickets, etc.

  Sign up to read

  Learn more about book
• 

  eBook - PDF

  Elementary Linear Algebra

  • Howard Anton, Anton Kaul(Authors)
  • 2020(Publication Date)
  • Wiley

    (Publisher)

  Entry by entry (Definition 5) 2. Row-column method (Formula (5)) 3. Column by column (Formula (6)) 4. Row by row (Formula (7)) 5. Column-row expansion (Formula (11)) Matrix Form of a Linear System Matrix Multiplication has an important application to systems of linear equations. Con- sider a system of m linear equations in n unknowns: a 11 x 1 + a 12 x 2 + ⋅ ⋅ ⋅ + a 1n x n = b 1 a 21 x 1 + a 22 x 2 + ⋅ ⋅ ⋅ + a 2n x n = b 2 . . . . . . . . . . . . a m1 x 1 + a m2 x 2 + ⋅ ⋅ ⋅ + a mn x n = b m 1.3 Matrices and Matrix Operations 35 Since two matrices are equal if and only if their corresponding entries are equal, we can replace the m equations in this system by the single matrix equation ⎡ ⎢ ⎢ ⎢ ⎣ a 11 x 1 + a 12 x 2 + ⋅ ⋅ ⋅ + a 1n x n a 21 x 1 + a 22 x 2 + ⋅ ⋅ ⋅ + a 2n x n . . . . . . . . . a m1 x 1 + a m2 x 2 + ⋅ ⋅ ⋅ + a mn x n ⎤ ⎥ ⎥ ⎥ ⎦ = ⎡ ⎢ ⎢ ⎢ ⎣ b 1 b 2 . . . b m ⎤ ⎥ ⎥ ⎥ ⎦ The m × 1 matrix on the left side of this equation can be written as a product to give ⎡ ⎢ ⎢ ⎢ ⎣ a 11 a 12 ⋅ ⋅ ⋅ a 1n a 21 a 22 ⋅ ⋅ ⋅ a 2n . . . . . . . . . a m1 a m2 ⋅ ⋅ ⋅ a mn ⎤ ⎥ ⎥ ⎥ ⎦ ⎡ ⎢ ⎢ ⎢ ⎣ x 1 x 2 . . . x n ⎤ ⎥ ⎥ ⎥ ⎦ = ⎡ ⎢ ⎢ ⎢ ⎣ b 1 b 2 . . . b m ⎤ ⎥ ⎥ ⎥ ⎦ If we designate these matrices by , x, and b, respectively, then we can replace the original system of m equations in n unknowns by the single matrix equation x = b The matrix  in this equation is called the coefficient matrix of the system. The aug- mented matrix for the system is obtained by adjoining b to A as the last column; thus the The vertical partition line in the augmented matrix [A ∣ b] is optional, but is a useful way of visually sepa- rating the coefficient matrix A from the column vector b. augmented matrix is [ ∣ b] = ⎡ ⎢ ⎢ ⎢ ⎣ a 11 a 12 ⋅ ⋅ ⋅ a 1n b 1 a 21 a 22 ⋅ ⋅ ⋅ a 2n b 2 . . . . . . . . . . . . a m1 a m2 ⋅ ⋅ ⋅ a mn b m ⎤ ⎥ ⎥ ⎥ ⎦ Transpose of a Matrix We conclude this section by defining two matrix operations that have no analogs in the arithmetic of real numbers.

  Sign up to read

  Learn more about book
• 

  eBook - PDF

  Finite Mathematics

  • Stefan Waner, Steven Costenoble(Authors)
  • 2017(Publication Date)
  • Cengage Learning EMEA

    (Publisher)

  All Rights Reserved. May not be copied, scanned, or duplicated, in whole or in part. WCN 02-300 254 Chapter 4 Matrix Algebra and Applications Introduction We used matrices in Chapter 3 simply to organize our work. It is time we examined them as interesting objects in their own right. There is much that we can do with matrices besides row operations: We can add, subtract, multiply, and even, in a sense, “divide” matrices. We use these operations to study game theory and input-output models in this chapter, and Markov chains in a later chapter. Many calculators, spreadsheets, and other computer programs can do these matrix operations, which is a big help in doing calculations. However, we need to know how these operations are defined to see why they are useful and to understand which to use in any particular application. 4.1 Matrix Addition and Scalar Multiplication Matrices Let’s start by formally defining what a matrix is and introducing some basic terms. Matrix, Dimension, and Entries An m 3 n matrix A is a rectangular array of real numbers with m rows and n columns. We refer to m and n as the dimensions of the matrix. The numbers that appear in the matrix are called its entries . We customarily use capital letters A , B , C , c for the names of matrices. Quick Examples 1. A 5 B 2 0 1 33 2 22 0 R is a 2 3 3 matrix because it has two rows and three columns. 2. B 5 D 2 3 10 44 2 1 3 8 3 T is a 4 3 2 matrix because it has four rows and two columns. ✱ The entries of A are 2, 0, 1, 33, 2 22 , and 0. The entries of B are the numbers 2, 3, 10, 44, 2 1 , 3, 8, and 3. ✱ Remember that the number of rows is given first and the num-ber of columns second. An easy way to remember this is to think of the acronym “RC” for “Row then Column.” Referring to the Entries of a Matrix There is a systematic way of referring to particular entries in a matrix. If i and j are numbers, then the entry in the i th row and j th column of the matrix A is called the ij th entry of A .

  Sign up to read

  Learn more about book
• 

  eBook - PDF

  Finite Mathematics and Applied Calculus

  • Stefan Waner, Steven Costenoble(Authors)
  • 2017(Publication Date)
  • Cengage Learning EMEA

    (Publisher)

  There, we worked with the augmented matrix of the system, which is simply A with B adjoined as an extra column. Copyright 2018 Cengage Learning. All Rights Reserved. May not be copied, scanned, or duplicated, in whole or in part. WCN 02-300 5.2 Matrix Multiplication 343 When we write a system of equations as AX 5 B , couldn’t we solve for the unknown X by dividing both sides by A? If we interpret division as multiplication by the inverse (for example, 2 4 3 5 2 3 3 2 1 ), we shall see in Section 5.3 that certain systems of the form AX 5 B can be solved in this way, by multiplying both sides by A 2 1 . We first need to discuss what we mean by A 2 1 and how to calculate it. 5.2 EXERCISES ▼ more advanced ◆ challenging indicates exercises that should be solved using technology In Exercises 1–28, compute the products. Some of these may be undefined. Exercises marked should be done by using tech-nology. The others should be done in two ways: by hand and by using technology where possible. [ HINT: See Example 3.] 1. 3 1 3 2 1 4 C 9 1 2 1 S 2. 3 4 0 2 1 4 C 2 4 1 8 S 3. C 2 1 1 2 D B 2 1 3 1 R 4. 3 2 1 1 4 B 3 4 1 4 R 5. 3 0 2 2 1 4 C x y z S 6. 3 4 2 1 1 4 C 2 x x y S 7. 3 1 3 2 4 B 1 2 1 R 8. 3 3 2 4 3 1 2 2 4 9. 3 2 1 1 4 B 2 3 1 4 3 0 1 2 2 1 R 10. 3 2 2 1 4 B 2 3 1 4 3 4 0 1 3 R 11. 3 1 2 1 2 3 4 D 2 1 2 0 2 2 1 0 0 5 2 2 1 8 1 T 12. 3 0 1 2 1 2 4 D 1 2 2 1 0 1 3 6 0 2 2 1 2 2 11 T 13. B 1 0 2 1 1 1 2 R C 0 1 2 1 1 0 1 4 8 0 S 14. B 0 1 2 1 3 1 2 1 R C 1 1 4 2 0 1 S 15. B 1 0 1 2 1 R B 0 1 0 1 R 16. B 1 2 1 1 2 1 R B 3 2 3 5 2 7 R 17. B 0 1 0 1 R B 1 0 1 2 1 R 18. B 3 2 3 5 2 7 R B 1 2 1 1 2 1 R 19. B 1 2 1 1 2 1 R B 2 3 2 3 R 20. B 0 1 1 0 R B 3 2 3 2 2 1 R 21. B 1 2 1 2 1 1 R C 2 3 2 3 1 1 S 22. B 0 1 2 1 0 2 1 1 R B 3 2 3 2 2 1 R 23. C 1 0 2 1 2 2 2 1 0 0 1 S C 1 2 1 4 1 1 0 0 4 1 S 24. C 1 2 0 4 2 1 1 1 0 1 S C 1 2 2 4 4 1 0 0 2 2 1 S 25. D 1 0 1 0 2 1 1 0 1 2 2 0 1 4 0 2 1 0 1 T D 1 2 3 2 0 T 26. D 1 1 2 7 0 2 1 0 2 4 2 1 0 2 2 1 1 2 1 1 1 T D 1 2 3 2 1 T 27.

  Sign up to read

  Learn more about book
• 

  eBook - ePub

  Fundamentals of University Mathematics

  • Colin McGregor, Jonathan Nimmo, Wilson Stothers(Authors)
  • 2010(Publication Date)
  • Woodhead Publishing

    (Publisher)

  Chapter 11

  Matrices and Linear Equations

  In Chapter 1 , we mentioned the fact that a pair (x, y ) of real numbers can be used to represent a point in the plane. In Chapter 6 , we used such a pair to represent a complex number. This is an example of an important aspect of mathematics— a mathematical object may be interpreted in several different ways. Once we have studied the mathematical objects, we have information which is available in every interpretation.

  In this chapter we introduce a new mathematical object—the matrix. An m × n matrix is a rectangular array of mn numbers. We can think of the matrix as consisting of m rows , each having n entries , or as n columns , each having m entries. For example,

  is a 2 × 3 matrix. We regard a matrix as a single entity, to be manipulated as a whole.

  We define addition on the set of m × n matrices. This operation has properties similar to the addition of real numbers. In particular, there is a

  zero matrix Om × n

  in the set which behaves like 0 in , i.e.

  Under certain circumstances, we can define multiplication of matrices. Now some of the results are unfamiliar. For example, there are matrices A and B for which AB ≠ BA.

  Matrices have many uses in mathematics and its applications. Here we consider just one—the solution of (systems of) linear equations. Looking at such a system leads to the introduction of new operations on matrices. We develop a systematic method for finding all the solutions.

  In the final sections, we return to the mathematical study of matrices. We consider the existence of matrix inverses. Along the way, we meet the concept of the determinant of a (square) matrix. This is an important topic in its own right and will be used in Chapter 13 in connection with the vector product.

  11.1 Basic Definitions

  Definitions 11.1.1 Let be a number system. A matrix defined over is a rectangular array of elements of . These elements are the entries of the matrix. If a matrix A has m rows (horizontal lines of entries) and n columns (vertical lines), then A is of type m × n or is an m × n bmatrix.

  Sign up to read

  Learn more about book
• 

  eBook - PDF

  Linear Algebra and Geometry

  • Al Cuoco, Kevin Waterman, Bowen Kerins, Elena Kaczorowski(Authors)
  • 2019(Publication Date)
  • American Mathematical Society

    (Publisher)

  Calculate the result of this Matrix Multiplication: ⎛ ⎝ 3 5 1 1 3 4 4 − 2 − 3 ⎞ ⎠ ⎛ ⎝ 2 1 5 ⎞ ⎠ 24. Write ⎛ ⎝ 11 11 6 ⎞ ⎠ as a linear combination of the columns of the matrix A where A = ⎛ ⎝ 3 5 1 1 3 4 4 − 2 − 3 ⎞ ⎠ 25. Show that ⎛ ⎝ 3 5 1 1 3 4 4 − 2 − 3 ⎞ ⎠ ⎛ ⎝ x y z ⎞ ⎠ = x ⎛ ⎝ 3 1 4 ⎞ ⎠ + y ⎛ ⎝ 5 3 − 2 ⎞ ⎠ + z ⎛ ⎝ 1 4 − 3 ⎞ ⎠ 26. Find a vector ⎛ ⎝ x y z ⎞ ⎠ so that ⎛ ⎝ 3 5 1 1 3 4 4 − 2 − 3 ⎞ ⎠ ⎛ ⎝ x y z ⎞ ⎠ = ⎛ ⎝ 11 11 6 ⎞ ⎠ 27. If A is an n × n matrix, the trace of A , written Tr( A ), is the sum of the elements on the “main diagonal” of A . Tr( A ) = A 11 + A 22 + · · · + A nn True or false? If true, prove it. If false, give a counterexample. a. Tr( A + B ) = Tr( A ) + Tr( B ) b. Tr( cA ) = c Tr( A ) c. Tr( AB ) = Tr( A ) Tr( B ) d. Tr( AB ) = Tr( BA ) e. Tr( A 2 ) = (Tr( A )) 2 175 Chapter 4 Matrix Algebra 4.5 Operations, Identity, and Inverse In the last lesson, Matrix Multiplication was formally defined as a gener-alized dot product. In this lesson, you will explore another way to think about Matrix Multiplication: a generalized linear combination. This repre-sentation of Matrix Multiplication will prove to be very useful. In this lesson, you will learn how to • set up a Matrix Multiplication as a linear combination of vectors • understand the relationship between Matrix Multiplication, dot prod-uct, and linear combination • find the inverse of a matrix, if it exists • use the inverse to solve a matrix equation Consider Exercises 22–25 from the previous lesson. Two of the exercises are types you explored in Chapter 3. The others align closely with them but take an approach through Matrix Multiplication.

  Sign up to read

  Learn more about book
• 

  eBook - PDF

  Discrete Wavelet Transformations

  An Elementary Approach with Applications

  • Patrick J. Van Fleet(Author)
  • 2019(Publication Date)
  • Wiley

    (Publisher)

  The same holds true for the second column of the product. The first entry of the second column is the average of the first three elements of a 2 , and the second entry is the average of the last three elements of a 2 . 46 VECTORS AND MATRICES So we can see that M processes the columns of A by computing averages of elements of each column and we can easily verify that MA =  M a 1 | M a 2  . If A consists of p columns, the interpretation is the same – the only difference is that the product would consist of p columns of averages rather than the two that resulted in this example. (Live example: Click Example2.12.) In general, suppose that M is an m × p matrix and A is a p × n matrix and we are interested in interpreting the product MA. We begin by partitioning A in terms of its columns. That is, if a 1 , a 2 , . . . , a n are the columns of A, then block Matrix Multiplication allows us to write MA = M  a 1 | a 2 | · · · | a n  and view this product as a 1 × 1 block (M ) times 1 × n blocks. Thus, MA = M  a 1 | a 2 | · · · | a n  =  M a 1 | M a 2 | · · · | M a n  (2.10) and we see that when we compute MA, we simply apply M to each column of A. Thus, when we multiply A on the left by M , we can view this product as processing the columns of A. Problem 2.39 allows you to further investigate this idea. 1 Alternatively, suppose that we are given p × n matrix P and we wish to apply it to input matrix A with dimensions m × p by way of the product AP . Using block Matrix Multiplication, we can view this product as a way of processing the rows of A with matrix P . In Problem 2.40 you will produce the block Matrix Multiplication that supports this claim. Transposes of Block Matrices As we will see in subsequent chapters, it is important to understand how to transpose block matrices.

  Sign up to read

  Learn more about book
• 

  eBook - PDF

  Linear Algebra, Matrix Theory and Applications

  • Stefano Spezia(Author)
  • 2019(Publication Date)
  • Arcler Press

    (Publisher)

  SECTION 6: COMPUTATIONS WITH MATRICES AND LINEAR PROGRAMMING Fast Matrix Multiplication 12 Markus Bläser Saarland University, Saarbrücken, Germany ABSTRACT We give an overview of the history of fast algorithms for Matrix Multiplication. Along the way, we look at some other fundamental problems in algebraic complexity like polynomial evaluation. This exposition is self-contained. To make it accessible to a broad audience, we only assume a minimal mathematical background: basic linear algebra, familiarity with polynomials in several variables over rings, and rudimentary knowledge in combinatorics should be sufficient to read (and understand) this article. This means that we have to treat tensors in a very concrete way (which might annoy people coming from mathematics), occasionally prove basic results from combinatorics, and solve recursive Citation: Markus Bläser, “Fast Matrix Multiplication” THEORY OF COMPUTING LIBRARY GRADUATE SURVEYS 5 (2013), pp. 1–60. http://dx.doi.org/10.4086/toc. gs.2013.005 Copyright © 2013 Markus Bläser. Licensed under a Creative Commons Attribution License (CC-BY). Linear Algebra, Matrix Theory and Applications 228 inequalities explicitly (because we want to annoy people with a background in theoretical computer science, too). Keywords and phrases: fast Matrix Multiplication, bilinear complexity, tensor rank INTRODUCTION Given two n×n-matrices x = (x ik ) and y = (y k j ) whose entries are indeterminates over some field K, we want to compute their product xy = (z i j ). The entries z i j are given by the following well-known bilinear forms (1.1) Each z i j is the sum of n products. Thus every z i j can be computed with n multiplications and n − 1 additions. This gives an algorithm that altogether uses n 3 multiplications and n 2 (n − 1) additions. This algorithm looks so natural and intuitive that it is very hard to imagine that there is better way to multiply matrices.

  Sign up to read

  Learn more about book
• 

  eBook - PDF

  Elementary Differential Equations with Linear Algebra

  • Albert L. Rabenstein(Author)
  • 2014(Publication Date)
  • Academic Press

    (Publisher)

  Let C = AB. Then C is an m xp matrix. The element c u in the ith row andyth column of C is the ith component of the vector Abj . This ith component is formed by multiplying the elements in the ith row of A by the corresponding elements in theyth column of B. Thus n Cij=Y a ik b kj, l < i < m , l < y < / ? . (2.5) fc=l Ac ■[ 2 -1 1 4 21 1 -1 2' 3 2.5 Matrix Multiplication 103 Thus if A is an m x n matrix and B is an n x p matrix (the number of columns of A must be the same as the number of rows of B) the product AB is an m x p matrix C whose elements are given by formula (2.5). To illustrate, let A = Ã1 3 L2 -11 0 4J -[ -! -3 Since A is of size 3 x 2 and B is of size 2 x 2 , the product AB is defined and is a 3 x 2 matrix. We have AB = (l)(2) + (-l)(-3) (3X2) +(OX-3) (2)(2) + (4X-3) (l)(l) + (-l)(-2) (3)(l) + (0)(-2) (2)(l) + (4)(-2) J 5 3' 6 3 -8 -6 Notice that the product BA is not defined in this example, since the number of columns of B is not the same as the number of rows of A. Even when AB and BA are both defined, the products are not necessarily the same. For instance, if = [3 lj ' B = [2 Oj ' the reader can verify that AB -[ 1 i]· so that AB ÖÂÁ. Thus Matrix Multiplication is not a commutative operation. When AB = BA, we say that A and B commute. Some properties of matrices that involve multiplication are given in the following theorem. Theorem 2.3 If c is a number and if A, B, C, and D are matrices such that the indicated sums and products are defined, then (cA)B = A(cB) = c(AB) A(B + C) = AB + AC (B + C)D = BD + CD A(BD) = (AB)D. We shall prove the second and fourth properties only, leaving the proofs of the remaining properties as exercises. First, consider the second property. 104 Matrices and Determinants Let the size of Ahem x n and let that of B and C be n x p. Then AB, AC, and A(B + C) are defined and have size m x p. Let E = >4(JB + C), F = y4i?, and G = ^C. We want to show that E = F + G or that e u =f tJ + # 0 - for all i and j .

  Sign up to read

  Learn more about book