Practical 8(b): Multiplying Two Matrices in a Function

Look at the subscripts in the innermost line. a[i][k] walks along row i of A as k grows; b[k][j] walks down column j of B. They move together, which is exactly the pairing the formula asks for. Getting a[k][i] or b[j][k] there is the commonest error in this practical, and the result is the product of transposes, which is a different matrix.

c[i][j] = 0; before the innermost loop is not optional. The element is an accumulator and it must start empty, for the reason given in [Practical 3(b): The Factorial of a Number].

Passing a matrix to a function

A one dimensional array is passed as an address and the function does not need to know how long it is. A two dimensional array is different: to work out where a[i][j] lives, the compiler must know how many columns there are in a row, because the rows are laid end to end.

So the parameter is written with the first size left out and every later size given:

void multiply(int a[][10], int b[][10], int c[][10], int m, int n, int q);

int a[][10] means "an array of rows, each row being ten ints". The number of rows may be left blank because it is never needed for the address arithmetic; the 10 may not.

That is why every matrix in this program is declared [10][10] and the used part is m by n: the second dimension must be a fixed number that the function and the caller agree on. Passing a 10 by 10 array to a function expecting int a[][20] does not compile, and it should not.

The program

#include <stdio.h>

void read_matrix(int a[][10], int rows, int cols, const char *name);
void print_matrix(int a[][10], int rows, int cols, const char *name);
void multiply(int a[][10], int b[][10], int c[][10], int m, int n, int q);

int main(void)
{
    int a[10][10], b[10][10], c[10][10];
    int m, n, p, q;

    printf("Rows and columns of the first matrix: ");
    scanf("%d %d", &m, &n);
    printf("Rows and columns of the second matrix: ");
    scanf("%d %d", &p, &q);

    if (n != p) {
        printf("Cannot multiply: the first has %d columns "
               "and the second has %d rows\n", n, p);
        return 0;
    }

    read_matrix(a, m, n, "A");
    read_matrix(b, p, q, "B");

    multiply(a, b, c, m, n, q);

    print_matrix(a, m, n, "A");
    print_matrix(b, p, q, "B");
    print_matrix(c, m, q, "A times B");

    return 0;
}

void read_matrix(int a[][10], int rows, int cols, const char *name)
{
    int i, j;

    printf("Enter %d values for matrix %s: ", rows * cols, name);

    for (i = 0; i < rows; i++)
        for (j = 0; j < cols; j++)
            scanf("%d", &a[i][j]);
}

void print_matrix(int a[][10], int rows, int cols, const char *name)
{
    int i, j;

    printf("\nMatrix %s (%d by %d)\n", name, rows, cols);

    for (i = 0; i < rows; i++) {
        for (j = 0; j < cols; j++)
            printf("%6d", a[i][j]);
        printf("\n");
    }
}

void multiply(int a[][10], int b[][10], int c[][10], int m, int n, int q)
{
    int i, j, k;

    for (i = 0; i < m; i++)
        for (j = 0; j < q; j++) {
            c[i][j] = 0;
            for (k = 0; k < n; k++)
                c[i][j] += a[i][k] * b[k][j];
        }
}

2 3
3 2
1 2 3 4 5 6
7 8 9 10 11 12

Rows and columns of the first matrix: Rows and columns of the second matrix: Enter 6 values for matrix A: Enter 6 values for matrix B:
Matrix A (2 by 3)
     1     2     3
     4     5     6

Matrix B (3 by 2)
     7     8
     9    10
    11    12

Matrix A times B (2 by 2)
    58    64
   139   154

The four numbers are the four worked out by hand above.

The mismatched case, refused

#include <stdio.h>

int main(void)
{
    int n = 3, p = 2;

    if (n != p)
        printf("Cannot multiply: first has %d columns, second has %d rows\n",
               n, p);
    else
        printf("The product is defined\n");

    return 0;
}

Cannot multiply: first has 3 columns, second has 2 rows

That is the whole guard, and a program that has it is a complete answer where one that does not is half of one.

Two facts about matrix multiplication worth a viva mark

It is not commutative. A times B is not generally B times A, and very often B times A does not even exist: with A of 2 by 3 and B of 3 by 2, A times B is 2 by 2 and B times A is 3 by 3. Two different matrices, from the same pair.

It is associative. (A times B) times C equals A times (B times C), whenever the sizes allow.

What beginners get wrong

Not testing that the columns of A match the rows of B.

Writing a[k][i] or b[j][k] in the innermost line. The subscripts are a[i][k] * b[k][j], in that order.

Forgetting c[i][j] = 0;. The element starts with whatever was in that memory and every answer is wrong by a random amount.

Putting c[i][j] = 0; in the wrong place. Inside the k loop it wipes the running total on every step and leaves only the last term.

Declaring the function parameter as int a[][]. Both dimensions blank does not compile: the column count is needed.

Assuming the answer has the same shape as the inputs. A of m by n times B of n by q gives m by q.

Quick revision

• A of m by n times B of p by q exists only when n equals p, and the answer is m by q.
• C[i][j] is row i of A against column j of B, multiplied term by term and added.
• Three loops: i over the answer's rows, j over its columns, k along the row and down the column.
• c[i][j] = 0; goes between the j loop and the k loop.
• The inner statement is c[i][j] += a[i][k] * b[k][j];.
• A function parameter is int a[][10]: the first size may be blank, the rest may not.
• Matrix multiplication is associative but not commutative.

What goes in your journal

Aim, the algorithm with all three loops, a flowchart, the program with the three functions, and the output showing both input matrices and the product. Work one element out by hand beside the output, the way C[0][0] is worked out in this chapter: it is the proof that you know where the numbers came from, and it is two lines of arithmetic.

Test yourself

1. When can two matrices be multiplied? When the number of columns of the first equals the number of rows of the second.

2. A is 3 by 5 and B is 5 by 2. What size is the product? 3 by 2.

3. What are the three loops for? The outer two visit each element of the answer, by row and by column. The innermost adds up the products of one row of A with one column of B.

4. Where does c[i][j] = 0; go, and why? Immediately inside the j loop and before the k loop, because the element is an accumulator and must be empty before the summing begins, but only once per element.

5. Why must a function parameter be int a[][10] rather than int a[][]? Because the compiler works out the address of a[i][j] from the number of columns in a row. The row count is never needed; the column count always is.

6. Is A times B the same as B times A? No. Matrix multiplication is not commutative, and for non square matrices the second product often does not exist at all.