Matrix Multiplication - Column Major

$AB=C$

In column-major multiplication, matrix $B$ transforms matrix $A$ by taking the linear combinations of the columns of $A$ to produce the columns of $C$.

This requires that the column count of the first matrix (the one on the left) be equal to the row count of the second matrix (the one on the right.) The reason behind this restriction will become clear by the end of the next section.

As an example, imagine that Matrix $A$ has 3 rows and 3 columns, and matrix $B$ has 3 rows and 4 columns.

To prepare for what follows, write the matrices in column major form and full form:

$A=\left[A_0{A}_1{A}_2\right]=\left( \begin{array}{c}{\alpha }_0\\ {\alpha }_1\\ {\alpha }_2\end{array} \begin{array}{c}{\beta }_0\\ {\beta }_1\\ {\beta }_2\end{array} \begin{array}{c}{\gamma }_0\\ {\gamma }_1\\ {\gamma }_2\end{array} \right)$

$B=\left[B_0{B}_1{B}_2{B}_3\right]=\left( \begin{array}{c}{\omega }_0\\ {\omega }_1\\ {\omega }_2\end{array} \begin{array}{c}{\delta }_0\\ {\delta }_1\\ {\delta }_2\end{array} \begin{array}{c}{\eta }_0\\ {\eta }_1\\ {\eta }_2\end{array} \begin{array}{c}{\zeta }_0\\ {\zeta }_1\\ {\zeta }_2\end{array} \right)$

$C=\left[C_0{C}_1{C}_2{C}_3\right]=\left( \begin{array}{c}{u}_0\\ u_1\\ u_2\end{array} \begin{array}{c}{v}_0\\ v_1\\ v_2\end{array} \begin{array}{c}{w}_0\\ w_1\\ w_2\end{array} \begin{array}{c}{x}_0\\ x_1\\ x_2\end{array} \right)$

Matrix B Transforms Columns of A

Repeating again, in column-major multiplication, matrix $B$ transforms matrix $A$ by taking the linear combinations of the columns of $A$ to produce the columns of $C$.

$\left[A_0{A}_1{A}_2\right]\left[B_0{B}_1{B}_2{B}_3\right]=\left[C_0{C}_1{C}_2{C}_3\right]$

Each column of $B$ produces the corresponding column of $C$. That is, the first column of $B$ produces the first column of $C$; the second column of $B$ produces the second column of $C$, and so on. Therefore, $C$ will have the same number of columns as $B$ has.

$\left[A_0{A}_1{A}_2\right]\left( \begin{array}{c}{\omega }_0\\ {\omega }_1\\ {\omega }_2\end{array} \begin{array}{c}{\delta }_0\\ {\delta }_1\\ {\delta }_2\end{array} \begin{array}{c}{\eta }_0\\ {\eta }_1\\ {\eta }_2\end{array} \begin{array}{c}{\zeta }_0\\ {\zeta }_1\\ {\zeta }_2\end{array} \right)=\left[C_0{C}_1{C}_2{C}_3\right]$

To compute a column of $C$, pick the corresponding column of $B$ and use its elements to form the linear combination of the columns of $A$. This requires that the row count of $B$ equal the column count $A$ simply because each element in a column of $B$ wants to multiply the corresponding column in $A$.

To compute the first column of $C$, multiply each column of $A$ by the corresponding element of the first columm of $B$ and sum the products. To compute the second column of $C$, multiply each column of $A$ by the corresponding element of the second columm of $B$ and sum the products; to compute the third column of $C$, multiply each column of $A$ by the corresponding element of the third columm of $B$ and sum the products; and so on. Multiplying each column of $A$ by the corresponding element of a column of $B$ means: multiplying the first column of $A$ by the first element of the column of $B$; multiplying the second column of $A$ by the second element of the column of $B$; multiplying the third column of $A$ by the third element of the column of $B$; and son on. Again, this implies that the row count of $B$ must equal the column count $A$.

Algebraically, here is how the columns of $C$ are computed as the linear combinations of the columns of $A$:

$C_0=\left( \begin{array}{c}{u}_0\\ u_1\\ u_2\end{array} \right)={\omega }_0{A}_0+{\omega }_1{A}_1+{\omega }_2{A}_2$

$C_1=\left( \begin{array}{c}{v}_0\\ v_1\\ v_2\end{array} \right)={\delta }_0{A}_0+{\delta }_1{A}_1+{\delta }_2{A}_2$

$C_2=\left( \begin{array}{c}{w}_0\\ w_1\\ w_2\end{array} \right)={\eta }_0{A}_0+{\eta }_1{A}_1+{\eta }_2{A}_2$

$C_3=\left( \begin{array}{c}{x}_0\\ x_1\\ x_2\end{array} \right)={\zeta }_0{A}_0+{\zeta }_1{A}_1+{\zeta }_2{A}_2$

Here we can see that matrix $C$'s row count equals matrix $A$'s row count, and that its column count equals matrix $B$'s column count.

Finally, it is important to understand that every element of the columns of $B$ plays a very important role in the formation of the linear combinations of the columns of $A$. By carefully choosing those elements, we can control how much each column of $A$ contributes to each column of $C$.