Solved exercise: exact rank and determinant with Bareiss in C

Solved C exam question: column products, rank and exact determinant of an integer matrix using Bareiss elimination, row pivoting and long long.

Updated on October 23, 2026

Exam Code C Programming fundamentals Top-grade level Tested code

CS1: Programming Fundamentals in C · Final examQuestion 4 · 2.5 points · 35 min

The simulation team of a structural engineering lab stores its linear systems as matrices of integer coefficients. Before launching a long computation, they want a checking tool that says whether a system has a unique solution. Because the coefficients are integers, the result must be exact: no operation on float or double is allowed anywhere in the program.

Input (from standard input): two integers m and n (number of rows and columns, 1 ≤ m, n ≤ 6), followed by the m·n entries of the matrix in row-major order, separated by spaces or newlines. Every entry satisfies |a| ≤ 20. You may assume the input is well formed.

Output: exactly three lines. The first starts with products: and contains the product of the entries of each column, from left to right, each preceded by one space. The second has the form rank: R. The third has the form determinant: D if the matrix is square, or determinant: undefined if it is not.

You must compute the rank and the determinant with fraction-free Gaussian elimination (the Bareiss method). At step k, every entry below and to the right of the pivot is replaced by (a[i][j]·a[k][k] − a[i][k]·a[k][j]) / p, where p is the pivot of the previous step (1 at the first step). That division is always exact. If the pivot is zero, look further down for a row with a non-zero entry in that column and swap the two rows. Each swap flips the sign of the determinant. If the whole remaining column is zero, move on to the next column without advancing the row.

Structure the code into functions: one that reads the matrix, one that computes the column products, and a function bareiss that triangularises the matrix in place, returns the rank and reports the accumulated sign. Justify your choice of integer type: intermediate values and the determinant itself may exceed the range of int.

Sample input

3 3
2 -1 0
-1 2 -1
0 -1 2

Expected output

products: 0 2 0
rank: 3
determinant: 4

Reads the matrix correctly and computes the column products before the matrix is modified

0.5

Searches for a non-zero pivot, swaps rows and tracks the sign of the determinant

0.75

Bareiss elimination with exact division by the previous pivot, no floating point and no overflow

0.75

Rank of rectangular or singular matrices, and a determinant only when the matrix is square

0.5

Hints

Hint 1 · In what order should things happen?

Elimination destroys the original matrix. That is why the column products must be computed before calling bareiss, or on a copy. The rank is the number of non-zero pivots you find. There is no separate formula for it: it is the row counter r, which advances each time you fix a pivot.

Hint 2 · What do I do with a zero pivot?

Use a while loop to find the first row p ≥ r whose entry in the current column is non-zero. If there is none (p == m), that column contributes no pivot: continue without incrementing r. If there is one and it is a different row, swap the whole rows and multiply the sign by −1.

Hint 3 · Why does the division not lose precision?

After each step, the entries of the not-yet-eliminated block are minors (determinants of submatrices) of the original matrix. The numerator of the formula is an exact multiple of the previous pivot. If you store the pivot you just used in prev and divide by it at the next step, every value stays an integer. At the end, for a square matrix of full rank, the last pivot is the determinant up to sign.

Solution

Explained solution

The solution splits the three tasks into functions with a clear contract. read_matrix fills a fixed 6×6 array and returns the dimensions through pointers, as covered in the pass by value and by reference exercise. column_products walks the matrix column by column. bareiss triangularises it in place and returns the rank.

Every entry is stored as long long, even though the input would fit in an int. With |a| ≤ 20 and size 6, the intermediate products reach values around 10^16. That fits comfortably in 64 bits, but not in 32.

#include <stdio.h>

#define MAXD 6

/* Reads m, n and the matrix in row-major order. Returns 1 on success. */
static int read_matrix(long long a[MAXD][MAXD], int *m, int *n)
{
    if (scanf("%d %d", m, n) != 2) return 0;
    if (*m < 1 || *m > MAXD || *n < 1 || *n > MAXD) return 0;
    for (int i = 0; i < *m; i++)
        for (int j = 0; j < *n; j++)
            if (scanf("%lld", &a[i][j]) != 1) return 0;
    return 1;
}

/* prod[j] = product of the entries of column j. */
static void column_products(long long a[MAXD][MAXD], int m, int n,
                            long long prod[MAXD])
{
    for (int j = 0; j < n; j++) {
        prod[j] = 1;
        for (int i = 0; i < m; i++)
            prod[j] *= a[i][j];
    }
}

/* Bareiss fraction-free elimination. Modifies a, returns the rank
   and stores in *sign (+1 or -1) the effect of the row swaps. */
