Matrix Multiplication - Row Major

$AB=C$

In row-major multiplication, matrix $A$ transforms matrix $B$ by taking the linear combinations of the rows of $B$ to produce the rows 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 row major form and in full form:

$A=\left(\begin{array}{c}{A}_0\\ \\ A_1\\ \\ A_2\end{array}\right)=\left(\begin{array}{c} \begin{array}{ccc}{\alpha }_0& {\alpha }_1& {\alpha }_2\end{array} \\ \begin{array}{ccc}{\beta }_0& {\beta }_1& {\beta }_2\end{array} \\ \begin{array}{ccc}{\theta }_0& {\theta }_1& {\theta }_2\end{array} \end{array}\right)$

$B=\left(\begin{array}{c}{B}_0\\ \\ B_1\\ \\ B_2\end{array}\right)=\left(\begin{array}{c} \begin{array}{cccc}{\mu }_0& {\mu }_1& {\mu }_2& {\mu }_3\end{array} \\ \begin{array}{cccc}{\delta }_0& {\delta }_1& {\delta }_2& {\delta }_3\end{array} \\ \begin{array}{cccc}{\eta }_0& {\eta }_1& {\eta }_2& {\eta }_3\end{array} \end{array}\right)$

$C=\left(\begin{array}{c}{C}_0\\ \\ C_1\\ \\ C_2\end{array}\right)=\left(\begin{array}{c} \begin{array}{cccc}{u}_0& u_1& u_2& u_3\end{array} \\ \begin{array}{cccc}{v}_0& v_1& v_2& v_3\end{array} \\ \begin{array}{cccc}{x}_0& x_1& x_2& x_3\end{array} \end{array}\right)$

Matrix A Transforms Rows of B

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

$\left(\begin{array}{c}{A}_0\\ \\ A_1\\ \\ A_2\end{array}\right)\left(\begin{array}{c}{B}_0\\ \\ B_1\\ \\ B_2\end{array}\right)=\left(\begin{array}{c}{C}_0\\ \\ C_1\\ \\ C_2\end{array}\right)$

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

$\left(\begin{array}{c} \begin{array}{ccc}{\alpha }_0& {\alpha }_1& {\alpha }_2\end{array} \\ \begin{array}{ccc}{\beta }_0& {\beta }_1& {\beta }_2\end{array} \\ \begin{array}{ccc}{\theta }_0& {\theta }_1& {\theta }_2\end{array} \end{array}\right)\left(\begin{array}{c}{B}_0\\ \\ B_1\\ \\ B_2\end{array}\right)=\left(\begin{array}{c}{C}_0\\ \\ C_1\\ \\ C_2\end{array}\right)$

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

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

Algebraically, here is how the rows of $C$ are computed as the linear combinations of the rows of $B$:

$C_0=\left[\begin{array}{cccc}{u}_0& u_1& u_2& u_3\end{array}\right]={\alpha }_0{B}_0+{\alpha }_1{B}_1+{\alpha }_2{B}_2$

$C_1=\left[\begin{array}{cccc}{v}_0& v_1& v_2& v_3\end{array}\right]={\beta }_0{B}_0+{\beta }_1{B}_1+{\beta }_2{B}_2$

$C_2=\left[\begin{array}{cccc}{x}_0& x_1& x_2& x_3\end{array}\right]={\theta }_0{B}_0+{\theta }_1{B}_1+{\theta }_2{B}_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 rows of $A$ plays a very important role in the formation of the linear combinations of the rows of $B$. By carefully choosing those elements, we can control how much each row of $B$ contributes to each row of $C$.