Does the associative property of matrix multiplication hold when one of the matrices is a permutation matrix?

For example consider the following:

X = [ 1 2 3 ] (a 1*3 matrix) P = [ 0 1 0; 0 0 1; 1 0 0 ] (a 3 * 3 permutation matrix) Y = transpose([1 4 2] ) (a 3 * 1 matrix)

Here (XP)Y = 9 and X(PY) = 11...

Can I conclude that the associative property of matrix multiplication holds only when all matrices have been reduced their "static" form after row and column exchanges - which is essentially what happens when you multiply by a permutation matrix?

  • 3
    $\begingroup$ Matrix multiplication is \emph{always} associative. $\endgroup$ – Igor Rivin Jan 4 '14 at 3:05
  • $\begingroup$ Igor - in the example above, (XP)Y = 9 and X(PY) = 11. $\endgroup$ – Student_forever Jan 4 '14 at 3:20
  • 2
    $\begingroup$ Um, you made a miscalculation.... $\endgroup$ – Gina Jan 4 '14 at 3:25
  • $\begingroup$ @IgorRivin What about ABC, where A:row matrix, B:column matrix and C:row matrix? $\endgroup$ – jinawee Mar 13 '14 at 17:40

$XP=[3\ 1\ 2]$ and $(XP)Y=3\cdot1+1\cdot4+2\cdot2=11$.

Like Igor said, matrix multiplication is always associative.

| cite | improve this answer | |

Matrix multiplication is in fact just a composition of linear transformation. Just like function in general, composition of function is associative (intuitively, in does not even make sense to even talk about bracketing a function composition). So yes, multiplication is probably a somewhat misleading term.

| cite | improve this answer | |

I was not satisfied with any explanation that I've read in Internet about associativity of the matrices product.

Algebric proof based on matrices product calculation is cumbersome, but it works. I like to consider matrices as a linear transformation operator.

Let's do it.

For me it's very intuitive that the functions are associative.

$ \color{blue}{ f(g(x)) = (f\circ g)x} $

For instance

$ \color{blue}{f(x) = 2x+1 \quad and \quad g(x) = x^2}$
$ \color{blue}{f(2) = 5 \qquad \rightarrow \qquad g(5) = 25}$

$\color{blue}{g(f(x)) = 4x^2 + 4x + 1 \quad \rightarrow \quad f(g(2)) = 25}$

Notice that we make the composition, using the operands like $\color{blue}{x}$ as a placeholder in place of the actual operand (in this case, $\color{blue}{2}$)

Imagine $\color{blue}{F}$, $\color{blue}{X}$, $\color{blue}{M}$, $\color{blue}{T}$, $\color{blue}{C}$ and $\color{blue}{U}$ as matrices. Consider $\color{blue}{R(M)}$ as the number of $\color{blue}{M}$ rows and $\color{blue}{C(M)}$ the number of $\color{blue}{M}$ columns.

We prove intuitively that $\color{blue}{T(UV) = (TU)V}$

We know that, by the algebric definition or linear transformation paradigm $\color{blue}{C(U) = R (V)}$ and $\color{blue}{C(V) = R(U)}$

Because in a multiplication of matrices, the left matrix $\color{blue}{F}$ represents in practice $\color{blue}{R (F)}$ functions composed of $\color{blue}{C(F)}$ coefficients, which will be the parameters of a scalar product, which will result in a single number (for each function execution)

The right-hand matrix $\color{blue}{X}$, represents a collection of $\color{blue}{C(X)}$ operands, where each has $\color{blue}{R(X)}$ values ​​for each of the $\color{blue}{R(F)}$ functions to act. So in the end we will have $\color{blue}{R(X) * C(X)}$ values

Thus in $\color{blue}{UV}$ we produce a matrix $\color{blue}{X}$, with $\color{blue}{R(U) * C(V)}$ values, which will be the target of the functions represented by the left matrix $\color{blue}{T}$, generating final values, one for each function execution. In short, $\color{blue}{T}$ acts on the effect it has on $\color{blue}{UV}$,

When we first make $\color{blue}{TU}$ we produce $\color{blue}{L (T) * R (U)}$ values, but, in fact, values are more than numbers, they are a functional composition that will act together on the values of $\color{blue}{V}$, making the same effect of the function composition.

It is similar than function composition, the function composition can use placeholders in place of the actual operands in $\color{blue}{V}$. In the end, one can get the final result, replacing the placeholders for the real $\color{blue}{V}$ values.

The only difference, as described, is that an array involves several function executions and each function has several parameters.

Apart from this multiplicity, the associativity it is the same property that holds for functions.

| cite | improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.