Matrix Multiplication in C — A Visual Guide

Matrices aren’t just grids of numbers — they’re the language of linear algebra, powering everything from video games to AI neural networks. Let’s learn matrix multiplication from the ground up.

What is a Matrix?

A matrix is a rectangular array of numbers arranged in rows and columns. An $m \times n$ matrix has $m$ rows and $n$ columns.

Each element is identified by its row and column indices: $A_{i,j}$ is the element at row $i$, column $j$.

The Dot Product

Before multiplying matrices, you need to understand the dot product.

Given two vectors of the same length, the dot product multiplies corresponding entries and sums them:

For example: \(\begin{bmatrix} 1 & 2 & 3 & 4 \end{bmatrix} \cdot \begin{bmatrix} 1 \\ 1 \\ 1 \\ 1 \end{bmatrix} = 1(1) + 2(1) + 3(1) + 4(1) = 10\)

Matrix Multiplication Rule

To multiply $A \times B$:

1. Check dimensions: $A$ must be $m \times k$ and $B$ must be $k \times n$. The inner dimensions ($k$) must match!
2. Result: The product $C = A \times B$ will be $m \times n$.
3. Each element: $C_{i,j}$ = dot product of row $i$ of $A$ and column $j$ of $B$.

Visual Intuition

Top: Each cell in the result is the dot product of a row from the first matrix and a column from the second. Bottom: The triple nested loop that implements this.

Why This Works

Matrix multiplication is essentially a system of linear equations. Each row of $A$ defines a linear combination, and each column of $B$ provides the coefficients. The result $C$ encodes how these transformations compose.

The dimension rule ($A_{cols} = B_{rows}$) exists because the dot product requires equal-length vectors. You can’t dot a 4-element row with a 3-element column.

The C Code

Here is a clean implementation with proper memory management:

#include <stdio.h>
#include <stdlib.h>

/*
 * Matrix Multiplication in C
 * A[rowA][colA] × B[rowB][colB] = C[rowA][colB]
 * 
 * Rule: colA MUST equal rowB for multiplication to be valid.
 */

#define ROW_A 4
#define COL_A 4
#define ROW_B 4
#define COL_B 4

// Function to multiply two matrices
// Returns a pointer to the resulting matrix C
int** multiply_matrices(int A[][COL_A], int B[][COL_B]);

int main() {
    // Matrix A: 4 rows, 4 columns
    int A[ROW_A][COL_A] = {
        {1, 2, 3, 4},
        {5, 6, 7, 8},
        {9, 10, 11, 12},
        {13, 14, 15, 16}
    };

    // Matrix B: 4 rows, 4 columns
    // Note: COL_A (4) must equal ROW_B (4) ✓
    int B[ROW_B][COL_B] = {
        {1, 2, 3, 4},
        {1, 2, 3, 4},
        {1, 2, 3, 4},
        {1, 2, 3, 4}
    };

    printf("Matrix A (%dx%d):\n", ROW_A, COL_A);
    for (int i = 0; i < ROW_A; i++) {
        for (int j = 0; j < COL_A; j++) {
            printf("%d\t", A[i][j]);
        }
        printf("\n");
    }

    printf("\nMatrix B (%dx%d):\n", ROW_B, COL_B);
    for (int i = 0; i < ROW_B; i++) {
        for (int j = 0; j < COL_B; j++) {
            printf("%d\t", B[i][j]);
        }
        printf("\n");
    }

    // Multiply!
    int **C = multiply_matrices(A, B);

    printf("\nResult C = A × B (%dx%d):\n", ROW_A, COL_B);
    for (int i = 0; i < ROW_A; i++) {
        for (int j = 0; j < COL_B; j++) {
            printf("%d\t", C[i][j]);
        }
        printf("\n");
    }

    // CRITICAL: Free allocated memory to prevent memory leaks
    for (int i = 0; i < ROW_A; i++) {
        free(C[i]);
    }
    free(C);

    return 0;
}

int** multiply_matrices(int A[][COL_A], int B[][COL_B]) {
    // Allocate result matrix C[ROW_A][COL_B] on the heap
    int **C = (int**)malloc(ROW_A * sizeof(int*));
    for (int i = 0; i < ROW_A; i++) {
        C[i] = (int*)malloc(COL_B * sizeof(int));
    }

    // Triple nested loop for matrix multiplication
    for (int i = 0; i < ROW_A; i++) {          // rows of A
        for (int j = 0; j < COL_B; j++) {      // columns of B
            C[i][j] = 0;                        // initialize cell

            // Compute dot product of row i of A and column j of B
            for (int k = 0; k < COL_A; k++) {  // COL_A == ROW_B
                C[i][j] += A[i][k] * B[k][j];
            }
        }
    }

    return C;
}

Expected Output

Matrix A (4x4): 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 Matrix B (4x4): 1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4 Result C = A × B (4x4): 10 20 30 40 26 52 78 104 42 84 126 168 58 116 174 232

Step-by-Step Verification

Let’s verify one cell manually: $C_{0,0}$

And $C_{1,2}$:

Why Use Pointers?

The function returns int** (a pointer to pointers) because C needs to allocate the result matrix dynamically on the heap. The stack can’t easily return 2D arrays.

Always free your memory! Forgetting free() causes a memory leak — your program gradually consumes more RAM until it crashes or slows down.

Common Mistakes

Identity Matrix Verification

The identity matrix $I$ is the "1" of matrix multiplication.

// 4x4 Identity Matrix
int I[4][4] = {
    {1, 0, 0, 0},
    {0, 1, 0, 0},
    {0, 0, 1, 0},
    {0, 0, 0, 1}
};
// Multiply A × I and verify you get A back

Time Complexity

For large matrices, $O(n^3)$ is too slow. Real-world systems use:

• Strassen’s algorithm: $O(n^{2.81})$
• Coppersmith-Winograd: $O(n^{2.37})$ (theoretical)
• GPU parallelization: Process thousands of cells simultaneously

Real-World Applications

Try It Yourself

1. Identity check: Multiply any $4 \times 4$ matrix by the identity matrix. What do you notice? (Hint: $A \times I = A$)
2. Dimension mismatch: What happens if you set COL_A = 3 and ROW_B = 4? Does it compile? Does it run correctly?
3. Cache optimization: Can you optimize the code by transposing matrix $B$ first? (Hint: better cache locality!)
4. Big matrices: Change the code to use double instead of int and multiply two $100 \times 100$ random matrices. Time it with clock().
5. Memory detective: Comment out the free() calls, run the program in a loop 100,000 times, and watch your system’s memory usage with top or Task Manager.