29
$\begingroup$

I know that the algorithm for multiplying 2 matrices is defined as:

$$(AB)_{ij} = (\text{row }i\text{ of matrix }A) ⋅ (\text{column }j\text{ of matrix }B)$$

And I know that matrix multiplication is associative. So in the case of 3 matrices:

$$(A ⋅ B) ⋅ C = A ⋅ (B ⋅ C)$$

Is there an algorithm for matrix multiplication that can multiply 3 matrices simultaneously?

For example, could one evaluate the expression $ABC$ without first evaluating either of:

  • $(AB) ⋅ C$
  • $A ⋅ (BC)$

Additional questions

I am in high school, so I am not sure if this is the correct terminology, but I read somewhere about binary operations, where for instance, an operation such as normal multiplication takes 2 elements (such as 2 real numbers) and produces an output, and you can't multiply 3 numbers together simultaneously.

  • Is matrix multiplication a binary operation, where you can't multiply 3 matrices simultaneously?
  • Is $A ⋅ B ⋅ C$ defined as $(A⋅ B)⋅ C$ or $A⋅ (B⋅ C)$?
  • Is the omission of the parentheses in $A⋅ B⋅ C$ (matrices) just a form of notation?
  • What is the most precise way to interpret expressions of multiplication or addition (associative operations) with more than 3 variables - where there are no brackets, such as $A⋅B⋅C⋅D$ ?
$\endgroup$
15
  • 4
    $\begingroup$ Matrix multiplication is defined as a binary operation. You could define a new, ternary operation (an operation that takes three inputs) that takes three matrices $A,B,C$ and returns a matrix equal to $(AB)C$, but computed (in principle) all at once without explicitly computing the intermediate result $AB$. One reason people haven't done this is that matrix multiplication is associative, so $(AB)C=A(BC)$, and therefore people tend to just write $ABC$ as a matrix product and assume it will be evaluated in one of those two ways, the same way we can write $2 \times 3\times 4$. $\endgroup$
    – David K
    Nov 26, 2023 at 6:40
  • 3
    $\begingroup$ The omission of brackets in the product $ABC$ is a little bit more than just notation. Omitting the brackets only makes sense because $(AB)C = A(BC)$, and so when talking about the product $ABC$ we're not interested in knowing which of these two products it is (since they're the same). Mathematicians would never write $ABC$ if it wasn't true that $(AB)C = A(BC)$. (Programmers might write it, and define some arbitrary priority for the notation, but mathematicians wouldn't) $\endgroup$
    – Stef
    Nov 26, 2023 at 18:40
  • 1
    $\begingroup$ @Stef: Exactly; see my answer. (I did also think of talking about precedence rules, but decided to leave it out in my post.) @‍Alice: The omission of brackets in "A·B·C" does tell you that mathematicians know that · is associative, but you must realize that it is not a communication tool. We also omit brackets in "7+5^3·2", but we stipulate precedence rules that tell us that "7+5^3·2" means "7+((5^3)·2)". It technically does not tell us anything else. So it seems that you have an incorrect notion of the purpose of omission of brackets in expressions; it is just to make it easy to read. $\endgroup$
    – user21820
    Nov 27, 2023 at 5:49
  • 1
    $\begingroup$ @Stef "Mathematicians would never write $ABC$ if it wasn't true that $(AB)C=A(BC)$." Why then do they write $x - y - z$ although this is not the same as $x - (y-z)$? $\endgroup$ Nov 27, 2023 at 14:26
  • 2
    $\begingroup$ @Stef Almost every mathematician I know will be perfectly happy to not only write $a^{b^c}$ without parentheses, but also explain why it should only ever mean $a^{(b^c)}$. Maybe we know very different mathematicians. $\endgroup$ Nov 28, 2023 at 1:24

4 Answers 4

19
$\begingroup$

