Multiplication and inverses

Fortunately, we shall not be forced to deal in this book too much with computations of matrix multiplications of large matrices. Roughly speaking, we shall eventually show how each move of the Rubik's Cube can be expressed in terms of matrices (more precisely, as a pair of matrices - an $8\times 8$ matrix corresponding to the movement of the $8$ corners and a $12\times 12$ matrix corresponding to the movement of the $12$ edges). Therefore, a little bit of brief background on matrix multiplication is appropriate.

When you multiply an $m\times n$ matrix $A$ by a $n\times p$ matrix $B$ , you get an $m\times p$ matrix $AB$ . The $(i,j)^{th}$ entry of $AB$ is computed as follows:

1. Let $k=1$ and $c_{0}=0$ .
2. If $k=m$ , you're done and $a_{ij}=c_m$ . Otherwise proceed to the next step.
3. Take the $k^{th}$ entry of the $i^{th}$ row of $A$ and multiply it by the $k^{th}$ entry of the $j^{th}$ row of $B$ . Let $c_{k}=c_{k-1}+a_{ik}b_{kj}$ .
4. Increment $k$ by $1$ and go to step 2.

In other words, multiply each element of row $i$ in $A$ with the corresponding entry of column $j$ in $B$ , add them up, and put the result in the $(i,j)$ position of the array for $AB$ . (For those who have had vector calculus, compute the ``dot product'' of the $i^{th}$ row of $A$ with the $j^{th}$ column of $A$ .)

In particular, if $A$ is an $n\times n$ matrix and if if $B$ is an $n\times 1$ matrix then both $B$ and $AB$ are column vectors in $F^n$ and the above multiplication defines a rule which sends column vectors to column vectors. In other words, $A$ defines a map

$$\begin{array}{ccc} A:&F^n\rightarrow &F^n,\ A:&v\longmapsto &Av, \end{array}$$ (5.1)

where $v\in F^n$ is written as a column vector.

If $A$ is a square $n\times n$ matrix and if there is a matrix $B$ such that $AB=I_n$ then we call $B$ the inverse matrix of $A$ , denoted $A^{-1}$ . If you think of $A$ as a function $A:F ^n \rightarrow F^n$ then $A^{-1}$ is the inverse function. As a practical matter, if $n$ is `small' (say, $n\leq 3$ ) then matrix inverses can be computed by pencil and paper using known techniques (see for example [JN]). For most larger matrices, computers are needed.