Matrix Multiplication

Matrix multiplication combines two matrices into a new one, written as $AB$. The first matrix’s column count must match the second matrix’s row count. The result has the first matrix’s rows and the second matrix’s columns. Unlike ordinary numbers, changing the order can change the result. See matrix algebra for the rules.

Definition

If $A$ is an $m\times n$ matrix and $B$ is an $n\times p$ matrix, then:

$$A=\left(\begin{array}{cccc}{a}_{11}& a_{12}& \cdots & a_{1n}\\ a_{21}& a_{22}& \cdots & a_{2n}\\ ⋮& ⋮& \ddots & ⋮\\ a_{m1}& a_{m2}& \cdots & a_{mn}\end{array}\right)$$ $$B=\left(\begin{array}{cccc}{b}_{11}& b_{12}& \cdots & b_{1p}\\ b_{21}& b_{22}& \cdots & b_{2p}\\ ⋮& ⋮& \ddots & ⋮\\ b_{n1}& b_{n2}& \cdots & b_{np}\end{array}\right)$$

The matrix product $C=AB$ is an $m\times p$ matrix:

$$C=\left(\begin{array}{cccc}{c}_{11}& c_{12}& \cdots & c_{1p}\\ c_{21}& c_{22}& \cdots & c_{2p}\\ ⋮& ⋮& \ddots & ⋮\\ c_{m1}& c_{m2}& \cdots & c_{mp}\end{array}\right)$$

Each entry $c_{ij}$ in $C$ is calculated as:

$$c_{ij}=a_{i1}{b}_{1j}+a_{i2}{b}_{2j}+\cdots +a_{in}{b}_{nj}=\sum _{k=1}^n{a}_{ik}{b}_{kj}$$

where $i=1,\cdots ,m$ and $j=1,\cdots ,p$.

Code Implementation

Here is a simple implementation of matrix multiplication in C++:

#include <iostream>
#include <vector>
using namespace std;
using Matrix = vector<vector<int>>;
 
Matrix matmul(const Matrix& a, const Matrix& b) {
  int m = a.size(), n = a[0].size(), p = b[0].size();
  Matrix c(m, vector<int>(p, 0));
  for (int i = 0; i < m; ++i) for (int j = 0; j < p; ++j) for (int k = 0; k < n; ++k) {
    c[i][j] += a[i][k] * b[k][j];
  }
  return c;
}
 
int main(void) {
  Matrix a = {{1, 2, 3}, {4, 5, 6}};
  Matrix b = {{7, 8}, {9, 10}, {11, 12}};
  Matrix c = matmul(a, b);
  
  for (const auto& row : c) {
    for (int val : row) cout << val << " ";
    cout << endl;
  }
  return 0;
}

References

• https://en.wikipedia.org/wiki/Matrix_multiplication