static int bareiss(long long a[MAXD][MAXD], int m, int n, int *sign)
{
    int r = 0;
    long long prev = 1;
    *sign = 1;
    for (int col = 0; col < n && r < m; col++) {
        int p = r;
        while (p < m && a[p][col] == 0)
            p++;
        if (p == m)
            continue;                 /* no pivot in this column */
        if (p != r) {
            for (int j = 0; j < n; j++) {
                long long t = a[p][j];
                a[p][j] = a[r][j];
                a[r][j] = t;
            }
            *sign = -*sign;
        }
        for (int i = r + 1; i < m; i++) {
            for (int j = col + 1; j < n; j++)
                a[i][j] = (a[i][j] * a[r][col] - a[i][col] * a[r][j]) / prev;
            a[i][col] = 0;
        }
        prev = a[r][col];
        r++;
    }
    return r;
}

int main(void)
{
    long long a[MAXD][MAXD];
    long long prod[MAXD];
    int m, n, sign;

    if (!read_matrix(a, &m, &n)) {
        printf("invalid input\n");
        return 0;
    }

    column_products(a, m, n, prod);
    printf("products:");
    for (int j = 0; j < n; j++)
        printf(" %lld", prod[j]);
    printf("\n");

    int rank = bareiss(a, m, n, &sign);
    printf("rank: %d\n", rank);

    if (m != n)
        printf("determinant: undefined\n");
    else if (rank < m)
        printf("determinant: 0\n");
    else
        printf("determinant: %lld\n", sign * a[m - 1][m - 1]);
    return 0;
}

main reads the matrix and calls column_products first. That order is mandatory, because bareiss overwrites a. Each product starts at 1 and is multiplied row by row. The largest possible magnitude is 20^6 = 64,000,000. In the 6×6 test every column holds one −20 and five 20s, so the program prints -64000000 six times.

Inside bareiss, r is the row where the next pivot will go, and col walks the columns. The loop stops when the columns run out or when every row already has a pivot. The while loop finds the first row p with a non-zero entry. If there is none, continue jumps to the next column without touching r. This is what makes rectangular and singular matrices work.

If the pivot sits in another row, the whole rows are swapped and *sign flips. Then, for each lower row i and each column j to the right, the formula from the statement is applied, dividing by prev. Only afterwards is a[i][col] set to zero. The order matters: the inner loop over j still needs the old value of a[i][col], so zeroing it earlier would corrupt the row.

In the example, the 3×3 tridiagonal matrix, the first pivot is 2 and prev is 1. Cell (1,1) becomes 2·2 − (−1)(−1) = 3 and cell (2,2) becomes 2·2 − 0·0 = 4. At the second step, with pivot 3 and prev equal to 2, cell (2,2) becomes (4·3 − (−2)(−2)) / 2 = 4. That last pivot is the determinant, and the rank is 3. The trace below shows each of these cells.

The second test starts with a zero in the corner. The program swaps the first two rows and the sign becomes −1. Later the third column has no pivot in row 2, so the rank stays at 2 and the determinant is 0: the third row minus twice the second reproduces the first. In the 2×4 matrix only one pivot appears, and the output says undefined.

For the determinant, main separates three cases. A non-square matrix has no determinant. If the rank is below m, the determinant is 0. Otherwise it is sign * a[m-1][m-1]. The 6×6 test confirms this with -8192000000, a value that does not fit in a 32-bit int. The 1×1 matrix and the zero matrix check the edges: a single negative entry is its own determinant, and a matrix with no pivot at all has rank 0.

Code and tests on GitLab

Step-by-step trace · generated by running the code

Step	r	col	i	j	prev	a_ij	Cell
1	0	0	0	0	1	2	(0,0)
2	0	0	1	1	1	3	(1,1)
3	0	0	1	2	1	-2	(1,2)
4	0	0	2	1	1	-2	(2,1)
5	0	0	2	2	1	4	(2,2)
6	1	1	1	1	2	3	(1,1)
7	1	1	2	2	2	4	(2,2)
8	2	2	2	2	3	4	(2,2)

Test cases

Case	Input	Expected output	Actual output	Result
Statement example: 3x3 tridiagonal	3 3 2 -1 0 -1 2 -1 0 -1 2	products: 0 2 0 rank: 3 determinant: 4	products: 0 2 0 rank: 3 determinant: 4	OK
Zero pivot with row swap, singular matrix	3 3 0 2 1 3 1 4 6 4 9	products: 0 8 36 rank: 2 determinant: 0	products: 0 8 36 rank: 2 determinant: 0	OK
Rectangular 2x4 matrix of rank 1	2 4 1 2 3 4 2 4 6 8	products: 2 8 18 32 rank: 1 determinant: undefined	products: 2 8 18 32 rank: 1 determinant: undefined	OK
Single negative entry	1 1 -7	products: -7 rank: 1 determinant: -7	products: -7 rank: 1 determinant: -7	OK
2x2 zero matrix	2 2 0 0 0 0	products: 0 0 rank: 0 determinant: 0	products: 0 0 rank: 0 determinant: 0	OK
Limit case 6x6 with entries ±20	6 6 -20 20 20 20 20 20 20 -20 20 20 20 20 20 20 -20 20 20 20 20 20 20 -20 20 20 20 20 20 20 -20 20 20 20 20 20 20 -20	products: -64000000 -64000000 -64000000 -64000000 -64000000 -64000000 rank: 6 determinant: -8192000000	products: -64000000 -64000000 -64000000 -64000000 -64000000 -64000000 rank: 6 determinant: -8192000000	OK

Actual outputs: code compiled with gcc 14.4.0 (C17) and run in an isolated container on 23 October 2026.

Complexity

Let k = min(m, n). For each of at most k pivots, the elimination visits the lower rows and the columns to the right. That gives O(m·n·k) operations; for a square matrix of order n, O(n³). The pivot search and the row swap cost O(m + n) per step, which is dominated. The column products cost O(m·n).

Memory is constant: one fixed 6×6 array of long long, the products array and a handful of scalars. No dynamic allocation is needed. The size limit also controls overflow. The Bareiss numerators are bounded by the product of two minors, and Hadamard's inequality keeps them below 10^17 for this data. With larger matrices or larger entries the bounds would have to be argued again, and 64 bits might no longer be enough.

Common mistakes

• Computing the column products after calling bareiss. By then the matrix is already triangular and the products are almost always 0.
• Storing the matrix as int. The product a[i][j] * a[r][col] overflows before the division, and the determinant of the 6×6 test does not even fit in 32 bits.
• Forgetting to flip the sign when swapping rows. The rank is still right, but the determinant comes out with the wrong sign whenever there is an odd number of swaps.
• Zeroing a[i][col] before the loop over j finishes. The rest of that row is then computed with a zero instead of the real multiplier.
• Not skipping zero columns and incrementing r anyway. The next pivot can then be 0, and the following step divides by zero.
• Doing the elimination with double and rounding at the end. Results such as -0.000000 or values with rounding error can appear, and the statement explicitly forbids floating point.

Variants

Solve the system when the determinant is non-zero

If a column of right-hand sides is added (an m×(m+1) augmented matrix), you can call bareiss on the augmented matrix unchanged. The system has a unique solution when the rank of the square part is m. To get each unknown as an exact fraction x_i = det_i / det, apply Cramer's rule: replace column i with the right-hand sides and reuse the same function on a copy. Finally, reduce each fraction by dividing numerator and denominator by their greatest common divisor.

Digit sum of the determinant

A classic short follow-up asks how many digits |det| has and what they add up to. A loop while (x > 0) { sum += x % 10; x /= 10; digits++; } on a positive long long solves it. The case det == 0 needs separate handling: it has one digit, not zero. For a refresher on basic matrix traversals, see the matrix sums, transpose and trace exercise in C.

What the professor will ask

“You divide by prev at every step. How do you know that integer division never truncates anything? And if you replaced long long with double, would the program still be correct?”

By Sylvester's identity, after step k every entry a[i][j] of the active block equals the determinant of the submatrix formed by the pivot rows used so far plus row i, and the pivot columns plus column j. So it is an integer. The numerator of the formula is that minor multiplied by the previous pivot, which means the division by prev is exact and the integer / operator discards nothing. With double the algorithm is the same, but values up to about 10^16 exceed 2^53, the limit of exactly representable integers. Rounding errors could creep in, and comparing a pivot with 0 would stop being reliable. The result would no longer be guaranteed.

On the syllabus

Two-dimensional arrays and their relationship with pointers appear in the syllabus of Algoritmos y Programación I (95.11) at the Universidad de Buenos Aires, whose Unit III covers arrays, multidimensional arrays, arrays and pointers, and array initialisation. This exercise exercises exactly that material: a fixed matrix passed to functions and modified in place.

At a more systems-oriented level, the syllabus of CC3301 Programación de Software de Sistemas at the Universidad de Chile covers C programming on Linux, where choosing integer types and reasoning about overflow, as this question demands, is everyday work.

Opinion · Open question

Open question: would a student who passes every test here know where the guarantee stops? The statement fixes the size at 6 and the entries at 20, and the whole case for long long rests on those two numbers. Raise either one and the 10^16 headroom disappears without a single warning from the compiler.

That is the part I would want examined. Writing Bareiss correctly is the skill; knowing the limit beyond which your exact answer quietly becomes a wrong one is the judgment.

Related articles from LaRebelión

Solved exercise: normalize a string in place with pointers in CSolved exercise: array-based stack and balanced brackets in CSolved exercise: dynamic matrices with malloc and free in C

• Programming exercises
• Solved exercise: pass by value and by reference in C
• Solved exercise: C matrix sums, transpose and trace in C

Article generated with AI.larebelion

Byline · Chief editor · English edition · London

“The algorithm is exact. The integer type is only exact up to a limit, and this exam asks you to know where it is.”