There are already some very good answers. Just a quick note to mention that although matrix multiplication is associative (and so $ABC=A(BC)=(AB)C$) the finite precision result as well as the computational cost may depend on the order of the operations. Regarding the second point, there may be massive differences in cost and so some software libraries actually define an N-ary operation in addition to the standard binary matrix multiplication. This N-ary operation will then perform the binary operations in the order that minimises the number of FLOPs. See for example numpy.linalg.multi_dot, which decides the order of multiplication using the algorithm [1]. The corresponding optimisation problem is called matrix chain ordering problem. That Wikipedia page has the following example:

If A is a 10 × 30 matrix, B is a 30 × 5 matrix, and C is a 5 × 60 matrix, then

  • computing (AB)C needs (10×30×5) + (10×5×60) = 1500 + 3000 = 4500 operations, while
  • computing A(BC) needs (30×5×60) + (10×30×60) = 9000 + 18000 = 27000 operations.

[1] Cormen, "Introduction to Algorithms", Chapter 15.2, p. 370-378.

$\endgroup$
4
  • 1
    $\begingroup$ More generally, consider np.einsum (or einops for numpy, torch, tensorflow, jax, ...) for efficient calculation of tensor products. $\endgroup$ Nov 27, 2023 at 12:16
  • 1
    $\begingroup$ OTOH if you then use $ABC$ to multiply it from the right with a column vector $v$ (a $60\times 1$ matrix), $((AB)C)v$ takes $10\times 60\times 1=600$ additional operations, for a total of $5100$ whereas multiplying $A(B(Cv))$ takes $(10\times 30\times 1) +(30\times 5 \times 1) + (5\times 60\times 1) = 750$ operations in total, so in this case it is less efficient (provided no memory speed issues) to not actually evaluate the intermediate matrix, even if the calculation is repeated for several different vectors (the turnover point is 35 repetitions if I did the math correctly in my head). $\endgroup$
    – tobi_s
    Nov 28, 2023 at 13:13
  • $\begingroup$ @tobi_s That's a very good point. If one needs to compute the product only once, one may call multi_dot(A,B,C,v) and let it figure out what's best. If all such vectors are available at the beginning, it may be better to stack them into a matrix V and call multi_dot(A,B,C,V). If they come one at the time, one must do some calculations to figure out the best combination, which may be $(AB)(Cv)$, depending on how many $v$s will need to be computed. $\endgroup$
    – Luca Citi
    Nov 28, 2023 at 18:12
  • $\begingroup$ Correction: I mistyped and ended up saying something that contradicts the rest of my post. It should say that it is MORE efficient to not evaluate the intermediate matrix. $\endgroup$
    – tobi_s
    Nov 29, 2023 at 15:06
12
$\begingroup$

There is a way to compute these matrices directly with notation involving summation. Assume the result of matrices to be $Y$ then: $$Y_{i,j}=\sum_{k_1=1}^n \sum_{k_2=1}^n A_{i,k_1}B_{k_1,k_2}C_{k_2,j}$$

This direct way is suitable opposed to the example in cited answer. Assuming $2×2$ matrix, you would need $4 × 2× 1=8$ additions and $4×2×2=16$ multiplications in the normal way of multiplying two matrices and then multiplying the resultant with other. --

Referring to comment by @r.e.s. the method involves more arithmetic operations.

