0
$\begingroup$

I have a final tomorrow and it includes multiplying matrices (getting a table of values) but i do not understand how he is getting some of the numbers

something like this

suppose the matrices are

 A3X4  B4X5    C5x7    D7X2 

in the results table he has

          A    B     C       D     A     0    60    165     134     B           0    140     110     C                0       70     D                        0       A     B      C      D A    A     A*B    A*B*C  A*B*C*D B          B      B*C    B*C*D C                 C      C*D D                        D 

How is he getting 165 unders C for example? I know how he is getting the twi dimentional ones like for instance the 140 under C would be B*C which is 4X5X7 = 140 but I have no idea how he is getting for the A*B*C = 165

Thank you

  • 0
    Does this make sense to other people?2011-05-01
  • 0
    It does to my professor :(, I think the value on the table is the number of possible multiplications.. butt as you can see, he gets the 140 by multiplying 4X5X7... Thanks for helping me figure itt out2011-05-01
  • 0
    edprog: by possible number of muliplications, do you mean the possible number of multiplications of entries necessary to compute the resulting Matrix? This simply isn't making sense, and we're going to need more clarification in order to point you in the right direction.2011-05-02
  • 0
    This is for Analysis and Design of Algorithms, I have a power point and this where the numbers are comming from, the topic is Multiplyinf Matrices2011-05-02
  • 0
    It's confusing for me too2011-05-02
  • 0
    Ok So i am able to get 165 like this A*B = 3x4x5 = 60 A*B*C = 3X5X7 = 105 The sum of both is 165 But how about the 110?, i cant replicate it :(.. i am gonna cry :'(2011-05-02

1 Answers 1

2

Here's my guess as to what's going on. The table purports to show the number of (scalar) multiplications necessary to carry out the indicated matrix multiplication in the most efficient way. E.g., the entry for $AB$ is $60$ because each entry in the product requires $4$ multiplications, and there are $15$ entries in the product, and $4\times15=60$.

Now things get a little tricky when there are more than two matrices involved. While of course $A(BC)=(AB)C$, the number of multiplications required can be different for the two ways of setting out the calculation. Let's look at $ABCD$ and see if we can reproduce that $134$. First, do $CD$. $7$ multiplications per entry, $10$ entries, so $70$ multiplications, resulting in a $5\times 2$ matrix. Then do $B(CD)$, a $4\times5$ times a $5\times2$. That takes $40$ multiplications, and yields a $4\times2$ matrix. Finally, do $A(B(CD))$, a $3\times4$ times a $4\times2$. That's another $24$ multiplications. All told, $70+40+24=134$, voila!

  • 0
    Excellent, if you were to find the 110, how would you go about it? using the table?2011-05-02
  • 0
    Nevermind, you did it already when you places B(CD).. hmmm interesting2011-05-02
  • 0
    @Gerry: Yes, I think you're right. Good job. I was wondering if something like that was going on.2011-05-02
  • 0
    That looks great, now so that I just completely understand.. how would you get the 165 with your concept?, i can use it tomorrow in my final2011-05-02
  • 0
    It seems like it depends from where I am picking the values.. if I start per row.. for 165 i can duplicate your throty but if i take per column.... i get a higher number.. I am just confused in which way to go2011-05-02
  • 0
    @edprog: A*B involves 3*4*5 = 60 scalar multiplications, and results in a 3x5 matrix (AB). (AB)*C involves 3*5*7 = 105 scalar multiplications, resulting in a 3*7 matrix. Altogether, that's 165 operations of scalar multiplications. I think, given your class, you may need to check both possibilities (AB)C and A(BC), looking for the more efficient of the two (fewest number of computations necessary).2011-05-02