Two-Dimensional Arrays and Matrices

The practical: reading an m by n matrix

MU's Practical 8(a).

#include <stdio.h>

#define MAX 10

int main(void)
{
    int a[MAX][MAX];
    int m, n;

    printf("Enter the number of rows and columns: ");
    if (scanf("%d %d", &m, &n) != 2) {
        printf("\nThose were not two numbers.\n");
        return 1;
    }
    if (m < 1 || m > MAX || n < 1 || n > MAX) {
        printf("\nRows and columns must be between 1 and %d.\n", MAX);
        return 1;
    }

    printf("Enter %d value(s), row by row: ", m * n);
    for (int r = 0; r < m; r++) {
        for (int c = 0; c < n; c++) {
            if (scanf("%d", &a[r][c]) != 1) {
                printf("\nRan out of numbers at row %d, column %d.\n", r, c);
                return 1;
            }
        }
    }

    printf("\nthe %d by %d matrix is\n", m, n);
    for (int r = 0; r < m; r++) {
        for (int c = 0; c < n; c++) {
            printf("%5d", a[r][c]);
        }
        printf("\n");
    }
    return 0;
}

2 3
1 2 3 4 5 6

Enter the number of rows and columns: Enter 6 value(s), row by row:
the 2 by 3 matrix is
    1    2    3
    4    5    6

int a[MAX][MAX] with m and n used only up to MAX is the standard way to handle a size the user chooses. The array is as big as it could need to be and only part of it is used. The bounds check is what makes that safe, and it is the line an examiner looks for.

Passing a matrix to a function

The parameter must give the column count:

void print_matrix(int a[][COLS], int rows);      /* correct     */
void print_matrix(int a[ROWS][COLS], int rows);  /* also fine   */
void print_matrix(int a[][], int rows);          /* will not compile */

The reason is the offset formula: to find a[r][c] the function must compute r * COLS + c, so it must know COLS. The row count is not needed for the arithmetic, which is why it may be left out, and is passed separately so the function knows when to stop.

The practical: multiplying two matrices using a function

MU's Practical 8(b). Two things have to be right: the shape rule, and the triple loop.

The shape rule. An m by n matrix times a p by q matrix is defined only when n == p, and the result is m by q. Each element of the result is a sum of n products:

c[i][j] = a[i][0]*b[0][j] + a[i][1]*b[1][j] + ... + a[i][n-1]*b[n-1][j]

#include <stdio.h>

#define MAX 10

void print_matrix(const char *label, int a[][MAX], int rows, int cols)
{
    printf("%s (%d by %d)\n", label, rows, cols);
    for (int r = 0; r < rows; r++) {
        for (int c = 0; c < cols; c++) {
            printf("%6d", a[r][c]);
        }
        printf("\n");
    }
}

/* Returns 1 on success, 0 if the shapes do not allow multiplication. */
int multiply(int a[][MAX], int m, int n,
             int b[][MAX], int p, int q,
             int c[][MAX])
{
    if (n != p) {
        return 0;
    }
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < q; j++) {
            int sum = 0;
            for (int k = 0; k < n; k++) {
                sum += a[i][k] * b[k][j];
            }
            c[i][j] = sum;
        }
    }
    return 1;
}

int main(void)
{
    int a[MAX][MAX] = {{1, 2, 3},
                       {4, 5, 6}};
    int b[MAX][MAX] = {{7, 8},
                       {9, 10},
                       {11, 12}};
    int c[MAX][MAX];
    int m = 2, n = 3, p = 3, q = 2;

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

    if (multiply(a, m, n, b, p, q, c)) {
        print_matrix("A times B", c, m, q);
    } else {
        printf("cannot multiply a %d by %d by a %d by %d\n", m, n, p, q);
    }

    /* the same two matrices the other way round: 3 by 2 times 2 by 3 */
    int d[MAX][MAX];
    if (multiply(b, p, q, a, m, n, d)) {
        print_matrix("B times A", d, p, n);
    }

    /* and a pair whose shapes do not allow it */
    if (!multiply(a, m, n, a, m, n, c)) {
        printf("\nA times A is refused: %d columns cannot meet %d rows\n", n, m);
    }
    return 0;
}

A (2 by 3)
     1     2     3
     4     5     6
B (3 by 2)
     7     8
     9    10
    11    12
A times B (2 by 2)
    58    64
   139   154
B times A (3 by 3)
    39    54    69
    49    68    87
    59    82   105

A times A is refused: 3 columns cannot meet 2 rows

Check one element by hand, because that is what a viva asks. c[0][0] is row 0 of A against column 0 of B:

1*7 + 2*9 + 3*11 = 7 + 18 + 33 = 58

And c[1][1] is row 1 of A against column 1 of B:

4*8 + 5*10 + 6*12 = 32 + 50 + 72 = 154

Three things that make this an answer rather than a sketch.

1. The shape check comes first. Without it the loops read b[k][j] for k beyond p, which is outside the data and is chapter 36's undefined behaviour.

2. sum is a local of the inner pair of loops, set to 0 for each element. A sum declared once outside and not reset is the commonest bug in this program.

3. A times B and B times A are different matrices, and here they are different shapes as well. Matrix multiplication is not commutative, and printing both makes the point without a paragraph.

The other matrix programs

Addition, transpose and the diagonal sum are the rest of what gets asked, and each is a few lines once the index order is clear.

#include <stdio.h>

