Commutative matrix multiplication Given two 3x3 matrix:
$$
V=
\begin{bmatrix}
1 & 0 & 9 \cr
6 & 4 & -18 \cr
-3 & 0 & 13 \cr
\end{bmatrix}\quad
W=
\begin{bmatrix}
13 & 9 & 3 \cr
-14 & -8 & 2 \cr
5 & 3 & -1 \cr
\end{bmatrix} 
$$
Is there any way to predict that $ V * W = W * V $
without actually calculating both multiplications
 A: Two matrices commute if and only if they have a same Jordan basis. This is important theoretically, but finding a Jordan basis is usually harder then multiplying directly and checking that they commute.
A: This question is interesting because multiplying $3\times 3$ matrices requires so few operations that it's very hard to find anything that beats the naive method  in terms of number of multiplications!

For $n$ relatively small, multiplying two $n\times n$ matrices together requires $n^3$ multiplications, so computing both $UV$ and $VU$ requires $2n^3$ multiplications.
One way that we can improve on this is by checking if $UVx = VUx$ for a random vector $x$.
If $U$ and $V$ commute then this inequality will hold.
On the other hand, if $x$ has a continuous distribution with respect to the Lebesgue measure on $\mathbf{R}^n$, then
$$
\Pr(UVx = VUx)
= \Pr(x \in \ker(UV - VU)).
$$
Since the kernel of $UV - VU$ is a subspace, if $UV \neq VU$, then $\Pr(x \in \ker(UV - VU)) = 0$.
Now, computing $UVx$ requires $n^2$ multiplications to compute $Vx$ and then $n^2$ more multiplications to compute $U(Vx)$ and vice versa for $VUx$.
Thus, checking if $UVx = VUx$ requires $4n^2$ multiplications.
When $n = 3$, this is $4\cdot 3^2 = 36$ multiplications compared to $2\cdot 3^3 = 54$ multiplications required to compute $UV$ and $VU$.
This speed-up gets more pronounced as $n$ grows.
Of course, if we're counting multiplications so closely, it may not be so cheap so sample a random $x$.
Probably the cheapest way to do it would be to sample three independent $U(0, 1)$ entries, which is very fast, but probably not as fast as $54 - 36 = 18$ multiplications.
There's also the fact that your matrices are integer matrices, so computing $UV$ and $VU$ costs $54$ integer multiplications, which would most likely be faster than $36$ floating point multiplications required to compute $UVx$ and $VUx$.
