Matrix multiplication

Matrix multiplication is one of the fundamental operations of matrices.

Some ground rules:

• Matrix multiplication is not commutative, i.e., $AB\ne BA$.
• With respect to matrix addition, multiplication is (left or right) distributive: $BD+CD=(B+C)D\ne D(B+C)$.
• For an $n\times m$ matrix $A$ and a $p\times q$ matrix $B$, the resulting matrix is $n\times q$.

Note that the product between two matrices isn’t a matrix of elementwise products. This is called the Hadamard product, and is instead denoted $A\odot B$.

Algorithms

When computing by hand, we usually use a primitive algorithm, where the average case time complexity is $\Theta (n^2)$. This is defined by:

$$C_{i,j}=\sum _k{A}_{i,k}{B}_{k,j}$$

See Strassen’s algorithm

Powers

We are occasionally faced with needing to take multiple successive multiplications of the same matrix, i.e., we take it to some power. There are a few broad approaches we can use.

One approach is to use diagonalisation to break the matrix down into a simpler to evaluate form. By theorem, for a matrix $A$, if it is diagonalisable, we can represent as:

$$A=SB{S}^{-1}$$ $$A^n=SB{S}^{-1}SB{S}^{-1}\cdots =S{B}^n{S}^{-1}$$

where the columns of $S$ consist of $A$‘s eigenvectors and the diagonal of $B$ the corresponding eigenvalues. Since $B$ is purely diagonal, we just evaluate scalars to the power of $n$ and matrix multiply $S$ and $S^{-1}$.

Sylvester’s theorem (which shows up sometimes in optics problems) is useful for multiplying $2\times 2$ matrices, if $\det A=1$. It states that:

$${\left[\begin{array}{cc}a& b\\ c& d\end{array}\right]}^n=\frac{1}{\sin \theta }\left[\begin{array}{cc}a\sin (n\theta )-\sin ((n-1)\theta )& b\sin (n\theta )\\ c\sin (n\theta )& d\sin (n\theta )-\sin ((n-1)\theta )\end{array}\right]$$

This is provably correct with induction.