#define MAX 10

void print_matrix(const char *label, int a[][MAX], int rows, int cols)
{
    printf("%s\n", label);
    for (int r = 0; r < rows; r++) {
        for (int c = 0; c < cols; c++) {
            printf("%5d", a[r][c]);
        }
        printf("\n");
    }
}

int main(void)
{
    int a[MAX][MAX] = {{1, 2, 3}, {4, 5, 6}, {7, 8, 9}};
    int b[MAX][MAX] = {{9, 8, 7}, {6, 5, 4}, {3, 2, 1}};
    int sum[MAX][MAX], t[MAX][MAX];
    int n = 3;

    for (int r = 0; r < n; r++) {
        for (int c = 0; c < n; c++) {
            sum[r][c] = a[r][c] + b[r][c];
            t[c][r] = a[r][c];              /* transpose: swap the indexes */
        }
    }
    print_matrix("A + B", sum, n, n);
    print_matrix("transpose of A", t, n, n);

    int main_diag = 0, other_diag = 0;
    for (int i = 0; i < n; i++) {
        main_diag += a[i][i];
        other_diag += a[i][n - 1 - i];
    }
    printf("main diagonal of A sums to %d\n", main_diag);
    printf("other diagonal of A sums to %d\n", other_diag);
    return 0;
}

A + B
   10   10   10
   10   10   10
   10   10   10
transpose of A
    1    4    7
    2    5    8
    3    6    9
main diagonal of A sums to 15
other diagonal of A sums to 15

The transpose is one line: t[c][r] = a[r][c]. Read it as "what was at row r, column c goes to row c, column r", and every transpose question is answered.

Addition needs both matrices to be the same shape; multiplication needs the columns of the first to equal the rows of the second. Those are different rules and confusing them is a standing mistake.

Three and more dimensions

int cube[2][3][4];      /* 2 layers of 3 rows of 4 columns: 24 ints */

The same rules apply, with one more index and one more loop. All dimensions but the first must be given in a parameter. You will not need three dimensions this semester.

What this does NOT mean

A two-dimensional array is not an array of pointers. It is one block of memory, rows columns sizeof(element) bytes, laid out row after row. An array of pointers is a different thing.

a[2][3] is not a[2, 3]. C has no comma subscript. a[2, 3] uses the comma operator and means a[3].

The column count is not optional in a parameter. The offset arithmetic needs it.

The row count is not needed for the arithmetic, which is why int a[][COLS] compiles. It is still needed by the function, so pass it.

Addition and multiplication do not have the same shape rule. Addition needs identical shapes; multiplication needs the inner dimensions to agree.

A times B is not B times A. Matrix multiplication is not commutative, and the two may not even have the same shape.

Quick revision

• int a[rows][cols] is an array of arrays, stored row after row in row-major order.
• a[r][c] is at offset r * cols + c.
• Indexes count from zero; the last row is rows - 1.
• In a parameter, every dimension except the first must be given: int a[][COLS].
• Rows: sizeof a / sizeof a[0]. Columns: sizeof a[0] / sizeof a[0][0].
• Declare a[MAX][MAX] and use only m by n of it when the user chooses the size, with a bounds check.
• Multiplication: m by n times p by q needs n == p and gives m by q.
• c[i][j] is the sum over k of a[i][k] * b[k][j], with sum reset for every element.
• Transpose: t[c][r] = a[r][c].
• Main diagonal a[i][i]; other diagonal a[i][n - 1 - i].

Test yourself

1. How many ints does int a[4][5]; hold, and how many bytes where int is 4 bytes?

20 ints, 80 bytes.

2. What is the valid range of each index of int a[3][4];?

The first index 0 to 2, the second 0 to 3.

3. Why must the column count appear in a function parameter?

Because the function computes the address of a[r][c] as the start plus r * columns + c, so it cannot find a row without knowing how long a row is.

4. Can a 2 by 3 matrix be multiplied by another 2 by 3 matrix?

No. Multiplication needs the columns of the first to equal the rows of the second, and 3 is not 2. Addition of two 2 by 3 matrices is fine.

5. What shape is the product of a 4 by 2 and a 2 by 7 matrix?

4 by 7.

6. Write the line that transposes a into t.

t[c][r] = a[r][c]; inside loops over r and c.

7. What is the commonest bug in a matrix multiplication program?

Not resetting the running sum to zero for each element of the result, so every element after the first is too large.

What can be asked on this, and how to answer it

"What is a two-dimensional array? Explain its declaration, initialisation and storage." Define it as an array of arrays, give the declaration and the braced initialiser, say that indexes count from zero, and state row-major storage with the offset formula r * cols + c. The offset formula is the part that shows understanding.

"Write a program to read an m by n matrix and display it." Give this chapter's program with MAX, the bounds check and the nested scanf loop with its return value checked.

"Write a program to multiply two matrices using a function." Give the shape rule first, then the function with the triple loop and the n != p check, then verify one element by hand. The hand check is what an examiner asks for next.

"Write a program to find the transpose of a matrix." One line inside two loops, t[c][r] = a[r][c], and note that an m by n matrix transposes to n by m.

"Distinguish between matrix addition and matrix multiplication in terms of shapes." Addition needs both matrices to have the same number of rows and the same number of columns, and works element by element. Multiplication needs the columns of the first to equal the rows of the second, gives a result with the rows of the first and the columns of the second, and each element is a sum of products.