QUESTION 35 · Matrices and Dimensions

When is A × B defined, and what is the result size?

2 marks

Answer

If A is r × k and B is k × c, the result is r × c.

The column count of A must equal the row count of B.
Each result element is a row-column sum of products.

Write a C program using a function to multiply two matrices.

5 marks

Answer in brief

Matrix multiplication combines each row of A with each column of B. It is not element-by-element multiplication.

Formula

C[i][j] = sum of A[i][t] * B[t][j]
          for t = 0 through inner - 1

Algorithm

Read both matrices’ dimensions. Require colsA == rowsB.
Read the two matrices within their allowed bounds.
For each result position i, j, set its running total to zero.
For each t, add A[i][t] × B[t][j].
Store and display the result.

Worked example

For A = [[1, 2], [3, 4]] and B = [[5, 6], [7, 8]], C[0][0] is 1×5 + 2×7 = 19. C[0][1] is 1×6 + 2×8 = 22. The second row is 43, 50. Each result is a dot product of one complete row and one complete column.

Initialisation and types

Set every result accumulator to zero before its inner loop. Otherwise a result might include an old or invalid value. The sample uses long long for the result and 1LL * a[i][t] * b[t][j] to perform the product in that type. Inputs are limited to magnitude 1000 and dimensions at most 5.

Time complexity

For r result rows and c result columns, each position requires k products and additions. The total is r × c × k, giving O(rkc) time. For square n × n matrices this becomes O(n³) for this basic method.

Space complexity

The output contains rc long long values. Output storage is O(rc), while the counters add O(1) auxiliary space beyond the inputs and output. Matrix multiplication is generally not commutative: reversing A and B may change the answer or make the dimensions incompatible.

Dimension table

↔ Scroll horizontally on a small screen

Matrix operation dimensions
Operation	Input sizes	Requirement	Output size
Addition	r × c and r × c	Both dimensions equal	r × c
Multiplication	r × k and k × c	Inner dimensions equal	r × c

Diagram or flowchart

CodeBhavya illustration of matrix product. — Write a C program using a function to multiply two matrices. · Download diagram

C program and output

Download .c Open compiler

/* CodeBhavya | PPS AR25 | Learning example */
#include <stdio.h>
#define MAX 5
int read_matrix(int a[][MAX], int rows, int cols)
{
    for (int i = 0; i < rows; ++i) {
        for (int j = 0; j < cols; ++j) {
            if (scanf("%d", &a[i][j]) != 1 || a[i][j] < -1000 || a[i][j] > 1000) {
                return 0;
            }
        }
    }
    return 1;
}
void multiply(int a[][MAX], int b[][MAX], long long c[][MAX],
              int rows, int inner, int cols)
{
    for (int i = 0; i < rows; ++i) {
        for (int j = 0; j < cols; ++j) {
            c[i][j] = 0;
            for (int t = 0; t < inner; ++t) {
                c[i][j] += 1LL * a[i][t] * b[t][j];
            }
        }
    }
}

int main(void)
{
    int ra, ca, rb, cb, a[MAX][MAX], b[MAX][MAX];
    long long c[MAX][MAX];
    if (scanf("%d%d%d%d", &ra, &ca, &rb, &cb) != 4 ||
        ra < 1 || ra > MAX || ca < 1 || ca > MAX ||
        rb < 1 || rb > MAX || cb < 1 || cb > MAX) {
        puts("Unsupported dimensions"); return 1;
    }
    if (ca != rb) { puts("Incompatible dimensions"); return 1; }
    if (!read_matrix(a, ra, ca) || !read_matrix(b, rb, cb)) {
        puts("Unsupported input"); return 1;
    }
    multiply(a, b, c, ra, ca, cb);
    for (int i = 0; i < ra; ++i) {
        for (int j = 0; j < cb; ++j) {
            if (j > 0) { putchar(' '); }
            printf("%lld", c[i][j]);
        }
        putchar('\n');
    }
    return 0;
}

Sample input and output

Input

2 2 2 2
1 2 3 4
5 6 7 8

Output

19 22
43 50