$\endgroup$
8
  • 3
    $\begingroup$ @Alice: if A, B and C are matrices, and (A⋅B)⋅C is well-defined given the size of the matrices, then yes A⋅B⋅C is well-defined and an accepted notation for (A⋅B)⋅C. The resulting matrix is equal to A⋅(B⋅C), which is also well-defined. $\endgroup$
    – fgrieu
    Nov 26, 2023 at 17:33
  • 4
    $\begingroup$ Sadly the other answer you link in your answer doesn't prove the equality, and worse, its wording seems to imply that this equality is the definition of a three-matrix product, rather than an inevitable consequence of the definition of a two-matrix product. I think it's important to highlight that this equality doesn't come from "We took the two-matrix product definition and tried to extend the formula in a way that looks cool with three matrices" but instead "we applied the two-matrix product definition twice and it resulted in this formula for three matrices" $\endgroup$
    – Stef
    Nov 26, 2023 at 18:46
  • 9
    $\begingroup$ You seem to have miscounted; e.g., in the $2\times 2$ case, the $(1,1)$-element of $A(BC)$ is $$ A_{11}(B_{11}C_{11}+B_{12}C_{21}) +A_{12}(B_{21}C_{11}+B_{22}C_{21})\\ =A_{11}B_{11}C_{11} +A_{11}B_{12}C_{21} +A_{12}B_{21}C_{11} +A_{12}B_{22}C_{21} $$ The first line shows the "normal way", using $6$ multiplications (hence $24$ for all four elements). The second line shows your "simultaneous method" and has $8$ multiplications (hence $32$ for all four elements). They both have $3$ additions (hence $12$ for all four elements). $\endgroup$
    – r.e.s.
    Nov 26, 2023 at 20:42
  • 4
    $\begingroup$ As @r.e.s. mentioned, this "simultaneous" method is actually less efficient (i.e. requires more multiplications) than the usual iterated binary method $\endgroup$
    – math54321
    Nov 26, 2023 at 23:00
  • 1
    $\begingroup$ Correction to my previous comment: For the $2\times 2$ case, computing $A(BC)$ the "normal way" requires (#multiplications, #additions)=$(16,8)$ -- not $(24,12)$--in contrast to $(32,12)$ by the "simultaneous method". This is clear because the normal computation just does two successive matrix multiplications, each of which has $8$ scalar multiplications and $4$ scalar additions. (Taking four times the number of operations in the first line of my equation, as I had done, doesn't properly count the total operations performed; however, using the second line this way is not a problem.) $\endgroup$
    – r.e.s.
    Nov 27, 2023 at 20:07
9
$\begingroup$

Whilst you could directly compute each individual element of the resulting matrix directly from the components of the original matrices, it would be grossly inefficient to do so.

Fairly obviously, multiplying $n+1$ square matrices together in the traditional manner (as repeated pairwise matrix multiplications), simply requires $n$ times as many of each operation as a single pairwise multiplication.

However multiplying the $n+1$ matrices together "directly" (computing each element as a sum of products) gets much worse very quickly - it goes up approximately as an exponential of $n$. If you then decide to factorise these sums, you eventually wind up back at something of comparable complexity to pairwise matrix multiplications.

If you only have binary multiplication and binary addition as your basic operations, then the following table indicates how many operations are required. (If you have vector operations, they're both faster, but the comparison between them gets worse.)

rank # matrices traditional
# mul ops, # add ops
direct sum-of-products
# mul ops, # add ops
2 2 8 muls, 4 adds (same)
2 3 16 muls, 8 adds 32 muls, 12 adds
2 4 24 muls, 12 adds 96 muls, 28 adds
2 5 32 muls, 16 adds 256 muls, 60 adds
2 6 40 muls, 20 adds 640 muls, 124 adds
2 7 48 muls, 24 adds 1536 muls, 252 adds
2 8 56 muls, 28 adds 3584 muls, 508 adds
2 9 64 muls, 32 adds 8192 muls, 1020 adds
2 $n+1$ $8n$ muls, $4n$ adds $2^{n+2}n$ muls, $4(2^{n}-1)$ adds
3 2 27 muls, 18 adds (same)
3 3 54 muls, 36 adds 162 muls, 72 adds
3 4 81 muls, 54 adds 729 muls, 234 adds
3 5 108 muls, 72 adds 2916 muls, 720 adds
3 6 135 muls, 90 adds 10935 muls, 2178 adds
3 7 162 muls, 108 adds 39366 muls, 6552 adds
3 9 216 muls, 144 adds 472392 muls, 59040 adds
3 $n+1$ $27n$ muls, $18n$ adds $3^{n+2}n$ muls, $9(3^{n}-1)$ adds
4 2 64 muls, 48 adds (same)
4 3 128 muls, 96 adds 512 muls, 240 adds
4 4 192 muls, 144 adds 3072 muls, 1008 adds
4 5 256 muls, 192 adds 16384 muls, 4080 adds
4 9 512 muls, 384 adds 8388608 muls, 1048560 adds
4 $n+1$ $64n$ muls, $48n$ adds $4^{n+2}n$ muls, $16(4^{n}-1)$ adds
5 2 125 muls, 100 adds (same)
5 3 250 muls, 200 adds 1250 muls, 600 adds
5 4 375 muls, 300 adds 9375 muls, 3100 adds
5 9 1000 muls, 800 adds 78125000 muls, 9765600 adds
5 $n+1$ $125n$ muls, $100n$ adds $5^{n+2}n$ muls, $25(5^{n}-1)$ adds
6 2 216 muls, 180 adds (same)
6 3 432 muls, 360 adds 2592 muls, 1260 adds
6 4 648 muls, 540 adds 23328 muls, 7740 adds
6 9 1728 muls, 1440 adds 483729408 muls, 60466140 adds
6 $n+1$ $216n$ muls, $180n$ adds $6^{n+2}n$ muls, $36(6^{n}-1)$ adds
7 2 343 muls, 294 adds (same)
7 3 686 muls, 588 adds 4802 muls, 2352 adds
7 9 2744 muls, 2352 adds 2259801992 muls, 282475200 adds
7 $n+1$ $343n$ muls, $294n$ adds $7^{n+2}n$ muls, $49(7^{n}-1)$ adds
8 2 512 muls, 448 adds (same)
8 3 1024 muls, 896 adds 8192 muls, 4032 adds
8 9 4096 muls, 3584 adds 8589934592 muls, 1073741760 adds
8 $n+1$ $512n$ muls, $448n$ adds $8^{n+2}n$ muls, $64(8^{n}-1)$ adds
9 2 729 muls, 648 adds (same)
9 3 1458 muls, 1296 adds 13122 muls, 6480 adds
9 9 5832 muls, 5184 adds 27894275208 muls, 3486784320 adds
9 $n+1$ $729n$ muls, $648n$ adds $9^{n+2}n$ muls, $81(9^{n}-1)$ adds
$r$ 2 $r^3$ muls, $(r-1)r^2$ adds $r^3$ muls, $r^2(r-1)$ adds
$r$ 3 $2r^3$ muls, $2(r-1)r^2$ adds $2r^4$ muls, $r^2(r^2-1)$ adds
$r$ 4 $3r^3$ muls, $3(r-1)r^2$ adds $3r^5$ muls, $r^2(r^3-1)$ adds
$r$ 5 $4r^3$ muls, $4(r-1)r^2$ adds $4r^6$ muls, $r^2(r^4-1)$ adds
$r$ 6 $5r^3$ muls, $5(r-1)r^2$ adds $5r^7$ muls, $r^2(r^5-1)$ adds
$r$ 7 $6r^3$ muls, $6(r-1)r^2$ adds $6r^8$ muls, $r^2(r^6-1)$ adds
$r$ 8 $7r^3$ muls, $7(r-1)r^2$ adds $7r^9$ muls, $r^2(r^7-1)$ adds
$r$ 9 $8r^3$ muls, $8(r-1)r^2$ adds $8r^{10}$ muls, $r^2(r^8-1)$ adds
$r$ 10 $9r^3$ muls, $9(r-1)r^2$ adds $9r^{11}$ muls, $r^2(r^9-1)$ adds
$r$ $n+1$ $nr^3$ muls, $n(r-1)r^2$ adds $nr^{n+2}$ muls, $r^2(r^n-1)$ adds

Non-square matrices scale in a similar manner, but there's no simple way to calculate how many operations are needed for $n+1$ matrices.

$\endgroup$
6
$\begingroup$

Is matrix multiplication a binary operation, where you can't multiply 3 matrices simultaneously and A⋅ B⋅ C is defined as (A⋅ B)⋅ C or A⋅ (B⋅ C)?

It is a binary operation, and yes in general that does mean that "A·B·C" could be considered to be a syntactically invalid expression, just like "gxjb eijalfv" is an invalid English expression. However, almost all binary operations in mathematics can be used in a chain and interpreted as being performed one at a time, either left to right or right to left. That is to say, rigorously we need to define "A·B·C" to denote "(A·B)·C" or "A·(B·C)".

I also wanted to clarify the following, is: A⋅ B⋅ C = (A⋅ B)⋅ C = A⋅ (B⋅ C)? Is the omission of the brackets in A⋅ B⋅ C, just a form of notation?

Yes to both. I have explained the second above. For the equality, it has not been mentioned in the other answers that matrices can be understood as linear functions and matrix multiplication is simply composition, and so associativity is trivial:

  ((f∘g)∘h)(x) = (f∘g)(h(x)) = f(g(h(x))) = f((g∘h)(x)) = (f∘(g∘h))(x).

From the linked post you can see that the definition of matrix multiplication itself is forced by the desired meaning of the matrix as a linear function. Similarly you can easily derive the summation in c00lSillyKid's answer from the multiple function composition, since you can trace all the possible paths:

$\pmatrix{x_3\\y_3\\z_3} \xleftarrow{A} \pmatrix{x_2\\y_2\\z_2} \xleftarrow{B} \pmatrix{x_1\\y_1\\z_1} \xleftarrow{C} \pmatrix{x_0\\y_0\\z_0}$

Every term that contributes to $x_3$ comes from $x_2,y_2,z_2$ with weights given by the first row of $A$, and the column matches which of $x_2,y_2,z_2$ it came from. Repeating that reasoning all the way yields the same product of matrix entries $A_{i,k_1}·B_{k_1,k_2}·C_{k_2,j}$ for each possible path (positions $i,k_1,k_2,j$ in the vectors above).

Clearly, this generalizes to the product of any number of matrices.

$\endgroup$
15
  • $\begingroup$ "That is to say, rigorously we need to define A·B·C to denote (A·B)·C or A·(B·C)." Don't we have a catch-all rule that says that operations are done in order of precedence (e.g. exponent first, then multiplication, then addition) and, in case of equal precedence, we proceed left to right? That means that, unless we use parentheses, A·B·C denotes (A·B)·C. This is immaterial in infinite precision so we can actually perform A·(B·C) with impunity but in principle there's no ambiguity. $\endgroup$
    – Luca Citi
    Nov 27, 2023 at 12:07
  • $\begingroup$ @LucaCiti: I talked about precedence rules in a comment on the question. Left-to-right default parsing is common, but not the conceptually correct direction in some cases. In fact, for function composition, right-to-left is the conceptually correct direction. Anyway we can have a catch-all rule, but that doesn't contradict my point that you need to define what consecutive binary operations mean. If you use a catch-all rule, you still need to be able to handle exceptional cases (e.g. implication). $\endgroup$
    – user21820
    Nov 27, 2023 at 12:30
  • 1
    $\begingroup$ @Alice: It is very good that you are trying to be absolutely precise. I would not call that pedantic, even if some other people might. As you guessed, it is more correct to say that it denotes either (A·B)·C or A·(B·C), and that by associativity it doesn't matter because they are equal. For precision, I would not say that it also denotes the alternative, since we are not free to alter definitions after making them. Suppose we define 2 = 1+1 and 3 = 2+1. Then we have 3 = (1+1)+1 = 1+(1+1) = 1+2. But we cannot say that 3 also denotes 1+2. Instead, 3 = 1+2 by reasoning, not definition. $\endgroup$
    – user21820
    Nov 29, 2023 at 4:38
  • 1
    $\begingroup$ By the way, if you would like to ask more about this and other mathematics, let me know here and I will grant you access to my Basic Math chat-room. =) $\endgroup$
    – user21820
    Nov 29, 2023 at 4:40
  • 1
    $\begingroup$ @Alice: That is right! By the way, in general it is rare for mathematicians to allow dropping brackets if the operation is not associative. But there is one common exception, namely ⇒ (implication), where some logicians define consecutive ⇒ to be parsed right-to-left, since it is the conceptually correct choice. Personally, I would not allow dropping brackets for ⇒, and would always write "A⇒(B⇒C)" or "(A⇒B)⇒C" as appropriate. Nevertheless if you study logic you might come across authors who allow dropping brackets (and hence have to stipulate the parsing direction). See you in chat! =) $\endgroup$
    – user21820
    Nov 30, 2023 at 13:06

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .